聚类算法与K-means实现

聚类算法与K-means实现

一、聚类算法的数学描述:

区别于监督学习的算法(回归,分类,预测等),无监督学习就是指训练样本的 label 未知,只能通过对无标记的训练样本的学习来揭示数据的内在规律和性质。无监督学习任务中研究最多的就是聚类算法(clustering)。我们假定一个样本集:

编号 色泽 根蒂 敲声 纹理 脐部 触感 密度 含糖率 好瓜
1 青绿 蜷缩 浊响 清晰 凹陷 硬滑 0.697 0.46
2 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 0.774 0.376
3 乌黑 蜷缩 浊响 清晰 凹陷 硬滑 0.634 0.264
4 青绿 蜷缩 沉闷 清晰 凹陷 硬滑 0.608 0.318
5 浅白 蜷缩 浊响 清晰 凹陷 硬滑 0.556 0.215

该样本集中包含5个样本数据,聚类算法的目的就是将这 5 个样本划分为互不相交的子集,每个子集被称为一个簇。比如,我们以色泽对样本进行划分,可以得到3个簇,分别为:\(\lambda_{1} = \{1,4\}, \lambda_{2} = \{2,3\},\lambda_{3} = \{5\}\)。值得说明的是,在实际的聚类过程中,没有 “色泽” 的概念,聚类过程仅仅能自动形成簇结构,而簇所对应的概念语义是人为赋予的。用数学语言描述上述过程:

假设样本集 \(D=\{x_{1},x_{2},...,x_{m}\}\) 包含 \(m\) 个无标记样本,每个样本由 \(n\) 维特征来描述,即 \(x_{i} = \{x_{i1},x_{i2},...x_{in}\}\) 。那么聚类算法的目的就是将样本集 \(D\) 划分为 \(k\) 个不相交的簇:\(D = \bigcup_{l=1}^{k} C_{l}\),且 \(C_{i} \bigcap C_{j} = \phi,\forall i\neq j\)。我们用 \(\lambda = \{\lambda_{1}, \lambda_{2},...\lambda_{k}\}\) 来代表 \(k\) 个簇的标记,因此第 \(j\) 个簇的所有元素可以标记为 \(C_{\lambda_{j}}\) 。对应上述过程,\(m=5, k=3, \lambda=\{青绿,乌黑,浅白\}\)。

二、聚类算法的度量

每一个样本可能有 \(n\) 个特征描述,那么有没有一个度量标准来判断聚类算法的好坏呢?其中一个最重要的原则就是:相同簇的样本尽可能相似,不同簇的样本尽可能不同。聚类的性能度量有两类:1)将聚类结果与某个参考模型进行比较,称为外部指标;2)直接考察聚类结果而步利用任何参考模型,称为内部指标。

2.1 外部指标法:

对数据集 \(D=\{x_{1},x_{2},...,x_{m}\}\) ,假设通过聚类给出的簇划分为 \(C = \{C_{1}, C_{2},...,C_{k}\}\),而参考模型给出的簇划分为\(C^{*} = \{C_{1}^{*}, C_{2}^{*},...,C_{s}^{*}\}\)。相应地,用 \(\lambda,\lambda^{*}\) 来分别表示与 \(C, C^{*}\) 对应的标记向量,于是我们定义如下:

\[a = |SS|,\quad SS = \{(x_{i},x_{j}) | \lambda_{i} = \lambda_{j}, \lambda_{i}^{*} = \lambda_{j}^{*}\} \\ b = |SD|,\quad SD = \{(x_{i},x_{j}) | \lambda_{i} = \lambda_{j}, \lambda_{i}^{*} \ne \lambda_{j}^{*}\} \\ c = |DS|,\quad DS = \{(x_{i},x_{j}) | \lambda_{i} \ne \lambda_{j}, \lambda_{i}^{*} = \lambda_{j}^{*}\} \\ d = |DD|,\quad DD = \{(x_{i},x_{j}) | \lambda_{i} \ne \lambda_{j}, \lambda_{i}^{*} \ne \lambda_{j}^{*}\} \\ \]

刚一看到上述公式会感觉有点懵,那么我们来直观地感受一下上述表达式描述的是什么。以 \(a\) 为例,\(SS\) 代表在 \(C\) 中属于同一类且在 \(C^{*}\) 中属于同一类的样本,那么 \(a\) 就等于 \(SS\) 中样本的个数。以此类推,\(b\) 代表在 \(C\) 中属于同一类,而在 \(C^{*}\) 中属于不同类的样本个数;\(c\) 代表在 \(C\) 中属于不同类,而在 \(C^{*}\) 中属于同一类的样本个数;\(d\) 代表在 \(C\) 中属于不同类,而在 \(C^{*}\) 中也属于不同类的样本个数。看到这,有没有类似于评价指标中的精准率,召回率?https://www.cnblogs.com/zhaozhibo/p/14954685.html。由于每个样本对 \((x_{i},x_{j})\) 只能出现在一个集合中,因此:\(a+b+c+d = m(m-1)/2\)。基于此,我们给出几个常用的聚类性能度量外部指标:

  1. Jaccard系数(JC系数):\(JC = \dfrac{a}{a+b+c}\)
  2. Rand指数(RI指数):\(RI = (a+d)/\dfrac{m(m-1)}{2} = \dfrac{2(a+d)}{m(m-1)}\)
  3. FM指数(FMI):\(FMI = \sqrt{\dfrac{a}{a+b}\times \dfrac{a}{a+c}}\)

其实不难理解,JC系数描述的是分类正确的样本数占总样本数的比例,RI指数描述的是分类正确(正样本和负样本)的个数占总的样本比例,FMI描述的是分类正确占 “分类正确+分类错误” 的比例。因此这三个指标都是在 \([0,1]\),且越大越好。

2.2 内部指标法:

仅仅考虑聚类结果的划分:\(C = \{C_{1}, C_{2},...,C_{k}\}\),定义:

\[avg(C) = \dfrac{2}{|C|(|C|-1)}\sum_{1\le i<j \le |C|}dist(x_{i},x_{j}) \\ diam(C) = max_{1\le i<j \le |C|}dist(x_{i},x_{j}) \\ d_{min}(C_{i},C_{j}) = min_{x_{i}\in C_{i}, x_{j} \in C_{j}} dist(x_{i},x_{j}) \\ d_{cen}(C_{i},C_{j})= dist(u_{i}, u_{j}) \]

其中,\(dist(\cdot,\cdot)\) 计算两个向量之间的距离,定义为:

\[dist(x_{i},x_{j}) = (\sum_{u=1}^{n}(|x_{iu}-x_{ju}|^{p})^{\dfrac{1}{p}}) \]

  1. 当 \(p=1\) 时,等效为曼哈顿距离:\(dist(x_{i},x_{j}) = (\sum_{u=1}^{n}(|x_{iu}-x_{ju}|^{}))\)
  2. 当 \(p=2\) 时,等效为欧氏距离:\(dist(x_{i},x_{j}) = \sqrt{(\sum_{u=1}^{n}(|x_{iu}-x_{ju}|^{2}))}\)

\(u_{i}\) 代表第 \(i\) 个簇的中心点,即:\(u_{i} = \dfrac{1}{|C_{i}|}\sum_{i=1}^{|C_{i}|} x_{i}\)。显然,\(avg(C)\) 代表簇 \(C\) 中任意两个样本距离的平均值,\(diam(C)\) 代表簇 \(C\) 内任意两个样本之间距离的最大值,\(d_{min}(C_{i},C_{j})\) 代表不同的簇中最近的两个样本之间的距离,\(d_{cen}(C_{i},C_{j})\) 代表不同簇中心点之间的距离。根据我们 “相同簇的样本尽可能相似,不同簇的样本尽可能不同” 的原则,\(avg(C_{i})\) 越小越好,而 \(d_{cen}(C_{i},C_{j})\) 越大越好;\(d_{min}(C_{i},C_{j})\) 越大越好,\(diam(C)\) 越小越好。因此我们有如下的内部度量指标:

  1. DB指数:\(DBI = \dfrac{1}{k}\sum_{i=1}^{k}max(\dfrac{avg(C_{i})+avg(C_{j})}{d_{cen}(C_{i},C_{j})})\)
  2. Dunn指数:\(min\{min\{ \dfrac{d_{min}(C_{i}, C_{j})}{max_{1 \le l \le k}diam(C_{l})}\}\}\)

显然,DB越小越好,而DI越大越好。

三、K-means聚类算法的实现

3.1 算法描述

给定样本集 \(D=\{x_{1},x_{2},...,x_{m}\}\) ,“K 均值” 算法针对聚类所得簇划分 \(C = \{C_{1}, C_{2},...,C_{k}\}\) 最小化平方误差:

\[E = \sum_{i=1}^{k}\sum_{x \in C_{i}}||x-u_{i}||_{2}^{2} \]

其中,\(u_{i}\) 是簇 \(C_{i}\) 的均值向量,于是 \(E\) 描述了簇内样本围绕簇均值向量的紧密程度,\(E\) 值越小,则簇内样本的相似度越高。但是优化起来并不容易,需要考虑样本集 \(D\) 的所有可能的簇划分,因此 \(k\) 均值采取了贪心策略,通过迭代优化来近似求解。具体的流程如下:

  1. 从样本集中随机选取 \(k\) 个向量作为初始均值向量 \(\{u_{1}, u_{2}, ..., u_{k}\}\),且簇 \(C_{i}\) 设置为空;
  2. 分别计算将所有的样本与初始均值向量 \(\{u_{1}, u_{2}, ..., u_{k}\}\) 的距离,将与 \(u_{i}\) 最小距离的样本 \(x_{j}\) 划分入 \(C_{i}\),并以此类推得到第一轮的迭代结果
  3. 重新更新簇 \(C_{i}\) 的均值,\(\{u_{1}^{'}, u_{2}^{'}, ..., u_{k}^{'}\}\),然后重复步骤2
  4. 直到下一轮与上一轮的结果相同,停止更新

3.2 代码实现

# k-means cluster 
def kmeans(dataSet, k): 
    numSamples = dataSet.shape[0] 
    # first column stores which cluster this sample belongs to, 
    # second column stores the error between this sample and its centroid 
    clusterAssment = mat(zeros((numSamples, 2))) 
    clusterChanged = True 
 
    ## step 1: init centroids 
    centroids = initCentroids(dataSet, k) 
    while clusterChanged: 
        clusterChanged = False 
        ## for each sample 
        for i in xrange(numSamples): 
            minDist  = 100000.0 
            minIndex = 0 
            ## for each centroid 
            ## step 2: find the centroid who is closest 
            for j in range(k): 
                distance = euclDistance(centroids[j, :], dataSet[i, :]) 
                if distance < minDist: 
                    minDist  = distance 
                    minIndex = j 
             
            ## step 3: update its cluster 
            if clusterAssment[i, 0] != minIndex: 
                clusterChanged = True 
                clusterAssment[i, :] = minIndex, minDist**2 
 
        ## step 4: update centroids 
        for j in range(k): 
            pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]] 
            centroids[j, :] = mean(pointsInCluster, axis = 0) 
 
    print 'Congratulations, cluster complete!' 
    return centroids, clusterAssment 
上一篇:【题解】ABC224G - Roll or Increment


下一篇:题解 P1297 [国家集训队]单选错位