私は宿題としてk-meansを実装しようとしています。私のエクササイズシートには、空のセンターに関する次のコメントがあります。
反復中に、クラスターセンターのいずれかにデータポイントが関連付けられていない場合は、ランダムなデータポイントに置き換えます。
それは私を少し混乱させます、最初に私が読んだウィキペディアまたは他の情報源はそれについて全く言及していません。さらに、「データに適切なkを選択する」という問題について読みました。空のクラスターに新しい中心を設定し始めた場合、アルゴリズムはどのように収束するはずです。
空のクラスターを無視すると、30〜40回の反復後に収束します。空のクラスターを無視するのは間違っていますか？
空のクラスターの処理は k-means アルゴリズムの一部ではありませんが、クラスターの品質が向上する可能性があります。収束について言えば、正確に保証されることはなく、ヒューリスティックにのみ保証されるため、収束の基準は反復の最大数を含めることによって拡張されます。
この問題に取り組む戦略に関しては、現在割り当てられている中心までの距離が大きいか小さいため、クラスターの品質に影響を与える可能性があるため、データポイントをランダムに割り当てることはあまり賢明ではありません. この場合のヒューリスティックは、最大のクラスターから最も遠い点を選択し、その空のクラスターを移動してから、空のクラスターがなくなるまで移動することです。
「データに適切な k を選択する」とは、適切な数のクラスターを選択する問題を指します。k-means アルゴリズムはあらかじめ決められた数のクラスター中心で機能するため、最初にその数を選択する必要があります。間違った数を選択すると、データ ポイントをクラスターに分割するのが難しくなったり、クラスターが小さくなり無意味になる可能性があります。
空のクラスターを無視するのが悪い考えかどうかについては、お答えできません。その場合、最初に定義した数よりも少ないクラスター数になる可能性があります。これは、k-means が特定の方法で機能することを期待する人々を混乱させますが、必ずしも悪い考えではありません。
空のクラスターの中心を再配置する場合、限られた回数しか発生しない場合でも、アルゴリズムはおそらく収束します。ただし、頻繁に移動する必要がある場合は、アルゴリズムが終了しないことがあります。
空のクラスターを無視するのではなく、置き換えてください。k-means はアルゴリズムであり、局所的な最小値しか提供できず、空のクラスターは不要な局所的な最小値です。ポイントをランダムなポイントに置き換えても、プログラムは収束します。アルゴリズムの開始時に、最初の K ポイントをランダムに選択することに注意してください。収束できる場合、K-1 点が 1 つのランダムな点で収束できないのはなぜですか? あと数回の反復が必要です。