6

私は今、Data Mining: Practical machine learning tools and technologies third editionという本を読んでいます。セクション 4.8 クラスタリングでは、 のパフォーマンスを使用k-d treesまたはball trees改善する方法について説明しますk-means algorithm。

すべてのデータ ポイントを使用してボール ツリーを構築した後、すべてのリーフ ノードを検索して、その中のポイントがそれぞれどのクラスタリング センターに近いかを確認します。より高い内部ノードによって表される領域が、単一のクラスター中心のドメイン内に完全に収まることがあります。次に、その子ノードをトラバースする必要はなく、すべての日付ポイントを 1 回で処理できます。

問題は、データ構造とアルゴリズムを実装するときに、内部ノードを参照する領域が単一のクラスター中心に該当するかどうかをどのように判断できるかということです。

2 次元または 3 次元空間では、これは難しくありません。クラスター中心のすべてのペアのすべての中垂線が、内部ノードを参照する領域に出くわすかどうかを確認できます。

しかし、より高次元の空間では、それをどのように認識するのでしょうか? これには一般的な方法論がありますか？

4

2 に答える 2

1

最大距離と最小距離を考慮する必要があります。

他のすべての手段までの空間オブジェクト（たとえば、半径rの球）の最小距離が1つまでの最大距離よりも大きい場合、コンテナ内のすべてのオブジェクトはその平均に属します。なぜなら

maxdist(mean_i, container) < min of all j != i mindist(mean_j, container)

特にコンテナ内のオブジェクトの場合

dist(mean_i, obj_in_container) < min of all j != i dist(mean_j, obj_in_container)

つまり、オブジェクトは意味iに属します。

球と長方形の最小距離と最大距離は、任意の寸法で簡単に計算できます。ただし、より高い次元では、mindistとmaxdistは非常に似たものになり、条件が維持されることはめったにありません。さらに、ツリーの構造が適切であるか（つまり、小さなコンテナー）、構造が不適切である（コンテナーが重複している）場合は、大きな違いが生じます。

kd-treesは、メモリ内の読み取り専用操作に適しています。挿入の場合、パフォーマンスはかなり悪くなります。R*ツリーはここではるかに優れています。さらに、R *ツリーの改善された分割戦略は、他の戦略よりも多くの長方形のボックスを生成するため、効果があります。

于 2012-11-04T09:40:29.557 に答える
0

私は自分で解決策を見つけましたが、私の意見ではあまり良いものではありません。
k 次元空間の場合、2 点の中垂線は超平面です。すべてのクラスタリング中心の中垂線のすべてのペアを計算します。
上記の問題に直面すると、ノードが表示されます。これは、領域を指定できます----空間内の超球です。最初に、超球の中心点 P に最も近いクラスタリング中心を見つけます。次に、2 つのうちの 1 つが上記のものである中心の各ペアのすべての中垂線 (超平面) について繰り返し、点 P と点 P の間のユークリッド距離を計算します。距離が超球の半径よりも小さい場合、超球が中垂線と交差していると推測されます。したがって、この内部ノードには、上記のクラスタリングの中心に属していない可能性のあるデータ ポイントが含まれている可能性があり、反復は中断されます。ブレーク、このノードに含まれるすべてのデータポイントを上記のクラスタリングセンターに一撃で入れても問題ないと言えます。

于 2012-11-04T09:19:41.520 に答える