K-Means 알고리즘을 소개한 PPT 자료입니다.

예제를 사용하여 알고리즘의 절차를 쉽게 이해할 수 있도록 작성하였습니다.
(EM 알고리즘 소개 자료의 앞부분 내용과 동일합니다.)

파일을 첨부합니다.



아래는 작성한 소스코드 입니다. 참고하세요. 

package xminer.mining.clustering;

import xminer.core.*;
import java.util.Random;

public class KMeans {
  Dataset m_dataset;
  int m_clusterSize;
  int m_maxIteration;
  int m_recordCount;
  int m_fieldCount;
  int m_recordClusterIndex[];   // 각 레코드에 대하여 소속 군집번호
  int m_clusterCount[];            // 각 클러스터별 소속 개수
  Record m_cetroids[];

  public KMeans(Dataset ds, int clusterSize, int maxIteration) {
    m_dataset = ds;
    this.m_clusterSize = clusterSize;
    this.m_maxIteration = maxIteration;
    this.m_recordCount = ds.getRecordCount();
    this.m_fieldCount = ds.getAttrCount();
    this.m_recordClusterIndex = new int[ ds.getRecordCount() ];
    this.m_cetroids = new Record[ this.m_clusterSize ];
    this.m_clusterCount = new int[ this.m_clusterSize ];
  }

  public void learn(){
    // 초기 랜덤 시드 결정
    int i=0;
    init_centroid();
    this.print_centroid();

    while(true){
      //System.out.println( i + "번재 수행결과");

      reAssign_Step();
      findNewCentroid_Step();

      // System.out.println();
      // this.print_centroid();
      // this.print_state();

      // 최대반복횟수에 의한 학습 종료
      i++;
      if( i >= this.m_maxIteration){
        System.out.println("최대반복횟수에 도달하여 종료합니다. 반복횟수 : " + i);
        break;
      }

      // 중심점(Centroid)의 고정에 의한 학습 종료
      // -- 새로운 중심점의 계산
      // -- 이전 중심점과의 차이를 계산
      // -- 만약 중심점의 변화가 없으면 끝

    }
    System.out.println( i + "번재 수행결과");
    System.out.println();
    this.print_centroid();
    this.print_state();

  }

  /**
   * 초기에 클러스터 개수만큼의 레코드를 선택하여 이들을 초기 군집 중심으로 합니다.
   * 이때 같은 레코드가 중복해서 다른 군집의 중심점이 되지 않도록 합니다.
   */

  public void init_centroid(){
    Random random = new Random();
    for(int c=0; c<this.m_clusterSize; c++){
      this.m_cetroids[c] = this.m_dataset.getRecord( random.nextInt(m_recordCount-1)).copy();
    }
  }

  /**
   * 군집의 중심을 새롭게 계산합니다.
   * 모든 레코드의 소속값을 고려하여 평균값을 정합니다.
   */

  public void findNewCentroid_Step(){
    // 초기화
    for(int c=0; c<this.m_clusterSize; c++){
      this.m_clusterCount[c] = 0;
      for(int f=0; f<this.m_fieldCount; f++){
       this.m_cetroids[c].add(f, 0.0);
      }
    }
    int c_num;
    // 클러스터별 소속 레코드 개수를 계산합니다.
    for(int r=0; r<this.m_recordCount; r++){
      c_num = this.m_recordClusterIndex[r];
      this.m_clusterCount[c_num]++;
    }
    // 클러스터별 중심을 계산합니다.
    for(int r=0; r<this.m_recordCount; r++){
      c_num = this.m_recordClusterIndex[r];
      Record record = this.m_dataset.getRecord(r).copy();
      for(int f=0; f<this.m_fieldCount; f++){
       this.m_cetroids[c_num].addOnPrevValue(f, record.getValue(f));
      }
    }
    for(int c=0; c<this.m_clusterSize; c++){
      //System.out.println("군집 " + c + "의 개수 : "  + this.m_clusterCount[c]);
      this.m_cetroids[c].multiply( 1.0/(double)this.m_clusterCount[c] );
    }
  }

  /**
   * 주어진 중심에 대하여 모든 레코드들을 지정(Assign)합니다.
   * 레코드와 각 군집중심과의 거리를 계산해보고 가장 거리가 가까운 군집에 지정합니다.
   */

  public void reAssign_Step(){
    int c_num;
    double min_dist = Double.POSITIVE_INFINITY;
    double distance;
    for(int r=0; r<this.m_recordCount; r++){
      Record record = this.m_dataset.getRecord(r).copy();
      c_num = 0;
      min_dist = 10000; //Double.POSITIVE_INFINITY;
      for(int c=0; c<this.m_clusterSize; c++){
        distance = this.m_dataset.getDistanceOfUclideanP(record, this.m_cetroids[c]);
        // 해당 레코드와 군집중심과의 거리를 계산합니다.
        if(distance < min_dist){ // 최소
          min_dist = distance;
          c_num = c;
        }
      }
      this.m_recordClusterIndex[r] = c_num;
    }
  }

  /**
   * 현재 중심점(Centroid)의 값을 출력합니다.
   */

  public void print_centroid() {
    for (int c = 0; c < this.m_clusterSize; c++) {
      System.out.println("군집[" + (c) + "]의 중심점 : " +  this.m_cetroids[c].toString());
    }
  }

  public void print_state(){
    for(int r=0; r<this.m_recordCount; r++){
      System.out.print("번호 "+ (r+1) + " : " );
      for(int f=0; f<this.m_fieldCount; f++){
        System.out.print( this.m_dataset.getRecord(r).getValue(f) + ", " );
      }
      System.out.println( this.m_recordClusterIndex[r] );
    }
  }

  public static void main(String[] args) {
    // 아이리스 원본 데이터
    Dataset ds = new Dataset("아이리스","D:\\ai-miner-test-data\\iris.csv",  

                       Dataset.FIRSTLINE_ATTR_NO_INFO, true);

    // 수치 필드만 있는 아이리스 데이터
    // Dataset ds = new Dataset("D:\\work\\(01) (입력모듈) Dataset\\datafile\\iris_4.csv",

                           Dataset.HAS_NOT_FIELD_NAME_LINE);

    ds.printDataInfo();
    KMeans km = new KMeans(ds, 3, 200); // 3개 군집, 최대 10번 반복, 종료변화값 0.01
    km.learn();
  }

}



더 참고할 만한 사이트

[1] http://adeuxist.egloos.com/971452

by 에이아이 2009. 7. 29. 18:57