K |
您所在的位置：网站首页 › 可视化代码执行过程 › K |
K
|
1.前言
最近在实现 K-means 算法的过程中，选用了 python 作为编程语言，由于平常编程用 java 比较多一点，所以对 python 并不是很熟，这就直接导致了后面踩了不少坑。也在网上参考了一些别人的代码，但很多代码都有一些小 bug，不能直接运行。折腾了一天，总算用 python 实现了 K-means 算法，记录下来，希望能给其它初学者提供一个参考，大神请无视。 2.K-means算法简介K-means(K 均值)算法是机器学习中常用的一种简单的聚类算法，该算法属于划分式聚类算法。其中，K 表示需要将数据集划分成的簇的个数。在运用Kmeans算法时，由于我们一般不知道数据的分布情况，也就无从得知数据的分簇的数目，所以一般通过枚举来确定 k 的值。另外，在实际应用中，由于K-means一般作为数据预处理，或者用于辅助分类贴标签，所以 k 值一般不会设置很大。 K-means 算法的思想：首先，确定 k 个初始点作为分簇的中心；接着，将数据集中的每个点分配到一个簇中，即为每个点找到距离其最近的质心，并将其分配给该质心所对应的簇；然后，每个簇的中心更新为该簇所有点的平均值。再次重新分配数据集中所有的点，如果所有的点被分配的簇和之前一样，即簇的中心不会再改变，则此时的 k 个簇就是我们所需要的；如果某个点被分配的簇改变了，则分配完所有的点之后重新更新每个簇的质心，重复分配、更新操作直到所有簇的中心不再改变。 3.K-means 算法的 python 实现本算法所用的数据集为 uci 上的聚类算法数据集 3D Road Network 。文件中的数据格式为如下（部分数据，用于示例）： 144552912,9.3498486,56.7408757,17.0527715677876 144552912,9.3501884,56.7406785,17.614840244389 如果对 numpy 库和 matplotlib 不熟悉，可以先参考下面这几篇博文，里面有简单的示例，对理解代码很有帮助。 Python中矩阵库Numpy基本操作Python的numpy库中将矩阵转换为列表等函数Python中scatter函数参数详解Python--matplotlib绘图可视化知识点整理好了，废话不多说，直接上代码。（这里有一点要注意：运行时需要把数据集放在和该 .py 文件的同一目录下）代码中有详细的注释，就不分开来讲了。下面是完整的代码： #！/usr/bin/env python # -*- coding: utf-8 -*- # @Time : 2018/6/21 23:18 # @Author : kingloon # @Site : # @File : K-means.py from numpy import * import matplotlib.pyplot as plt def loadDataSet(fileName): dataSet = [] f = open(fileName) for line in f.readlines(): curLine = line.strip().split(',') # 这里","表示以文件中数据之间的分隔符","分割字符串 row = [] for item in curLine: row.append(float(item)) dataSet.append(row) return mat(dataSet) # 求向量距离 def distEclud(vecA, vecB): return sqrt(sum(power(vecA - vecB, 2))) # 随机生成k个点作为初始质心 # 若选择随机生成的点作为初始质心，则有可能导致后面更新质心时出现有的质心为 NaN(非数) 的情况 # def initCent(dataSet, k): # n = shape(dataSet)[1] # n是列数 # centroids = mat(zeros((k, n))) # for j in range(n): # minJ = min(dataSet[:, j]) # 找到第j列最小值 # rangeJ = max(dataSet[:, j]) - minJ # 求第j列最大值与最小值的差 # centroids[:, j] = minJ + random.rand(k, 1) * rangeJ # 生成k行1列的在(0, 1)之间的随机数矩阵 # return centroids # 选前k个点作为初始质心 def initCent(dataSet, k): data = [] for i in range(k): data.append(dataSet[i].tolist()) a = array(data) centroids = mat(a) return centroids # K均值聚类算法实现 def KMeans(dataSet, k, distMeas=distEclud): m = shape(dataSet)[0] #数据集的行 clusterAssment = mat(zeros((m, 2))) centroids = initCent(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 #记录最小距离质心下标，最小距离的平方 for cent in range(k): #更新质心位置 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]] #获得距离同一个质心最近的所有点的下标，即同一簇的坐标 centroids[cent,:] = mean(ptsInClust, axis=0) #求同一簇的坐标平均值，axis=0表示按列求均值 return centroids, clusterAssment # 取数据的前两维特征作为该条数据的x , y 坐标， def getXY(dataSet): import numpy as np m = shape(dataSet)[0] # 数据集的行 X = [] Y = [] for i in range(m): X.append(dataSet[i,0]) Y.append(dataSet[i,1]) return np.array(X), np.array(Y) # 数据可视化 def showCluster(dataSet, k, clusterAssment, centroids): fig = plt.figure() plt.title("K-means") ax = fig.add_subplot(111) data = [] for cent in range(k): #提取出每个簇的数据 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]] #获得属于cent簇的数据 data.append(ptsInClust) for cent, c, marker in zip( range(k), ['r', 'g', 'b', 'y'], ['^', 'o', '*', 's'] ): #画出数据点散点图 X, Y = getXY(data[cent]) ax.scatter(X, Y, s=80, c=c, marker=marker) centroidsX, centroidsY = getXY(centroids) ax.scatter(centroidsX, centroidsY, s=1000, c='black', marker='+', alpha=1) # 画出质心点 ax.set_xlabel('X Label') ax.set_ylabel('Y Label') plt.show() if __name__ == "__main__": cluster_Num = 3 data = loadDataSet("network.txt") centroids, clusterAssment = KMeans(data, cluster_Num) showCluster(data, cluster_Num, clusterAssment, centroids)代码运行结果如下：
|
【本文地址】