Schnelle Information-Gain-Berechnung
Ich brauche, um zu berechnen, Informationen Gewinnen erreicht souverän für >100 K-Funktionen >10k Dokumente für text-Klassifikation. Der Code unten funktioniert einwandfrei, aber für den vollen Datenbestand ist sehr langsam - dauert mehr als eine Stunde auf einem laptop. Dataset ist 20newsgroup und ich bin mit scikit-learn, chi2 Funktion, die in scikit arbeitet extrem schnell.
Keine Idee, wie compute-Informationen Verschaffen Sie sich schneller für einen solchen Datensatz?
def information_gain(x, y):
def _entropy(values):
counts = np.bincount(values)
probs = counts[np.nonzero(counts)] / float(len(values))
return - np.sum(probs * np.log(probs))
def _information_gain(feature, y):
feature_set_indices = np.nonzero(feature)[1]
feature_not_set_indices = [i for i in feature_range if i not in feature_set_indices]
entropy_x_set = _entropy(y[feature_set_indices])
entropy_x_not_set = _entropy(y[feature_not_set_indices])
return entropy_before - (((len(feature_set_indices) / float(feature_size)) * entropy_x_set)
+ ((len(feature_not_set_indices) / float(feature_size)) * entropy_x_not_set))
feature_size = x.shape[0]
feature_range = range(0, feature_size)
entropy_before = _entropy(y)
information_gain_scores = []
for feature in x.T:
information_gain_scores.append(_information_gain(feature, y))
return information_gain_scores, []
EDIT:
Ich zusammengeführt, die internen Funktionen und lief cProfiler
als unten (auf einen Datensatz beschränkt sich auf ~15k features und ~1k Dokumente):
cProfile.runctx(
"""for feature in x.T:
feature_set_indices = np.nonzero(feature)[1]
feature_not_set_indices = [i for i in feature_range if i not in feature_set_indices]
values = y[feature_set_indices]
counts = np.bincount(values)
probs = counts[np.nonzero(counts)] /float(len(values))
entropy_x_set = - np.sum(probs * np.log(probs))
values = y[feature_not_set_indices]
counts = np.bincount(values)
probs = counts[np.nonzero(counts)] /float(len(values))
entropy_x_not_set = - np.sum(probs * np.log(probs))
result = entropy_before - (((len(feature_set_indices) /float(feature_size)) * entropy_x_set)
+ ((len(feature_not_set_indices) /float(feature_size)) * entropy_x_not_set))
information_gain_scores.append(result)""",
globals(), locals())
Ergebnis top 20 von tottime
:
ncalls tottime percall cumtime percall filename:lineno(function)
1 60.27 60.27 65.48 65.48 <string>:1(<module>)
16171 1.362 0 2.801 0 csr.py:313(_get_row_slice)
16171 0.523 0 0.892 0 coo.py:201(_check)
16173 0.394 0 0.89 0 compressed.py:101(check_format)
210235 0.297 0 0.297 0 {numpy.core.multiarray.array}
16173 0.287 0 0.331 0 compressed.py:631(prune)
16171 0.197 0 1.529 0 compressed.py:534(tocoo)
16173 0.165 0 1.263 0 compressed.py:20(__init__)
16171 0.139 0 1.669 0 base.py:415(nonzero)
16171 0.124 0 1.201 0 coo.py:111(__init__)
32342 0.123 0 0.123 0 {method 'max' of 'numpy.ndarray' objects}
48513 0.117 0 0.218 0 sputils.py:93(isintlike)
32342 0.114 0 0.114 0 {method 'sum' of 'numpy.ndarray' objects}
16171 0.106 0 3.081 0 csr.py:186(__getitem__)
32342 0.105 0 0.105 0 {numpy.lib._compiled_base.bincount}
32344 0.09 0 0.094 0 base.py:59(set_shape)
210227 0.088 0 0.088 0 {isinstance}
48513 0.081 0 1.777 0 fromnumeric.py:1129(nonzero)
32342 0.078 0 0.078 0 {method 'min' of 'numpy.ndarray' objects}
97032 0.066 0 0.153 0 numeric.py:167(asarray)
Sieht, dass die meiste Zeit verbracht wird _get_row_slice
. Ich bin nicht ganz sicher über die erste Zeile, sieht es deckt den gesamten block I zur Verfügung gestellt cProfile.runctx
, obwohl ich nicht weiß, warum es eine so große Lücke zwischen der ersten Zeile totime=60.27
und das zweite tottime=1.362
. Wo war der Unterschied verbracht? Ist es möglich zu überprüfen, in cProfile
?
Grundsätzlich sieht das problem mit sparse-matrix-Operationen (slicing, erste Elemente) -- die Lösung wäre wohl zu berechnen Informationen Gewinnen mit matrix-algebra (wie chi2 wird umgesetzt in scikit). Aber ich habe keine Ahnung wie ich das Ausdrücken Berechnung in Bezug auf die Matrizen-Operationen... Jemand eine Idee????
- Haben Sie versucht, zu verwenden, profiler, um zu sehen, wo der Engpass ist? Haben Sie versucht, die parallele Verarbeitung Ihrer Daten?
- Danke, ich bearbeitet die post
- Mein Rat, unabhängig von der Frage: reduzieren Sie die Funktion einstellen, bevor Sie berechnen den Informationsgewinn, der durch einfachere Mittel, die einfacher zu berechnen. Zum Beispiel, viele ngrams (was ich vermute, sind Ihre Funktionen) nur einmal oder zweimal im Korpus und ausgeschlossen werden sollte vorher, reduzieren Sie Ihren featureset stark.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Weiß nicht ob es noch hilft, da ist ein Jahr vergangen. Aber jetzt habe ich gerade vor der gleichen Aufgabe für text-Klassifikation. Ich habe umgeschrieben, Ihren code mit dem ungleich null() Funktion für sparse-matrix. Ich habe dann einfach Scannen nz, zählen die entsprechenden y_value und berechnen Sie die Entropie.
Den folgenden code braucht nur Sekunden, um zu laufen news20 dataset (geladen mit libsvm sparse matrix format).
Hier ist eine version, die verwendet matrix-Operationen. Die IG für ein feature ist ein Mittel über seine Klasse-spezifische erzielt.
Auf einem Datensatz mit 1000 Instanzen und 1000 einzigartige features, diese Implementierung ist >100 schneller, als das ohne matrix-Operationen.
Es ist dieser code
feature_not_set_indices = [i for i in feature_range if i not in feature_set_indices]
nimmt 90% der Zeit, versuchen zu ändern, um den Betrieb