グラフクラスタリングとコミュニティ検索。 パート2：k-medoidと修正

こんにちは、Habr！ このパートでは、 最初のパートのグラフの色を取得するアルゴリズムを説明します。 アルゴリズムはk-medoidに基づいています-これはかなり単純で透過的な方法です。 これは、一般的なk-meansの変形であり、ほとんどの人が既に考えていることでしょう。



k-medoidsでは、k-meansとは異なり、どの点も重心として機能することはできませんが、利用可能な観測の一部のみです。 頂点間のグラフでは距離を決定できるため、k-medoidはグラフのクラスタリングに適しています。 この方法の主な問題は、クラスターの数を明示的に指定する必要があることです。つまり、コミュニティーの識別ではなく、指定された数の部分への最適な分割（グラフ分割）です。



これに対処するには2つの方法があります。

• または、パーティションの「品質」の特定のメトリックを設定し、最適なクラスター数を選択するプロセスを自動化する。
• または、色付きのグラフを描画して、「論理的に」最も論理的なパーティションを決定しようとします。

2番目のオプションは、小さなデータと数十個以下のクラスターにのみ適しています（または、マルチレベルクラスタリングでアルゴリズムを使用する必要があります）。 グラフが大きくなるほど、品質を「目で」評価する際に満足する必要がある詳細が粗くなります。 同時に、特定のグラフごとに、手順を新たに繰り返す必要があります。

PAM

k-medoidの最も一般的な実装は、 PAM （Partitioning Around Medoids）と呼ばれます。 これは、非常に非効率的なヒューリスティックを備えた貪欲なアルゴリズムです。 グラフの付録のように見えます。

 入力：グラフG、指定されたクラスター数k
出力：k個のクラスターへの最適な分割+各クラスターの「中心」頂点
初期化：medoidとしてk個のランダムノードを選択します。
各点について、最も近いmedoidを見つけ、初期クラスター化を形成します。
 minCost =初期設定からの損失関数
メドイドが安定するまで：
    各medoid mについて：
         mを中心とするクラスター内の各頂点v！= M：
             vでハニロイドを移動します
            新しいmedoid間のすべての頂点を再配布します
            コスト=グラフ全体の損失関数
            コスト<minCostの場合：
                メドイドを暗記する
                 minCost =コスト
             medoidを所定の位置に置きます（m）
    見つかったすべてのものを最適に置き換えます（つまり、1つのクラスター内で1つのmedoidを変更します）-これは1回の繰り返しです。 

反復ごとに、アルゴリズムは繰り返します グラフポイント（ここで ノードの合計数です）、対応するハニロイドをそこに移動します。 そのような置換ごとに、彼はmedoidへのすべてのポイントの距離を再計算する必要があります。 ポイント間のすべてのペアワイズ距離がメモリに収まる場合、このステップは アクション。 さらに最適な交換には、 アクション。 最悪の場合の反復の合計の複雑さ これは絶対に受け入れられません。 数千のノードを持つグラフの反復回数は約30〜50です。

最も貪欲なヒューリスティック

このアルゴリズムを少し使用して、プロセスを高速化する方法を考え始めました。1台のマシンで1,200ノードのみのグラフをクラスター化するには数分かかりました（10,000ノードの場合、すでに数時間）。 考えられる改善の1つは、同じクラスター内のごく一部のポイントに対して、1つのクラスターのみ、またはさらに優れた最適な置換を検索することにより、アルゴリズムをさらに貪欲にすることです。 最後の発見的バリアントは、アルゴリズムに次の形式を与えます。

入力：グラフG、指定されたクラスター数k
出力：k個のクラスターへの最適な分割+各クラスターの「中心」頂点
各点について、最も近いmedoidを見つけ、初期クラスター化を形成します。
改善がなかった行の反復回数：StableSequence = 0  
 Trueの場合：
    各medoid mについて：
         mを中心とするクラスター内のs点をランダムに選択
         sの各頂点vに対して：
             vでハニロイドを移動します
            新しいmedoid間のすべての頂点を再配布します
            コスト=グラフ全体の損失関数
            コスト<minCostの場合：
                メドイドを暗記する
                 minCost =コスト
             medoidを所定の位置に置きます（m）
         sの最適な置換が損失関数を改善する場合：
            この交換を行います
             StableSequence = 0
        そうでなければ：
             StableSequence + = 1
             StableSequence>しきい値の場合：
                現在の構成を返します 

簡単に言えば、グラフのすべての頂点ではなく、1つのクラスターの最適な置換を探しています。このクラスター内のすべての頂点をソートするのではなく、 それらの。 この場合、1つの反復の複雑さは次のようになります。 ノード数が線形。 同時に 、計算の複雑さを大幅に削減しますが、クラスターの品質はこのような単純化された単純化によって低下しませんか？ 以下のようなパラメーターを持つアルゴリズムの例を提供する記事があります 意味。



2に減少しても1に減少しても、実際にはさまざまなクラスター品質メトリック（ モジュール性など ）を悪化させることはありません。 したがって、私たちは取ることにしました （同じクラスター内の2つのポイントのいずれかを選択します）、次の場合はプロセスを停止します 行の反復（StableSequence）の現在の最適化は変更されません。 通常のPAMでは、このような反復が1回行われるとプロセスが終了します。 実際には、これにより、新しいヒューリスティックを使用した反復回数が10〜20倍に増加しますが、各反復の加速は補正されません。 その結果、この変更により、グラフのクラスタリング時間を1209ノードから5.5秒、10,000ノードから2〜3分に短縮することができました。これはすでに許容されますが、非常に長い時間です。 それにもかかわらず、これはアルゴリズムの最も重要な改善であり、その後、最も難しいステップはクラスタリング自体ではなく、データの前処理、特に頂点間のペアワイズの類似性/距離の計算です。

クララ

k-medoidのスケーラビリティを改善するための次のステップは、 claraと呼ばれるかなりよく知られているPAMの修正です。 頂点のサブセットが元のグラフからランダムに選択され、これらの頂点によって形成されるサブグラフがクラスター化されます。 次に（グラフが接続されていると仮定して）、残りの頂点はサブグラフから最も近いmedoidに単純に分散されます。 すべてのクララソルトは、頂点のさまざまなサブセットでアルゴリズムを順番に実行し、最適な結果を選択することで構成されます。 このため、個々の実行ごとに情報の一部を除外することによる損害を補償するとともに、極小値にとどまることを回避することになっています。 結果を選択する際の最適性の尺度として、モジュール性を使用しました。 最初の段階でサブグラフを分離するための多くのトリッキーな方法を思いつくことができますが、いくつかの簡単な方法を使用しました。

1. 等しい確率での頂点のランダム選択。
2. 元のグラフの頂点の次数に比例する確率。
3. 常に最大数の固定数の頂点を選択し、同じ確率でランダムに頂点を選択します。
4. しきい値を超えたジャカード測定値と、同じ確率で欠落している（または近傍でクロールする）頂点のペアを選択します。

すべての方法は、人気のあるWTFメトリックに従ってクラスターの品質がほぼ同じであることを示しました。これは、感嘆符「What the fuck？」の数に相当します。



claraのサブサンプリングボリュームを選択することも、品質と速度のトレードオフを表します。 データ内に存在するクラスターが多いほど、サンプリング機能は低下します。一部のクラスターは単にサンプルに含まれない場合があります。 クラスタサイズの違いが大きい場合、このアプローチは一般的に禁忌です。 構造がほぼ均一である場合は、サンプリングをお勧めします ノード-グラフの半分。 WTFメトリックに基づいて、この比率に達しました。 教師なしで学習を扱う場合、このメトリックは多くの場合最も有用です。



どうやら、クララはもともとクラスタリングアルゴリズムの実行時間を短縮することを目的としていたため、その計算の複雑さは頂点の数よりも速く増加します（サブグラフで数回実行すると、グラフ全体で1回より速くなります）。 したがって、改善されたヒューリスティック（線形複雑度）を使用する場合のクララの利点は大幅に低下します。 ただし、クララの別の使用法が見つかりました。アンサンブルアプローチです。これについては後で説明します。

局部間伐（L-Spar）

次のステップはL-Spar （ローカルスパース化から）と呼ばれ、 ここで詳細に説明されています 。 これは、クラスタリング前のグラフ前処理方法です。 原則として、その接続性を破壊することなく、エッジの一部（ノードではなく！）を削除することにより、グラフを「薄く」します。



このステップを実装するには、2つのノード間の「類似性」の程度を知る必要があります。 k-medoidの各反復で類似性が必要なため、事前に類似性マトリックスを読み取り、ディスクに保存することにしました。 類似性の尺度として、ジャカード尺度が使用されましたが、おそらくあなたはすでにそれを満たしています：









どこで ノードの近隣のセットです 。



L-Sparアルゴリズムは非常に単純です。 各ノードで最初に 彼のrib骨すべて 降順で並べ替え 、その後、リストの末尾がフィルタリング用のセットに含まれます。 次の各頂点は、既存のエッジと組み合わされたフィルタリング用の独自のエッジセットを提供します。 各頂点が処理されると、結果のセットのすべてのエッジがグラフから削除されます。 この方法の著者は、「生存者」のリストに含めることを提案しています rib骨 -ノード度 、そして -0〜1の次数。少なくとも1つのノードの「生存者」リストにエッジがある場合、「生存」します。 したがって、新しい孤立ノードは形成されず、元のグラフが接続されていた場合、スパース確率は接続されたままになる可能性があります。



同時に、グラフの次数分布のべき乗則が保存され、平均して2つのノード間の最短パスの長さが非常に短い場合、「タイトな世界」または「小さな世界」の現象につながることが証明されています。 このプロパティは、人間によって生成されたほとんどのネットワークに固有であり、L-Sparはそれを破壊しません。



L-Sparには、たとえば、すべてのリブを 特定のしきい値を下回ると、グラフ全体で同じになります。 つまり、後者の方法では、より疎なクラスターでは、ほとんどすべてのエッジが削除されますが、最も密度の高いコミュニティはほとんど影響を受けません。 同時に、L-Sparの細線化の程度は、ノードのすぐ近くのグラフの密度に依存し、密集したコミュニティと疎なコミュニティの両方の構造を保持します。



もちろん、グラフ前処理のこの方法は、あらゆるクラスタリング方法で使用できます。 複雑さはエッジの数のみに依存し、ノードの数には依存しないアルゴリズムの場合、エッジの数のみが削減されるため、最大の効果が得られます。 この点で、k-medoidは不運でした。その複雑さはノードの数にのみ依存しますが、より明確なコミュニティ構造では、収束に必要な反復回数が減少する場合があります。 スパース化により「ノイズのある」エッジが除去される場合、コミュニティのより明確な構造、したがって反復回数の減少が期待できます。 この仮説は、この方法の著者の実験によって確認されましたが、我々の実験では確認されませんでした。



頂点間の弱いアフィニティは事前にフィルタリングされているため、グラフドメインには「ノイズのある」エッジはありません。 クラスターが視覚的に適切に割り当てられていない場合、データ内で適切に割り当てられていません。 したがって、グラフでは、k-medoidの反復回数は細線化の程度に依存しません。 で 1200ドメインまたは10000ドメインでは、ランタイムに影響はありません。 さらに、k-medoidを使用すると、ネガティブな副作用が発生します。グラフ密度が低いほど、特定のノードがすべてのmedoidとのジャカードとの類似性がゼロになる可能性が高くなります。 これは、比較的少数のmedoid自体、つまりクラスターによって悪化します。 したがって、k-medoidを実行する前にL-Sparを使用しないことが決定されました（ただし、他のアルゴリズムでは非常に有用です）。



L-Sparのもう1つのプロパティに注目する価値があります。これは、mightとmainで使用しました。画像の読みやすさを改善することです。 rib骨の数が大幅に減少したため、ソーシャルネットワークのヘアボールをよりよく視覚化し、その上にコミュニティを表示できるようになりました。 このような視覚化の例は、この投稿の前の部分にありました。L-Sparを適用した後、その前に1285のWebドメインのグラフがありました。

クラスターの数を選択する

k-medoidの問題の1つは、クラスターの固定数です。 最適なクラスター数を見つけるために、いくつかのオプションを試しました。 モジュール性、導電率、正規化されたカットおよびその他のメトリックの問題は、解像度の制限に悩まされ、それらの最大値に到達するのが低すぎることです。 （私たちの目が私たちに言うことと比較して）。 ここに、例えば、私たちによって得られたモジュール性のグラフがあります 1年以上前の1029ノードのWebドメインのグラフの場合：



青はk-medoidの100回の繰り返しごとの平均モジュール性とその1.95標準偏差を示し、緑は100回の繰り返しごとの最大モジュール性を示します。 赤色は、クラスターの最大数に対応するポイントを示します 平均モジュール性が、次の信頼区間の上限より低くない 。 ポイント すでにモジュール性の低下のゾーンにありますが、視覚的に（WTF）に見えるほど多くのコミュニティがデータに存在しています。 まさに 最終的に選ばれました。

安定したコア

上記の変更はスケーラビリティの点では優れている場合がありますが、2つの興味深い問題につながります。 まず、クラスターの品質が低下する可能性があります。ヒューリスティックを単純化するとき（特にサブグラフを選択するか、エッジのほとんどを削除するとき）、パーティションロジックがどの程度低下するかは明らかではありません。 第二に、結果の安定性がかかっています。同じ初期データであっても、2回目の実行でのクラスターへのパーティションは、最初の実行でのパーティションとは大きく異なります。 すべての変更により、アルゴリズムがさらにランダム化されました。 しかし、グラフが時間とともに進化する場合はどうでしょうか？ 互いに異なる実行からクラスターを識別する方法は？



k-medoidの安定性をテストするために、1209ノードのドメイングラフで小規模な実験を行いました。 すべての修正を伴うアルゴリズムの2つの異なる実行について、各クラスター内で最も「中央」のノード（調和中心性メトリックによる）が見つかりました。クラスター内のノードの総数の4分の1で、8以上です。 次に、最初のパーティションの各クラスターについて、2番目のパーティションのクラスターを見つけました。これには、その「中央」ノードの最大数が含まれています。 もし 、その後、最初の実行からの9〜10クラスターのみのパーティションのほとんどのペアについて、「中央ノード」の少なくとも半分が一致する2番目からのアナログを見つけることができます。 これは、たとえば、広告キャンペーンのセグメントを構築する場合には明らかに十分ではありません。 同時に、ドメインの人気とその関係の両方が時間とともに変化するため、ダイナミクスでどのような結果が発生したかはわかりません。



次の記事は、この問題に取り組んでいます： one 、 two 、 three 。 彼らは、頂点を1つだけ追加または削除すると、パーティション全体を根本的に変更し、最も近い隣人だけでなく、グラフの遠くの部分にも影響を与えると言っています。 この問題の1つの解決策は、クラスタリングの平均化です。 これは、教師による指導で実証されているアンサンブルアプローチをクラスター化タスクに適応させる試みです。 1つではなく、たとえば100回のアルゴリズムを実行し、常に同じクラスター内にある頂点（カーネル）のグループを見つけた場合、これらのグループは個々の実行の結果よりもはるかに安定しています。 この方法の唯一の欠点はその速度です。数十回の繰り返しは、アルゴリズムの高速化の成果を無効にする可能性があります。 ただし、核を見つけるときは、より低い損失でグラフをサンプリングできます。 claraを使用します。



コアを取得するためのわずかに異なるオプションを実装しました。 頂点のペアごとに、同じクラスターに分類された実行の割合を検討します。 得られたデータは、新しい完全なグラフでrib骨の重量（近接度）として解釈できます。 さらにこのグラフでは、階層的なクラスタリングが構築されます。 クラスタリング時の距離の関数として、 scipy.linkage凝集法とWard法を使用しました。



ここでは、樹形図の完全版を見ることができます。



カットオフしきい値は、異なる数のクラスターを受け取りながら、任意の高さに設定できます。 クラスターの数が、樹状図自体が受信されたときに実行される各k-medoidのクラスターの数と等しくなるように、このようなしきい値を設定するのが最も論理的に思われるかもしれません。 しかし、実際には、奇妙なことに、k-medoidに適切なものを選択した場合 、樹状図のしきい値を下げながら、はるかに小さいサイズの論理的な「サブコミュニティ」を分離することができます。 たとえば、下のツリーの一部では、12個のコアに対応するしきい値を持つターコイズ色のクラスターが取得されましたが、このクラスターはしきい値を下げながら、上からの車と下からの心理学という2つの意味のあるサブクラスターに分割できます。 これがスクリーンショットです：





本やゲームの断片、シリアルクラスターもフレームに落ちました



この方法で取得したドメインカーネルは、 Exebid.DCA RTBシステムのユーザーセグメントとして正常に機能します。



すでに、ベストプラクティスよりも高速で効率的な優れたコミュニティ割り当てアルゴリズムがいくつかあります。 Louvain、MLR-MCL、SCD、Infomap、Spinner、Stochastic Blockmodelingはその一部です。 将来的には、これらの方法を使用した実験について書く予定です。 しかし、私たちは自分で何かを書きたかったのです。 改善すべき領域の一部を次に示します。

• ジャカード測定の計算は、最もリソースを消費する段階であり、 操作。 MinHashと呼ばれる類似性をすばやく取得する方法で知られています。 それについては、例えばここで読むことができます 。 BayesLSHなど、より洗練された方法があります。
  
  
  
  
• 計算の複雑さは、クラスターの数によって異なりますが、kメドイドのこの機能により、広範なタスクに適用できなくなります。 この方法で対処できます。各反復の各medoidについて、「隣接」medoidのリストを検索して保存し、各反復でのみ再カウントします。
  
  
  
  
• クラスター数の任意の選択 -k-medoidのもう1つの難しさ。 1つの方法は、異なる結果を比較する価値のあるメトリックを見つけることです。 。 この役割は、クラスターの内側と外側の閉じた三角形の分析に基づいて、WCC（加重コミュニティクラスタリング係数）によって主張されています。 おそらく、各反復での最適な置換の選択も、このメトリックに変換する必要があります。

ご清聴ありがとうございました！