Loading article…
統計学において、k-中央値クラスタリング[1] [2]はクラスター分析アルゴリズムの一種です。これは、単一クラスターに対して定義された 幾何中央値または1中央値アルゴリズムの一般化です。
k中央値はk平均法クラスタリングの一種で、各クラスターの重心を決定するためにクラスターごとに平均を計算する代わりに、中央値を計算します。これは、2ノルム距離メトリックの 2 乗 ( k平均法が行う) ではなく、2 ノルム距離メトリックに関してすべてのクラスターの誤差を最小化する効果があります。
これは、 k個の中心から構成されるクラスターが 2 ノルムに関して最もコンパクトになるようなk個の中心を見つける問題であるk中央値問題に直接関係します。正式には、データ ポイントのセットxが与えられた場合、各xから最も近い c iまでの距離の合計が最小になるようにk個の中心c iが選択されます。
このように定式化された基準関数は、距離の二乗の合計が使用されるk平均法クラスタリングアルゴリズムで使用される基準よりも優れた基準となる場合があります。距離の合計は、施設配置問題などのアプリケーションで広く使用されています。
提案されたアルゴリズムは、期待値 (E) と最大化 (M) ステップを交互に実行するロイド スタイルの反復処理を使用して、期待値最大化アルゴリズムを実現します。E ステップでは、すべてのオブジェクトが最も近い中央値に割り当てられます。M ステップでは、各単一次元の中央値を使用して中央値が再計算されます。
中央線とメドイド
k中央値問題のマンハッタン距離定式化では、各次元で中央値が計算されるため、個々の属性はデータセットから取得されます (またはデータセットの 2 つの値の平均になります)。これにより、離散データ セットやバイナリ データセットでもアルゴリズムの信頼性が高まります。対照的に、平均値またはユークリッド距離中央値を使用すると、必ずしもデータセットから個々の属性が取得されるわけではありません。マンハッタン距離定式化を使用しても、個々の属性はデータセット内の異なるインスタンスから取得される可能性があるため、結果の中央値は入力データセットのメンバーではない可能性があります。
このアルゴリズムは、 k -medoidsアルゴリズムとよく混同されます。ただし、medoid はデータセットからの実際のインスタンスである必要がありますが、多変量マンハッタン距離中央値の場合、これは単一の属性値にのみ当てはまります。したがって、実際の中央値は複数のインスタンスの組み合わせになる場合があります。たとえば、ベクトル (0,1)、(1,0)、(2,2) が与えられた場合、マンハッタン距離中央値は (1,1) ですが、これは元のデータには存在しないため、medoid にはなりません。
ソフトウェア
- ELKI には、k 中央値を含むさまざまな k 平均法のバリエーションが含まれています。
- FORTRAN kmedians 関数
- GNU R には、「flexclust」パッケージに k-medians が含まれています。
- Stata kmedians の統計
参照
参考文献
- ^ AK Jainおよび RC Dubes、「データクラスタリングのアルゴリズム」、Prentice-Hall、1988 年。
- ^ PS Bradley、OL Mangasarian、WN Street、「Clustering via Concave Minimization」、Advances in Neural Information Processing Systems、第9巻、MC Mozer、MI Jordan、T. Petsche編。マサチューセッツ州ケンブリッジ：MIT Press、1997年、368～374ページ。