学习数据挖掘基本算法。

分类与聚类

聚类(clustering)是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。

在分类（ classification ）中，对于目标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来。

聚类分析也称无监督学习， 因为和分类学习相比，聚类的样本没有标记，需要由聚类学习算法来自动确定。聚类分析是研究如何在没有训练的条件下把样本划分为若干类。

K-Means 算法

从上图中，我们可以看到，A, B, C, D, E 是五个在图中点。

而灰色的点是我们的种子点，也就是我们用来找点群的点。

有两个种子点，所以K=2。 然后，K-Means的算法如下： 随机在图中取K（这里K=2）个种子点。 然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A,B属于上面的种子点，C,D,E属于下面中部的种子点） 接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步） 然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A,B,C，下面的种子点聚合了D，E）。

K-Means算法过程

输入：簇的数目k和包含n个对象的数据库。

输出：k个簇，使平方误差准则最小。

算法步骤：

1.为每个聚类确定一个初始聚类中心，这样就有K 个  初始聚类中心。

2.将样本集中的样本按照最小距离原则分配到最邻近聚类  

3.使用每个聚类中的样本均值作为新的聚类中心。

4.重复步骤2.3直到聚类中心不再变化。

5.结束，得到K个聚类

JAVA代码实现

Point类

public class Point implements Comparable
    
     {	private double x;	private double y;	private Double distance;	private String className;	public Point (String x,String y){		this.x=Double.parseDouble(x);		this.y=Double.parseDouble(y);	}		public double EuclideanDistance(Point p){		this.distance=Math.sqrt(Math.pow(p.x-this.x,2)+Math.pow(p.y-this.y,2));		return distance;	}	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 double getDistance() {		return distance;	}	public void setDistance(double distance) {		this.distance = distance;	}	public String getClassName() {		return className;	}	public void setClassName(String className) {		this.className = className;	}	@Override  	public int compareTo(Point o) {  	     return this.distance.compareTo(o.distance);  	 }  }
    

Kmeans类

public class Kmeans {	private String filePath;	private double judgeStandrad=Double.MAX_VALUE;	private int k;	private ArrayList
    
      dataArray;	private ArrayList
     
       basePoint;	private ArrayList
      
        totalPoint;	private int pointNum;	public Kmeans(String filePath, int k) {		this.filePath = filePath;		this.k = k;	}	public void Init() {		try {			BufferedReader bufferedReader = new BufferedReader(new FileReader(new File(filePath)));			String line;			while ((line = bufferedReader.readLine()) != null) {				String[] data = line.split(" ");				dataArray.add(data);			}			for (String[] data : dataArray) {				Point point = new Point(data[0], data[1]);				totalPoint.add(point);			}			pointNum = totalPoint.size();			Set set = new TreeSet
       
        ();			while (set.size() < k) {				int number = (int) (Math.random() * (pointNum - 1));				if (!set.contains(number)) {					set.add(number);				}			}			Iterator
        
          iterator = set.iterator();			while (iterator.hasNext()) {				Integer integer = iterator.next();				Point point = totalPoint.get(integer);				point.setClassName(integer.toString());				basePoint.add(point);			}		} catch (IOException e) {			e.printStackTrace();		}	}	public void Cluster(){				while (judgeStandrad > 0.01*k) {  						for(Point point :totalPoint){				double minDistance=Double.MAX_VALUE;				for(Point basePoint:basePoint){					double tempDistance=basePoint.EuclideanDistance(point);				}				Collections.sort(basePoint);				point.setClassName(basePoint.get(0).getClassName());			}			judgeStandrad=0;			for(Point basepoint:basePoint){				int count =0;				double tempx=0;				double tempy=0;				for(Point point :totalPoint){					if (point.getClassName().equals(basepoint.getClassName())) {						count++;						tempx=tempx+point.getX();						tempy=tempy+point.getY();					}				}				tempx=tempx/count;				tempy=tempy/count;				judgeStandrad += Math.abs((tempx - basepoint.getX()));  				judgeStandrad += Math.abs((tempy- basepoint.getY()));  				basepoint.setX(tempx);				basepoint.setY(tempy);			}		}		for (Point point :basePoint) {   	        System.out.println("聚类中心："+point.getX()+","+point.getY());	    }  	}}