11

二等分k-meansアルゴリズムを作成する必要がありましたが、アルゴリズムを理解できませんでした。私はk-meansアルゴリズムを知っています。

アルゴリズムを説明できますが、学術用語では説明できません

ありがとう。

4

1 に答える 1

15

アイデアは、ポイントのクラウドを2つの部分に繰り返し分割することです。つまり、ランダムなバイナリツリーを構築します。各分割（2つの子を持つノード）は、クラウドのポイントを2に分割することに対応します。

あなたは点群から始めます。

  • その重心（重心）を計算しますw

  • 雲の点の中からランダムなcLで点を選択します

  • wと比較したときにcLの対称点として点cRを作成します（セグメントcL->wはw->cRと同じです）

  • クラウドのポイントを2つに分けます。cRに最も近いポイントはサブクラウドRに属し、cLに最も近いポイントはサブクラウドLに属します。

  • サブクラウドRとLについて繰り返します

ノート ：

使用したランダムポイントは破棄できます。ただし、すべてのサブケーブルの図心を保持します。

サブクラウドにポイントが1つだけ含まれている場合は停止します。

k個のクラスターが必要な場合は、最初のクラウドのすべてのポイントが含まれるようにk個の重心を取得します。必要に応じて、さらに複雑な作業を行うことができます（雲の分散を最小化するなど）。4つのクラスター（便宜上2の累乗）が必要だとします。次に、雲を2つに分割し、次にそれぞれを切断するだけです。 2つのサブクラウド。8つのクラスターが必要な場合は、これらのサブクラウドを2つに1回カットします。また、16クラスターの場合。

Kが2の累乗ではない（たとえば24）Kクラスターが必要な場合は、2の最も近い劣った累乗を調べます。それは16です。まだ8つのクラスターが不足しています。各「level-16-cluster」は「level-16-subcloud」の重心です。あなたがすることは、8つの「レベル16クラスター」（例えばランダムに）を取り、それらをそれぞれ2つの「子」「レベル32クラスター」に置き換えることです。（これらの2つの子「level-32-clusters」は、親の「level-16-subcloud」に追加される2つの「level-32-subclouds」に対応します）

于 2011-07-29T10:17:04.583 に答える