K-Meansクラスターアルゴリズム

より多くのデータマイニングアルゴリズム:https://github.com/linyiqun/DataMiningAlgorithm
アルゴリズムの紹介
K-MeansはK平均アルゴリズムと呼ばれています.彼はクラスターアルゴリズムです.ここのKはクラスター中心の個数です.データの中にどれぐらいのデータクラスターがあるかを表しています.K-Meansはクラスターアルゴリズムで非常に簡単なアルゴリズムです.KNNアルゴリズムと似ていますが、距離ベクトル計量を使って、小分類の基準としてヨーロッパ距離を使います.
アルゴリズムステップ
(1)、数字kを設定し、n個の初期データからランダムにk個の点をクラスターの中心点とします.
(2)n点毎のデータ点について、k個のクラスターの中心点までの距離を遍歴して計算し、最後にどの中心点から一番近いかによって、そのカテゴリに区分する.
(3)各区分されているn個の点に対して、同じ種類の点に対して平均値を求め、このような別の新しい中心点とする.
(4)、循環(2)、(3)最終的な中心点が収束するまで.
以上の計算過程は下記の私のプログラムの実現に反映されます.
アルゴリズムのコード実装
入力データ:

3 3
4 10
9 6
14 8
18 11
21 7

メイン実装クラス:

package DataMining_KMeans;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;

/**
 * k       
 * 
 * @author lyq
 * 
 */
public class KMeansTool {
	//         
	private String filePath;
	//       
	private int classNum;
	//    
	private ArrayList<String> classNames;
	//      
	private ArrayList<Point> classPoints;
	//         
	private ArrayList<Point> totalPoints;

	public KMeansTool(String filePath, int classNum) {
		this.filePath = filePath;
		this.classNum = classNum;
		readDataFile();
	}

	/**
	 *         
	 */
	private void readDataFile() {
		File file = new File(filePath);
		ArrayList<String[]> dataArray = new ArrayList<String[]>();

		try {
			BufferedReader in = new BufferedReader(new FileReader(file));
			String str;
			String[] tempArray;
			while ((str = in.readLine()) != null) {
				tempArray = str.split(" ");
				dataArray.add(tempArray);
			}
			in.close();
		} catch (IOException e) {
			e.getStackTrace();
		}

		classPoints = new ArrayList<>();
		totalPoints = new ArrayList<>();
		classNames = new ArrayList<>();
		for (int i = 0, j = 1; i < dataArray.size(); i++) {
			if (j <= classNum) {
				classPoints.add(new Point(dataArray.get(i)[0],
						dataArray.get(i)[1], j + ""));
				classNames.add(i + "");
				j++;
			}
			totalPoints
					.add(new Point(dataArray.get(i)[0], dataArray.get(i)[1]));
		}
	}

	/**
	 * K        
	 */
	public void kMeansClustering() {
		double tempX = 0;
		double tempY = 0;
		int count = 0;
		double error = Integer.MAX_VALUE;
		Point temp;

		while (error > 0.01 * classNum) {
			for (Point p1 : totalPoints) {
				//              
				for (Point p2 : classPoints) {
					p2.computerDistance(p1);
				}
				Collections.sort(classPoints);

				//   p1           
				p1.setClassName(classPoints.get(0).getClassName());
			}

			error = 0;
			//              
			for (Point p1 : classPoints) {
				count = 0;
				tempX = 0;
				tempY = 0;
				for (Point p : totalPoints) {
					if (p.getClassName().equals(p1.getClassName())) {
						count++;
						tempX += p.getX();
						tempY += p.getY();
					}
				}
				tempX /= count;
				tempY /= count;

				error += Math.abs((tempX - p1.getX()));
				error += Math.abs((tempY - p1.getY()));
				//     
				p1.setX(tempX);
				p1.setY(tempY);

			}
			
			for (int i = 0; i < classPoints.size(); i++) {
				temp = classPoints.get(i);
				System.out.println(MessageFormat.format("     {0}，x={1},y={2}",
						(i + 1), temp.getX(), temp.getY()));
			}
			System.out.println("----------");
		}

		System.out.println("     ");
		for (int i = 0; i < classPoints.size(); i++) {
			temp = classPoints.get(i);
			System.out.println(MessageFormat.format("     {0}，x={1},y={2}",
					(i + 1), temp.getX(), temp.getY()));
		}

	}

}

ポイントクラス:

package DataMining_KMeans;

/**
 *     
 * 
 * @author lyq
 * 
 */
public class Point implements Comparable<Point>{
	//       
	private double x;
	//       
	private double y;
	//               
	private String className;
	//           
	private Double distance;

	public Point(double x, double y) {
		this.x = x;
		this.y = y;
	}
	
	public Point(String x, String y) {
		this.x = Double.parseDouble(x);
		this.y = Double.parseDouble(y);
	}
	
	public Point(String x, String y, String className) {
		this.x = Double.parseDouble(x);
		this.y = Double.parseDouble(y);
		this.className = className;
	}

	/**
	 *      p       
	 * 
	 * @param p
	 */
	public void computerDistance(Point p) {
		if (p == null) {
			return;
		}

		this.distance = (this.x - p.x) * (this.x - p.x) + (this.y - p.y)
				* (this.y - p.y);
	}

	public double getX() {
		return x;
	}

	public void setX(double x) {
		this.x = x;
	}

	public double getY() {
		return y;
	}

	public void setY(double y) {
		this.y = y;
	}
	
	public String getClassName() {
		return className;
	}

	public void setClassName(String className) {
		this.className = className;
	}

	public double getDistance() {
		return distance;
	}

	public void setDistance(double distance) {
		this.distance = distance;
	}

	@Override
	public int compareTo(Point o) {
		// TODO Auto-generated method stub
		return this.distance.compareTo(o.distance);
	}
	
}

コールクラス:

/**
 * K-means（K  ）     
 * @author lyq
 *
 */
public class Client {
	public static void main(String[] args){
		String filePath = "C:\\Users\\lyq\\Desktop\\icon\\input.txt";
		//        
		int classNum = 3;
		
		KMeansTool tool = new KMeansTool(filePath, classNum);
		tool.kMeansClustering();
	}
}

テスト出力結果:

     1，x=15.5,y=8
     2，x=4,y=10
     3，x=3,y=3
----------
     1，x=17.667,y=8.667
     2，x=6.5,y=8
     3，x=3,y=3
----------
     1，x=17.667,y=8.667
     2，x=6.5,y=8
     3，x=3,y=3
----------
     
     1，x=17.667,y=8.667
     2，x=6.5,y=8
     3，x=3,y=3

K-Meansアルゴリズムの長所と短所
まず長所はもちろんアルゴリズムが簡単で、分かりやすく、特に複雑なデータ構造には触れていません.
2、短所1は最初のKの数の値とKのクラスターの中心点の設定がよく決まっていません.始終時に異なるkの中心点の設定は、後の反復計算の動きに大きな影響を与えます.この場合、クラスの自動合併と分裂によってこのkを決定することができます.
3、欠点2計算は反復式であるため、距離を計算する時は完全に中心点を巡回する必要があり、データの規模が大きい時は出費が大きくなります.