k平均法クラスタリング

k平均法クラスタリングは、もともと信号処理から派生したベクトル量子化手法で、 n 個の観測値をk 個のクラスターに分割することを目的とします。各クラスターは、クラスターのプロトタイプとして機能する、最も近い平均(クラスター中心またはクラスター重心) を持つクラスターに属します。これにより、データ空間がボロノイ セルに分割されます。k平均法クラスタリングは、クラスター内分散 (ユークリッド距離の二乗) を最小化しますが、通常のユークリッド距離は最小化しません。通常のユークリッド距離は、より困難なウェーバー問題です。平均は二乗誤差を最適化しますが、幾何中央値のみがユークリッド距離を最小化します。たとえば、 k中央値とkメドイドを使用すると、より優れたユークリッド解を見つけることができます。

この問題は計算上困難 ( NP 困難) ですが、効率的なヒューリスティック アルゴリズムにより、局所最適解にすばやく収束します。これらは通常、k 平均法とガウス混合モデリングの両方で採用されている反復改良アプローチを介した、ガウス分布の混合に対する期待値最大化アルゴリズムに似ています。どちらもクラスター中心を使用してデータをモデル化しますが、k平均法クラスタリングでは、同程度の空間範囲のクラスターが見つかる傾向がありますが、ガウス混合モデルでは、クラスターの形状が異なる場合があります。

教師なしk平均法アルゴリズムは、名前のせいでk平均法と混同されることが多い、分類のための一般的な教師あり機械学習手法であるk最近傍分類器と緩い関係があります。 k平均法によって取得されたクラスター中心に 1 最近傍分類器を適用すると、新しいデータが既存のクラスターに分類されます。これは、最近接重心分類器またはRocchio アルゴリズムとして知られています。

観測値の集合( x ₁ , x ₂ , ..., x _n )が与えられ、各観測値は次元の実数ベクトルである場合、k平均クラスタリングは、n 個の観測値をk ( ≤ n )個の集合S = { S ₁ , S ₂ , ..., S _k }に分割して、クラスター内二乗和 (WCSS) (つまり、分散) を最小化することを目的とします。正式には、目的は次のとおりです。 ここで、 μ _{i は}内の点の平均 (重心とも呼ばれる) 、 つまり のサイズ、 は通常のL ²ノルムです。これは、同じクラスター内の点のペアワイズ二乗偏差を最小化することと同じです。 同等性は恒等式 から推測できます。合計分散は一定であるため、これは異なるクラスター内の点間の二乗偏差の合計(クラスター間二乗和、BCSS) を最大化することと同じです。^[1]この決定論的な関係は確率論における 全分散の法則とも関連している。${\displaystyle d}$$${\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}}$$${\displaystyle S_{i}}$$${\displaystyle {\boldsymbol {\mu _{i}}}={\frac {1}{|S_{i}|}}\sum _{\mathbf {x} \in S_{i}}\mathbf {x} ,}$$ ${\displaystyle |S_{i}|}$${\displaystyle S_{i}}$${\displaystyle \|\cdot \|}$$${\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} \right\|^{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}}$

「 k平均法」という用語は、1967年にジェームズ・マックイーンによって初めて使用されましたが^[2]、そのアイデアは1956年のヒューゴ・スタインハウスに遡ります。^[3]標準アルゴリズムは、 1957年にベル研究所のスチュアート・ロイドによってパルス符号変調の技術として最初に提案されましたが、1982年まで論文として発表されませんでした。^[4] 1965年にエドワード・W・フォーギーが本質的に同じ方法を発表したため、ロイド・フォーギーアルゴリズムと呼ばれることもあります。^[5]

最も一般的なアルゴリズムは、反復改良法を使用する。その普遍性から、このアルゴリズムは「k平均法アルゴリズム」と呼ばれることが多い。また、特にコンピュータサイエンスの分野では、ロイドのアルゴリズムとも呼ばれる。より高速な代替法が存在するため、「ナイーブk平均法」と呼ばれることもある。^[6]

初期k平均集合m ₁ ⁽¹⁾ , ..., m _k ⁽¹⁾（下記参照）が与えられると、アルゴリズムは2つのステップを交互に実行して進行する：^[7]

1. 割り当てステップ: 各観測値を最も近い平均値を持つクラスター、つまり最小二乗ユークリッド距離を持つクラスターに割り当てます。^{[8] (数学的には、これは平均値によって生成された}ボロノイ図に従って観測値を分割することを意味します。)ここで、各観測値は、2つ以上の観測値に割り当てることができる場合でも、正確に1つの観測値に割り当てられます。$${\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\},}$$${\displaystyle x_{p}}$${\displaystyle S^{(t)}}$
2. 更新手順:各クラスターに割り当てられた観測値の平均 (重心) を再計算します。$${\displaystyle m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$$

k平均法の目的関数はWCSS (クラスター内の二乗和) です。各反復の後、WCSS は減少し、非負の単調減少シーケンスが得られます。これにより、k平均法は常に収束しますが、必ずしもグローバル最適値に収束するとは限りません。

アルゴリズムは、割り当てが変化しなくなったとき、または同等にWCSSが安定したときに収束したとみなされます。アルゴリズムが最適値を見つけることは保証されていません。^[9]

このアルゴリズムは、オブジェクトを距離に応じて最も近いクラスターに割り当てるものとしてよく提示されます。ユークリッド距離 (2 乗) 以外の距離関数を使用すると、アルゴリズムが収束しない可能性があります。球面k平均法やkメドイド法など、k平均法のさまざまな修正法が提案され、他の距離測定法を使用できるようになりました。

擬似コード

以下の擬似コードは、標準のk平均法クラスタリング アルゴリズムの実装の概要を示しています。重心の初期化、ポイントと重心間の距離メトリック、および新しい重心の計算は設計上の選択であり、実装によって異なります。この例の擬似コードでは、最小値のインデックスを見つけるために argminが使用されています。

def  k_means_cluster ( k , ポイント):
    # 初期化: k 個の重心を選択 (Forgy、ランダム パーティションなど)
    重心 =  [ c1 ,  c2 ,  ... ,  ck ]
    
    # クラスタリストを初期化する
    クラスター =  [[]  _の 範囲( k ) ]  
    
    # 収束するまでループする
    収束 = 偽
     収束していない 間：
        # 以前のクラスターをクリア
        クラスター =  [[]  _の 範囲( k ) ]  
    
        # 各点を「最も近い」重心に割り当てる
         ポイント内のポイントの 場合: 
            distances_to_each_centroid  =  [重心間の重心の距離(点、 重心)  ]   
            cluster_assignment  =  argmin (各重心までの距離)
            クラスター[クラスター割り当て] . append (ポイント)
        
        # 新しい重心を計算する
        # （標準実装では、
        # 新しい重心を決定するためのクラスター)
        new_centroids  =  [ calculate_centroid ( cluster ) クラスター内のクラスター ]  
        
        収束 =  (新しい重心 == 重心)
        重心 = 新しい重心
        
         収束した場合:
             クラスターを返す

一般的に使用される初期化方法は、Forgy 法とランダム パーティション法です。^[10] Forgy 法では、データセットからk 個の観測値をランダムに選択し、これを初期平均値として使用します。ランダム パーティション法では、最初に各観測値にクラスターをランダムに割り当て、次に更新ステップに進み、クラスターのランダムに割り当てられたポイントの重心となる初期平均値を計算します。Forgy 法では初期平均値が広がる傾向がありますが、ランダム パーティション法ではすべての初期平均値がデータセットの中心近くに配置されます。Hamerly らによると、^{[10]ランダム パーティション法は、} k調和平均やファジーk平均などのアルゴリズムに一般的に適しています。期待値最大化アルゴリズムと標準k平均アルゴリズムには、Forgy 初期化法が適しています。しかし、Celebiらによる包括的な研究^[11]では、Forgy、Random Partition、Maximinなどの一般的な初期化方法はパフォーマンスが低いことが多いのに対し、BradleyとFayyadのアプローチ^[12]は「最良のグループ」で「一貫して」パフォーマンスを発揮し、k -means++は「一般的に良好」なパフォーマンスを発揮することがわかりました。

• 標準アルゴリズムのデモンストレーション
• 
  1. k 個の初期「平均」（この場合はk =3）がデータ領域内でランダムに生成されます（色で表示されます）。
• 
  2.各観測値を最も近い平均値に関連付けることで、 k 個のクラスターが作成されます。ここでのパーティションは、平均値によって生成されたボロノイ図を表します。
• 
  3. k個のクラスターそれぞれの重心が新しい平均になります。
• 
  4. 収束に達するまで手順 2 と 3 を繰り返します。

このアルゴリズムは、グローバル最適値への収束を保証するものではありません。結果は初期クラスターに依存する可能性があります。このアルゴリズムは通常高速であるため、異なる開始条件で複数回実行するのが一般的です。ただし、最悪の場合のパフォーマンスは遅くなる可能性があります。特に、特定のポイントセットは、2次元であっても、指数時間、つまり2 ^{Ω( n )}で収束します。^{[13]これらのポイントセットは実際には発生しないようです。これは、} k平均法の平滑化された実行時間が多項式であるという事実によって裏付けられています。^[14]

「割り当て」ステップは「期待値ステップ」と呼ばれ、「更新ステップ」は最大化ステップであるため、このアルゴリズムは一般化 期待値最大化アルゴリズムのバリエーションになります。

d次元の観測値に対するk平均クラスタリング問題の最適解を見つけることは次のようになります。

• 一般的なユークリッド空間（d次元）では2つのクラスターに対してもNP困難である。 ^{[15] [16]}
• 平面上のクラスターの一般的な数kに対してもNP困難である。 ^[17]
• kとd（次元）が固定されている場合、問題は時間で正確に解くことができます。ここでnはクラスタリングされるエンティティの数です。^[18]${\displaystyle O(n^{dk+1})}$

したがって、上記に示したロイドのアルゴリズムなどの さまざまなヒューリスティック アルゴリズムが一般的に使用されます。

ロイドのアルゴリズム（およびほとんどの変種）の実行時間は、^{[9] [19]}で示される。ここで、 ${\displaystyle O(nkdi)}$

• nはd次元ベクトルの数（クラスタ化される）
• kクラスターの数
• i収束までに必要な反復回数。

クラスタリング構造を持つデータでは、収束までの反復回数は少なく、最初の12回の反復後には結果がわずかに改善されるだけです。そのため、ロイドのアルゴリズムは実際には「線形」複雑性を持つと考えられることが多いですが、収束まで実行すると最悪の場合、超多項式になります。^[20]

• 最悪の場合、ロイドのアルゴリズムは反復を必要とするため、ロイドのアルゴリズムの最悪ケースの複雑さは超多項式となる。^[20]${\displaystyle i=2^{\Omega ({\sqrt {n}})}}$
• ロイドのk平均法アルゴリズムは、多項式平滑化実行時間を持ちます。 ^[14]によれば、内の任意のn点集合に対して、各点が平均0および分散の正規分布によって独立に摂動を受ける場合、 k平均法アルゴリズムの期待実行時間はによって制限されます。これは、 n、k、d、およびの多項式です。解析に失敗しました (SVG (MathML はブラウザ プラグインで有効にできます): サーバー "http://localhost:6011/en.wikipedia.org/v1/" からの応答 ("Math 拡張機能は Restbase に接続できません。") が無効です: {\displaystyle 1/\sigma} 。${\displaystyle [0,1]^{d}}$${\displaystyle \sigma ^{2}}$${\displaystyle O(n^{34}k^{34}d^{8}\log ^{4}(n)/\sigma ^{6})}$
• 単純なケースではより良い境界が証明されています。例えば、k平均法アルゴリズムの実行時間は整数格子内のn点に対してで制限されることが示されています。^[21]${\displaystyle O(dn^{4}M^{2})}$ ${\displaystyle \{1,\dots ,M\}^{d}}$

ロイドのアルゴリズムは、この問題に対する標準的なアプローチです。しかし、k個のクラスターの中心とn 個のデータ ポイント間の距離を計算するのに多くの処理時間がかかります。ポイントは通常、数回の反復処理の後は同じクラスターに留まるため、この作業の多くは不要であり、単純な実装は非常に非効率的です。一部の実装では、キャッシュと三角不等式を使用して境界を作成し、ロイドのアルゴリズムを高速化しています。^{[9] [22] [23] [24] [25]}

k平均法クラスタリングの最適なクラスター数（k）を見つけることは、クラスタリング結果が有意義で有用なものとなるようにするための重要なステップです。^[26]適切なクラスター数を決定するための手法はいくつかあります。ここでは、よく使われる手法をいくつか紹介します。

• エルボー法（クラスタリング）：この方法では、説明された変動をクラスター数の関数としてプロットし、曲線のエルボーをクラスター数として選択します。^[27]しかし、「エルボー」の概念は明確に定義されておらず、信頼性が低いことが知られています。^[28]
• シルエット（クラスタリング）：シルエット分析はクラスタリングの質を測定し、結果として得られるクラスター間の分離距離についての洞察を提供します。^[29]シルエットスコアが高いほど、オブジェクトが自身のクラスターとよく一致し、隣接するクラスターとは一致しにくいことを示します。
• ギャップ統計：ギャップ統計は、kの異なる値に対するクラスター内変動の合計を、データのヌル参照分布の下での期待値と比較します。^[30]最適なkは、最大のギャップ統計をもたらす値です。
• デイヴィス・ボールディン指数：デイヴィス・ボールディン指数は、クラスター間の分離の程度を測る指標です。^[31]デイヴィス・ボールディン指数の値が低いほど、分離が良好なモデルであることを示します。
• Calinski-Harabasz指数：この指数は、クラスターのコンパクトさと分離に基づいてクラスターを評価します。この指数は、クラスター間の分散とクラスター内の分散の比率を使用して計算され、値が高いほどクラスターが明確に定義されていることを示します。^[32]
• ランド指数：同じクラスターまたは異なるクラスターに正しく割り当てられた要素のペアの両方を考慮して、2つのクラスター間の一致率を計算します。^[33]値が高いほど類似性が高く、クラスタリングの品質が優れていることを示します。より正確な測定を提供するために、1985年にHubertとArabieによって導入された調整ランド指数（ARI）は、偶然によるすべてのペアの予想される類似性を調整することでランド指数を修正します。^[34]

• ジェンクス自然ブレーク最適化:単変量データへのk平均法の適用
• k中央値クラスタリングでは、平均の代わりに各次元の中央値を使用し、この方法でノルムを最小化します (タクシーの幾何学)。${\displaystyle L_{1}}$
• k -medoids (別名: Partitioning Around Medoids、PAM) は平均の代わりに medoid を使用し、任意の距離関数の距離の合計を最小化します。
• ファジー C 平均法クラスタリングはk平均法のソフト バージョンであり、各データ ポイントは各クラスターに属する度合いがファジーです。
• 期待最大化アルゴリズム(EM アルゴリズム) を使用してトレーニングされたガウス混合モデルは、決定論的な割り当てではなくクラスターへの確率的な割り当てを維持し、平均ではなく多変量ガウス分布を維持します。
• k -means++ は、 WCSS 目的関数に証明可能な上限を与えるような方法で初期中心を選択します。
• フィルタリングアルゴリズムはk -dツリーを使用して各k -meansステップを高速化します。^[35]
• いくつかの方法では、三角不等式を使用してk平均法の各ステップを高速化しようとします。^{[22] [23] [24] [36] [25]}
• クラスター間のポイントを交換することで局所最適状態から脱出する。^[9]
• 球状k平均法クラスタリングアルゴリズムはテキストデータに適している。^[37]
• 二分k平均法^[38]、 X平均法クラスタリング^[39]、G平均法クラスタリング^[40] などの階層的な変種は、階層を構築するためにクラスターを繰り返し分割し、データセット内のクラスターの最適な数を自動的に決定しようとすることもできます。
• クラスターシルエットなどの内部クラスター評価尺度は、クラスターの数を決定するのに役立ちます。
• ミンコフスキー重み付きk平均法は、クラスター固有の特徴の重みを自動的に計算し、特徴が異なると関連性の度合いが異なる可能性があるという直感的な考えをサポートします。^[41]これらの重みは、特定のデータセットを再スケーリングするためにも使用でき、クラスターの予想される数でクラスター妥当性指標が最適化される可能性が高まります。^[42]
• ミニバッチk平均法：メモリに収まらないデータセットに対して「ミニバッチ」サンプルを使用するk平均法。 ^[43]
• 大津法

Hartiganと Wong の方法^[9]は、異なる解の更新を伴う最小二乗和問題の局所的最小値に向かって進むk平均法アルゴリズムのバリエーションを提供します。この方法は、このプロセスによって目的関数が改善される限り、サンプルを別のクラスターに再配置することを繰り返し試みる局所探索です。目的関数の改善によってサンプルを別のクラスターに再配置できない場合、この方法は停止します (局所的最小値で)。従来のk平均法と同様に、このアプローチは、最終解が必ずしもグローバルに最適であるとは限らないため、ヒューリスティックのままです。

を の個別コストとし、 をクラスターの中心 として定義します。${\displaystyle \varphi (S_{j})}$${\displaystyle S_{j}}$${\textstyle \sum _{x\in S_{j}}(x-\mu _{j})^{2}}$${\displaystyle \mu _{j}}$

割り当てステップ

Hartigan と Wong の方法は、ポイントをランダムなクラスターに分割することから始まります。${\displaystyle \{S_{j}\}_{j\in \{1,\cdots k\}}}$

更新手順

次に、次の関数が最大値に達する および を決定します。この最大値に達するについては、クラスター からクラスター に移動します。${\displaystyle n,m\in \{1,\ldots ,k\}}$${\displaystyle x\in S_{n}}$$${\displaystyle \Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\setminus \{x\})-\varphi (S_{m}\cup \{x\}).}$$${\displaystyle x,n,m}$${\displaystyle x}$${\displaystyle S_{n}}$${\displaystyle S_{m}}$

終了

アルゴリズムは、すべてに対して がゼロ未満になると終了します。${\displaystyle \Delta (m,n,x)}$${\displaystyle x,n,m}$

異なる移動受け入れ戦略を使用することができる。第一改善戦略では、改善するあらゆる再配置を適用することができるが、最善改善戦略では、すべての可能な再配置が反復的にテストされ、各反復で最良のものだけが適用されます。前者のアプローチは速度を重視し、後者のアプローチは一般的に追加の計算時間を犠牲にしてソリューションの品質を重視します。再配置の結果を計算するために使用される関数は、等式^{[44]を使用して効率的に評価することもできます。}${\displaystyle \Delta }$

$${\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 つの代替手段です。最近では、分岐限定法と半正定値計画法に基づく大域的最適化アルゴリズムにより、最大 4,177 のエンティティと 20,531 の特徴を持つデータセットに対して「実証済みの最適」ソリューションが生成されました。^{[45]予想どおり、基礎となる最適化問題の}NP 困難性により、このサイズを超えると、 k平均法の最適アルゴリズムの計算時間は急速に増加します。小規模および中規模の最適ソリューションは、他のヒューリスティックの品質を評価するためのベンチマーク ツールとして依然として価値があります。制御された計算時間内で最適性の保証なしに高品質の局所最小値を見つけるために、他の研究では、増分アプローチと凸最適化に基づくメタヒューリスティクスやその他のグローバル最適化手法、 ^[46]ランダムスワップ^[47]（つまり、反復局所探索）、可変近傍探索^[48]および遺伝的アルゴリズム[ ^49]などが研究されてきた。^[50]最小二乗和クラスタリング問題のより良い局所最小値を見つけることが、高次元の特徴空間におけるクラスター構造の回復の成功と失敗の違いを生む可能性があることは確かに知られている。^[50]$${\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}.}$$

k平均法の効率性を高める 3 つの重要な特徴は、しばしば最大の欠点と見なされます。

• ユークリッド距離はメトリックとして使用され、分散はクラスター散布の尺度として使用されます。
• クラスターの数kは入力パラメータです。k を不適切に選択すると、結果が悪くなる可能性があります。そのため、k 平均法を実行するときは、データ セット内のクラスターの数を決定するための診断チェックを実行することが重要です。
• 局所的最小値への収束により、直感に反する（「間違った」）結果が生じる可能性があります（図の例を参照）。

k平均法の主な制限は、そのクラスター モデルです。この概念は、平均がクラスターの中心に向かって収束するように分離可能な球状クラスターに基づいています。クラスターは同様のサイズであることが期待されるため、最も近いクラスターの中心に割り当てるのが正しい割り当てになります。たとえば、の値を持つk平均法をよく知られたアヤメのデータ セットに適用すると、結果ではデータ セットに含まれる 3種類のアヤメを分離できないことがよくあります。 を使用すると、2 つの目に見えるクラスター (1 つに 2 種類が含まれる) が検出されますが、 を使用すると、2 つのクラスターのうちの 1 つが 2 つの均等な部分に分割されます。実際、データ セットには 3 つのクラスが含まれていますが、 の方がこのデータ セットに適しています。他のクラスタリング アルゴリズムと同様に、k平均法の結果では、データが特定の基準を満たしていると想定しています。これは、一部のデータ セットではうまく機能しますが、他のデータ セットでは機能しません。 ${\displaystyle k=3}$${\displaystyle k=2}$${\displaystyle k=3}$${\displaystyle k=2}$

k平均法の結果は、クラスター平均のボロノイ セルとして見ることができます。データはクラスター平均の中間で分割されるため、マウスの例で見られるように、最適ではない分割につながる可能性があります。期待値最大化アルゴリズムで使用されるガウス モデル ( k平均法の一般化とも言える) は、分散と共分散の両方を持つため、より柔軟です。したがって、EM の結果は、 k平均法よりもはるかに適切に、可変サイズのクラスターや相関クラスター (この例ではそうではありません) に対応できます。一方、EM では、より多くの自由パラメーターの最適化が必要であり、クラスターの消失や条件の悪い共分散行列による方法論上の問題がいくつか発生します。k平均法は、ノンパラメトリックベイズ モデルと密接に関連しています。^[52]

k平均法クラスタリングは、特にロイドのアルゴリズムなどのヒューリスティックを使用する場合、大規模なデータ セットにも簡単に適用できます。市場セグメンテーション、コンピューター ビジョン、天文学など、さまざまな分野で効果的に使用されています。他のアルゴリズムの前処理手順として、たとえば開始構成を見つけるために使用されることがよくあります。

ベクトル量子化は、信号処理やコンピュータグラフィックスでよく使用される手法で、画像のカラーパレットをkと呼ばれる固定数の色に減らします。ベクトル量子化を実現する一般的な方法の 1 つは、 k平均法クラスタリングです。このプロセスでは、k平均法を画像の色空間に適用して、画像を k 個のクラスターに分割します。各クラスターは画像内の異なる色を表します。この手法は、類似した色を識別してグループ化するのに役立つ画像セグメンテーションタスクで特に役立ちます。

例:コンピュータグラフィックスの分野では、k平均法クラスタリングは画像圧縮におけるカラー量子化によく使用されます。画像を表現するために使用される色の数を減らすことで、見た目の品質を大幅に損なうことなくファイルサイズを大幅に削減できます。たとえば、数百万色の画像について考えてみましょう。kをより小さな数値に設定してk平均法クラスタリングを適用すると、画像はより限定されたカラーパレットを使用して表現できるため、圧縮バージョンではストレージスペースと帯域幅の消費が少なくなります。ベクトル量子化のその他の用途には、非ランダムサンプリングが含まれます。k 平均法を使用すると、大規模なデータ セットからk個の異なるプロトタイプ オブジェクトを簡単に選択して、さらに分析することができます。

クラスター分析は、データマイニングと機械学習の基本的なタスクであり、一連のデータポイントを類似性に基づいてクラスターにグループ化します。k平均法クラスタリングは、データを k 個のクラスターに分割するために使用される一般的なアルゴリズムで、各クラスターはその重心によって表されます。

ただし、純粋なk平均法アルゴリズムは柔軟性に欠けるため、用途が限られています (上記のようなベクトル量子化が実際に望ましい使用例である場合を除く)。特に、パラメータkは、外部制約によって指定されていない場合は選択が難しいことが知られています (上記で説明したとおり)。もう 1 つの制限は、任意の距離関数や非数値データでは使用できないことです。これらの使用例には、他の多くのアルゴリズムの方が優れています。

例: マーケティングでは、類似した特性や行動を持つ顧客をグループ化する市場セグメンテーションにk平均法クラスタリングがよく使用されます。たとえば、小売企業は、購買行動、人口統計、地理的位置などの要因に基づいて、顧客ベースを明確なグループに分割するためにk平均法クラスタリングを使用できます。その後、これらの顧客セグメントをターゲットにして、カスタマイズされたマーケティング戦略と製品提供を行い、売上と顧客満足度を最大化できます。

k平均法クラスタリングは、（半）教師あり学習または教師なし学習のいずれかにおいて、特徴学習（または辞書学習）ステップとして使用されてきました。^[53]基本的なアプローチは、まず入力トレーニングデータ（ラベルを付ける必要はありません）を使用して、 k平均法クラスタリング表現をトレーニングすることです。次に、入力データを新しい特徴空間に投影するために、データと重心位置のしきい値付き行列積などの「エンコード」関数を使用して、データから各重心までの距離、または単に最も近い重心の指標関数を計算します。 ^{[53] [54]}または距離の滑らかな変換。^[55]または、サンプルクラスター距離をガウス RBFで変換すると、ラジアル基底関数ネットワークの隠れ層が得られます。^[56]

このk平均法は、 NLP（特に名前付きエンティティの認識）^[57]やコンピュータビジョンにおける半教師あり学習のための単純な線形分類器とうまく組み合わせられてきました。物体認識タスクでは、オートエンコーダや制限付きボルツマンマシンなどのより洗練された特徴学習アプローチと同等のパフォーマンスを発揮することが確認されました。^[55]ただし、各データポイントは1つの「特徴」にしか寄与しないため、同等のパフォーマンスを得るには、通常、より多くのデータが必要です。^[53]

例:自然言語処理(NLP) では、k平均法クラスタリングが、固有表現抽出(NER)などの半教師あり学習タスク用の単純な線形分類器と統合されています。最初にk平均法を使用してラベルなしテキスト データをクラスタリングすることで、意味のある特徴を抽出し、NER モデルのパフォーマンスを向上させることができます。たとえば、k平均法クラスタリングを適用して、入力テキストで頻繁に共起する単語またはフレーズのクラスターを識別し、それを NER モデルのトレーニング用の特徴として使用できます。このアプローチは、ラベル付きデータに対する要件は高くなりますが、 オートエンコーダーや制限付きボルツマン マシンなどのより複雑な特徴学習手法と同等のパフォーマンスを実現することが示されています。

k平均法クラスタリングの応用における最近の進歩には、より効果的な方法で初期クラスター重心を選択するためのk平均法++初期化の使用など、初期化手法の改善が含まれます。さらに、研究者は、コンピューター ビジョン、自然言語処理、およびその他のドメインにおけるさまざまなタスクのパフォーマンスを向上させるために、畳み込みニューラル ネットワーク(CNN) や再帰型ニューラル ネットワーク(RNN)などのディープラーニング手法とk平均法クラスタリングの統合を研究してきました。

k平均法クラスタリングの低速な「標準アルゴリズム」と、それに関連する期待値最大化アルゴリズムは、ガウス混合モデルの特殊なケース、具体的には、すべての共分散を対角で等しく、無限小の小さな分散を持つように固定した場合の極限ケースです。^{[58] : 850}小さな分散の代わりに、ハードクラスター割り当てを使用して、k平均法クラスタリングと「ハード」ガウス混合モデリングの特殊なケースの別の同等性を示すこともできます。^{[59] : 354、11.4.2.5}これは、ガウス混合モデリングを使用してk平均法を計算することが効率的であることを意味するのではなく、理論的な関係があり、ガウス混合モデリングがk平均法の一般化として解釈できることを意味します。逆に、k平均法クラスタリングを使用して、困難なデータに対するガウス混合モデリングの開始点を見つけることが提案されています。^{[58] : 849}

k平均法アルゴリズムのもう一つの一般化はk -SVDアルゴリズムであり、これはデータポイントを「コードブックベクトル」のスパース線形結合として推定する。k平均法は、重みが1の単一のコードブックベクトルを使用する特殊なケースに対応する。^[60]

クラスター指標によって指定されるk平均法クラスタリングの緩和された解は、主成分分析 (PCA) によって与えられます。^{[61] [62]} 直感的には、k平均法は球形 (ボールのような) のクラスターを表します。データに 2 つのクラスターがある場合、2 つの重心を結ぶ線が最適な 1 次元投影方向であり、これが最初の PCA 方向でもあります。線を質量の中心で切断すると、クラスターが分離します (これは、離散クラスター指標の連続緩和です)。データに 3 つのクラスターがある場合、3 つのクラスター重心が張る 2 次元平面が最適な 2 次元投影です。この平面も、最初の 2 つの PCA 次元によって定義されます。十分に分離されたクラスターは、ボール形のクラスターによって効果的にモデル化されるため、k平均法によって検出されます。ボール形以外のクラスターは、近くにあると分離が困難です。たとえば、空間で絡み合った 2 つの半月形のクラスターは、PCA サブスペースに投影しても十分に分離しません。k平均法はこのデータではうまく機能しないと考えられる。^[63]クラスター重心部分空間が主方向によって張られるという主張に対する反例を挙げるのは簡単である。^[64]

基本的な平均シフト クラスタリング アルゴリズムは、入力データセットと同じサイズのデータ​​ ポイント セットを維持します。最初に、このセットは入力セットからコピーされます。次に、すべてのポイントは、周囲のポイントの平均に向かって反復的に移動されます。対照的に、k平均法は、クラスター セットをkクラスターに制限します。これは通常、入力データセット内のポイントの数よりもはるかに少ない数で、前のクラスター内の、そのポイントに重心 (たとえば、各更新ポイントのボロノイ分割内) のどのポイントよりも近いすべてのポイントの平均を使用します。k 平均法に似た平均シフト アルゴリズムは、尤度平均シフトと呼ばれ、置換されるポイント セットを、変更セットから指定された距離内にある入力セット内のすべてのポイントの平均に置き換えます。^[65] k平均法に対する平均シフト クラスタリングの利点は、クラスターの数を決定するパラメーターがないため、データセット内の任意の数のクラスターを検出できることです。平均シフトはk平均法よりもはるかに遅くなることがあり、帯域幅パラメーターの選択も必要です。

スパース性の仮定の下で、入力データがホワイトニング変換で前処理されると、k平均法は線形独立成分分析（ICA）タスクのソリューションを生成します。これは、k平均法を特徴学習に適用するのに成功したことを説明するのに役立ちます。^[66]

k平均法は、入力データセットの順序は重要ではないと暗黙的に想定しています。バイラテラルフィルタは、平均値に繰り返し置き換えられるデータポイントのセットを維持するという点で、 k平均法や平均値シフトに似ています。ただし、バイラテラルフィルタは、（カーネル重み付け）平均の計算を、入力データの順序が近いポイントのみを含むように制限します。^[65]これにより、画像内のピクセルの空間配置が非常に重要である画像ノイズ除去などの問題に適用できます。

クラスター関数を最小化する二乗誤差のセットには、k-メドイドアルゴリズムも含まれます。これは、各クラスターの中心点を実際の点の 1 つに強制するアプローチです。つまり、重心の代わりにメドイドを使用します。

アルゴリズムの異なる実装ではパフォーマンスに違いが見られ、テストデータセットでは最速で10秒、最も遅いものでは25,988秒（約7時間）かかりました。^[1]この違いは、実装の品質、言語とコンパイラの違い、終了基準と精度レベルの違い、加速のためのインデックスの使用に起因します。

以下の実装は、フリー/オープンソース ソフトウェアライセンスの下で利用可能であり、ソース コードは公開されています。

• Accord.NET には、 k -means、k -means++、k -modesの C# 実装が含まれています。
• ALGLIB には、 k -means およびk -means++用の並列化された C++ および C# 実装が含まれています。
• AOSP には、k平均法の Java 実装が含まれています。
• CrimeStat は2 つの空間k平均アルゴリズムを実装しており、そのうちの 1 つではユーザーが開始場所を定義できます。
• ELKI には、 k平均法 (Lloyd および MacQueen 反復法、およびk平均法++ 初期化などのさまざまな初期化を含む) と、より高度なさまざまなクラスタリング アルゴリズムが含まれています。
• Smile には、k平均法やその他のさまざまなアルゴリズムと結果の視覚化 (Java、Kotlin、Scala 用) が含まれています。
• Julia には、 JuliaStats Clustering パッケージにk平均法の実装が含まれています。
• KNIME には、 k平均法とkメドイド法のノードが含まれています。
• Mahout にはMapReduceベースのk平均法が含まれています。
• mlpack にはk平均法の C++ 実装が含まれています。
• Octave にはk平均法が含まれます。
• OpenCV にはk平均法の実装が含まれています。
• Orange には、kの自動選択とクラスター シルエット スコアリングを備えたk平均法クラスタリングのコンポーネントが含まれています。
• PSPPにはk平均法が含まれており、QUICK CLUSTER コマンドはデータセットに対してk平均法クラスタリングを実行します。
• Rには 3 つのk平均法バリエーションが含まれています。
• SciPyとscikit-learn には複数のk平均法の実装が含まれています。
• Spark MLlib は分散k平均法アルゴリズムを実装します。
• Torch には、k平均法クラスタリングを提供するunsupパッケージが含まれています。
• Weka にはk平均法とx平均法が含まれています。

以下の実装は独自のライセンス条件に基づいて利用可能であり、ソース コードが公開されていない可能性があります。

• K-メドイド
• BFRアルゴリズム
• 重心ボロノイ分割
• クラスター分析
• DBスキャン
• ヘッド/テールブレイク
• k qフラット
• k平均++
• リンデ・ブゾ・グレイアルゴリズム
• 自己組織化マップ