前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >机器学习 学习笔记（13）聚类

机器学习 学习笔记（13）聚类

作者头像
丹
发布于 2018-09-04 10:37:08
9240
发布于 2018-09-04 10:37:08
举报
文章被收录于专栏：WD学习记录WD学习记录

在无监督学习中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础，此类学习任务中研究最多、应用最广的是聚类。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个簇。

聚类技能作为一个单独过程，用于找寻数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。

聚类算法涉及的两个基本问题：性能度量和距离计算

聚类性能度量亦成为有效性指标，与监督学习中的性能度量作用相似，对聚类结果，需要通过某种性能度量来评估其好坏，另一方面，若明确了最终将要使用的性能度量，则可以直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。

聚类结果的“簇内相似度”高且“簇间相似度低”。

聚类性能度量大致有两类，一类是将聚类结果与某个“参考模型”进行比较，称为外部指标；另一类是直接考场聚类结果而不利用任何参考模型，称为内部指标。

对数据集

D=\{x_1,x_2,...,x_m\}
D=\{x_1,x_2,...,x_m\}

，假定通过聚类给出的簇划分为

C=\{C_1,C_2,...,C_k\}
C=\{C_1,C_2,...,C_k\}

，参考模型给出的簇划分为

C^*=\{C^*_1,C^*_2,...,C^*_s\}
C^*=\{C^*_1,C^*_2,...,C^*_s\}

。相应的，令

\lambda
\lambda

与

\lambda ^*
\lambda ^*

分别表示C和

C^*
C^*

对应的簇标记向量，将样本两两配对考虑，定义：

a=|SS|,SS=\{(x_i,x_j)|\lambda _i=\lambda _j,\lambda _i^*=\lambda _j^*,i<j\}
a=|SS|,SS=\{(x_i,x_j)|\lambda _i=\lambda _j,\lambda _i^*=\lambda _j^*,i<j\}
b=|SD|,SD=\{(x_i,x_j)|\lambda _i=\lambda _j,\lambda _i^*\neq \lambda _j^*,i<j\}
b=|SD|,SD=\{(x_i,x_j)|\lambda _i=\lambda _j,\lambda _i^*\neq \lambda _j^*,i<j\}
c=|DS|,DS=\{(x_i,x_j)|\lambda _i\neq \lambda _j,\lambda _i^*=\lambda _j^*,i<j\}
c=|DS|,DS=\{(x_i,x_j)|\lambda _i\neq \lambda _j,\lambda _i^*=\lambda _j^*,i<j\}
d=|DD|,DD=\{(x_i,x_j)|\lambda _i\neq \lambda _j,\lambda _i^*\neq \lambda _j^*,i<j\}
d=|DD|,DD=\{(x_i,x_j)|\lambda _i\neq \lambda _j,\lambda _i^*\neq \lambda _j^*,i<j\}

其中集合SS包含了在C中属于相同簇且在

C^*
C^*

属于相同簇的样本对。

有下面这些外部性能度量指标：

Jaccard系数（Jaccard Coefficient，JC）：

JC=\frac{a}{a+b+c}
JC=\frac{a}{a+b+c}

Jaccard系数刻画了所有属于同一类的样本对（要么在C中属于同一类，要么在

C^*
C^*

中属于同一类），同时在C，

C^*
C^*

中属于同一类的样本量的比值

FM指数（Fowlkes and Mallows Index, FMI）:

FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}
FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}

FM指数刻画的是在C中属于同一类的样本对中，同时属于

C^*
C^*

的样本对的比例为P1，在

C^*
C^*

中属于同一类的样本对同时属于C的样本对的比例为P2，FMI就是P1与P2的几何平均。

Rand指数（Rand Index, RI）:

RI=\frac{2(a+d)}{m(m-1)}
RI=\frac{2(a+d)}{m(m-1)}

RI刻画的是同时隶属于C，

C^*
C^*

的样本对于同时不隶属于C，

C^*
C^*

的样本对之和占所有样本对的比例。

ARI指数（Adjusted Rand Index）：

ARI=\frac{RI-E[RI]}{max(RI)-E[RI]}
ARI=\frac{RI-E[RI]}{max(RI)-E[RI]}

使用RI时存在一个问题，就是对于随机聚类，RI不保证接近0，可能还会很大，而ARI指数可以利用随机情况下的RI即

E[RI]
E[RI]

来解决这个问题。

上述性能度量的结果值均在[0,1]区间，值越大越好。

考虑聚类结果的簇划分

C=\{C_1,C_2,...,C_k\}
C=\{C_1,C_2,...,C_k\}

，定义

avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1\leqslant i\leqslant j\leqslant |C|} dist(x_i,x_j)
avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1\leqslant i\leqslant j\leqslant |C|} dist(x_i,x_j)
diam(C)=max_{1\leqslant i\leqslant j\leqslant |C|}dist(x_i,x_j)
diam(C)=max_{1\leqslant i\leqslant j\leqslant |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_{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(\mu _i,\mu _j)
d_{cen}(C_i,C_j)=dist(\mu _i,\mu _j)

上面四个式子分别计算了簇C内样本间平均距离，簇C样本间最远距离，簇Ci和Cj最近样本间距离，簇Ci和Cj中心点间的距离。

可以导出下面这些常用的聚类性能度量内部指标：

DB指数（Davies-Bouldin Index, DBI）:

DBI=\frac{1}{k}\sum_{i=1}^k \max_{j \neq i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})
DBI=\frac{1}{k}\sum_{i=1}^k \max_{j \neq i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})

DB指数刻画的是给定两个簇，每个簇样本之间的平均值之和比上两个簇的中心点之间的距离作为度量，然后考察该度量对所有簇的平均值，显然DBI越小越好，如果每个簇样本之间的平均值很小，则DBI很小，如果两个簇间中心店距离越大，DBI越小。

Dunn指数（Dunn Index,DI）:

DI=\min_{1\leqslant i\leqslant k}\{\min_{j \neq i}(\frac{d_{min}(C_i,C_j)}{max_{1\leqslant l\leqslant k diam(C_l)}})\}
DI=\min_{1\leqslant i\leqslant k}\{\min_{j \neq i}(\frac{d_{min}(C_i,C_j)}{max_{1\leqslant l\leqslant k diam(C_l)}})\}

Dunn指数刻画的是任意两个簇之间最近的距离的最小值除以人一个簇内距离最远的两个点的距离最大值，DI越大越好，如果簇间最近的距离最小值越大，DI越大，如果任意一个簇内距离最远的两个点的距离的最大值越小，则DI越大。

距离计算需要满足的基本性质：

  • 非负性
  • 同一性，当且仅当两点相同时，距离为0
  • 对称性
  • 直递性（三角不等式）

闵可夫斯基距离用于有序属性：

dist_{mk}(x_i,x_j)=(\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}}
dist_{mk}(x_i,x_j)=(\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}}

对于无序属性可采用VDM(Value Difference Metric)，令

m_{u,a}
m_{u,a}

表示在属性u上取值为a的样本数，

m_{u,a,i}
m_{u,a,i}

表示在第i个样本簇中在属性u上取值为a的样本数，k为样本簇数，则属性u上两个离散值a与b的VDM距离为：

VDM_p(a,b)=\sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}- \frac{m_{u,b,i}}{m_{u,b}}|^p
VDM_p(a,b)=\sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}- \frac{m_{u,b,i}}{m_{u,b}}|^p

将闵可夫斯基距离和VDM结合即可处理混合属性，假定有

n_c
n_c

个有序属性，

n-n_c
n-n_c

个无序属性，不失一般性，令有序属性排在无序属性之前，则：

MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^n VDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}
MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^n VDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}

当样本空间中不同属性的重要性不同时，可使用加权距离。

原型聚类

原型是指样本空间中有代表性的点。

原型聚类假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示，将产生不同的算法。

代码如下：

代码语言：javascript
复制
# 代码主要来源于机器学习实战
from numpy import *

def loadDataSet(fileName):
    dataMat=[]
    fr=open(fileName)
    for line in fr.readlines():
        curLine=line.strip().split('\t')
        fltLine=list(map(float,curLine))
        dataMat.append(fltLine)
    return  dataMat

# 计算两个向量的欧式距离
def distEclud(vecA,vecB):
    return sqrt(sum(power(vecA-vecB,2)))

def randCent(dataSet,k):
    n=shape(dataSet)[1]
    centroids=mat(zeros((k,n)))
    # 构建簇质心
    for j in range(n):
        minJ=min(dataSet[:,j])
        rangeJ=float(max(dataSet[:,j])-minJ)
        centroids[:,j]=minJ+rangeJ*random.rand(k,1)
    return centroids

# k-均值聚类算法
# 4个输入参数，只有数据集合簇的数目是必须的
# 用来计算距离和创建初始质心的函数都是可选的
# 一开始确定数据集中数据点的总数，然后创建一个矩阵来存储每个点的分配结果。
# 簇分配结果矩阵clusterAssment包含两列，一列记录索引值，第二列存储误差
# 这里的误差是指当前点到簇质心的举例
# 后面会用该误差来评价聚类的效果
#
def kMeans(dataSet,k,distMeas=distEclud,createCent=randCent):
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))
    centroids=createCent(dataSet,k)
    clusterChanged=True
    while clusterChanged:
        clusterChanged=False
        for i in range(m):
            minDist=inf
            minIndex=-1
            for j in range(k):
                distJI=distMeas(centroids[j,:],dataSet[i,:])
                if distJI<minDist:
                    minDist=distJI
                    minIndex=j
            if clusterAssment[i,0]!=minIndex:clusterChanged=True
            clusterAssment[i,:]=minIndex
            minDist**2
        print(centroids)
        for cent in range(k):
            ptsInClust=dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:]=mean(ptsInClust,axis=0)
    return centroids,clusterAssment

K-均值算法：

给定样本集

D=\{x_1,x_2,...,x_m\}
D=\{x_1,x_2,...,x_m\}

，k均值算法针对聚类所得簇划分

C=\{C_1,C_2,...,C_k\}
C=\{C_1,C_2,...,C_k\}

最小化平方误差：

E=\sum_{i=1}^k\sum_{x\in C_i}||x-\mu_i||^2_2
E=\sum_{i=1}^k\sum_{x\in C_i}||x-\mu_i||^2_2

，其中

\mu_i
\mu_i

是簇

C_i
C_i

的均值向量。

E=\sum_{i=1}^k\sum_{x\in C_i}||x-\mu_i||^2_2
E=\sum_{i=1}^k\sum_{x\in C_i}||x-\mu_i||^2_2

在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度。

学习向量量化：

学习向量量化（learning vector quantization，LVQ）也是试图找到一组原型向量来刻画聚类结构，但与一般聚类算法不同的是，LVQ假设数据样本带有类别标记，学习过程中利用样本的这些监督信息来辅助聚类。

给定样本集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}
D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，每个样本

x_j
x_j

是由n个属性描述得特征向量

(x_{j1},x_{j2},...,x_{jn})
(x_{j1},x_{j2},...,x_{jn})

，

y_j\in y
y_j\in y

是样本

x_j
x_j

的标记，。LVQ的目标是学得一组n维原型向量

\{p_1,p_2,...,p_q\}
\{p_1,p_2,...,p_q\}

，每个原型向量代表一个聚类簇标记

t_i \in y
t_i \in y

算法描述如下：

输入：样本集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}
D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，原型向量个数q，各原型向量预设的类别标记

\{t_1,t_2,...,t_q\}
\{t_1,t_2,...,t_q\}

。学习率

\eta \in (0,1)
\eta \in (0,1)

过程：

初始化一组原型向量

\{p_1,p_2,...,p_q\}
\{p_1,p_2,...,p_q\}

repeat

    从样本集D随机选取样本

(x_j,y_j)
(x_j,y_j)

    计算样本

x_j
x_j

与

p_i
p_i

的距离，

d_{ij}=||x_j-p_i||_2
d_{ij}=||x_j-p_i||_2

    找出与

x_j
x_j

距离最近的原型向量

p_{i^*}
p_{i^*}

，

i^*=arg min_{i \in \{1,2,...,q\}} d_{ij}
i^*=arg min_{i \in \{1,2,...,q\}} d_{ij}

    if 

y_j=t_{i^*}
y_j=t_{i^*}

 then

p'=p_{i^*}+\eta \cdot (x_j-p_{i^*})
p'=p_{i^*}+\eta \cdot (x_j-p_{i^*})

    else

p'=p_{i^*}-\eta \cdot (x_j-p_{i^*})
p'=p_{i^*}-\eta \cdot (x_j-p_{i^*})

    end if

    将原型向量

p_{i^*}
p_{i^*}

更新为

p'
p'

until 满足停止条件

输出：原型向量

\{p_1,p_2,...,p_q\}
\{p_1,p_2,...,p_q\}

代码如下：

代码语言：javascript
复制
# https://github.com/AnnDWang/MachineLearning/blob/master/secondbook/Clustering/LVQ1.py
# -*- coding:utf-8 -*-
import numpy as np

# lvq 学习向量量化聚类
# 自己按照书上的方法实现的lvq 学习向量量化
# 但是停止条件没有去判断均值向量的更新，而是选择了一定的迭代次数

dataSet = [
        # 1
        [0.697, 0.460,1],
        # 2
        [0.774, 0.376,1],
        # 3
        [0.634, 0.264,1],
        # 4
        [0.608, 0.318,1],
        # 5
        [0.556, 0.215,1],
        # 6
        [0.403, 0.237,1],
        # 7
        [0.481, 0.149,1],
        # 8
        [0.437, 0.211,1],
        # 9
        [0.666, 0.091,0],
        # 10
        [0.243, 0.267,0],
        # 11
        [0.245, 0.057,0],
        # 12
        [0.343, 0.099,0],
        # 13
        [0.639, 0.161,0],
        # 14
        [0.657, 0.198,0],
        # 15
        [0.360, 0.370,0],
        # 16
        [0.593, 0.042,0],
        # 17
        [0.719, 0.103,0],
        # 18
        [0.359, 0.188,0],
        # 19
        [0.339, 0.241,0],
        # 20
        [0.282, 0.257,0],
        # 21
        [0.748, 0.232,0],
        # 22
        [0.714, 0.346,1],
        # 23
        [0.483, 0.312,1],
        # 24
        [0.478, 0.437,1],
        # 25
        [0.525, 0.369,1],
        # 26
        [0.751, 0.489,1],
        # 27
        [0.532, 0.472,1],
        # 28
        [0.473, 0.376,1],
        # 29
        [0.725, 0.445,1],
        # 30
        [0.446, 0.459,1],
    ]

# 特征值列表
labels = ['密度', '含糖率']

def lvq(dataset,k,itera_nums,learnrate):
    # k为聚类的数目
    m, n = np.shape(dataset)
    # n为样本特征数目

    # 创建k个随机向量作为原型向量
    mean_dots = {}
    for i in range(0, k):
        temp = np.random.random((1, n))
        mean_dots[i] = temp[0]
    # 确定聚类中心以后，判断每个元素所属的簇
    for itera_num in range(0, itera_nums):
        print('当前迭代次数为：' + str(itera_num))
        # 创建k个簇
        classes_dic = {}
        for k in mean_dots:
            classes_dic[k] = []
        for data in dataset:
            # 计算每个值距离初始中心点的距离
            temp_distance_dict = []
            for j in mean_dots:
                dots = mean_dots[j]
                distance = np.sqrt(
                    (data[0] - dots[0]) * (data[0] - dots[0]) + (data[1] - dots[1]) * (data[1] - dots[1]))
                temp_distance_dict.append((distance, j))
            temp_distance_dict.sort()
            # 所属的分类为
            label = temp_distance_dict[0][1]
            # 当前数据的实际分类为
            real_label=data[2]
            print('第' + str(label) + '个簇当前旧的中心点为' + str(mean_dots[label]))
            if label==real_label:
                # 更新原型向量
                mean_dots[label]=mean_dots[label]+learnrate*(data-mean_dots[label])
            else:
                # 更新原型向量
                mean_dots[label] = mean_dots[label] - learnrate * (data - mean_dots[label])
            print('第' + str(label) + '个簇当前新的中心点为' + str(mean_dots[label]))

        return mean_dots

prototype_vectors=lvq(dataSet,3,10,0.1)

print('最后的原型向量为' + str(prototype_vectors))

高斯混合聚类：

高斯混合聚类采用概率模型来表达聚类原型。对n维样本空间中的随机向量x，若x服从高斯分布，则其概率密度函数为：

p(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma |^{\frac{1}{2}}}e^{-\frac{1}{2}(x-\mu)^T\Sigma ^{-1}(x-\mu)}
p(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma |^{\frac{1}{2}}}e^{-\frac{1}{2}(x-\mu)^T\Sigma ^{-1}(x-\mu)}

，

\mu
\mu

是n维均值向量，

\Sigma
\Sigma

是nxn的协方差矩阵，高斯分布完全由

\mu
\mu

和

\Sigma
\Sigma

确定，为了明确显示高斯分布与相应参数的依赖关系，将概率密度函数记为

p(x|\mu,\Sigma )
p(x|\mu,\Sigma )

。

定义高斯混合分布为：

p(x)=\sum_{i=1}^k \alpha _i\cdot p(x|\mu_i,\Sigma _i)
p(x)=\sum_{i=1}^k \alpha _i\cdot p(x|\mu_i,\Sigma _i)

该分布共由k个混合成分组成，每个混合成分对应一个高斯分布，其中

\mu_i
\mu_i

和

\Sigma _i
\Sigma _i

是第i个高斯混合成分的参数，

\alpha _i>0
\alpha _i>0

为相应的混合系数，

\sum_{i=1}^k\alpha _i=1
\sum_{i=1}^k\alpha _i=1

。

若训练集

D=\{x_1,x_2,...,x_m\}
D=\{x_1,x_2,...,x_m\}

由上述过程生成，令随机变量

z_j \in\{1,2,...,k\}
z_j \in\{1,2,...,k\}

表示生成样本

x_j
x_j

的高斯混合成分，其取值位置，显然

z_j
z_j

的先验概率

P(z_j=i)
P(z_j=i)

对应于

\alpha _i(i=1,2,...,k)
\alpha _i(i=1,2,...,k)

，根据贝叶斯定理，

z_j
z_j

的后验分布对应于：

p(z_j=i|x_j)=\frac{P(z_j=i)\cdot p(x_j|z_i=i)}{p(x_j)}=\frac{\alpha _i\cdot p(x_j|\mu_i,\Sigma _i)}{\sum_{l=1}^k\alpha _l\cdot p(x_j|\mu _l,\Sigma _l)}
p(z_j=i|x_j)=\frac{P(z_j=i)\cdot p(x_j|z_i=i)}{p(x_j)}=\frac{\alpha _i\cdot p(x_j|\mu_i,\Sigma _i)}{\sum_{l=1}^k\alpha _l\cdot p(x_j|\mu _l,\Sigma _l)}

。

p(z_j=i|x_j)
p(z_j=i|x_j)

给出了样本

x_j
x_j

由第

i
i

个高斯混合成分生成的后验概率，将其简记

\gamma _{ji}(i=1,2,...,k)
\gamma _{ji}(i=1,2,...,k)

。

当高斯混合分布已知时，高斯混合聚类将把样本集D划分为k个簇

C=\{C_1,C_2,...,C_k\}
C=\{C_1,C_2,...,C_k\}

，每个样本

x_j
x_j

的簇标记

\lambda _j
\lambda _j

由如下确定：

\lambda _j=\arg \max \limits_{i\in \{1,2,...,k\}} \gamma _{ji}
\lambda _j=\arg \max \limits_{i\in \{1,2,...,k\}} \gamma _{ji}

从原型聚类的角度来看，高斯混合聚类是采用概率模型（高斯分布）对原型进行刻画，簇划分则由原型对应后验概率确定。

高斯混合聚类算法如下所示：

输入：样本集

D=\{x_1,x_2,...,x_m\}
D=\{x_1,x_2,...,x_m\}

，高斯混合成分个数k

过程：

初始化高斯混合分布的模型参数

\{(\alpha _i,\mu_i,\Sigma _i)|1\leqslant i\leqslant k\}
\{(\alpha _i,\mu_i,\Sigma _i)|1\leqslant i\leqslant k\}

repeat

    for j=1,2,...,m do

        根据

p(z_j=i|x_j)=\frac{P(z_j=i)\cdot p(x_j|z_i=i)}{p(x_j)}=\frac{\alpha _i\cdot p(x_j|\mu_i,\Sigma _i)}{\sum_{l=1}^k\alpha _l\cdot p(x_j|\mu _l,\Sigma _l)}
p(z_j=i|x_j)=\frac{P(z_j=i)\cdot p(x_j|z_i=i)}{p(x_j)}=\frac{\alpha _i\cdot p(x_j|\mu_i,\Sigma _i)}{\sum_{l=1}^k\alpha _l\cdot p(x_j|\mu _l,\Sigma _l)}

计算各混合成分生成的后验概率，即

\gamma _{ji}=p(z_j=i|x_j)(1\leqslant i\leqslant k)
\gamma _{ji}=p(z_j=i|x_j)(1\leqslant i\leqslant k)

    end for

    for i=1,2,...,k do

        计算新均值向量：

\mu'=\frac{\sum_{j=1}^m\gamma _{ji}x_j}{\sum_{j=1}^m\gamma _{ji}}
\mu'=\frac{\sum_{j=1}^m\gamma _{ji}x_j}{\sum_{j=1}^m\gamma _{ji}}

        计算新协方差矩阵：

\Sigma '_i=\frac{\sum_{j=1}^m\gamma _{ji}(x_j-\mu'_i)(x_j-\mu'_i)^T}{\sum_{j=1}^m\gamma _{ji}}
\Sigma '_i=\frac{\sum_{j=1}^m\gamma _{ji}(x_j-\mu'_i)(x_j-\mu'_i)^T}{\sum_{j=1}^m\gamma _{ji}}

        计算新混合系数

\alpha '_i=\frac{\sum_{j=1}^m\gamma _{ji}}{m}
\alpha '_i=\frac{\sum_{j=1}^m\gamma _{ji}}{m}

    end for

    将模型参数

\{(\alpha_i,\mu _i,\Sigma _i|1\leqslant i\leqslant k)\}
\{(\alpha_i,\mu _i,\Sigma _i|1\leqslant i\leqslant k)\}

更新为

\{(\alpha'_i,\mu' _i,\Sigma' _i|1\leqslant i\leqslant k)\}
\{(\alpha'_i,\mu' _i,\Sigma' _i|1\leqslant i\leqslant k)\}

until 满足停止条件

C_i=\varnothing (1\leqslant i\leqslant k)
C_i=\varnothing (1\leqslant i\leqslant k)

for j=1,2,..,m do 

    根据

\lambda _j=\arg \max \limits_{i\in \{1,2,...,k\}} \gamma _{ji}
\lambda _j=\arg \max \limits_{i\in \{1,2,...,k\}} \gamma _{ji}

确定

x_j
x_j

的簇标记

\lambda _j
\lambda _j

    将

x_j
x_j

划入相应的簇：

C_{\lambda _j}=C_{\lambda _j}\cup \{x_j\}
C_{\lambda _j}=C_{\lambda _j}\cup \{x_j\}

end for

输出：簇划分

C=\{C_1,C_2,...,C_k\}
C=\{C_1,C_2,...,C_k\}

密度聚类

基于密度的聚类（density-based clustering），假设聚类结构能够通过样本分布的紧密程度确定，通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本的不断扩展聚类簇以获得最终结果。

DBSCAN是一种著名的密度聚类算法，基于一组领域（neighborhood）参数来刻画样本分布的紧密程度。给定数据集

D=\{x_1,x_2,...,x_m\}
D=\{x_1,x_2,...,x_m\}

，定义以下概念：

\epsilon -
\epsilon -

领域：对

x_j\in D
x_j\in D

，其

\epsilon -
\epsilon -

领域包含样本集D中与

x_j
x_j

的距离不大于

\epsilon
\epsilon

的样本，即

N_\epsilon (x_j)=\{x_j\in D|dist(x_j,x_j)\leqslant \epsilon \}
N_\epsilon (x_j)=\{x_j\in D|dist(x_j,x_j)\leqslant \epsilon \}
  • 核心对象：若
x_j
x_j

的

\epsilon -
\epsilon -

领域至少包含MinPts个样本，即

|N_\epsilon(x_j) |\geqslant MinPts
|N_\epsilon(x_j) |\geqslant MinPts

，则

x_j
x_j

是一个核心对象。

  • 密度直达：若
x_j
x_j

位于

x_i
x_i

的

\epsilon -
\epsilon -

领域中，且

x_i
x_i

是核心对象，则称

x_j
x_j

由

x_i
x_i

密度直达

  • 密度可达：对
x_i
x_i

与

x_j
x_j

，若存在样本序列

p_1,p_2,....,p_n
p_1,p_2,....,p_n

，其中

p_1=x_i,p_n=x_j
p_1=x_i,p_n=x_j

且

p_{i+1}
p_{i+1}

由

p_i
p_i

密度直达，则称

x_j
x_j

有

x_i
x_i

密度可达

  • 密度相连：对
x_i
x_i

与

x_j
x_j

，若存在

x_k
x_k

使得

x_i
x_i

与

x_j
x_j

均由

x_k
x_k

密度可达，则成

x_i
x_i

与

x_j
x_j

密度相连

基于这些概念，DBSCAN将簇定义为：有密度可达关系导出的最大的密度相连样本集合，形式化而言，给定领域参数

(\epsilon ,MinPts)
(\epsilon ,MinPts)

，簇

C\subseteq D
C\subseteq D

是满足以下性质的非空样本子集：

  • 连接性：
x_i\in C,x_j \in C
x_i\in C,x_j \in C

则

x_i
x_i

与

x_j
x_j

密度相连

  • 最大性：
x_i \in C
x_i \in C

,

x_j
x_j

由

x_i
x_i

密度可达，则

x_j \in C
x_j \in C

DBSCAN算法描述如下：

输入：样本集

D=\{x_1,x_2,...,x_m\}
D=\{x_1,x_2,...,x_m\}

，领域参数

(\epsilon ,MinPts)
(\epsilon ,MinPts)

过程：

初始化核心对象集合，

\Omega =\varnothing
\Omega =\varnothing

for j=1,2,...,m do

    确定样本

x_j
x_j

的

\epsilon
\epsilon

-领域

N_{\epsilon }(x_j)
N_{\epsilon }(x_j)

    if 

|N_{\epsilon }(x_j)|\geqslant MinPts
|N_{\epsilon }(x_j)|\geqslant MinPts

 then

        将样本

x_j
x_j

加入核心对象集合：

\Omega =\Omega \cup \{x_j\}
\Omega =\Omega \cup \{x_j\}

    end if

end for 

初始化聚类簇数：

k=0
k=0

初始化未访问样本集合：

\Gamma =D
\Gamma =D

while 

\Omega =\varnothing
\Omega =\varnothing

 do

    记录当前未访问样本集合：

\Gamma _{old}=\Gamma
\Gamma _{old}=\Gamma

    随机选取一个核心对象

o\in \Omega
o\in \Omega

，初始化队列

Q=<o>
Q=<o>
\Gamma =\Gamma \setminus {o\}
\Gamma =\Gamma \setminus {o\}

    while 

Q\neq \varnothing
Q\neq \varnothing

 DO 

        取出队列Q中的首个样本q

        if 

|N_\epsilon (q)|\geqslant MinPts
|N_\epsilon (q)|\geqslant MinPts

 then

            令

\Delta =N_\epsilon (q)\cap \Gamma
\Delta =N_\epsilon (q)\cap \Gamma

            将

\Delta
\Delta

中的样本加入队列Q

\Gamma =\Gamma \setminus \Delta
\Gamma =\Gamma \setminus \Delta

        end if

    end while

    k=k+1，生成聚类簇

C_k=\Gamma _{old} \setminus \Gamma
C_k=\Gamma _{old} \setminus \Gamma
\Omega =\Omega \setminus C_k
\Omega =\Omega \setminus C_k

end while

输出：簇划分

C=\{C_1,C_2,...,C_k\}
C=\{C_1,C_2,...,C_k\}

代码如下：

代码语言：javascript
复制
# https://github.com/AnnDWang/MachineLearning/blob/master/secondbook/Clustering/DBSCAN1.py
# -*- coding:utf-8 -*-
import numpy as np

# DBSCAN聚类
# 自己按照书上的方法实现的DNSCAN 密度聚类
# 好像有点问题，在计算密度可达的所有样本部分，与书上结果不一致


dataSet = [
        # 1
        [0.697, 0.460],
        # 2
        [0.774, 0.376],
        # 3
        [0.634, 0.264],
        # 4
        [0.608, 0.318],
        # 5
        [0.556, 0.215],
        # 6
        [0.403, 0.237],
        # 7
        [0.481, 0.149],
        # 8
        [0.437, 0.211],
        # 9
        [0.666, 0.091],
        # 10
        [0.243, 0.267],
        # 11
        [0.245, 0.057],
        # 12
        [0.343, 0.099],
        # 13
        [0.639, 0.161],
        # 14
        [0.657, 0.198],
        # 15
        [0.360, 0.370],
        # 16
        [0.593, 0.042],
        # 17
        [0.719, 0.103],
        # 18
        [0.359, 0.188],
        # 19
        [0.339, 0.241],
        # 20
        [0.282, 0.257],
        # 21
        [0.748, 0.232],
        # 22
        [0.714, 0.346],
        # 23
        [0.483, 0.312],
        # 24
        [0.478, 0.437],
        # 25
        [0.525, 0.369],
        # 26
        [0.751, 0.489],
        # 27
        [0.532, 0.472],
        # 28
        [0.473, 0.376],
        # 29
        [0.725, 0.445],
        # 30
        [0.446, 0.459],
    ]

# 获取一个点的密度可达的数据
def getDensityAvaliable(center,dataset,epislon,temp):
    if center not in temp:
        temp.append(center)
    new_temp=[]
    for data in dataset:
        cur_distance=np.sqrt((center[0]-data[0])*(center[0]-data[0])+(center[1]-data[1])*(center[1]-data[1]))
        if cur_distance<=epislon and cur_distance!=0:
            if data not in temp:
                temp.append(data)
                new_temp.append(data)
    # new_temp[] 是当前点的密度直达对象
    # 遍历temp[] 获取密度可达的点
    for data in new_temp:
        cur_temp=getDensityAvaliable(data,dataset,epislon,temp)
        for cur_data in cur_temp:
            if cur_data not in temp:
                temp.append(cur_data)
    return temp

def dbscan(dataset,epislon,minpts):
    # 先获取核心对象
    center_dots=[]
    for data in dataset:
        cur_data=data
        temp_neighbors=[]
        for data1 in dataset:
            if data1!=cur_data:
                cur_distance=np.sqrt((data1[0]-cur_data[0])*(data1[0]-cur_data[0])+(data1[1]-cur_data[1])*(data1[1]-cur_data[1]))
                if cur_distance<=epislon:
                    temp_neighbors.append(data1)
        if len(temp_neighbors)>=minpts:
            center_dots.append(data)
    # 获取核心对象后，再从核心对象组中一一取出
    classes_dic={}
    i=0
    for center in center_dots:
        # 获取center点密度可达的所有点
        temp=[]
        cur_avaliable=getDensityAvaliable(center,dataset,epislon,temp)
        classes_dic[i]=cur_avaliable
        i+=1
        # 去掉核心对象在当前簇中的点
        for ca in cur_avaliable:
            if ca in center_dots:
                center_dots.remove(ca)

    return classes_dic



final_dict=dbscan(dataSet,0.11,5)

print('最终结果为：'+str(final_dict))

层次聚类

层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用自底向上聚合策略，也可采用自顶向下的分拆策略。

AGNES是一种采用自底向上聚合策略的层次聚类算法，它先将数据集中的每个样本看着一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数，这里关键是如何计算聚类簇之间的距离，实际上，每个簇是一个样本集合，因此，只需采用关于集合的某种距离即可。例如，给定聚类簇Ci和Cj，可通过下面的式子来计算距离：

最小距离：

d_{min}(C_i,C_j)=min_{x \in C_i,z\in C_j} dist(x,z)
d_{min}(C_i,C_j)=min_{x \in C_i,z\in C_j} dist(x,z)

最大距离：

d_{max}(C_i,C_j)=max_{x \in C_i,z\in C_j} dist(x,z)
d_{max}(C_i,C_j)=max_{x \in C_i,z\in C_j} dist(x,z)

平均距离：

d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{x \in C_i}\sum_{z \in C_j} dist(x,z)
d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{x \in C_i}\sum_{z \in C_j} dist(x,z)

AGNES算法描述如下：

输入：样本集

D=\{x_1,x_2,...,x_m\}
D=\{x_1,x_2,...,x_m\}

，聚类簇距离度量函数d，聚类簇数k

过程：

for j=1,2,...,m do

C_j=\{x_j\}
C_j=\{x_j\}

end for

for i=1,2,...,m do

    for j=i+1,...,m do

        M(i,j)=d(C_i,C_j)

        M(j,i)=M(i,j)

    end for

end for

设置当前聚类个数：q=m

while q>k do

    找出距离最近的两个聚类簇

C_{i^*}
C_{i^*}

和

C_{j^*}
C_{j^*}

    合并

C_{i^*}
C_{i^*}

和

C_{j^*}
C_{j^*}

：

C_{i^*}=C_{i^*}\cup C_{j^*}
C_{i^*}=C_{i^*}\cup C_{j^*}

    for j=j*+1,j*+2,...,q do

        将聚类簇

C_j
C_j

重新编号为

C_{j-1}
C_{j-1}

    end for

    删除距离矩阵M的第j*行和第j*列

    for j=1,2,...,q-1 do

M(i^*,j)=d(C_{i^*},C_j)
M(i^*,j)=d(C_{i^*},C_j)
M(j,i^*)=M(i^*,j)
M(j,i^*)=M(i^*,j)

    end for

    q=q-1

end while

输出：簇划分

C=\{C_1,C_2,...,C_k\}
C=\{C_1,C_2,...,C_k\}

使用

d_{min}
d_{min}

计算，AGNES算法为单链接

使用

d_{max}
d_{max}

计算，AGNES算法为全链接

使用

d_{avg}
d_{avg}

计算，AGNES算法为均链接

二分-KMEANS算法：

k-均值算法收敛于局部最小值，二分k-Means被提出，该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个 簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。

代码如下：

代码语言：javascript
复制
# 代码主要来源于机器学习实战，https://github.com/AnnDWang/MachineLearning/blob/master/thirdbook/ch10/kMeans.py
# 二分K-均值聚类算法
# 该函数首先创建一个矩阵来存储数据集中每个点的簇分配结果及平方误差，然后计算整个数据集的质心
# 并使用一个列表来保留所有的质心。得到上述质心之后，可以遍历数据集中所有点来计算每个点到质心的误差值
# 接下来进行while循环，该循环不停地对簇进行划分，直到得到想要的簇数目位置
# 可以通过考察簇列表中的值来获得当前簇的数目
# 然后遍历所有的簇来决定最佳的簇进行划分
# 为此需要比较划分前后的SSE，一开始将SSE设置为无穷大
# 然后遍历簇列表centList中的每一个簇
# 对每一个簇，将该簇中的所有点看成一个小的数据集ptsInCurrCluster
# 将ptsInCurrCluster输入到kMeans中进行处理，k均值算法会生成两个质心，同时给出每个簇的误差值
# 这些误差与剩余数据集的误差之和作为本次划分的误差
# 如果该划分的SSE值最小，则本次划分被保存
# 一旦决定了要划分的簇，接下来就要实际执行划分操作
# 划分操作很容易，只需要将要划分的簇中所有点的簇分配结果进行修改即可
# 当使用kMeans函数并且指定k=2时，会得到两个编号分别为1和0的结果簇
# 需要将这些簇编号修改为划分簇及新加簇的编号
# 该过程可以通过两个数组过滤器来完成，最后，新的簇分配结果被更新，新的质心被添加到centList中
def biKmeans(dataSet,k,distMeas=distEclud):
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))
    centroid0=mean(dataSet,axis=0).tolist()[0]
    centList=[centroid0]
    for j in range(m):
        clusterAssment[j,1]=distMeas(mat(centroid0),dataSet[j,:])**2
    while (len(centList)<k):
        lowestSSE=inf
        for i in range(len(centList)):
            ptsInCurrCluster=dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
            centroidMat,splitClustAss=kMeans(ptsInCurrCluster,2,distMeas)
            sseSplit=sum(splitClustAss[:,1])
            sseNotSplit=sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
            print('sseSplit, and notSplit: ',sseSplit,sseNotSplit)
            if(sseSplit+sseNotSplit)<lowestSSE:
                bestCentToSplit=i
                bestNewCents=centroidMat
                bestClustAss=splitClustAss.copy()
                lowestSSE=sseSplit+sseNotSplit
        # 更新簇分配的结果
        bestClustAss[nonzero(bestClustAss[:,0].A==1)[0],0]=len(centList)
        bestClustAss[nonzero(bestClustAss[:,0].A==0)[0],0]=bestCentToSplit
        print('the bestCentToSplit is : ', bestCentToSplit)
        print('the len of bestClusAss is: ',len(bestClustAss))
        centList[bestCentToSplit]=bestNewCents[0,:].tolist()[0]
        centList.append(bestNewCents[1,:].tolist()[0])
        clusterAssment[nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClustAss
    return mat(centList),clusterAssment

参考：

  1. 《机器学习》
  2. 《机器学习实战》
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年08月13日，如有侵权请联系 cloudcommunity@tencent.com 删除
机器学习

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ，欢迎热爱写作的你一起参与！

机器学习
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 原型聚类
    • K-均值算法：
      • 学习向量量化：
        • 高斯混合聚类：
        • 密度聚类
        • 层次聚类
        • 二分-KMEANS算法：
          • 参考：
          领券

          腾讯云开发者

          扫码关注腾讯云开发者

          扫码关注腾讯云开发者

          领取腾讯云代金券

          热门产品

          热门推荐

          更多推荐

          Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

          深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

          腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

          Copyright © 2013 - 2024 Tencent Cloud.

          All Rights Reserved. 腾讯云 版权所有

          登录 后参与评论