Kmeans 算法
计算方法
- 从n个向量中选择k个向量作为初始的聚类中心
- 根据在步骤（1）中设置的k个向量，计算每个向量与这k个中心的距离
- 对于（2）中的计算，将距离这个向量最近的中心向量归在一个类簇里
- 重新计算每个类簇的位置
- 重复（3）（4）步骤，直到类簇变化量极少为止
K-means算法的演示
- 生成数据
可见，数据分4簇，有两簇比较集中，两簇比较分散 - 随机分配中心
/**
* 初始化聚簇中心
* @param dataset
* @return
*/
public ArrayList<ArrayList<Double>> initializeCenter(ArrayList<ArrayList<Double>> dataset)
{
Random random = new Random();
Integer k = this.getK();
HashSet<Integer> set = new HashSet<>(k);
ArrayList<ArrayList<Double>> centres = new ArrayList<ArrayList<Double>>(k);
for (int i=0;i<k;i++)
{
int index=-1;
do{
index = random.nextInt(dataset.size());
}while (set.contains(index));
set.add(index);
centres.add(dataset.get(index));
}
return centres;
}
- 计算距离
- 分配类簇
- 重新定位中心
为了算法的效率，我把上述三步写到了一起
public ClusterResult changeCentre(ArrayList<ArrayList<Double>> dataset,ArrayList<ArrayList<Double>> centres)
{
ArrayList<Integer> labels = new ArrayList<>(dataset.size());
Integer k = this.getK();
DistanceContext distanceContext = this.getDistanceContext();
ArrayList<HashSet<Integer>> inverted = new ArrayList<>(k);
ArrayList<ArrayList<Double>> newCentre = new ArrayList<>(k);
double[][] sum = new double[k][dataset.get(0).size()];
for (int i=0;i<k;i++) //初始化倒排表
inverted.add(new HashSet<Integer>());
for (int i=0;i<dataset.size();i++)
{
int min=-1;
double minValue = 9999999;
//计算出距离
for (int j=0;j<k;j++) {
double distance = distanceContext.getDistance(dataset.get(i), centres.get(j));
if (minValue > distance){
minValue = distance;
min = j;
}
}
labels.add(min);
inverted.get(min).add(i);
//重定位累加
for (int j=0;j<dataset.get(i).size();j++)
sum[min][j]+=dataset.get(i).get(j);
}
//计算平均距离
for (int i=0;i<k;i++)
{
ArrayList<Double> list = new ArrayList<>(sum[i].length);
for (int j=0;j<sum[i].length;j++)
list.add(sum[i][j] / inverted.get(i).size());
newCentre.add(list);
}
return new ClusterResult(inverted,labels,newCentre);
}
- 不断重复，直到变化很少
private final int MAX_ITERATE_NUM=100; //最大迭代次数
@Override
public ClusterResult getClusterResult(ArrayList<ArrayList<Double>> dataset) {
ArrayList<ArrayList<Double>> centers = initializeCenter(dataset);
ClusterResult result=new ClusterResult();
double costLast = 99999999;
result = changeCentre(dataset, centers);
for (int i=0;i<this.MAX_ITERATE_NUM;i++) {
double cost = this.getCost(dataset, result.getClusterCenter(), result.getClusterIndexSet());
if (Math.abs((cost-costLast))<0.00000000000001)
break;
else
costLast = cost;
result = changeCentre(dataset, result.getClusterCenter());
}
System.out.println(costLast);
return result;
}
算法结果
可见分配还是较为合适的。
算法分析
因为Kmeans算法的初始化的不确定性，我们提出了算法的改进。
改进，K-means++算法
主要思想：初始的聚类中心之间的相互距离要尽可能的远。
- 随机选取一个样本作为第一个聚类中心 c1；
- 计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离）
- 用轮盘法选出下一个聚类中心；
- 重复步骤二，知道选出 k 个聚类中心
private ArrayList<ArrayList<Double>> initializeCentres(ArrayList<ArrayList<Double>> dataset)
{
Integer k = super.getK();
ArrayList<ArrayList<Double>> centres = new ArrayList<>(k);
Random random = new Random();
centres.add(dataset.get(random.nextInt(dataset.size()))); //初始化第一个聚类中心
for (int i=0;i<k-1;i++)
{
ArrayList<Double> list = new ArrayList<>(); //暂时存放概率
double sum = 0.0; //计算距离的和
for (int j=0;j<dataset.size();j++)
{
double closestDistance = getClosestDistance(dataset.get(j), centres);
//double closestDis_pow = Math.pow(closestDistance, 2);
list.add(closestDistance);
sum += closestDistance;
}
double pointer = Math.random(); //轮盘的指标
sum*=pointer;
for (int j=0;j<list.size();j++)
{
//double possibility=list.get(j)/sum; //概率
sum-=list.get(j);
if (sum<0) //轮盘命中
{
centres.add(dataset.get(j));
break;
}
}
}
return centres;
}
在k值比较大的情况下这个算法是比较慢的，但是在K值较小数据较多的时候，这个算法是比较快速的，它牺牲了一部分时间来进行初始化计算，但减少了后续聚类的时间和次数，在同时增加了准确性。