まえがき
仕事で苦痛を伴うトピックの1つに対する解決策を求めて、インターネットの英語圏を歩いていると、「高速しきい値クラスタリングアルゴリズム」と呼ばれる非常に興味深いアルゴリズムに出会いました。 注目に値するこのクラスタリングアルゴリズムは比較的最近、つまり今年の11月に登場し、著者はDavid Varadiです。 ソースへのリンクは、記事の最後にあります。
まず、クラスタリングとは何ですか？
クラスタリングは、特定のオブジェクトのセットから作成できるプログラムです。グループは、意味またはコンテンツによって形成され、これらのグループの数は同時に、事前に知られていない可能性があります。 これらのオブジェクトは、グループ化する必要があるものに応じて、ドキュメントまたは番号のいずれかです。
さまざまな実装および解釈の通常のK-meansから、理解するためのより複雑なアルゴリズムに至るまで、多くの多様なクラスタリングアルゴリズムがあります。 特定のアルゴリズムを追い越す一般的な問題は間違いです。 特に実際の人間の発話を含むドキュメントについて話している場合は、間違いが常に発生します。 確かに、サルタンについての物語をどこに置くか、政治、古代ロシアの歴史、またはクラスターを作成する場所は、機械にとって常に明確ではありません。 オブジェクトは、プロパティが異なる他のオブジェクトと多くの関係を持つことができます。 彼らはまだこの仕事に苦労しています。
そして、このエラーを回避する方法は？
エラーを回避する方法はたくさんあります。 オブジェクトの重要なプロパティを明確に強調表示できます。これらのプロパティは、1つのクラスターに含めることはできませんが、理想的には別のクラスターに収めることができます。 たとえば、上記の例では、「lived-were」、「kingdom-state」などの単語の存在を検索できますが、特定のクラスターにはこのドキュメントを含めません。 また、オブジェクト間の依存関係のグラフを作成し、このグラフを見て、さらに推論を行うことができます（この方法は、たとえばSCTやLingoで機能します）。 特定のデータセットのプロパティを満たすための松葉杖の条件でさえ、全体としてクラスタリングの精度を大幅に向上させることができます。
また、最初はどのようなアルゴリズムについて話しましたか？
デビッドによって記述されたアルゴリズムは、その漸近性や実際の適用可能性ではなく、その単純さによって私の注目を集めました。 通常の人間の論理に基づいて構築されており、他のアルゴリズムと非常に似ています。
まず、グループ化するオブジェクトのセットと、2つのオブジェクトが互いにどの程度似ているかをパーセンテージで表す関数があると想像してください。
F（x、y）= F（y、x）= ...％
-2つのオブジェクトの相関関数。
（実際には、オブジェクトをグループ化するときに人間の脳が通常使用するのはこれだけです。）
次に、平均類似性の概念を紹介します。
G（x、y1、y2、...、yn）= SUM（F（x、yk））/ n
-この関数は、オブジェクトが他のオブジェクトのグループにどれだけ似ているかを示します。
アルゴリズム
最初の（そして長い）ステップでは、便宜上、他のオブジェクトとの平均相関に従って昇順ですべてのオブジェクトをソートする必要があります。 つまり、最初の要素のリストを取得します。その最初の要素は、平均相関が最小の要素であり、逆に、最大の相関を持つ最後の要素です。
次に、作成するクラスターの数と原則を決定する必要があります。 原則は何ですか？ そして、これが私たちのTresholdです-オブジェクトは同じグループ内で一緒になるのに十分類似していると見なされる境界線です。
クラスターは、次のアルゴリズムを使用して作成されます。
1）オブジェクトをソートします。
2）ソートされたリストから最初と最後のオブジェクトを取得します。
•それらの相関が類似の境界よりも大きい場合-これら2つのオブジェクトの最初の要素で1つのクラスターを作成し、残りのオブジェクトからすべてのオブジェクトを見つけます。クラスター全体との平均相関はごみ箱以上になります。
•それらの相関が類似性境界よりも小さい場合、上記と同じ原理に従ってそれらが含まれる要素の2つのクラスターを作成します。
3）オブジェクトが1つ残っている場合-別のクラスターを作成し、そこに押し込みます。 それ以外の場合は、手順1に戻ります。
以上で、最終的にはかなり安定したクラスターが得られます。 このアルゴリズムは、どこにも収まらないオブジェクトに対して個別のクラスターを非常に賢明に作成し、パーセンテージの類似性パラメーターを調整する機能があることは注目に値します。 したがって、これらのオブジェクトは独自の生息地を作成し、この生息地に入り込んで全体像を台無しにするためにゴミ箱を通過しないエラーを許可しません。
また、ロジックを少し掘り下げると、速度を落とすことで精度を非常に簡単に高めることができるという意味で、アルゴリズムが非常に柔軟であることを理解できます。 たとえば、各クラスターに移動可能なごみ箱機能を追加すると、クラスター内のオブジェクトの平均的な接続性が表示されます。 したがって、エラーは減少せず、減少します（ただし、要素をクラスターに挿入すると、このゴミ箱の再計算がトリガーされ、パフォーマンスが低下します）。 逆に、標準のクラスターのコアに似たオブジェクトをクラスターに追加することで、アルゴリズムの精度を低下させ、パフォーマンスを向上させることができます。
まとめ
要約すると、ダビデがなぜ「ファスト」と訳されている「ファスト」という言葉で名前を始めたのか、まだ理解できていません。 もちろん、このアルゴリズムは、各オブジェクトの巨大な相関行列を各オブジェクトの平均値ごとに使用しない限り、高速に呼び出すことはできませんが、相関関数自体の複雑さの可能性があるため、これをすべて計算することは非常に難しい操作です。 理論的には、このアイデアは非常に優れており、実質的に同じです。少量のデータを処理できます。
アルゴリズムの通常の漸近的な複雑さは、おそらく複雑な関数F（x、y）のO（n ^ 3）です。 相関行列を使用すると、O（n ^ 2）の速度とO（n ^ 2）のメモリが得られます。これにより、RAMからのすべての交通渋滞が解消されます。 これらはパイ、親愛なるKhabrachaneです。
次回は、このアルゴリズムのテスト結果についてお話します。
出典： cssanalytics.wordpress.com/2013/11/26/fast-threshold-clustering-algorithm-ftca