説明 観測値の集合( x 1 , x 2 , ..., x n が与えられたとき、各観測値はd {\displaystyle d} k 平均クラスタリングは、n個 の観測値をk個 （≤ n ）の集合S = { S 1 , S 2 , ..., S k }に分割し、クラスター内平方和（WCSS）（すなわち分散 ）を最小化することを目的としています。正式には、目的は次の値を求めることです。 1 r g m 私 n S ∑ 私 = 1 k ∑ x ∈ S 私 ‖ x − μ 私 ‖ 2 = 1 r g m 私 n S ∑ 私 = 1 k | S 私 | バラ S 私 {\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}=\mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}} μ i S 私 {\displaystyle S_{i}} μ 私 = 1 | S 私 | ∑ x ∈ S 私 x 、 {\displaystyle {\boldsymbol {\mu _{i}}}={\frac {1}{|S_{i}|}}\sum _{\mathbf {x} \in S_{i}}\mathbf {x} ,} | S 私 | {\displaystyle |S_{i}|} S 私 {\displaystyle S_{i}} ‖ ⋅ ‖ {\displaystyle \|\cdot \|} L2 ノルムです。これは、 1 r g m 私 n S ∑ 私 = 1 k 1 | S 私 | ∑ x 、 y ∈ S 私 ‖ x − y ‖ 2 {\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\,{\frac {1}{|S_{i}|}}\,\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \右\|^{2}} | S 私 | ∑ x ∈ S 私 ‖ x − μ 私 ‖ 2 = 1 2 ∑ x 、 y ∈ S 私 ‖ x − y ‖ 2 {\textstyle |S_{i}|\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\frac {1}{2}}\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}} 総分散は一定であるため、これは異なる クラスター内の点間の二乗偏差の合計（クラスター間二乗和、BCSS）を最大化することと同等です。[ 1 ] 総分散の法則 にも関連しています。
歴史 「 k -means」という用語は、1967年にジェームズ・マックイーンによって初めて使用されましたが[ 2 ] ヒューゴ・スタインハウスに遡ります [ 3 ]。 ベル研究所のスチュアート・ロイドによって パルス符号変調 の手法として初めて提案されましたが、1982年まで学術論文として発表されませんでした[ 4 ]。 [ 5 ] 。
ベル研究所ホルムデル複合施設の空撮写真。スチュアート・ロイドはこの場所で、信号処理とベクトル量子化のための初期のk平均クラスタリング手法を開発した。 k-meansアルゴリズムの初期の応用例は、主に信号処理とデータ圧縮、特に ベクトル量子化 の分野で見られました。ベル研究所 でのロイドの研究は、限られた離散値のセットを使用してアナログ信号を表現することに焦点を当てており、クラスタリングを使用して信号品質を維持しながら必要なデータ量を削減しました。[ 4 ]
計算能力の向上に伴い、k-meansクラスタリングは、その単純さと計算効率の高さから、パターン認識や統計的分類に広く用いられるようになった。その後、大規模データセットを扱う初期の 機械学習 やデータ分析タスクにも採用された。[ 6 ]
広く利用されているにもかかわらず、初期重心位置への感度や非球形クラスターの処理の難しさといった限界が早期に認識され、改良されたクラスタリング手法や初期化技術の開発が促された。
それ以来、k-means の多くの拡張が開発され、元のアルゴリズムの限界に対処してきました。これには、データ点がさまざまなメンバーシップの度合いで複数のクラスターに属することを可能にするファジー c-means や、カーネル関数を使用して非線形分離可能なクラスターを識別するカーネル k-means などの方法が含まれます。[ 6 ]
アルゴリズム
k 平均法）k 平均法の収束最も一般的なアルゴリズムは、反復的な改良手法を使用します。広く普及しているため、「k -meansアルゴリズム」と呼ばれることが多く、特にコンピュータサイエンスの分野では ロイドのアルゴリズム とも呼ばれます。より高速な代替手法が存在するため、「ナイーブk -means」と呼ばれることもあります。[ 7 ]
初期セットのk m 1 (1) 、 ...、m k (1) [ 8 ]
割り当て手順：各観測値を、最も近い平均値（重心）を持つクラスター、すなわち最小二乗 ユークリッド距離 を持つクラスターに割り当てます。[ 9 ] （数学的には、これは平均値によって生成されたボロノイ図 に従って観測値を分割することを意味します。）S 私 （ t ） = { x p : ‖ x p − m 私 （ t ） ‖ 2 ≤ ‖ x p − m j （ t ） ‖ 2 ∀ j 、 1 ≤ j ≤ k } 、 {\displaystyle S_{i}^{(t)}=\left\{x_{p}:\left\|x_{p}-m_{i}^{(t)}\right\|^{2}\leq \left\|x_{p}-m_{j}^{(t)}\right\|^{2}\ \forall j,1\leq j\leq k\right\},} x p {\displaystyle x_{p}} S （ t ） {\displaystyle S^{(t)}} 更新手順 ：各クラスターに割り当てられた観測値の平均値（重心 ）を再計算します。これは再適合とも呼ばれます。m 私 （ t + 1 ） = 1 | S 私 （ t ） | ∑ x j ∈ S 私 （ t ） x j {\displaystyle m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}} k -means法の目的関数はWCSS（クラスター内平方和）です。各反復後、WCSSは単調減少し、非負の単調減少数列が得られます。これにより、k -means法は常に収束しますが、必ずしも大域的最適解に収束するとは限りません。
アルゴリズムは、割り当てが変化しなくなったとき、または同等に、WCSSが安定したときに収束した。アルゴリズムは最適なクラスタ割り当てを見つけることを保証するものではない。[ 10 ]
このアルゴリズムは、距離に基づいてオブジェクトを最も近いクラスターに割り当てるものとして説明されることが多い。(二乗)ユークリッド距離以外の距離関数を使用すると、アルゴリズムが収束しない可能性がある。球面k 平均法やk メドイド法 など、k 平均法のさまざまな改良版が提案されており、他の距離尺度の使用を可能にしている。
擬似コード 以下の擬似コードは、標準的なk 平均クラスタリングアルゴリズムの実装の概要を示しています。重心の初期化、点と重心間の距離尺度、および新しい重心の計算は設計上の選択であり、実装によって異なります。この擬似コード例では、distance()指定された点間の距離を返します。
関数 kmeans(k, points)は // 重心を初期化する 重心 ← k個の開始重心のリスト 収束した ← 偽 間 、 // 空のクラスターを作成する クラスター ← k 個の空リストのリスト // 各点を最も近い重心に割り当てる i ← 0から length(points) - 1まで繰り返す ポイント ← ポイント[i] 最も近いインデックス ← 0 minDistance ← distance(point, centroids[0]) から k - 1まで繰り返す 。d ← distance (point, centroids[j]) d < minDistance の場合 、 最小距離 ← d 最も近いインデックス ← j clusters[closestIndex] .append (point) // 各クラスターの平均として重心を再計算する newCentroids ← 空のリスト i ← 0から k - 1まで 、newCentroid ← calculateCentroid (clusters[i])を実行します。 newCentroid ) // 収束性を確認する もし newCentroids == centroidsならば 収束した ← 真 それ以外 重心 ← 新しい重心 を返す
初期化方法 一般的に使用される初期化方法は、Forgy と Random Partition です。[ 11 ] k 個の 観測値をランダムに選択し、これらを初期平均として使用します。Random Partition 法は、まず各観測値にランダムにクラスタを割り当て、次に更新ステップに進み、クラスタにランダムに割り当てられた点の重心を初期平均として計算します。Forgy 法は初期平均を広げる傾向がありますが、Random Partition 法は、データセットの中心付近にすべて配置します。Hamerly らによると、[ 11 ] Random Partition 法は、 k 調和平均やファジーk 平均などのアルゴリズムに一般的に好ましいです。期待値最大化および標準k 平均アルゴリズムには、初期化の Forgy 法が好ましいです。しかし、 Celebiらによる包括的な研究[ 12 ] [ 13 ] k -means++は
このアルゴリズムは、グローバル最適解への収束を保証するものではありません。結果は初期クラスタに依存する可能性があります。このアルゴリズムは通常高速であるため、異なる開始条件で複数回実行するのが一般的です。ただし、最悪の場合のパフォーマンスは遅くなる可能性があります。特に、2 次元であっても、特定の点集合は指数時間、つまり2 Ω( n ) で収束します。[ 14 ] これらの点集合は実際には発生しないようです。これは、 k -means の 平滑化された 実行時間が多項式であるという事実によって裏付けられています。[ 15 ]
「割り当て」ステップは「期待値ステップ」と呼ばれ、「更新ステップ」は最大化ステップであるため、このアルゴリズムは一般化 期待値最大化アルゴリズム の変種となる。
複雑 d次元の観測データに対する k 平均クラスタリング問題の最適解を見つけるには、次の手順が必要です。
そのため、上記で示したロイドのアルゴリズムなど、さまざまなヒューリスティックアルゴリズムが一般的に使用される。
ロイドのアルゴリズム（およびほとんどの変種）の実行時間はO （ n k d 私 ） {\displaystyle O(nkdi)} 10 ] [ 20 ]ここ で
nは d 次元ベクトルの数（クラスタリング対象）です。kは クラスターの数i は 収束までに必要な反復回数です。クラスタリング構造を持つデータの場合、収束までの反復回数は少ないことが多く、最初の十数回の反復後も結果はわずかにしか改善されません。そのため、ロイドのアルゴリズムは、収束まで実行した場合、最悪の場合 には超多項式となるものの、実際には「線形」複雑性を持つとみなされることが多いのです。[ 21 ]
最悪の場合、ロイドのアルゴリズムは私 = 2 Ω （ n ） {\displaystyle i=2^{\Omega ({\sqrt {n}})}} 超多項式に なります。[ 21 ] ロイドのk 平均法アルゴリズムは、多項式平滑化実行時間を持つ。[ 15 ] では、任意のn 個の点の集合に対して、[ 0 、 1 ] d {\displaystyle [0,1]^{d}} 各点が平均0 、分散 の正規分布によって独立に摂動される場合σ 2 {\displaystyle \sigma ^{2}} すると、 k -meansアルゴリズムの期待実行時間は以下によって制限される。O （ n 34 k 34 d 8 ログ 4 （ n ） / σ 6 ） {\displaystyle O(n^{34}k^{34}d^{8}\log ^{4}(n)/\sigma ^{6})} これはn 、k 、d の多項式であり、1 / σ {\displaystyle 1/\sigma } 単純なケースでは、より良い上限が証明されています。たとえば、k -meansアルゴリズムの実行時間は次のように制限されることが示されています。O （ d n 4 M 2 ） {\displaystyle O(dn^{4}M^{2})} 整数格子 内のn 個の点について{ 1 、 … 、 M } d {\displaystyle \{1,\dots ,M\}^{d}} 22 ] ロイドのアルゴリズムはこの問題に対する標準的なアプローチです。しかし、k 個のクラスタ中心とn 個の データ点の間の距離を計算するために多くの処理時間を費やします。点は通常、数回の反復後に同じクラスタに留まるため、この作業の多くは不要であり、単純な実装は非常に非効率的です。一部の実装では、キャッシングと三角不等式を使用して境界を作成し、ロイドのアルゴリズムを高速化します。[ 23 ] [ 10 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ]
最適なクラスター数 k -meansクラスタリングにおいて最適なクラスタ数（k ）を見つけることは、クラスタリング結果が有意義で有用であることを保証するための重要なステップです。[ 28 ]
エルボー法（クラスタリング） ：この方法は、説明された変動をクラスター数の関数としてプロットし、曲線のエルボーをクラスター数として選択します。[ 29 ] [ 30 ] シルエット（クラスタリング） ：シルエット分析はクラスタリングの品質を測定し、結果として得られるクラスター間の分離距離についての洞察を提供します。[ 31 ] ギャップ統計量 ：ギャップ統計量は、k の異なる値におけるクラスター内変動の合計を、データのヌル参照分布の下での期待値と比較します。[ 32 ] デイビス・ボールディン指数 ：デイビス・ボールディン指数は、クラスター間の分離の度合いを示す指標です。[ 33 ] カリンスキー・ハラバス指数 ：この指数は、クラスターのコンパクトさと分離度に基づいてクラスターを評価します。この指数は、クラスター間の分散とクラスター内の分散の比率を使用して計算され、値が高いほど、より明確に定義されたクラスターであることを示します。[ 34 ] ランド指数 ：これは、同じクラスターまたは異なるクラスターに正しく割り当てられた要素のペアの両方を考慮して、2 つのクラスター間の一致の割合を計算します。[ 35 ] [ 36 ]
Hartigan とWongの方法[ 10 ] k -meansアルゴリズムの変種を提供します。この方法は、目的関数が改善される限り、サンプルを別のクラスターに再配置することを反復的に試みる局所探索 です。目的関数を改善しながらサンプルを別のクラスターに再配置できない場合、この方法は停止します（局所最小値に到達します）。古典的なk -meansと同様に、このアプローチは最終的な解が必ずしもグローバル最適解であることを保証するものではないため、ヒューリスティックなままです。
させてφ （ S j ） {\displaystyle \varphi (S_{j})} S j {\displaystyle S_{j}} ∑ x ∈ S j （ x − μ j ） 2 {\textstyle \sum _{x\in S_{j}}(x-\mu _{j})^{2}} μ j {\displaystyle \mu _{j}}
割り当て手順 ハーティガンとウォンの方法は、まず点をランダムなクラスターに分割することから始まる。{ S j } j ∈ { 1 、 ⋯ k } {\displaystyle \{S_{j}\}_{j\in \{1,\cdots k\}}} 更新手順 次に決定しますn 、 m ∈ { 1 、 … 、 k } {\displaystyle n,m\in \{1,\ldots ,k\}} x ∈ S n {\displaystyle x\in S_{n}} Δ （ m 、 n 、 x ） = φ （ S n ） + φ （ S m ） − φ （ S n ∖ { x } ） − φ （ S m ∪ { x } ） 。 {\displaystyle \Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\setminus \{x\})-\varphi (S_{m}\cup \{x\}).} x 、 n 、 m {\displaystyle x,n,m} x {\displaystyle x} S n {\displaystyle S_{n}} S m {\displaystyle S_{m}} 終了 アルゴリズムは一度終了しますΔ （ m 、 n 、 x ） {\displaystyle \Delta (m,n,x)} x 、 n 、 m {\displaystyle x,n,m} 異なる移動受容戦略を用いることができる。第一改善 戦略では、改善する移動であればどれでも適用できるが、最良改善 戦略では、可能なすべての移動が繰り返しテストされ、各反復で最良のものだけが適用される。前者のアプローチは速度を優先するが、後者のアプローチは一般的に追加の計算時間を犠牲にして解の質を優先する。Δ {\displaystyle \Delta } [ 46 ]
Δ （ x 、 n 、 m ） = ∣ S n ∣ ∣ S n ∣ − 1 ⋅ ‖ μ n − x ‖ 2 − ∣ S m ∣ ∣ S m ∣ + 1 ⋅ ‖ μ m − x ‖ 2 。 {\displaystyle \Delta (x,n,m)={\frac {\mid S_{n}\mid }{\mid S_{n}\mid -1}}\cdot \lVert \mu _{n}-x\rVert ^{2}-{\frac {\mid S_{m}\mid }{\mid S_{m}\mid +1}}\cdot \lVert \mu _{m}-x\rVert ^{2}.}
古典的なk 平均法アルゴリズムとその変種は、次のように定義される最小二乗和クラスタリング問題の局所的最小値にのみ収束することが知られています。 1 r g m 私 n S ∑ 私 = 1 k ∑ x ∈ S 私 ‖ x − μ 私 ‖ 2 。 {\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}.} 分岐限定法 と半正定値計画法 に基づくグローバル最適化アルゴリズムが、最大 4,177 個のエンティティと 20,531 個の特徴を持つデータセットに対して「証明された最適」解を生成しています。[ 47 ] 予想どおり、基となる最適化問題のNP 困難性 のため、 k -meansの最適アルゴリズムの計算時間は、このサイズを超えると急速に増加します。小規模および中規模の最適解は、他のヒューリスティックの品質を評価するためのベンチマーク ツールとして依然として価値があります。最適性の保証なしに、制御された計算時間内で高品質の局所最小値を見つけるために、他の研究では、メタヒューリスティクス やその他のグローバル最適化 手法、たとえば、増分アプローチと凸最適化に基づくもの[ 48 ] [ 49 ] 反復局所探索 ）、可変近傍探索 [ 50 ] 遺伝的アルゴリズム [ 51 ] [ 52 ] [ 52 ] 。
アプリケーション k平均クラスタリングは、特に ロイドのアルゴリズム などのヒューリスティックを用いる場合、大規模なデータセットにも比較的容易に適用できます。市場セグメンテーション 、コンピュータビジョン 、天文学 など、多くの分野で成功裏に活用されています。また、他のアルゴリズムの前処理ステップとして、例えば初期構成を見つけるためによく用いられます。
生物学 クラスター化されたゲノム共検出データのヒートマップ。各行はゲノムウィンドウ、各列は核プロファイルを表し、白は検出された領域、黒は検出されなかった領域を示します。クラスター化された配置により、類似した共検出パターンを持つ領域のグループが明らかになり、クラスタリングによって協調的なゲノム挙動を特定できることが示されています。 生物学的応用では、標準的なk -means クラスタリングの限界は、実験データの構造をよりよく反映するように使用する距離尺度と目的関数を調整することによって対処されることが多い。ユークリッド距離 や分散に基づくクラスタ散布尺度に頼るのではなく、 k-means でゲノムデータセットを分析する際には、ジャッカード指数 などの代替類似度指標が使用されることがある。このような状況では、クラスタリングは距離行列上で直接実行され、算術平均の代わりにメドイド (クラスタ内の他のすべての点との平均距離が最小となる代表的なデータ点) がクラスタ中心として選択されることがある。これにより、クラスタリング手法は、従来のユークリッド分析では十分に表現されない、共有ゲノム特徴や共起のパターンを捉えることができる。[ 55 ]
クラスタリングは、遺伝子発現プロファイルやゲノム相互作用マトリックスなどの高次元データセットのパターンを特定するために、生物学的データ解析で広く使用されています。k-meansクラスタリングなどの手法は、 類似性に基づいて観測値をグループに分割し、研究者が複雑なデータセットの構造を検出できるようにします。遺伝子発現研究では、クラスタリングは、類似した発現プロファイルを持つ遺伝子をグループ化するためによく使用され、多くの場合、共調節遺伝子と根底にある生物学的相互作用を明らかにします。[ 56 ]
遺伝子発現解析に加えて、クラスタリング手法はクロマチン相互作用データに適用され、協調的な活性領域を特定します。ジャッカード指数などの類似度尺度は、観測間の共通特徴を定量化するために使用でき、結果として得られる距離行列のクラスタリングにより、ゲノム内の構造的組織が明らかになります。これらのパターンは、一般的にヒートマップを使用して視覚化され、クラスタリングされた領域は相互作用または共分離のドメインに対応し、ゲノムの制御組織に関する洞察を提供します。[ 55 ] [ 55 ]
クラスタリング法は、複雑なデータセットから生物学的に意味のある構造を明らかにするための実用的な方法を提供する。ゲノム検出、発現、または相互作用の類似したパターンを持つ観測をグループ化することにより、これらの技術は機能的関係、核内の空間的組織、および制御挙動を明らかにすることができる。多くのアプリケーションでは、結果として得られるクラスターは明確な生物学的状態または構造ドメインに対応しており、k-meansクラスタリングの幅広い適用性をさらに示している。[ 56 ]
ベクトル量子化 ベクトル量子化は 、信号処理やコンピュータグラフィックスで一般的に用いられる手法で、画像のカラーパレットを k個 の固定色に削減するものです。ベクトル量子化を 実現する一般的な方法の一つに、 k 平均クラスタリングがあります。この方法では、画像の色空間にk 平均法を適用して、画像をk個のクラスターに分割します。各クラスターは、画像内の異なる色を表します。この手法は、類似した色を識別してグループ化するのに役立つ画像セグメンテーションタスクにおいて特に有効です。
赤と緑のチャンネルのみを含むサンプル画像（説明用） 上記画像に含まれる色をk 平均法を用いてボロノイセルにベクトル量子化する。 例：コンピュータグラフィックス の分野では、k平均クラスタリングは画像圧縮における 色量子化 によく用いられます。画像を表現するために使用する色の数を減らすことで、視覚的な品質を大きく損なうことなくファイルサイズを大幅に削減できます。例えば、数百万色を含む画像を考えてみましょう。kを小さい値に設定してk 平均 クラスタリングを適用することで、より限定されたカラーパレット を使用して画像を表現でき、結果としてストレージ容量と帯域幅を節約できる圧縮版が得られます。ベクトル量子化の他の用途としては、非ランダムサンプリング があります。k平均法を用いることで、大規模なデータセットから k個 の異なるが典型的なオブジェクトを簡単に選択し、さらに分析することができます。
クラスター分析 機械学習における基本的なタスクである クラスタ分析は 、一連のデータポイントを類似性に基づいてクラスターにグループ化するものです。k平均 クラスタリングは、データをk個のクラスターに分割するために用いられる一般的なアルゴリズムであり、各クラスターはその重心によって表されます。
しかしながら、純粋なk 平均法アルゴリズムは柔軟性に乏しく、そのため用途が限られています（上記のようなベクトル量子化が実際に望ましいユースケースである場合を除く）。特に、パラメータk は、外部制約によって与えられていない場合、選択が難しいことが知られています（前述のとおり）。また、任意の距離関数や非数値データには適用できないという制約もあります。これらのユースケースにおいては、他の多くのアルゴリズムの方が優れています。
例：マーケティングにおいて、k平均クラスタリングは 市場セグメンテーション によく用いられます。これは、類似した特性や行動を持つ顧客をグループ化する手法です。例えば、小売企業はk 平均クラスタリングを用いて、購買行動、人口統計、地理的位置などの要素に基づいて顧客層を明確なグループに分割することができます。こうして分割された顧客セグメントに対して、それぞれに合わせたマーケティング戦略や製品を提供することで、売上と顧客満足度を最大化することが可能になります。
特徴学習 k -meansクラスタリングは、(半 )教師あり学習 または教師なし学習のいずれにおいても、 特徴学習 (または辞書学習 )ステップとして使用されてきました。[ 57 ] k -meansクラスタリング表現をトレーニングすることです。次に、任意の入力データを新しい特徴空間に投影するために、データと重心位置の閾値付き行列積などの「エンコーディング」関数が、データから各重心までの距離を計算するか、単に最も近い重心の指示関数[ 57 ] [ 58 ] [ 59 ] ガウスRBFで変換すると、 放射基底関数ネットワーク の隠れ層が得られます。[ 60 ]
このk -meansの使用は、 NLP （特に固有表現認識 ）[ 61 ] コンピュータビジョン における半教師あり学習のために、単純な線形分類器 とうまく組み合わされてきた。物体認識タスクでは、オートエンコーダ や制限付きボルツマンマシン などのより高度な特徴学習アプローチと同等の性能を示すことがわかった。[ 59 ] [ 57 ]
例：自然言語処理 （NLP）では、k -meansクラスタリングは 、固有表現認識 （NER）などの半教師あり学習タスクにおいて、単純な線形分類器と統合されています。まず、ラベルなしテキストデータをk -meansを用いてクラスタリングすることで、 NERモデル のパフォーマンスを向上させるための意味のある特徴を抽出できます。例えば、k -meansクラスタリングを適用して、入力テキスト内で頻繁に共起する単語やフレーズのクラスターを特定し、それをNERモデルのトレーニング用の特徴として使用できます。このアプローチは、オートエンコーダ や制限付きボルツマンマシン などのより複雑な特徴学習 手法と同等のパフォーマンスを達成できることが示されていますが、ラベル付きデータに対する要求はより大きくなります。
ビッグデータ並列化 OpenMP、OpenACC、および逐次処理を用いた場合の、データセットサイズが増加するにつれてのk平均クラスタリングアルゴリズムの実行時間。 標準的なロイドのアルゴリズム は本質的に逐次処理です。実効的な時間計算量 はO(nkdi)であり、データ点数(n)または次元数(d)が増加するにつれてボトルネックとなります。ソーシャルネットワークのような大規模な多次元データセットで使用する場合、これは非効率的になる可能性があります。そのため、マルチコアプロセッサ、GPU、分散クラスタにワークロードを分散させるための様々な並列化戦略が開発されています。
共有メモリモデル（OpenMP ）： このアプローチでは、プロセスの再割り当てステップの作業をCPU スレッド間で分割します。これらのスレッドは、重心までの距離を独立して計算します。各スレッドからの部分的な合計とカウントが集約され、次の反復のための新しい重心が計算されます。[ 62 ] GPU並列化（OpenACC ）： OpenMP実装とは異なり、OpenACCプログラムの並列ディレクティブは、最初ではなく必要な各ステップで呼び出されます。これにより、 GPUのSIMT （単一命令複数スレッド）アーキテクチャを利用して、数千の距離計算を同時に実行できます。[ 62 ] 並列処理版では、いずれの場合も大規模データセットにおいて効率が大幅に向上することがわかります。この高速化は、 GPU アーキテクチャの超並列性により、OpenACCの実装において特に顕著です。
天文学 恒星を光度とスペクトル型でプロットしたヘルツシュプルング・ラッセル図。これは、k平均法による恒星分類で使用される特徴データの一種である。 APOGEEやガイアカタログのような現代の天文調査では、数百万個の星の分光データと測光データが収集されるため、大規模な手動分類は非現実的です。K平均 クラスタリングは、光度、温度、色、化学組成などの特性に基づいて、異なる恒星集団を自動的に識別するためにこのデータに適用されています。[ 63 ]
主要な応用例の 1 つは、化学標識による恒星集団の識別です。同じ星団で一緒に形成された星は似たような化学組成を共有しているため、存在量データにクラスタリングアルゴリズムを適用することで、星が銀河全体に広がった後でもこれらのグループを復元できます。APOGEE赤外線スペクトルにk -means を使用した研究では、最大 13 元素の存在量を測定し、既知の星団を周囲のフィールド星からうまく区別しました。[ 63 ]
K -meansは次元削減技術と組み合わされて、観測された光の特性に基づいて恒星、銀河、クエーサーを分離することで、ラベル付けされていない多数のサーベイ対象を分類するためにも用いられてきました。確認された例からのラベルは、近くのクラスターメンバーに伝播されます。このアプローチは、必要なラベル付き例がはるかに少ないにもかかわらず、完全教師あり法に匹敵する精度を達成しており、現代のスカイサーベイの規模に非常に適しています。[ 64 ]
クラスタリングアルゴリズムでグローバル最適解を見つけるには、適切な初期化が非常に重要です。k平均クラスタリングではランダム初期化がよく使用されますが、これはクラスタの品質低下につながる可能性があります。[ 65 ] k-means++ 初期化アルゴリズムが開発されました。[ 65 ] [ 65 ]
k -means++ アルゴリズムは、初期クラスタ中心を広げることで機能します。データセットから最初の中心を均一にランダムに選択します。後続の各中心は確率的に選択され、点が選択される確率は、全体のエラーへの寄与に比例します。[ 65 ] [ 65 ]
k-meansにおける初期化ラウンド数とオーバーサンプリング係数（ℓ）がクラスタリングコストに及ぼす影響。グラフは、最初の数回のラウンドでクラスタリング品質が急速に向上し、ラウンド数が増えるにつれて効果が逓減することを示しています。 標準的なk-means++ の主な欠点は、その本質的に逐次的な性質です。k 個の初期中心を見つけるには、アルゴリズムはデータに対して k 回の個別のパスを実行する必要があります。これは、各新しい中心の選択が以前の選択に依存するためです。[ 66 ] [ 66 ]
これらの制限を克服するために、研究者らは k-means|| というk-means++ の並列バージョンを開発しました。[ 66 ] [ 66 ] [ 66 ] [ 66 ] これらの中心には、それらに近い点の数に基づいて重みが割り当てられ、多くの場合標準のk-means++ を使用して再クラスタリングされ、最終的なセットを正確に k 個の中心に削減します。[ 66 ]
他のアルゴリズムとの関連性
ガウス混合モデル k -meansクラスタリングの遅い「標準アルゴリズム」と、それに関連する期待値最大化アルゴリズム は、ガウス混合モデルの特殊なケースであり、具体的には、すべての共分散を対角化、等しく、無限小の小さな分散を持つように固定した場合の極限ケースです。[ 67 ] : k -meansクラスタリングと「ハード」ガウス混合モデリングの特殊なケースとの別の等価性を示すこともできます。[ 68 ] : これは、 k -meansを計算するためにガウス混合モデリング を k -meansの一般化として解釈できることを意味するだけです。逆に、困難なデータでガウス混合モデリングの開始点を見つけるためにk -meansクラスタリングを使用することが提案されています。[ 67 ] :
k -SVDk -meansアルゴリズムのもう1つの一般化はk -SVDアルゴリズムであり、これはデータポイントを「コードブックベクトル」の疎な線形結合として推定します。k - meansは、重み1の単一のコードブックベクトルを使用する特殊なケースに対応します。[ 69 ]
主成分分析 クラスタ指標によって指定されるk [ 70 ] [ 71 ] k -means は球形 (ボール状) のクラスタを記述します。データに 2 つのクラスタがある場合、2 つの重心を結ぶ線が最適な 1 次元投影方向であり、これは最初の PCA 方向でもあります。重心で線を切断すると、クラスタが分離されます (これは離散クラスタ指標の連続緩和です)。データに 3 つのクラスタがある場合、3 つのクラスタ重心によって張られる 2 次元平面が最適な 2 次元投影です。この平面は、最初の 2 つの PCA 次元によっても定義されます。十分に分離されたクラスタは、効果的にボール状のクラスタによってモデル化され、したがってk- means によって発見されます。ボール状でないクラスタは、近接している場合に分離するのが困難です。たとえば、空間で絡み合った 2 つの半月状のクラスタは、PCA 部分空間に投影するとうまく分離されません。k -means はこのデータではうまく機能するとは期待できない。[ 72 ] [ 73 ]
平均シフトクラスタリング 基本的な平均シフトクラスタリングアルゴリズムは、入力データセットと同じサイズのデータポイントのセットを維持します。最初は、このセットは入力セットからコピーされます。次に、すべてのポイントは、周囲のポイントの平均に向かって反復的に移動します。対照的に、k -means は、クラスタのセットをk 個のクラスタに制限します。これは通常、入力データセットのポイント数よりもはるかに少なく、重心として、前のクラスタ内のすべてのポイントの平均を使用します (たとえば、各更新ポイントのボロノイ分割内)。k-means に似た平均シフトアルゴリズムは、 尤度平均シフト と呼ばれ、置換されるポイントのセットを、変更セットから指定された距離内にある入力セット内のすべてのポイントの平均で置き換えます。[ 74 ] k -meansに対する平均シフトクラスタリングの利点は、クラスタ数を決定するパラメータがないため、データセット内の任意の数のクラスタを検出できることです。平均シフトはk -meansよりもはるかに遅くなる可能性があり、帯域幅パラメータの選択が必要です。
双方向フィルタリング k -means は、入力データセットの順序が重要ではないことを暗黙のうちに仮定しています。バイラテラルフィルタは、k -means や平均シフト と同様に、反復的に平均値に置き換えられるデータポイントのセットを保持します。ただし、バイラテラルフィルタは、(カーネル重み付き) 平均の計算を、入力データの順序が近いポイントのみを含むように制限します。[ 74 ]
同様の問題 二乗誤差を最小化するクラスタ関数のセットには、k- メドイド重心 の代わりにメドイドを 使用します。
ソフトウェア実装 アルゴリズムの実装によってパフォーマンスに違いがあり、テストデータセットで最速のものは10秒で完了し、最遅のものは25,988秒（約7時間）かかりました。[ 1 ]
以下の実装は、フリー／オープンソースソフトウェア ライセンスの下で提供されており、ソースコードは公開されています。
Accord.NETには、 k -means、k -means++、k -modesのC#実装が含まれています。ALGLIBには、 k -meansおよびk -means++の並列化されたC++およびC#実装が含まれています。AOSPには、 k -means法のJava実装が含まれています。CrimeStatは 2つの空間k 平均法アルゴリズムを実装しており、そのうちの1つではユーザーが開始位置を定義できます。ELKIには、 k -means（LloydとMacQueenの反復法、および k -means++初期化などのさまざまな初期化方法を含む）と、より高度なクラスタリングアルゴリズムが多数含まれています。Smileには、 k -meansをはじめとする様々なアルゴリズムと、結果の可視化機能（Java、Kotlin、Scalaに対応）が含まれています。 Juliaには 、JuliaStatsクラスタリングパッケージにk 平均法の実装が含まれています。KNIMEには、 k -means法とk -medoids法のためのノードが含まれています。Mahoutには MapReduce ベースのk -meansが含まれています。mlpackには、 k -means法のC++実装が含まれています。Octaveには k -meansが含まれています。OpenCVには k -means法の実装が含まれています。Orangeには、 k の自動選択とクラスタシルエットスコアリング機能を備えたk 平均クラスタリングのコンポーネントが含まれています。PSPPには k -meansが含まれており、QUICK CLUSTERコマンドはデータセットに対してk -meansクラスタリングを実行します。 R には3つのk -meansのバリエーションが含まれています。SciPy とscikit-learnには、 複数のk -means実装が含まれています。Spark MLlibは、分散型k 平均法アルゴリズムを実装しています。Torchには、 k 平均クラスタリングを提供するunsup パッケージが含まれています。Wekaには k -meansとx -meansが含まれています。
専有 以下の実装は独自の ライセンス条件に基づいて提供されており、ソースコードは公開されていない場合があります。
参考文献 1 2 Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "実行時評価の（黒魔術）：アルゴリズムを比較しているのか、実装を比較しているのか？". Knowledge and Information Systems . 52 (2): 341– 378. doi : 10.1007/s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 . ↑ MacQueen, JB (1967). Some Methods for classification and Analysis of Multivariate Observations . Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1. University of California Press. pp. 281–297 . MR 0214227 . Zbl 0214.46201 . Retrieved 2009-04-07 . ↑ シュタインハウス、ヒューゴ (1957)。 「パーティーにおける軍団資材の部門」。 ブル。アカド。ポロン。科学。 （フランス語で）。 4 (12): 801–804 . MR 0090073 。 Zbl 0079.16403 。 1 2 Lloyd, Stuart P. (1957). 「PCMにおける最小二乗量子化」 ベル電話研究所論文 。 Lloyd, Stuart P. (1982). "Least squares quantization in PCM" (PDF) . IEEE Transactions on Information Theory . 28 (2): 129– 137. Bibcode : 1982ITIT...28..129L . CiteSeerX 10.1.1.131.1338 . doi : 10.1109/TIT.1982.1056489 . S2CID 10833328 . 2009年4月15日 取得 . ↑ Forgy, Edward W. (1965). "多変量データのクラスター分析：分類の効率性と解釈可能性". Biometrics . 21 (3): 768–769 . JSTOR 2528559 . 1 2 Jain, AK (2010). "データクラスタリング: k-means から 50 年". IEEE Transactions on Pattern Analysis and Machine Intelligence . 31 (11): 651– 666. Bibcode : 2010PaReL..31..651J . doi : 10.1016/j.patrec.2009.09.011 . ↑ Pelleg, Dan; Moore, Andrew (1999). "幾何学的推論による正確な k 平均アルゴリズムの高速化" . 第5回ACM SIGKDD国際知識発見・データマイニング会議議事録 . 米国カリフォルニア州サンディエゴ: ACM Press. pp. 277–281 . doi : 10.1145/312129.312248 . ISBN 9781581131437 . S2CID 13907420 . ↑ MacKay, David (2003). 「第20章 推論タスクの例：クラスタリング」 （PDF） . 情報理論、推論、学習アルゴリズム . Cambridge University Press. pp. 284–292 . ISBN 978-0-521-64298-9 . MR 2012999 . ↑ 平方根は単調関数であるため、これは最小ユークリッド距離の割り当てでもあります。 1 2 3 4 5 Hartigan, JA; Wong, MA (1979). "アルゴリズム AS 136: k -Means クラスタリング アルゴリズム". Journal of the Royal Statistical Society, Series C . 28 (1): 100– 108. JSTOR 2346830 . 1 2 Hamerly, Greg; Elkan, Charles (2002). " より良いクラスタリングを見つける k -meansアルゴリズムの代替案" (PDF) . 第11回国際情報知識管理会議 (CIKM) 議事録 。 ↑ Celebi, ME; Kingravi, HA; Vela, PA (2013). " k -meansクラスタリングアルゴリズムの効率的な初期化方法の比較研究". Expert Systems with Applications . 40 (1): 200–210 . arXiv : 1209.1960 . doi : 10.1016/j.eswa.2012.07.021 . S2CID 6954668 . ↑ Bradley, Paul S.; Fayyad, Usama M. (1998). " k -Meansクラスタリングの初期点の改良 ". 第15回国際機械学習会議議事録 。 ↑ Vattani, A. (2011). "k-meansは平面上でも指数関数的に多くの反復を必要とする" (PDF) . Discrete and Computational Geometry . 45 (4): 596– 616. doi : 10.1007/s00454-011-9340-1 . S2CID 42683406 . 1 2 Arthur, David; Manthey, B.; Roeglin, H. (2009). "k-means は多項式平滑化複雑度を持つ". 第 50 回コンピュータサイエンス基礎シンポジウム (FOCS) 議事録 . arXiv : 0904.1113 . ↑ Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). "NP-hardness of Euclidean sum-of-squares clustering" . Machine Learning . 75 (2): 245– 249. Bibcode : 2009MLear..75..245A . doi : 10.1007/s10994-009-5103-0 . ↑ Dasgupta, S.; Freund, Y. (2009年7月). "ベクトル量子化のためのランダム射影木". IEEE Transactions on Information Theory . 55 (7): 3229–42 . arXiv : 0805.1390 . Bibcode : 2009ITIT...55.3229D . doi : 10.1109/TIT.2009.2021326 . S2CID 666114 . ↑ Mahajan, Meena ; Nimbhorkar, Prajakta; Varadarajan, Kasturi (2009). "平面k平均法問題はNP困難である". WALCOM: Algorithms and Computation . Lecture Notes in Computer Science. Vol. 5431. pp. 274–285 . doi : 10.1007/978-3-642-00202-1_24 . ISBN 978-3-642-00201-4 。↑ 稲葉正人、加藤直樹、今井弘（1994）。 重み付き ボロノイ 図とランダム化の分散ベースの k クラスタリング への応用。 第10回ACM計算幾何学シンポジウム論文集 。pp. 332–9。doi : 10.1145/177424.178042 。 ↑ マニング、クリストファー D.;ラガヴァン、プラバーカール。シュッツェ、ハインリッヒ (2008)。 情報検索の概要 。ケンブリッジ大学出版局。 ISBN 978-0521865715 OCLC 190786122。 1 2 Arthur, David; Vassilvitskii, Sergei (2006-01-01). " k -means法はどれくらい遅いのか？". Proceedings of the twenty-second annual symposium on Computational geometry . SCG '06. ACM. pp. 144–153 . doi : 10.1145/1137856.1137880 . ISBN 978-1595933409 . S2CID 3084311 . ↑ Bhowmick, Abhishek (2009). " k -meansクラスタリング のためのロイドのアルゴリズムの理論的分析" (PDF) 。 2015年12月8日に オリジナル (PDF) からアーカイブされました。 ↑ Ding, Yufei; Zhao, Yue; Shen, Xipeng; Musuvathi, Madan; Mytkowiczyear, Todd. "Yinyang K-Means: 一貫した高速化を実現した従来の K-Means のドロップイン代替法" (PDF) . Proceedings of the Thirty Second International Conference on Machine Learning (ICML) . 1 2 Phillips, Steven J. (2002). "Acceleration of K-Means and Related Clustering Algorithms". Mount, David M.; Stein, Clifford (eds.). Acceleration of k -Means and Related Clustering Algorithms . Lecture Notes in Computer Science. Vol. 2409. Springer. pp. 166–177 . doi : 10.1007/3-540-45643-0_13 . ISBN 978-3-540-43977-6 。1 2 Elkan, Charles (2003). "三角形不等式を使用して k -meansを加速する" (PDF) . Proceedings of the Twentieth International Conference on Machine Learning (ICML) . 1 2 Hamerly, Greg (2010). "k-meansをさらに高速化". 2010 SIAM International Conference on Data Mining 論文集 . pp. 130–140 . doi : 10.1137/1.9781611972801.12 . ISBN 978-0-89871-703-7 。1 2 Hamerly, Greg; Drake, Jonathan (2015). "k-MeansクラスタリングのためのLloydアルゴリズムの高速化". Partitional Clustering Algorithms . pp. 41–78 . doi : 10.1007/978-3-319-09259-1_2 . ISBN 978-3-319-09258-4 。↑ Ikotun, Abiodun M.; Ezugwu, Absalom E.; Abualigah, Laith; Abuhaija, Belal; Heming, Jia (2023). "K-meansクラスタリングアルゴリズム：包括的なレビュー、バリアント分析、ビッグデータ時代の進歩". Information Sciences . 622 : 178– 210. doi : 10.1016/j.ins.2022.11.139 . ↑ ソーンダイク、ロバート L. (1953). 「家族に属するのは誰か？」. サイコメトリカ . 18 (4): 267– 276. doi : 10.1007/BF02289263 . ↑ Schubert, Erich (2023). "k-means のエルボー基準の使用をやめて、代わりにクラスター数を選択する方法". ACM SIGKDD Explorations Newsletter . 25 : 36–42 . doi : 10.1145/3606274.3606278 . ↑ Rousseeuw, Peter J. (1987). "Silhouettes: A graphical aid to the interpretation and validation of cluster analysis". Journal of Computational and Applied Mathematics . 20 : 53–65 . doi : 10.1016/0377-0427(87)90125-7 . ↑ Tibshirani, Robert; Walther, Guenther; Hastie, Trevor (2001). "ギャップ統計量によるデータセット内のクラスター数の推定". Journal of the Royal Statistical Society Series B: Statistical Methodology . 63 (2): 411– 423. doi : 10.1111/1467-9868.00293 . ↑ Davies, David L.; Bouldin, Donald W. (1979). "A Cluster Separation Measure". IEEE Transactions on Pattern Analysis and Machine Intelligence . 1 (2): 224– 227. Bibcode : 1979ITPAM...1..224D . doi : 10.1109/TPAMI.1979.4766909 . PMID 21868852 . ↑ Caliński, T.; Harabasz, J. (1974). "クラスター分析のための樹状突起法". Communications in Statistics . 3 : 1–27 . doi : 10.1080/03610927408827101 . ↑ Rand, William M. (1971). "クラスタリング手法の評価のための客観的基準". Journal of the American Statistical Association . 66 (336): 846– 850. doi : 10.2307/2284239 . JSTOR 2284239 . ↑ Hubert, Lawrence; Arabie, Phipps (1985). "Comparing partitions". Journal of Classification . 2 : 193–218 . doi : 10.1007/BF01908075 . ↑ Kanungo, Tapas; Mount, David M. ; Netanyahu, Nathan S. ; Piatko, Christine D. ; Silverman, Ruth; Wu, Angela Y. (2002). "効率的な k 平均クラスタリングアルゴリズム：分析と実装" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 24 (7): 881– 892. Bibcode : 2002ITPAM..24..881K . doi : 10.1109/TPAMI.2002.1017616 . S2CID 12003435 . 2009年10月7日に オリジナル( PDF) からアーカイブ済み。 2009年4月24日 に取得 。 ↑ Drake, Jonathan (2012). " 適応距離境界付き加速 k- 平均法" (PDF) . 第5回NIPS機械学習最適化ワークショップ、OPT2012 . ↑ Dhillon, IS; Modha, DM (2001). "クラスタリングを用いた大規模スパーステキストデータの概念分解" . Machine Learning . 42 (1): 143– 175. Bibcode : 2001MLear..42..143D . doi : 10.1023/a:1007612920971 . ↑ Steinbach, M.; Karypis, G.; Kumar, V. (2000). " Workshop on Text Mining 400 ( 1): 525–526 。↑ Pelleg, D.; & Moore, AW (2000年6月)「 X-means:クラスター数の効率的な推定によるk -meansの拡張（ Wayback Machine に2016年9月9日に アーカイブ）」 ICML 、第1巻 ↑ Hamerly, Greg; Elkan, Charles (2004). "Learning the k in k-means" (PDF) . Advances in Neural Information Processing Systems . 16 : 281. ↑ Amorim, RC; Mirkin, B. (2012). " K -Meansクラスタリングにおけるミンコフスキー距離、特徴重み付け、異常クラスタ初期化 ". Pattern Recognition . 45 (3): 1061– 1075. doi : 10.1016/j.patcog.2011.08.012 . ↑ Amorim, RC; Hennig, C. (2015). "特徴再スケーリング係数を使用してノイズ特徴を持つデータセットのクラスタ数を復元する". Information Sciences . 324 : 126–145 . arXiv : 1602.06989 . doi : 10.1016/j.ins.2015.06.039 . S2CID 315803 . ↑ Sculley, David (2010). "Webスケール k 平均クラスタリング" . 第19回国際ワールドワイドウェブ会議議事録 . ACM. pp. 1177–1178 . 2016年12月21 日 取得 。 ↑ Telgarsky, Matus. "Hartigan's Method: k -means Clustering without Voronoi" (PDF) . ↑ ピッチャリ、ヴェロニカ。スドーソ、アントニオ M.ヴィーゲレ、アンジェリカ (2022-03-28)。 「SOS-SDP: 最小二乗和クラスタリングのための正確なソルバー」 。 INFORMS ジャーナル・オン・コンピューティング 。 34 (4 ) : 2144–2162。arXiv : 2104.11542 。 土井 ： 10.1287/ijoc.2022.1166 。 ISSN 1091-9856 。 S2CID 233388043 。 ↑ Bagirov, AM; Taheri, S.; Ugon, J. (2016). "最小二乗和クラスタリング問題に対する非平滑DCプログラミングアプローチ". Pattern Recognition . 53 : 12–24 . Bibcode : 2016PatRe..53...12B . doi : 10.1016/j.patcog.2015.11.011 . ↑ Fränti, Pasi (2018). "ランダムスワップクラスタリングの効率性" . Journal of Big Data . 5 (1) 13: 1– 21. doi : 10.1186/s40537-018-0122-y . ↑ Hansen, P.; Mladenovic, N. (2001). "J-Means: 最小二乗和クラスタリングのための新しい局所探索ヒューリスティック". Pattern Recognition . 34 (2): 405–413 . Bibcode : 2001PatRe..34..405H . doi : 10.1016/S0031-3203(99)00216-2 . ↑ Krishna, K.; Murty, MN (1999). "Genetic k-means algorithm" . IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics . 29 (3): 433– 439. Bibcode : 1999ITSMB..29..433K . doi : 10.1109/3477.764879 . PMID 18252317 . 1 2 Gribel, Daniel; Vidal, Thibaut (2019). "HG-means: 最小二乗和クラスタリングのためのスケーラブルなハイブリッドメタヒューリスティック". Pattern Recognition . 88 : 569–583 . arXiv : 1804.09813 . doi : 10.1016/j.patcog.2018.12.022 . S2CID 13746584 . ↑ Mirkes, EM 「K-means and k -medoids applet」 。 2016年 1月2日 取得 。 ↑ Kulis, Brian; Jordan, Michael I. (2012-06-26). " k -meansの再検討：ベイズノンパラメトリックによる新しいアルゴリズム" (PDF) . ICML . Association for Computing Machinery. pp. 1131–1138 . ISBN 9781450312851 。1 2 3 ビーグリー、ロバート A.スカルドーネ、アントニオ。シューラー、マイケル。クレイマー、ダニエル CA。チョタリア、マルコム。謝松濤 Q.バルビエリ、マルコ。デ・サンティアゴ、イグナシオ。ラヴィタス、ローラ＝マリア。フレイザー、ジェームズ。ドスティ、ジョゼ。アナ・ポンボ (2017)。 「ゲノム構造マッピングによって捕捉された複雑なマルチエンハンサー接触」 。 自然 。 543 (7646): 519–524 。 ビブコード : 2017Natur.543..519B 。 土井 ： 10.1038/nature21411 。 PMC 5366070 。 PMID 28273065 。 1 2 Eisen, Michael B.; Spellman, Paul T.; Brown, Patrick O.; Botstein, David (1998). "ゲノムワイド発現パターンのクラスター分析と表示" . Proceedings of the National Academy of Sciences . 95 (25): 14863– 14868. Bibcode : 1998PNAS...9514863E . doi : 10.1073/pnas.95.25.14863 . PMC 24541 . PMID 9843981 . 1 2 3 Coates, Adam; Ng, Andrew Y. (2012). " k- means による特徴表現の学習" (PDF) . Montavon, G.; Orr, GB; Müller, K.-R. (編) 『ニューラルネットワーク：コツ』 Springer。 ↑ Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Visual categorization with bags of keypoints (PDF) . ECCV Workshop on Statistical Learning in Computer Vision. 1 2 Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). 教師なし特徴学習における単層ネットワークの分析 (PDF) . 人工知能と統計に関する国際会議 (AISTATS). 2013年5月10日に オリジナル (PDF) からアーカイブされました 。 ↑ Schwenker, Friedhelm; Kestler, Hans A.; Palm, Günther (2001). "放射基底関数ネットワークの3つの学習フェーズ". Neural Networks . 14 ( 4–5 ): 439–458 . Bibcode : 2001NN.....14..439S . CiteSeerX 10.1.1.109.312 . doi : 10.1016/s0893-6080(01)00027-2 . PMID 11411631 . ↑ Lin, Dekang; Wu, Xiaoyun (2009). 識別学習のためのフレーズクラスタリング (PDF) . ACL および IJCNLP年次会議 . pp. 1030– 1038. 1 2 「ビッグデータクラスタリングへの応用を伴うK平均法アルゴリズムの並列化」 . arxiv.org . 2026年4月21日 取得 。 1 2 García Pérez, AE, et al. (2019). APOGEEにおける機械学習：化学組成による恒星集団の識別。天文学・天体物理学 。https ://www.aanda.org/articles/aa/full_html/2019/09/aa35223-19/aa35223-19.html ↑ Slijepcevic, IV, et al. (2025). K平均法とランダムフォレスト法を用いた恒星、銀河、クエーサーの半教師あり分類。天文学・天体物理学 。https ://www.aanda.org/articles/aa/full_html/2025/08/aa55620-25/aa55620-25.html 1 2 3 4 5 Arthur, David; Vassilvitskii, Sergei. "K-means++: 慎重なシードの利点" (PDF) . 第 18 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA) の議事録 : 1027–1035 . 1 2 3 4 5 6 7 バフマーニ、バフマーン。モーズリー、ベンジャミン。ヴァッターニ、アンドレア。クマール、ラヴィ。ヴァシルヴィツキ、セルゲイ (2012)。 「スケーラブルな K 平均法++」 (PDF) 。 VLDB 基金の議事録 。 5 (7): 622–633 。 土井 : 10.14778/2180912.2180915 。 1 2 Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「第 16.1 節 ガウス混合モデルと k 平均クラスタリング」 . Numerical Recipes: The Art of Scientific Computing (第 3 版). ニューヨーク (NY): Cambridge University Press. ISBN 978-0-521-88068-8 。↑ケビン・P ・ マーフィー（2012）。 機械学習 ：確率論的視点 。マサチューセッツ州ケンブリッジ：MIT Press。ISBN 978-0-262-30524-2 OCLC 810414751 ↑ Aharon, Michal ; Elad, Michael; Bruckstein, Alfred (2006). "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF) . IEEE Transactions on Signal Processing . 54 (11): 4311. Bibcode : 2006ITSP...54.4311A . doi : 10.1109/TSP.2006.881199 . S2CID 7477309 . 2019-12-02 に オリジナル (PDF)からアーカイブ済み . 2019-12-02 に取得 . ↑ Zha, Hongyuan; Ding, Chris; Gu, Ming; He, Xiaofeng; Simon, Horst D. (2001年12月). " k -meansクラスタリング のためのスペクトル緩和" (PDF) . Neural Information Processing Systems Vol.14 (NIPS 2001) : 1057– 1064. ↑ Ding, Chris; He, Xiaofeng (2004年7月). "主成分分析によるK平均クラスタリング" (PDF) . 国際機械学習会議 (ICML 2004) 論文集 : 225–232 . ↑ Drineas, Petros; Frieze, Alan M.; Kannan, Ravi; Vempala, Santosh; Vinay, Vishwanathan (2004). "Clustering large graphs via the singular value decomposition" (PDF) . Machine Learning . 56 ( 1– 3): 9– 33. Bibcode : 2004MLear..56....9D . doi : 10.1023/b:mach.0000033113.59016.96 . S2CID 5892850 . 2012-08-02 に取得 . ↑ Cohen, Michael B.; Elder, Sam; Musco, Cameron; Musco, Christopher; Persu, Madalina (2014). " k -meansクラスタリングと低ランク近似のための次元削減（付録B）". arXiv : 1410.6801 [ cs.DS ]. 1 2 Little, Max A.; Jones, Nick S. (2011). "区分的定数信号からのノイズ除去のための一般化された方法とソルバー。I. 背景理論" . Proceedings of the Royal Society A . 467 (2135): 3088– 3114. Bibcode : 2011RSPSA.467.3088L . doi : 10.1098/rspa.2010.0671 . PMC 3191861 . PMID 22003312 . ↑ Vinnikov, Alon; Shalev-Shwartz, Shai (2014). "K-means Recovers ICA Filters when Independent Components are Sparse" (PDF) . Proceedings of the International Conference on Machine Learning (ICML 2014) . 
![{\displaystyle [0,1]^{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e13ae4917276744b214714a20b3cb8ee305e309d)
