聚类
将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。
聚类和分类
分类：指从数据中归纳出一种做判断的模型，对于新的数据，通过这个模型，可以给出对应的标签。（如垃圾邮件过滤，带“推销房子”词语的标注为垃圾邮件，通过训练，再有带“推销房子”词语的邮件，就判断为垃圾邮件）
聚类：将数据划分成不同区间，但是具体怎么划分的事先并不清楚，只知道每个区间内的数据具有一定的相似度，在最终结论出来之前不知道哪一类有什么特点，新数据出现时候判断与哪一类数据相似度最高，就把它归到哪一类。简单说就是把相似的东西聚在一起，而不关心这一类是什么。
K-均值算法
K-均值算法是一种聚类算法，将对象集划分为K个簇，把数据点到原型的某种距离作为优化的目标函数（原型可以理解为簇中心，最能代表簇特征的点）
算法流程
a、随机生成K个中心点
b、计算数据点到各个中心点的距离，把所有数据点归到最近的中心点所在簇
c、根据划分情况，更新所有中心点的值（中心点所在簇中所有数据点的平均值作为更新值）
d、对比上一次划分情况，如果没有数据点改变所属簇，则结束，否则重复b和c两步
1.随机生成中心点
2.把数据点归到最近的簇
3.更新中心点
4.重复2和3，直到聚类结果不再变化
全局最优和局部最优
不同中心点会得到不同的聚类结果，有时会出现局部最优的情况
不同聚类结果
显而易见，通常我们不希望出现局部最优的情况，解决该问题的关键在于中心点初始化。
解决算法
这里的损失函数是所有数据点到所属簇中心点的距离的平方和
吴恩达机器学习课程里还提到另外一种中心点选择方法——在数据集中随机找K个数据点作为初始中心点
python实现
一些支持函数
随机生成N个点
"""
随机生成N个二维点，如[2,3]
参数：
N：生成点数
maxX：X维最大值,默认最大值5
maxY：Y维最大值，默认最大值5
minX：X维最小值，默认最小值0
minY：Y维最小值，默认最小值0
decimal:生成随机数后小数位数
返回参数
pointList: 生成点列表
返回类型为数组
"""
def creatPoint(N,maxX=5,maxY=5,minX=0,minY=0,decimal=8):
pointList=[]
for i in range(N):
x=random.uniform(minX,maxX)
y=random.uniform(minY,maxY)
x=round_(x,decimal)
y=round_(y,decimal)
point=[x,y]
pointList.append(point)
return array(pointList)
用echart显示点
"""
用echart显示散点图表
参数：
centerPointList：聚类中心点列表
pointList：点列表
pointClassList：
返回参数:
无
"""
def showEchart(centerPointList,pointList,pointClassList):
s = Scatter("散点图", width=500, height=500)
cn = shape(centerPointList)[0] #centerPointList的个数
pn=shape(pointList)[0] #pointList点的个数
for i in range(cn):
s.add("中心",[center_point_list[i][0]],[center_point_list[i][1]], symbol_size=16,symbol="diamond")
for i in range(pn):
s.add(pointClassList[i],[pointList[i][0]],[pointList[i][1]])
s.render()
距离度量（二维点的欧式距离）
"""
计算点与点的距离
参数：
va，vb：点二维向量
返回参数:
dist：点的欧式距离
"""
def distEcloud(va,vb):
return sqrt(sum(power(va-vb,2)))
k-means算法
"""
kmeans函数
参数：
dataList：点
centerList：中心点
distMeas：点的欧式距离计算函数，默认为distEcloud
返回参数
classAndLoss: classAndLoss[:,0]为数组簇类，classAndLoss[:,1]为与中心点距离
"""
def kMeans(centerList,dataList):
k=shape(centerList)[0]
m=shape(dataList)[0]
classAndLoss=mat(zeros((m,2)))
ChangeFlag=True
while ChangeFlag:
ChangeFlag=False
for i in range(m): #计算每个点最近的中心簇点
minDist=inf
minClass=-1
for j in range(k):
dist=distEcloud(dataList[i],centerList[j])
if dist<minDist:
minDist=dist
minClass=j
if classAndLoss[i,0] != minClass:
ChangeFlag=True
classAndLoss[i,0]=minClass
classAndLoss[i,1]=minDist
for cent in range(k): #更新中心簇点
centerXSum=[]
centerYSum=[]
for i in range(m):
if classAndLoss[i,0]==cent:
centerXSum.append(dataList[i][0])
centerYSum.append(dataList[i][1])
if len(centerXSum)!=0: #可能出现一个中心点，没有随机点归到这个类，所以len（centerXSum）作为分母而报错
centerList[cent][0] = sum(centerXSum) / len(centerXSum)
if len(centerYSum)!=0:
centerList[cent][1]=sum(centerYSum)/len(centerYSum)
return classAndLoss[:,0],classAndLoss[:,1]
主函数
if __name__ == '__main__':
pn=20 #生成随机点数
cn=3 #聚类数
sample_point_list=creatPoint(pn) #随机生成点
minLoss=inf
minClass=[]
minCenter=[]
for i in range(100): #随机生成100个中心点集合
#center_point_list = creatPoint(cn) # 方法1：随机生成cn个中心点
center_point_list = createCenterPointBySample(cn, sample_point_list) # 方法2：从样本点集中随机选择cn个点
sample_class_list, sample_loss_list = kMeans(center_point_list, sample_point_list) # 返回点分类向量和距离损失向量
sumLoss = sum(power(sample_loss_list, 2)) # 计算总损失
if sumLoss < minLoss:
minLoss = sumLoss
minClass = sample_class_list
minCenter = center_point_list
center_point_list=minCenter
sample_class_list=minClass
showEchart(center_point_list,sample_point_list,sample_class_list)
运行结果
聚类结果
问题思考总结
k-means算法简单易于实现，但当数据点数量级较大时候，效率比较低。
二维坐标点的横纵坐标代表对象的两个特征，当对象多个特征使用K-means算法，距离度量公式应该不一样？？
网友评论