Schnellste Möglichkeit, Nachnamen in Python zu klassifizieren

Question

Ich habe eine Liste mit 12K asiatischen Nachnamen aus einer Volkszählung und eine Liste mit 200K Namen. Ich würde diese 200K Leute gerne als Asiaten oder Nicht-Asiaten einstufen, basierend darauf, ob ihr Nachname auf meiner 12K Liste steht.

Gibt es eine schnelle Möglichkeit zu überprüfen, ob eines der Elemente in der Liste einen der Nachnamen in der 12K-Liste enthält?

Answer 1

Hängt davon ab, was Sie mit "schnell" meinen.

James schlug vor, mit Python integrierten set für die Mitgliedschaft zu testen. Pythons set Implementierung verwendet Hash-Tabellen. Durchschnitt Zeit Komplexität ist O (1), aber der schlimmste Fall kann sein O (n) wo n ist die Kardinalität der Reihe von asiatischen Nachnamen. So in der Worst Case Szenario, Sie könnte nur am Ende mit O (Mn) anstelle von O (M), wo m ist die Kardinalität des Satzes von Namen zu klassifizieren.

Als Referenz finden Sie unter: https://wiki.python.org/moin/TimeComplexity

Wenn Sie eine Garantie auf den schlimmsten Fall haben wollen, können Sie es mit Sortieren der Satz n und tun binäre Suche erreichen können. Dies wird mit der Zeitkomplexität von O (mgg n) enden.

Binary Suche: https://docs.python.org/3.1/library/bisect.html

Es hängt wirklich davon ab, wie gut die Hash-Funktion für Ihre Daten arbeitet.

Answer 2

Am besten konvertieren Sie Ihre 12K-Liste in eine festgelegte Datenstruktur. Dann können Sie über die Volkszählungsdaten iterieren und prüfen, ob jeder in der Menge ist.

# O(n) where n is the length of the surname_list 
surname_set = set(surname_list) 

for name in census: 
    # This is now O(1) operation 
    if name in surname_set: 
     do whatever... 

ist dies mit ziemlicher Sicherheit der schnellste Weg, was Sie in Python oder einer beliebigen Sprache, und sollte recht schnell sein auf einer 200K Größe Liste müssen zu erreichen.

Wai Leong Yeow schlägt eine binäre Suche vor, die schneller ist, als die Liste direkt zu überprüfen, aber das ist immer noch eine Operation O (log n) auf 200K verschiedenen Namen, wobei N 12.000 ist, was bedeutet, dass es wahrscheinlich mehr ist als 10x langsamer nur für den iterativen Teil (Dies ist eine Vereinfachung - in der Realität gibt es einige konstante Faktoren maskiert durch die große O-Notation, aber die Konstanten-Zeit-Lösung ist sicherlich noch schneller). Die Sortierung dauert O (n log n), wobei die Umwandlung in eine Menge O (n) dauert, was bedeutet, dass diese Methode auch schneller vorverarbeitet wird.

Answer 3

Es hängt von Ihrem wirklichen Problem ab. Möchtest du maschinelles Lernen (wie du kennst: Klassifikation), um einen asiatischen/nicht-asiatischen Namen vorherzusagen?

Wenn ja: Versuchen Sie einige halb überwachte Methoden. Um dies zu tun, wählen Sie zuerst zufällig (in der Nähe von 10%) Ihrer 200k Daten, suchen Sie danach in 12k, wenn es existiert, beschriften Sie es auf 1, sonst beschriften Sie es mit 0. Verwenden Sie dann einen Klassifizierungsalgorithmus wie, Random Forest, SVM oder KNN. Sie können Ihre Namen auch etwas wie Bag Of Word modellieren (In Ihrem Problem Bag Of Letter!oder so ähnlich): https://en.wikipedia.org/wiki/Bag-of-words_model

für Klassifikationsaufgabe, werfen Sie einen Blick auf Scikit-Learn lib: http://scikit-learn.org/

---

Wenn nein (Sie wollen nicht für maschinelles Lernen Lösungen verwenden): Es existieren ein schneller String-Suchalgorithmus, der eine Zeichenfolge in einem Korpus einer anderen Zeichenfolge mit einigen Techniken sucht. es gibt viele Algorithmus, wie Boyer Moore: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Weitere Details dieses gut sein kann: https://softwareengineering.stackexchange.com/questions/183725/which-string-search-algorithm-is-actually-the-fastest

Answer 4

ich vor dem Training alle Modelle für maschinelles Lernen local sensitive hashing im ersten Schritt zu verwenden, empfehlen würde. Das wird wahrscheinlich helfen, da Sie nicht viele Funktionen haben. Wenn Sie etwas stärkeres wollen, können Sie Naive Bayes und ein Feature-Engineering verwenden.