抄録

○服部正嗣・青山一生（NTT）

大規模データを多クラスに分割する効率的なk-meansクラスタリング法を提案する．
典型的なk-meansクラスタリング法であるLloyd法を，距離の三角不等式を利用し高速化する方法にElkan法がある．Elkan法はオブジェクト数（N）と中心数（k<N）に対して距離格納用にO(N・k)の記憶容量を必要とするため，汎用計算機では大規模データを多クラスに分割することが困難であるという問題があった．
我々は，新たに少数（p<<k）のピボットを導入し，距離の三角不等式によるLloyd法に対する高速性と，小記憶容量O((N+k)p)を両立する。提案法の効率性を人工データと実画像データを用いて実験的に示す．