概要: k-means 問題は、おそらく古典的なクラスタリング問題であり、しばしば Lloyd のアルゴリズム（1957）と同義である。Hartigan のアルゴリズム（1975）は、ほとんどの場合においてより良い結果を与えることが明らかになっている。Telgarsky–Vattani は、典型的な改善が 5\% -- 10\% であることを指摘している。Hartigan の手法のごくわずかな変形によって、さらに別の 2\% -- 5\% の改善が得られることを示す。改善は、どちらか一方でも次元または k が増加すると大きくなる傾向がある。
Hartigan k-meansアルゴリズムの効果的な変種
arXiv cs.LG / 2026/4/24
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- この論文は、古典的なクラスタリング問題であるk-meansについて扱い、標準的なLloydのアルゴリズムと、ほとんどのケースでより良い結果を出すHartiganのアルゴリズムを比較している。
- TelgarskyとVattaniによる先行研究として、Hartigan手法がLloydの方法に対しておおよそ5%〜10%の改善を示すことが引用されている。
- 著者らはHartigan手法のごく些細な変種を提案し、さらに2%〜5%の追加的な改善が得られると述べている。
- 改善効果は、問題の次元数やクラスタ数kが増えるほど大きくなる傾向がある。
- 本件はarXivでの新規アナウンス（v1）として提示されており、研究上の貢献であって産業での本格的な導入を直接意味するものではない。
