机器学习算法学习---处理聚类问题常用算法（一）
簇识别给出聚类结果的含义。假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是什么。聚类有时也被称作无监督分类。
1、K-均值聚类算法
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。它可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。
优点：容易实现
缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢
适用数据：数值型
工作流程：首先，随机确定k个初始点作为质心；然后将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。分配完成后，更新质心为每个簇所有点的平均值。重复该操作至质心不再变化。（计算质心-分配-重新计算，反复迭代直到所有数据点的簇分配结果不再改变为止。）
算法性能会受到所选距离计算方法的影响。
K-均值 from numpy import * def loadDataSet(filename): dataMat=[] f=open(filename) lines=f.readlines() for line in lines: line=line.strip().split() fltline=map(float,line) dataMat.append(fltline) return dataMat def distEclud(vecA,vecB):#距离函数 return sqrt(sum(power(vecA-vecB,2)))#欧氏距离 def randCent(dataSet,k):#构建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 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
2、使用后处理来提高聚类性能
在包含簇分配结果的矩阵中保存着每个点的误差，即该点到簇质心的距离平方值。
K-均值算法的k选的不合适的话，结果收敛但效果较差，因为收敛到了局部最小值，而非全局最小值（局部最小值指结果还可以但并非最好结果，全局最小值是可能的最好结果）。
一种用于度量聚类效果的指标是：SSE（误差平方和）
SSE值越小表示数据点越接近于它们的质心，聚类效果越好。
一种肯定可以降低SSE值的方法：增加簇的个数，但这违背了聚类的目标。
聚类目标：保持簇数目不变的情况下提高簇的质量。
改进方法：对生成的簇进行后处理，将具有最大SSE值的簇划分成两个簇。具体实现：将最大簇包含的点过滤出来并在这些点上运行K-均值算法，其中k设为2。为了保持簇总数不变，可以将某两个簇进行合并。
两种合并方法：
（1）合并最近的质心。通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。
（2）合并两个使得SSE增幅最小的质心。合并两个簇然后计算总SSE值；在所有可能的两个簇上重复上述操作，直到找到合并最佳的两个簇为止。
3、二分K-均值算法
为克服K-均值算法收敛于局部最小值的问题而提出。
算法过程：首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分；选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。
另一种做法是选择SSE最大的簇进行划分，直到簇数目达到用户指定的数目为止。
二分K-均值 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,sseNotSplit",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)#更新号，划分的1簇编号更新为质心列表长度 bestClustAss[nonzero(bestClustAss[:,0].A==0)[0],0]=bestCentToSplit#划分的0簇编号保持原来编号 print('the bestCentToSplit is: ',bestCentToSplit) print('the len of bestClustAss is: ',len(bestClustAss)) centList[bestCentToSplit]=bestNewCents[0,:]#更新质心列表 centList.append(bestNewCents[1,:]) clusterAssment[nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClustAss return mat(centList),clusterAssment
