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.
InformationsquelleAutor p_b_garcia | 2014-08-23
Schreibe einen Kommentar