BigData処理の並列アルゴリズム：落とし穴と課題

この出版物は、Autumn BigData ConferenceでのAlexSerbulによるプレゼンテーションに基づいています。

ビッグデータはトレンディで関連性のあるトピックです。 しかし、多くの人は、理論的考察の過剰と実際的な推奨事項の特定の欠如に依然として恐れています。 この投稿では、このギャップを部分的に埋め、1,000万アイテムの製品カタログをクラスター化する例を使用して、ビッグデータを処理するための並列アルゴリズムの使用について説明します。

残念ながら、大量のデータがある場合、MapReduceを使用して並行して動作するように、古典的なアルゴリズムを再度「再発明」する必要があります。 そしてそれは大きな問題です。



出口は何ですか？ 時間とお金を節約するために、並列クラスタリングアルゴリズムを実装できるライブラリを見つけようとすることは確かです。 もちろん、Javaプラットフォームには、死にゆくApache Mahoutと成長を続けるApache Spark MLlibがあります。 残念ながら、MahoutはMapReduceでサポートするアルゴリズムはほとんどありません。それらのほとんどは一貫しています。

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

• K-means
• ガウス混合
• 電力反復クラスタリング（PIC）
• 潜在ディリクレ割り当て（LDA）
• ストリーミングk-means

クラスタリング用に1000万〜2000万のエンティティがある場合、上記のソリューションはもはや役に立ちません。ハードコアが必要です。 しかし、まず最初に。

そのため、1,000万アイテムのカタログをクラスター化する必要があります。 なぜこれが必要なのですか？ 実際、ユーザーはオンラインストアで推奨システムを使用できます。 また、彼女の仕事は、当社のプラットフォームで動作するすべてのサイトの商品の集約されたカタログの分析に基づいています。 ある店舗で、買い手がaを切るためにrecommendedを選ぶように勧められたとしましょう（そう、これは企業ブログですが、ビッグデートや数学について話すことはできません-誰もが眠っています）。 システムはこれについて学習し、分析し、別のストアで同じバイヤーにボタンアコーディオンをプレイして楽しむことを推奨します。 つまり、クラスタリングによって解決される最初のタスクは、関心のある転送です。

2番目のタスク：商品の正しい論理リンクを確実に作成して、関連する売上を増やすこと。 たとえば、ユーザーがカメラを購入した場合、システムはバッテリーとメモリーカードを推奨します。 つまり、同様の製品をクラスターで収集し、クラスターレベルで既に別のストアで作業する必要があります。

上記のように、当社の製品データベースは、1C-Bitrixプラットフォームで動作する数万のオンラインストアのカタログで構成されています。 ユーザーはそこにさまざまな長さのテキスト記述を入力し、誰かが商品、モデル、メーカーのブランドを追加します。 数万の店舗からすべての製品を収集および分類するための一貫した正確な統一システムをコンパイルすることは、費用がかかり、長く、困難です。 そして、類似の製品を迅速に結合し、協調フィルタリングの品質を大幅に改善する方法を探していました。 結局のところ、システムが購入者をよく知っている場合、どの特定の製品とそのブランドが彼が興味を持っているかは問題ではなく、システムは常に彼に提供するものを見つけます。

ツール選択

まず、「ビッグ」データを扱うのに適したストレージシステムを選択する必要がありました。 少し繰り返しますが、素材の固定には便利です。 私たち自身のために、データベースの4つの「キャンプ」を特定しました。

• MapReduce SQL：Hive、Pig、Spark SQL 。 10億行をRDBMSにダウンロードし、データ集約を実行します-このクラスのストレージシステムは、このタスクに「あまり適していません」ことが明らかになります。 したがって、直感的には、MapReduceを使用してSQLを使用することができます（Facebookはかつて使用していました）。 ここでの明らかな欠点は、短いクエリの実行速度です。
• SQL on MPP（大規模並列処理）：Impala、Presto、Amazon RedShift、Vertica 。 このキャンプの代表者は、MapReduceを介したSQLは行き止まりであると主張しているため、データが保存されている各ノードでドライバーを実際に起動する必要があります。 しかし、これらのシステムの多くは不安定性に悩まされています。
• NoSQL：Cassandra、HBase、Amazon DynamoDB 3番目のキャンプでは、BigDataはNoSQLです。 しかし、実際、NoSQLはリング構造に統合された「memcachedサーバー」のセットであり、「値によってキーを取得して応答を返す」などのクエリをすばやく実行できることを理解しています。 また、キーによってランダムアクセスメモリでソートされたデータセットを返すこともできます。 それはほとんどすべてです-JOINSを忘れてください。
• クラシック：MySQL、MS SQL、Oracleなど。 モンスターはあきらめず、上記のすべて-ゴミ、心からの悲しみ、およびリレーショナルデータベースがBigDataでうまく機能すると主張します。 フラクタルツリー（ https://en.wikipedia.org/wiki/TokuDB ）を提供している人もいれば、クラスターを提供している人もいます。 モンスターも生きたい。

クラスタリングの問題を綿密に処理した結果、市場には既製のオファーがそれほど多くないことがわかりました。

• Spark MLlib（Scala / Java / Python / R）-大量のデータがある場合。
• scikit-learn.org（Python）-データがほとんどない場合。
• R-実装のひどい曲率（数学者や統計学者へのプログラミングの信頼）により矛盾した感情を引き起こしますが、多くの既製のソリューションがあり、最近のSparkとの統合は非常に楽しいものです。

結局、SparkMLlibに決めました。なぜなら、見たところ、信頼できる並列クラスタリングアルゴリズムがあるからです。

クラスタリングアルゴリズムの検索

最初に、商品のテキストによる説明（名前と短い説明）をクラスターに結合する方法を理解する必要がありました。 自然言語ワードプロセッシングは、機械学習や情報検索など、コンピューターサイエンスの別の巨大な分野です。
言語学、さらには（タダム！）ディープラーニング。

クラスタリング用に数十、数百、数千のデータがある場合、ほぼすべての古典的なアルゴリズム、さらには階層的なクラスタリングでも可能です。 問題は、階層的クラスタリングのアルゴリズムの複雑さがほぼO（N ³ ）であることです。 つまり、巨大なクラスター上のデータボリュームで機能するまで、「数十億年」待つ必要があります。 また、特定のサンプルのみの処理に限定することは不可能でした。 したがって、額の階層的クラスタリングは私たちに適していない。

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



これは非常にシンプルで、十分に研究され、普及しているアルゴリズムです。 ただし、ビッグデータでは非常にゆっくりと動作します。アルゴリズムの複雑さは約O（nkdi）です。 n = 10,000,000（商品の数量）、k = 1,000,000（予想されるクラスター数）、d = <1,000,000（単語のタイプ、ベクトル次元）、i = 100（概算の反復数）、O = 10 ²¹操作。 比較のために、地球の年齢は1.4 * 10 ¹⁷秒です。

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％を解決できるシンプルで効果的なソリューションをいつでも見つけることができると信じています！ ビッグデータを扱うことに成功し、成功しました！