だいたいでええやろで書いたk-平均法

前提
k個のクラスタを作る

①全てのデータに対してランダムなクラスタを割り振る
②クラスタ毎に重心を作る
③重心との距離に応じて各データのクラスタを振り直す

④終了条件を満たすまで繰り返す
終了条件
クラスタの振り直しが無くなるまで繰り返す
なんらかの量の変位が既定値を下回るまで繰り返す
規定の回数繰り返す

ここでは入力された２Dベクトル座標群をクラスタリングします。
processingで書きます。

//n回ループ
HashMap<Integer, List<PVector>> kmeans_n(List<PVector> vectors, int k, int n)
{
  //ベクトル毎にインデックスを割り付けた辞書HashMap<PVector, Integer>を作る
  var map = setup_cluster(vectors, k);
    
  for(int i = 0; i<n; i++)
  {
    //現在のmap : HashMap<PVector, Integer>からクラスター : HashMap<Integer, List<PVector>>を作成する
    var clusters = get_clusters(map, k);
    //クラスタ毎の重心を作成する
    var centroids = setup_centroid(clusters, k);          
    //mapの更新    
    update_cluster(map,vectors,centroids);    
  }  
  
  return get_clusters(map, k);
}

①全てのデータに対してランダムなクラスタを割り振る

入力データにクラスタを割り振るため、なんらかのデータ構造が必要です。

その１、クラスタークラスを作る。
その２、ジャグ配列作る。
その３、辞書使う。

ここでは辞書を使います。
ベクトルList<PVector>に、各々ランダムなインデックスを割り付けると考えて、HashMap<PVector, Integer>が割り付けられた状態です。
この構造ではPVectorをnewしただけでぶっ壊れる可能性があります。

import java.util.Random;
Random random;

HashMap<PVector, Integer> setup_cluster(List<PVector> vectors, int k)
{
  var map = new HashMap<PVector, Integer>();
  for(int i = 0; i<vectors.size(); i++)
  {
    int random_index = random.nextInt(k);
    map.put(vectors.get(i), random_index);    
  }  
  return map;
}

HashMap<PVector, Integer>はList<PVector>の延長です。
座標単位で処理を行うにはこっちのほうが楽です。
クラスター単位で処理を行う場合はHashMap<Integer, List<PVector>>の方が楽でしょう。

HashMap<PVector, Integer>を変数mapとし
HashMap<Integer, List<PVector>>を変数clustersとします。
mapのkeyは座標群の個数だけあり、
clustersのkeyはクラスターの個数k個だけあります。

HashMap<Integer, List<PVector>> get_clusters(HashMap<PVector, Integer> map, int k)
{
  var clusters = new HashMap<Integer, List<PVector>>();
  
  for(int i = 0; i<k; i++)
  {
    clusters.put(i, new ArrayList<PVector>() );
  }
  
  //keyでループ
  //for(var pv : map.keySet())
  //{
  //  int cluster_index = map.get(pv);
  //  clusters.get(cluster_index).add(pv);
  //}
  
  //keyとvalueでループ
  for(var entry : map.entrySet())
  {
    clusters.get(entry.getValue()).add(entry.getKey());
  }
  
  return clusters;
}

②クラスタ毎に重心を作る

重心はクラスタ毎に処理をするのでHashMap<Integer, List<PVector>>を使います。

エラー処理の類をなんにもしとらんことにご注意ください。

List<PVector>setup_centroid(HashMap<Integer, List<PVector>> clusters, int k)
{
  var centroids = new ArrayList<PVector>();  
  for(var entry : clusters.entrySet())
  {
    if(entry.getValue().size()<1){continue;}
    
    var centroid = CalucuCentroid(entry.getValue());
    centroids.add(centroid);
  }
  return centroids;
}

PVector CalucuCentroid(List<PVector> vectors)
{
  PVector centroid = new PVector(0,0);
  for(var v : vectors)
  {
    centroid.add(v);
  }
  return centroid.div(vectors.size());
}

③重心との距離に応じて各データのクラスタを振り直す

座標単位でクラスタインデックスを振りなおすのでHashMap<PVector, Integer>を使います。

void update_cluster(HashMap<PVector, Integer> map, List<PVector> vectors, List<PVector> centroids)
{
  for(int i = 0; i<vectors.size(); i++)
  {
    var t = vectors.get(i);   
    //最も近い重心のインデックス
    int centroid_index = nearest_index(centroids, t);
    map.put(t,centroid_index);
  }      
}


//最近接点(今回未使用）
PVector nearest_vector(List<PVector> vectors, PVector v)
{
  float nearest_distance = Float.MAX_VALUE;
  int nearest_index = 0;
  
  for(int i = 0; i<vectors.size(); i++)
  {
    var t = vectors.get(i);
    var distance = PVector.sub(t,v).mag();
    if(distance<nearest_distance)
    {
      nearest_distance=distance;
      nearest_index = i;
    }    
  }
  return vectors.get(nearest_index);
}

//最近接点のインデックス
int nearest_index(List<PVector> vectors, PVector v)
{
  float nearest_distance = Float.MAX_VALUE;
  int nearest_index = 0;
  
  for(int i = 0; i<vectors.size(); i++)
  {
    var t = vectors.get(i);
    var distance = PVector.sub(t,v).mag();
    if(distance<nearest_distance)
    {
      nearest_distance=distance;
      nearest_index = i;
    }    
  }
  return nearest_index;  
}