使用 Python实现 K_Means聚类算法:
问题定义
聚类问题是数据挖掘的基本问题,它的本质是将n个数据对象划分为 k个聚类,以便使得所获得的聚类满足以下条件:
同一聚类中的数据对象相似度较高;
不同聚类中的对象相似度较小。
相似度可以根据问题的性质进行数学定义。
K-means算法就是解决这类问题的经典聚类算法
它的基本思想是以空间中k个点为中心,进行聚类,对最靠近他们的对象归类。
通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果
其IPO描述如下:
输入:N个数据
操作:聚类算法
输出:图形化显示聚类结果
K-means算法步骤为:
从 n个数据对象任意选择 k 个对象作为初始聚类中心;并设定最大迭代次数
计算每个对象与k个中心点的距离,并根据最小距离对相应对象进行划分,
即,把对象划分到与他们最近的中心所代表的类别中去;
对于每一个中心点,遍历他们所包含的对象,计算这些对象所有维度的和的均值,获得新的中心点;
如果聚类中心与上次迭代之前相比,有所改变,
或者,算法迭代次数小于给定的最大迭代次数,则继续执行第2、3两步,否则,程序结束返回聚类结果。
K-means算法运行过程
程序代码如下:
程序的控制部分:
首先从文件读入数据,并将其存储在Numpy的数组对象中,
指定聚类个数,与,最大迭代次数,
调用kmeans聚类函数,得到聚类结果
将聚类结果以图的形式展示出来。
子函数定义
Initialize center函数通过使用numpy库的zeros函数和random.uniform函数,
随机选取了k个数据做聚类中心, 并将结果存放在Numpy的Array对象centers中
Dist2Centers这个函数用来计算一个数据点到所有聚类中心的距离,将其存放在dis2cents中返回
kmeans函数.
这部分代码完成了kmeans算法中为数据点决定所属类别以及迭代更新类中心点的主要功能。
注意numpy库的返回最小值索引的argmin函数以及计算平均值的mean函数的使用方法
showcluster函数中,利用matplotlib库的plot函数将不同类别数据以不同颜色展现出来。
完整Python代码如下:
import numpy as np import matplotlib.pyplot as plt #子函数:Initialize center函数通过使用numpy库的zeros函数和random.uniform函数, # 随机选取了k个数据做聚类中心, 并将结果存放在Numpy的Array对象centers中 def initCenters(dataSet,k): numSamples,dim=dataSet.shape centers=np.zeros((k,dim)) for i in range(k): index=int(np.random.uniform(0,numSamples)) # random get k centers centers[i,:]=dataSet[index,:] print(centers) return centers #子函数:Dist2Centers这个函数用来计算一个数据点到所有聚类中心的距离,将其存放在dis2cents中返回 def Dist2Centers(sample,centers): k=centers.shape[0] dis2cents=np.zeros(k) for i in range(k): dis2cents[i]=np.sqrt(np.sum(np.power(sample-centers[i,:],2))) return dis2cents #子函数:kmeans函数. # 这部分代码完成了kmeans算法中为数据点决定所属类别以及迭代更新类中心点的主要功能。 # 注意numpy库的返回最小值索引的argmin函数以及计算平均值的mean函数的使用方法 def kmeans(dataSet,k,iterNum): numSamples=dataSet.shape[0] iterCount=0 #clusterAssignment stores which cluster this sample belongs to clusterAssignment=np.zeros(numSamples) clusterChanged=True ##step 1: initialize centers centers=initCenters(dataSet,k) while clusterChanged and iterCount <iterNum: clusterChanged=False iterCount=iterCount+1 # for each sample for i in range(numSamples): dis2cent=Dist2Centers(dataSet[i,:],centers) minIndex=np.argmin(dis2cent) #返回最小值索引的argmin函数 ## step 3: update its belonged cluster if clusterAssignment[i] !=minIndex: clusterChanged=True clusterAssignment[i]=minIndex ## step 4: update centers for j in range(k): pointsInCluster=dataSet[np.nonzero(clusterAssignment[:]==j)[0]] centers[j,:]=np.mean(pointsInCluster,axis=0) #计算平均值的mean函数 print("Congratulations ! Cluster Achieved !") return centers,clusterAssignment #子函数:showcluster函数中,利用matplotlib库的plot函数将不同类别数据以不同颜色展现出来 def showCluster(dataSet,k,centers,clusterAssignment): numSamples,dim=dataSet.shape mark=['or','ob','og','om'] #draw all samples for i in range(numSamples): markIndex=int(clusterAssignment[i]) plt.plot(dataSet[i,0],dataSet[i,1],mark[markIndex]) mark=['Dr','Db','Dg','Dm'] #draw the centroids 图心,几何中心 for i in range(k): plt.plot(centers[i,0],centers[i,1],mark[i],markersize=17) plt.title("K=%d"%k) plt.show() def main(): ## step 1: load dataset print("step 1: loading dataset...") dataSet=[] dataSetFile=open("180320-testSet.txt") for line in dataSetFile: lineArr=line.strip().split(' ') dataSet.append([float(lineArr[0]),float(lineArr[1])]) ## step 2: clustering... print("step 2: clustering...") dataSet=np.mat(dataSet) k=2 centers_result,clusterAssignment_result=kmeans(dataSet,k, 100) ##step 3: show the result print("tep 3: show the result...") showCluster(dataSet,k,centers_result,clusterAssignment_result) main()
实验结果:
运行程序,
下面依次是,将数据,聚为两类,三类,四类的程序结果图。也可以通过调整迭代次数,观察生成簇的变化
【完整源码】:点我获取
【测试文件】:点我获取