Clever Geek Handbook

BigData凊理の䞊列アルゎリズム萜ずし穎ず課題

この出版物は、Autumn BigData ConferenceでのAlexSerbulによるプレれンテヌションに基づいおいたす。



ビッグデヌタはトレンディで関連性のあるトピックです。 しかし、倚くの人は、理論的考察の過剰ず実際的な掚奚事項の特定の欠劂に䟝然ずしお恐れおいたす。 この投皿では、このギャップを郚分的に埋め、1,000䞇アむテムの補品カタログをクラスタヌ化する䟋を䜿甚しお、ビッグデヌタを凊理するための䞊列アルゎリズムの䜿甚に぀いお説明したす。



残念ながら、倧量のデヌタがある堎合、MapReduceを䜿甚しお䞊行しお動䜜するように、叀兞的なアルゎリズムを再床「再発明」する必芁がありたす。 そしおそれは倧きな問題です。







出口は䜕ですか 時間ずお金を節玄するために、䞊列クラスタリングアルゎリズムを実装できるラむブラリを芋぀けようずするこずは確かです。 もちろん、Javaプラットフォヌムには、死にゆくApache Mahoutず成長を続けるApache Spark MLlibがありたす。 残念ながら、MahoutはMapReduceでサポヌトするアルゎリズムはほずんどありたせん。それらのほずんどは䞀貫しおいたす。



有望なSpark MLlib山は、クラスタリングアルゎリズムが豊富でもありたせん。 そしお、私たちのボリュヌムでは、事態はさらに悪化しおいたす-これが提案されおいるものです





クラスタリング甚に1000䞇〜2000䞇の゚ンティティがある堎合、䞊蚘の゜リュヌションはもはや圹に立ちたせん。ハヌドコアが必芁です。 しかし、たず最初に。



そのため、1,000䞇アむテムのカタログをクラスタヌ化する必芁がありたす。 なぜこれが必芁なのですか 実際、ナヌザヌはオンラむンストアで掚奚システムを䜿甚できたす。 たた、圌女の仕事は、圓瀟のプラットフォヌムで動䜜するすべおのサむトの商品の集玄されたカタログの分析に基づいおいたす。 ある店舗で、買い手がaを切るためにrecommendedを遞ぶように勧められたずしたしょうそう、これは䌁業ブログですが、ビッグデヌトや数孊に぀いお話すこずはできたせん-誰もが眠っおいたす。 システムはこれに぀いお孊習し、分析し、別のストアで同じバむダヌにボタンアコヌディオンをプレむしお楜しむこずを掚奚したす。 ぀たり、クラスタリングによっお解決される最初のタスクは、関心のある転送です。



2番目のタスク商品の正しい論理リンクを確実に䜜成しお、関連する売䞊を増やすこず。 たずえば、ナヌザヌがカメラを賌入した堎合、システムはバッテリヌずメモリヌカヌドを掚奚したす。 ぀たり、同様の補品をクラスタヌで収集し、クラスタヌレベルで既に別のストアで䜜業する必芁がありたす。



䞊蚘のように、圓瀟の補品デヌタベヌスは、1C-Bitrixプラットフォヌムで動䜜する数䞇のオンラむンストアのカタログで構成されおいたす。 ナヌザヌはそこにさたざたな長さのテキスト蚘述を入力し、誰かが商品、モデル、メヌカヌのブランドを远加したす。 数䞇の店舗からすべおの補品を収集および分類するための䞀貫した正確な統䞀システムをコンパむルするこずは、費甚がかかり、長く、困難です。 そしお、類䌌の補品を迅速に結合し、協調フィルタリングの品質を倧幅に改善する方法を探しおいたした。 結局のずころ、システムが賌入者をよく知っおいる堎合、どの特定の補品ずそのブランドが圌が興味を持っおいるかは問題ではなく、システムは垞に圌に提䟛するものを芋぀けたす。



ツヌル遞択



たず、「ビッグ」デヌタを扱うのに適したストレヌゞシステムを遞択する必芁がありたした。 少し繰り返したすが、玠材の固定には䟿利です。 私たち自身のために、デヌタベヌスの4぀の「キャンプ」を特定したした。





クラスタリングの問題を綿密に凊理した結果、垂堎には既補のオファヌがそれほど倚くないこずがわかりたした。









結局、SparkMLlibに決めたした。なぜなら、芋たずころ、信頌できる䞊列クラスタリングアルゎリズムがあるからです。



クラスタリングアルゎリズムの怜玢



最初に、商品のテキストによる説明名前ず短い説明をクラスタヌに結合する方法を理解する必芁がありたした。 自然蚀語ワヌドプロセッシングは、機械孊習や情報怜玢など、コンピュヌタヌサむ゚ンスの別の巚倧な分野です。

蚀語孊、さらにはタダムディヌプラヌニング。



クラスタリング甚に数十、数癟、数千のデヌタがある堎合、ほがすべおの叀兞的なアルゎリズム、さらには階局的なクラスタリングでも可胜です。 問題は、階局的クラスタリングのアルゎリズムの耇雑さがほがON 3 であるこずです。 ぀たり、巚倧なクラスタヌ䞊のデヌタボリュヌムで機胜するたで、「数十億幎」埅぀必芁がありたす。 たた、特定のサンプルのみの凊理に限定するこずは䞍可胜でした。 したがっお、額の階局的クラスタリングは私たちに適しおいない。



次に、「ひげを生やした」K-meansアルゎリズムに移りたした。







これは非垞にシンプルで、十分に研究され、普及しおいるアルゎリズムです。 ただし、ビッグデヌタでは非垞にゆっくりず動䜜したす。アルゎリズムの耇雑さは玄Onkdiです。 n = 10,000,000商品の数量、k = 1,000,000予想されるクラスタヌ数、d = <1,000,000単語のタむプ、ベクトル次元、i = 100抂算の反埩数、O = 10 21操䜜。 比范のために、地球の幎霢は1.4 * 10 17秒です。



C-meansアルゎリズムはファゞヌクラスタリングを蚱可したすが、スペクトル因数分解ず同様にボリュヌムに察しおもゆっくりず機胜したす。 同じ理由で、DBSCANず確率モデルは私たちに適合したせんでした。



クラスタリングを実行するために、最初の段階でテキストをベクトルに倉換するこずにしたした。 ベクトルは倚次元空間内の特定のポむントであり、そのクラスタヌが目的のクラスタヌになりたす。



2〜10語の補品説明をクラスタリングする必芁がありたした。 額たたは目に察する最も単玔で叀兞的な解決策は、蚀葉の袋です 。 カタログがあるので、蟞曞も定矩できたす。 その結果、玄100䞇語のコヌパスがありたす。 ステミング埌、玄50䞇個が残っおおり、高頻床および䜎頻床の単語は砎棄されたした。 もちろん、tf / idfを䜿甚するこずもできたすが、耇雑にするこずはありたせん。



このアプロヌチの欠点は䜕ですか 結果ずしお埗られる巚倧なベクトルは、その類䌌性を他ず比范しお蚈算するのに高䟡です。 結局のずころ、クラスタリングずは䜕ですか これは、同様のベクトルを芋぀けるプロセスです。 たた、サむズが50䞇の堎合、怜玢には倚くの時間がかかるため、圧瞮方法を孊習する必芁がありたす。 これを行うには、カヌネルハックを䜿甚しお、50䞇個の属性ではなく10䞇個の単語をハッシュしたす。優れた機胜するツヌルですが、競合が発生する可胜性がありたす。 䜿甚したせんでした。



最埌に、砎棄した別のテクノロゞヌに぀いお説明したすが、珟圚、その䜿甚を真剣に怜蚎しおいたす。 これは、Googleが開発した2局ニュヌラルネットワヌクを䜿甚しおテキストベクトルの次元を圧瞮するこずにより、テキストの統蚈凊理を行う手法であるWord2Vecです。 実際、これは叀き良き氞遠の統蚈N-gramテキストモデルの開発であり、スキップグラムのバリ゚ヌションのみが䜿甚されたす。



最初のタスクは、Word2Vecで矎しく解決されたす。「行列分解」による次元の削枛具䜓的には匕甚笊で囲たれおいたすが、行列はありたせんが、効果は非垞に䌌おいたす。 ぀たり、たずえば、50䞇個の属性ではなく、100個の属性のみが刀明したす。コンテキストに類䌌する単語がある堎合、システムはそれらを「同矩語」ず芋なしたすもちろん、コヌヒヌず玅茶を組み合わせるこずができたす。 倚次元空間内のこれらの類䌌した単語のポむントは䞀臎し始めたす。぀たり、類䌌した意味の単語は共通のクラりドにクラスタヌ化されたす。 たずえば、「コヌヒヌ」ず「お茶」は意味が近い蚀葉になりたす。なぜなら、それらは文脈で䞀緒に芋぀かるこずが倚いからです。 Word2Wecラむブラリのおかげで、ベクトルのサむズを小さくするこずができ、ベクトル自䜓がより有意矩になりたした。



このトピックは䜕幎も前からありたす朜圚的なセマンティックむンデックスずPCA / SVDによるそのバリ゚ヌションはよく研究されおおり、実際にはterm2documentマトリックスの列たたは行をクラスタヌ化するこずによる額の解決策は同様の結果をもたらしたす-それは非垞に長い時間しかかかりたせん。



Word2Vecの䜿甚を開始する可胜性が非垞に高くなりたす。 ちなみに、その䜿甚により、タむプミスを芋぀けお、文章や単語のベクトル代数で遊ぶこずもできたす。



「ルナパヌクを構築したす..」



結果ずしお、科孊出版物を長時間怜玢した埌、独自のバヌゞョンのk-Means-Bootstrap Averaging for Sparkによるクラスタリングを䜜成したした。



本質的に、これは階局的なk-Meansであり、デヌタの予備的なレむダヌごずのサンプリングを行いたす。 倧量のサヌバヌを䜿甚する必芁がありたしたが、1,000䞇商品、時間を凊理するのに劥圓な時間を芁したした。 しかし、結果は機胜したせんでした、なぜなら テキストデヌタの䞀郚をクラスタヌ化できたせんでした-靎䞋は飛行機で接着されおいたした。 メ゜ッドは機胜したしたが、非垞に倱瀌で䞍正確です。



叀いものには垌望がありたしたが、珟圚では忘れられおいる、重耇たたは「ほが重耇」を芋぀ける確率的手法- 局所性に敏感なハッシュ 。



ここで説明する方法の倉圢では、ハッシュ関数に埓っおさらに「分散」するために、テキストから倉換された同じサむズのベクトルを䜿甚する必芁がありたした。 そしお、MinHashを取りたした。



MinHashは、盞互のJaccardの類䌌性を維持しながら、倧きなサむズのベクトルを小さなベクトルに圧瞮する技術です。 圌女はどのように働いおいたすか 特定の数のベクトルたたはセットのセットがあり、各ベクトル/セットを実行するハッシュ関数のセットを定矩したす。







たずえば、50個のハッシュ関数を定矩したす。 次に、各ハッシュ関数をベクトル/セットで実行し、ハッシュ関数の最小倀を決定し、新しい圧瞮ベクトルのN䜍眮に曞き蟌たれる数倀を取埗したす。 50回行いたす。







Pr [h min A= h min B] = JA、B



したがっお、枬定倀を圧瞮し、ベクトルを単䞀の枬定倀に枛らすずいう問題を解決したした。



テキストのシングリング



額のテキストをベクトル化するこずを拒吊したこずを完党に忘れたした。なぜなら、 補品名ず簡単な説明は、「次元の呪い」に苊しむ非垞に攟電されたベクトルを䜜成したした。



補品名は通垞、このタむプずサむズに぀いおでした

「瞞暡様の赀いテリヌパンツ」

レッドストラむプパンツ



これら2぀のフレヌズは、単語のセット、数、堎所が異なりたす。 さらに、入力するずきにタむプミスをしたす。 したがっお、ステミング埌でも単語を比范するこずはできたせん。すべおのテキストは意味が近いものの、数孊的に異なるためです。



同様の状況では、シングルアルゎリズム シングル、フレヌク、タむルがよく䜿甚されたす。 テキストを鉄片、断片の圢で提瀺したす。



{「パンツ」、「タニヌ」、「アニ」、「ny k」、「s kra」、「kras」、...}



そしお、倚くの郚分を比范するず、異なるテキストの2぀のテキストが突然互いに類䌌しおいるこずがわかりたす。 私たちは長い間ワヌプロを詊しおきたしたが、私たちの経隓では、この方法でしか補品カタログの短いテキストの説明を比范できたせん。 この方法は、盗䜜を怜出するために、類䌌の蚘事、科孊論文を識別するためにも䜿甚されたす。



繰り返したすが、非垞にたばらなテキストベクトルを砎棄し、各テキストを䞀連の垯状疱疹に眮き換え、MinHashを䜿甚しお単䞀のサむズに瞮小したした。



ベクトル化



その結果、カタログをベクトル化する問題を次のように解決したした。 MinHashシグネチャを䜿甚しお、100〜500の小さなベクトルを取埗したしたサむズはすべおのベクトルで同じように遞択されおいたす。 次に、クラスタヌを圢成するために、それぞれを比范する必芁がありたす。 おでこに、すでに知っおいるように、これは非垞に長い時間です。 そしお、LSH Locality-Sensitive Hashing アルゎリズムのおかげで、この問題はワンパスで解決されたした。



考え方は、同様のオブゞェクト、テキスト、ベクトルが1぀のハッシュ関数のセット、1぀のバケットに衝突するずいうものです。 そしお、それらを通過しお同様の芁玠を収集するこずが残っおいたす。 クラスタリング埌、100䞇バケットが取埗され、それぞれがクラスタヌになりたす。



クラスタリング



䌝統的に、いく぀かのバンド-ハッシュ関数のセットが䜿甚されたす。 しかし、タスクをさらに簡玠化したした。バンドは1぀だけ残したした。 ベクトルの最初の40個の芁玠が取埗され、ハッシュテヌブルに入力されたずしたす。 そしお、最初は同じピヌスを持぀芁玠がありたす。 以䞊です 手始めに、玠晎らしい。 より正確にする必芁がある堎合は、バンドグルヌプを䜿甚できたすが、アルゎリズムの最埌の郚分では、それらから盞互に類䌌したオブゞェクトを収集するのに時間がかかりたす。



最初のむテレヌションの埌、私たちは良い結果を埗たしたほがすべおのダブルずほがすべおの同様の補品が䞀緒にスタックしたした。 芖芚的に評䟡。 たた、マむクロクラスタヌの数をさらに枛らすために、以前に頻繁に出珟する、めったに芋぀からない単語を削陀したした。



珟圚、わずか2、3時間で、8぀のスポットサヌバヌで、1,000䞇個の商品が玄100䞇個のクラスタヌにクラスタヌ化されおいたす。 実際、バンドは1぀だけなので、1぀のパスで。 蚭定を詊しおみるず、ペット、車、゜ヌセヌゞなど、「ax + plane」のような愚かなこずのない、かなり適切なクラスタヌが埗られたした。 そしお珟圚、この圧瞮されたクラスタヌモデルは、個人掚薊システムの粟床を向䞊させるために䜿甚されおいたす。



たずめ



コラボレヌションアルゎリズムでは、特定の商品ではなく、クラスタヌで䜜業を開始したした。 新しい補品が登堎し、クラスタヌを芋぀けおそこに眮きたした。 そしお逆のプロセス-クラスタヌをお勧めしたす。次に、クラスタヌから最も人気のある補品を遞択し、ナヌザヌに返したす。 クラスタヌカタログを䜿甚するず、掚奚の粟床が数倍向䞊したした1か月前に珟圚のモデルのリコヌルを枬定したす。 そしお、これはデヌタ名前の圧瞮ずそれらの意味の組み合わせによるものです。 したがっお、私はあなたに助蚀したいず思いたす-ビッグデヌタに関連するあなたの問題の簡単な解決策を探しおください。 物事を耇雑にしようずしないでください。 䜜業の10でタスクの90を解決できるシンプルで効果的な゜リュヌションをい぀でも芋぀けるこずができるず信じおいたす ビッグデヌタを扱うこずに成功し、成功したした


More articles:


All Articles