2 请描述K-means的原理,说明选择聚类中心的方法

kmeans是一种聚类算法下面是算法的描述

  • 给定训练样本是这里写图片描述每一个

这里写图片描述,即每一个样本元素都是n维向量。为了便于理解在后面的示意图中采用二维的向量。

step1:
随机选取k个聚类质心点为这里写图片描述

step2:
重复下面过程直到手链

对于每一个样本i计算其应该属于的类这里写图片描述

对于每一个类这里写图片描述,重新计算该类的质心这里写图片描述

以下是转自http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html的解释

其中,K是给定的聚类数,这里写图片描述代表样例i与k个类中距离最近的那个类,这里写图片描述的值是1到k中的一个。质心这里写图片描述代表我们对属于同一个类的样本中心点的猜测,拿星团模型来解释就是要将所有的星星聚成k个星团,首先随机选取k个宇宙中的点(或者k个星星)作为k个星团的质心,然后第一步对于每一个星星计算其到k个质心中每一个的距离,然后选取距离最近的那个星团作为这里写图片描述,这样经过第一步每一个星星都有了所属的星团;第二步对于每一个星团,重新计算它的质心(对里面所有的星星坐标求平均)。重复迭代第一步和第二步直到质心不变或者变化很小。

相信到这里很多人看的一头雾水,这里我接着博主的描述再进一步解释。

第一个公式中的arg是标记符号,即表明哪个样本参数属于哪个类用的,后面的紧跟着的min最小化j是我们接下来要说的J这个函数。如下:这里写图片描述
这是kmeans算法中定性描述,公式里面的符号还是上面所说的符号。这里写图片描述这里写图片描述表示第1个样本所属的类别,这里写图片描述表示数据点x(i)被归类到 这里写图片描述的时候为 1 ,否则为 0 。

下面通过图文来解释这个公式,一直按照流程聚类一个样本相信大家就能很好地理解这个公式表达的意思了

这里写图片描述

  • 用kmeans算法将三个样本聚类成2类,图中的红点为样本点,蓝点为随即初始的两类的样本点的质心,黑色连线代表每个样本点到某一类质心的距离。J函数最小的意思就是选取这些黑色的距离线使其长度和最小,并且从红点出发的线只能选取一次,即如图中的1.9这条线和2这条线由于都是从同一个红点出发所以只能选取一个进行相加,选取的总线数就是红点的个数,下面两张图分别是多种组合选择的二种选取结果

这里写图片描述

其中绿线为选取的线,他们的和为1.9+2+2.3=6.2

这里写图片描述

其中绿线为选取的线,他们的和为1.9+1.2+1=4.1

对比上面两张图可以看出,后者的和小,即J值小。这里第二种选取方案也是全局最优选取方案,即所有选取方案中最小的一个。此时,可以把三个点分成两类,如下图
这里写图片描述
分成2类后再重新计算每类的质心,以及质心到各个样本点的距离,如下图。需要注意的是由于黄色类只有一个样本点,即该类的质点就是该样本点,故其中一个“0”表示质点到该样本点的距离为零。
这里写图片描述
仍然按照,找每个红点到蓝点的一条线的和最小的组合方式,注意每个红点到蓝点的多个距离值只容许一条计算,下图是错误的,其中一个红有两条线参加了计算,1和0.8这两条线只能有一天参与求和。
这里写图片描述
此时,样本被分成新的两类,如下图
这里写图片描述
再求新分的两类的质心
这里写图片描述
重复以上操作,直到质心不变,即J函数值最小,结束算法。
这里写图片描述

 

k-means 聚类算法原理:

1、从包含多个数据点的数据集 D 中随机取 k 个点,作为 k 个簇的各自的中心。

2、分别计算剩下的点到 k 个簇中心的相异度,将这些元素分别划归到相异度最低的簇。两个点之间的相异度大小采用欧氏距离公式衡量,对于两个点 T0(x1,y2)和 T1(x2,y2),T0 和 T1 之间的欧氏距离为:

欧氏距离越小,说明相异度越小

3、根据聚类结果,重新计算 k 个簇各自的中心,计算方法是取簇中所有点各自维度的算术平均数。

4、将 D 中全部点按照新的中心重新聚类。

5、重复第 4 步,直到聚类结果不再变化。

6、将结果输出。

 举例说明, 假设包含 9 个点数据 D 如下(见 simple_k-means.txt), 从 D 中随机取 k 个元素,作为 k 个簇的各自的中心, 假设选 k=2, 即将如下的 9 个点聚类成两个类(cluster)

  1.假设选 C0(1 1)和 C1(2 1)前两个点作为两个类的簇心。
  2. 分别计算剩下的点到 k 个簇中心的相异度,将这些元素分别划归到相异度最低的簇。结果为:
  3.根据 2 的聚类结果,重新计算 k 个簇各自的中心,计算方法是取簇中所有元素各自维度的算术平均数。
C0 新的簇心为: 1.0,1.5
C1 新的簇心为: 5.857142857142857, 5.714285714285714
  4.将 D 中全部元素按照新的中心重新聚类。
  5.重复第 4 步,直到聚类结果不再变化。当每个簇心点前后移动的距离小于某个阈值t的时候,就认为聚类已经结束了,不需要再迭代,这里的值选t=0.001,距离计算采用欧氏距离。
C0 的簇心为: 1.6666666666666667, 1.75
C1 的簇心为: 7.971428571428572, 7.942857142857143
C0 的簇心为: 1.777777777777778, 1.7916666666666667
C1 的簇心为: 8.394285714285715, 8.388571428571428

C0 的簇心为: 1.7962962962962965, 1.7986111111111114

C1 的簇心为: 8.478857142857143, 8.477714285714285
C0 的簇心为: 1.799382716049383, 1.7997685185185184
C1 的簇心为: 8.495771428571429, 8.495542857142857

C0 的簇心为: 1.7998971193415638, 1.7999614197530864

C1 的簇心为: 8.499154285714287, 8.499108571428572

[cpp] view plain copy

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <vector>
  5. #include <cmath>
  6. using namespace std;
  7. class Cluster//聚类,每个聚类都包含两个属性,一个是簇心的属性(维数),另一个是距离本簇心最近的样本点
  8. {
  9. public:
  10.     vector <double> centroid;//存放簇心的属性(维数)
  11.     vector <int> samples;//存放属于相同簇心样本的下标
  12. };
  13. double CalculateDistance(vector<double> a, vector<double> b)//计算两个向量之间的距离
  14. {
  15.     int len1 = a.size();
  16.     int len2 = b.size();
  17.     if(len1 != len2)
  18.         cerr<<“Dimensions of two vectors must be same!!\n”;
  19.     double temp = 0;
  20.     for(int i = 0; i  < len1; ++i)
  21.         temp += pow(a[i]-b[i], 2);
  22.     return sqrt(temp);
  23. }
  24. //max_iteration表示最大的迭代次数,min_move_distance
  25. vector<Cluster> KMeans(vector<vector<double> >data_set, int k, int max_iteration, double threshold)
  26. {
  27.     int row_number = data_set.size();//数据的个数
  28.     int col_number = data_set[0].size();//每个向量(属性)的维数
  29.     //初始随机选取k个质心
  30.     vector<Cluster> cluster(k);//存放k个簇心。vector<T> v(n,i)形式,v包含n 个值为 i 的元素
  31.     srand((int)time(0));
  32.     for(int i = 0; i < k; ++i)
  33.     {
  34.         int c = rand()%row_number;
  35.         cluster[i].centroid = data_set[c];//把第c个作为簇心,并把它相应的属性赋值给centroid
  36.     }
  37.     //iteration
  38.     int iter = 0;
  39.     while(iter < max_iteration)
  40.     {
  41.         iter++;
  42.         for(int i = 0; i < k; ++i)
  43.             cluster[i].samples.clear();
  44.         //找出每个样本点所属的质心
  45.         for(int i = 0; i < row_number; ++i)
  46.         {
  47.             double min_distance = INT_MAX;
  48.             int index = 0;
  49.             //计算离样本点i最近的质心
  50.             for(int j = 0; j < k; ++j)
  51.             {
  52.                 double temp_distance = CalculateDistance(data_set[i], cluster[j].centroid);
  53.                 if(min_distance > temp_distance)
  54.                 {
  55.                     min_distance = temp_distance;
  56.                     index = j;
  57.                 }
  58.             }
  59.             cluster[index].samples.push_back(i);//把第i个样本点放入,距离其最近的质心的samples
  60.         }
  61.         double max_move_distance = INT_MIN;
  62.         //更新簇心
  63.         for(int i = 0; i < k; ++i)
  64.         {
  65.             vector<double> temp_value(col_number, 0.0);
  66.             for(int num = 0; num < cluster[i].samples.size(); ++num)//计算每个样本的属性之和
  67.             {
  68.                 int temp_same = cluster[i].samples[num];
  69.                 for(int j = 0; j < col_number; ++j)
  70.                     temp_value[j] += data_set[temp_same][j];
  71.             }
  72.             vector<double> temp_centroid = cluster[i].centroid;
  73.             for(int j = 0; j < col_number; ++j)
  74.                 cluster[i].centroid[j] = temp_value[j]/cluster[i].samples.size();
  75.             //计算从上一个簇心移动到当前新的簇心的距离
  76.             double temp_distance = CalculateDistance(temp_centroid, cluster[i].centroid);
  77.             if(max_move_distance < temp_distance)
  78.                 max_move_distance = temp_distance;
  79.         }
  80.         if(max_move_distance < threshold)
  81.             break;
  82.     }
  83.     return cluster;
  84. }
  85. int main()
  86. {
  87.     int threshold = 0.001;//当从上一个簇心移动到当前粗心的距离几乎不变时,可以结束。这里用threshold作为阈值
  88.     vector <vector<double> >data_set(9, vector<double>(2, 0.0));
  89.     int point_number;
  90.     cin>>point_number;
  91.     for(int i = 0; i < point_number; ++i)
  92.     {
  93.         for(int j = 0; j < 2; ++j)
  94.             cin>>data_set[i][j];
  95.     }
  96.     int col = data_set[0].size();
  97.     vector<Cluster> cluster_res = KMeans(data_set, 2, 200, threshold);
  98.     for(int i = 0; i < cluster_res.size(); ++i)
  99.     {
  100.         cout<<“Cluster “<<i<<” : “<<endl;
  101.         cout<<“\t”<<“Centroid: “;//<<endl;
  102.         cout<<“(“;
  103.         for(int j = 0; j < cluster_res[i].centroid.size()-1; ++j)
  104.             cout<< cluster_res[i].centroid[j]<<“,”;
  105.         cout<<cluster_res[i].centroid[cluster_res[i].centroid.size()-1]<<“)”<<endl;
  106.         cout<<“\t”<<“Samples: “;
  107.         for(int j = 0; j < cluster_res[i].samples.size(); ++j)
  108.         {
  109.             int c = cluster_res[i].samples[j];
  110.             cout<<“(“;
  111.             for(int m = 0; m < col-1; ++m)
  112.                 cout<<data_set[c][m]<<“,”;
  113.             cout<<data_set[c][col-1]<<“)  “;
  114.         }
  115.         cout<<endl;
  116.     }
  117.     return 0;
  118. }
  119. /**
  120. 1 1
  121. 2 1
  122. 1 2
  123. 2 2
  124. 3 3
  125. 8 8
  126. 8 9
  127. 9 8
  128. 9 9
  129. */

Leave a Reply

Your email address will not be published. Required fields are marked *