K-Means聚类_请以1.6号数据为初始点,进行k-means聚类

什么是K-Means

一种最简单的无监督聚类算法，其核心思想在于“均值”，即各个聚类中心分别使用每类的样本均值进行更新。

步骤

1. 初始化聚类中心

最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点，如下面k为要聚成几类，dataCount为数据量。

for (int i = 0; i<k; i++){
    centroidx[i] = x[rand() % dataCount];
    centroidy[i] = y[rand() % dataCount];
}
1
2
3
4

但是上述方法在有些情况下的效果较差，每次迭代计算完成后聚类得出的结果可能都不太一样，初始聚类中心的选取可以参考这篇博客。

2. 为数据集中每个点指定各自的中心

距离度量：距离度量有很多中方式，这里一般采用欧氏距离。两点间的欧氏距离实现如下：

// 欧氏距离
double calculateDistance(double x, double y, double x1, double y1)
{
    double part1 = (x - x1) * (x - x1);
    double part2 = (y - y1) * (y - y1);
    double answer = sqrt(part1 + part2);

    return answer;
}
1
2
3
4
5
6
7
8
9

指定聚类中心：详细内容见代码标注。

// 为每个点分配聚类中心
void assignCentroid(){
    // 重新分配，全部清0
    for (int i = 0; i < k; i++)
        centroidcount[i] = 0;

    for (int i = 0; i<dataCount; i++)
    {
        assignCentroid(x[i], y[i], i);
    }
}

// 为点point，分配聚类中心
void assignCentroid(double x, double y, int point)
{
    double smallest = 999;
    int chosenCentroid = 999;

    for (int i = 0; i<k; i++)
    {
        // 计算指定点到每个聚类中心的距离，选出最小的最为它的中心
        double distanceToCentroid = calculateDistance(x, y, centroidx[i], centroidy[i]);

        if (distanceToCentroid < smallest)
        {
            smallest = distanceToCentroid;
            chosenCentroid = i;
        }
    }
    assignedto[point] = chosenCentroid;
    centroidcount[chosenCentroid]++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3. 迭代更新聚类中心

double calculateNewCentroid()
{
    double max_movement = -1;
    for (int i = 0; i<k; i++)
    {
        // cout << endl;
        outfile << endl;

        oldcentroidx[i] = centroidx[i];
        oldcentroidy[i] = centroidy[i];

        double xsum = 0;
        double ysum = 0;
        double count = 0;

        for (int j = 0; j < dataCount; j++){
            // 分配到我这一类的所有点，求个和
            if (assignedto[j] == i)
            {
                xsum += x[j];
                ysum += y[j];
                count++;
            }
        }
        // 更新聚类中心
        if (count == 0){
            centroidx[i] = -1;
            centroidy[i] = -1;
        }
        else{
            centroidx[i] = xsum / count;
            centroidy[i] = ysum / count;
        }
        double movement = calculateDistance(oldcentroidx[i], oldcentroidy[i], centroidx[i], centroidy[i]);
        max_movement = max(max_movement, movement);
    }
    // 返回聚类中心最大的移动量，可以用这个作为迭代终止的条件
    return max_movement;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

4. 重复2/3直至稳定

缺点

• 分几类？
  K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。

• 如何初始聚类中心？
  算法需要初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。初始选取的样本点不同，所得的结果就会有所差异，而初始聚类中心一般需要随机选取。关于这一步相关优化比较多，可以进一步查阅相关资料。

• 计算量大

• 对离群点敏感
  因为采用样本均值计算作为聚类中心的更新策略，所以质心很大程度上都不在样本集内，例：当一个cluster样本点只有少数几个，如（1,1）（1,2）（2,1）（100,100），其中（100,100）是噪声。如果按照k-means质心大致会处在（1,1）（100,100）中间，这显然不是我们想要的，在这一层面上的改进方法主要有k-medoids，他会在（1,1）（1,2）（2,1）（100,100）中选出一个样本点使cluster的绝对误差最小，计算可知一定会在前三个点中选取。