Pythonで姓を分類する最速の方法

国勢調査から12Kアジアの姓と200Kの名前を持つリストを持っています。彼らの姓が私の12Kリストに載っていることに基づいて、アジア人または非アジア人として200K人を分類したいと思います。Pythonで姓を分類する最速の方法

リスト内のelemenstの1つに12Kリストの姓が含まれているかどうかを確認する方法はありますか。

2016-07-24 NicolasVega

あなたの姓のリストから '' 'set''を作成して[メンバーシップのテスト]（https://docs.python.org/3/reference/expressions.html#membership-test-operations） – wwii

それはです社会的に名前 - >レースを考慮する傾向にあり、モチベーションレースの分類自体もむしろ邪魔です。https://techcrunch.com/2015/08/02/machine-learning-and-human-bias-an-uneasy-pair/ http://www.fatml.org/cfp.html – alvas

OPには、LeeやLongのような名前のあいまいな分類もあります。非アジア人もそれらの名前を持つことができます。 –

-1

"高速"とは何ですか？

Jamesは、Pythonの組み込みのsetを使用してメンバーシップをテストすることを提案しました。 Pythonのset実装はハッシュテーブルを使用します。平均時間の複雑さはO（1）ですが、最悪の場合はです。はO（n）となります.nはアジアの姓のカーディナリティです。だから最悪の場合の場合、はO（m）の代わりにO（mn）で終わることができます。ここで、mは分類する名前の集合の基数です。参考のため

、以下を参照してくださいhttps://wiki.python.org/moin/TimeComplexity

を使用すると、最悪の場合に保証を持っているしたい場合は、セットnをソートし、バイナリ検索を行うと、それを達成することができます。これはO（m lg n）時間の複雑さで終わるでしょう。

バイナリ検索：https://docs.python.org/3.1/library/bisect.html

それは本当にハッシュ関数は、あなたのデータのためにどのように動作するかも依存します。

出典

2016-07-24 04:01:05

あなたの解決策が最速である_why_を追加してください。 [James]（http://stackoverflow.com/a/38548652/5488275）の答えによれば、あなたのアプローチはこの特定の問題に対してはかなり遅いかもしれません。 –

@ NanderSpeerstra私は答えを編集しました。基本的には最悪の場合の保証です。 –

文字列をハッシュしているときに、その最悪の場合に対処する可能性は薄いです。 *あなたが独自のハッシュ関数を書いている場合を除き、最悪の場合に対抗することはほとんどありません。組み込みの関数は確かに文字列を扱えるほど頑丈です。私はあなたの答えが今何かを加えているので私はdownvoteを削除しましたが、Askerがこの最悪の事態に立ち向かうことは天文学的にはないと言えることは確かに価値があります。 – James

これを行う最良の方法は、12Kリストをセットデータ構造に変換することです。次に、国勢調査データを繰り返し処理し、それぞれがセットに含まれているかどうかを確認することができます。

# 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...

これはほぼ確実にPythonであなたが必要なものを達成するための最速の方法または任意の言語であり、200Kのサイズのリストに合理的に高速である必要があります。

Wai Leong Yeowは、リストを直接チェックするよりも速いバイナリ検索を提案していますが、これは200Kの異なる名前でO（ログn）操作になります（Nは12,000です。（これは単純化されています - 実際には大きなO表記によってマスクされたいくつかの一定の要因がありますが、一定時間のソリューションは確かにまだまだ高速です）。ソートするとO（n log n）時間がかかります。ここでは、集合に変換するにはO（n）時間かかるので、この方法では前処理が高速になります。

出典

2016-07-24 04:08:53 James

実際の問題によって異なります。 asian/non-asianの名前を予測する機械学習（あなたのタグ：分類）をしたいですか？

「はい」の場合：いくつかの準監督方法を試してください。これを行うには、まずランダムに200kのデータをランダムに選択してから12kで検索し、存在する場合は1にラベル付けし、それ以外の場合は0にラベルを付けます。ランダムフォレスト、SVMなどの分類アルゴリズムを使用しますまたはKNN。また、あなたの名前をBag of wordのようにモデル化することもできます（あなたの問題Bag of Letter！NOは、（あなたが機械学習ソリューションを使用したくない）場合http://scikit-learn.org/

：が存在またはそのような何か）：分類タスクのためのhttps://en.wikipedia.org/wiki/Bag-of-words_model

、scikit-学ぶlibのを見てみましょういくつかのテクニクスで他の文字列のコーパスの文字列を検索するいくつかの高速文字列検索アルゴリズム。詳細についてはhttps://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

これは良いことができます：ボイヤームーアのような多くのアルゴリズムは、あるhttps://softwareengineering.stackexchange.com/questions/183725/which-string-search-algorithm-is-actually-the-fastest

出典

2016-07-24 15:26:34 Masoud

あなたは既に持っているリストの単語を拾い読みするためにモデルを訓練することのポイントは何ですか？モデルを訓練したい場合は、偽陰性である可能性が高い*ではない陰性データを探します。また、ストリング・マッチングを行う場合は、はるかに簡単な解決法があります： 'set（）'。 – alexis

@alexis、私が言及したように、それは問題に依存します。たとえば、200kの名前を毎秒分類し、結果をできるだけ速く検索したい場合（ユーザーが '最も速い方法'を尋ねるので）依存 ' – Masoud

あなたは、統計的な分類子がセットの検索より速いと言っていますか？それはただ不可能です。 – alexis

私は任意の機械学習モデルを訓練する前に、最初のステップでlocal sensitive hashingを使用することをお勧めします。おそらくあなたは多くの機能を持っていないので、おそらく役に立ちます。何かを強くしたいなら、Naive Bayesといくつかの機能エンジニアリングを使うことができます。

出典

2016-07-25 18:34:16

Pythonで姓を分類する最速の方法

答えて

関連する問題