甘肃龙网

  1. 首页 > 生活 > >

K-means算法思路与代码实现

生活百科聚类

K-means 算法 0. 有监督/无监督学习
有监督学习：训练集有明确答案，监督学习就是寻找问题（又称输入、特征、自变量）与答案（又称输出、目标、因变量）之间关系的学习方式 。监督学习模型分为分类和回归两类 。
无监督学习：只有数据，无明确答案，即训练集没有标签 。常见的无监督学习算法有聚类()，由计算机自己找出规律 ， 把有相似属性的样本放在一组，每个组也称为簇（） 。
1. 什么是聚类
聚类是指在数据中发现数据对象之间的关系，将数据进行分组 ， 组内的相似性越大，组间的差别越大，则聚类效果越好 。
聚类和分类的区别：聚类是无监督的学习算法，分类是有监督的学习算法 。聚类算法是没有标签的，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起；而分类是有已知标签的训练集（也就是说提前知道训练集里的数据属于哪个类别）的，分类算法在训练集上学习到相应的参数，构建模型，然后应用到测试集上 。
2. K-means 算法原理及优缺点
算法原理：对于给定的样本集，按照样本之间的距离大?。?将样本集划分为K个簇 。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大 。
优点：
缺点：
算法复杂度：O(tkn) ， 其中 n 是样本总个数，k 是簇的个数 ， t 是迭代次数
[1]伸缩性：在数据集较大时，依然能够保持处理小数据集时的优越效果 。
3. K-means 算法步骤
? ①首先给定一个 k 值 ， 即要把样本聚为 k 类，然后随机选取 k 个样本点作为初始聚类中心；
? ②对于数据集中的每一个样本点，计算它到这 k 个聚类中心的距离，并把它分到距离最小的类簇中；
? ③每个类簇中已有若干样本点，重新计算每个类簇的中心点 ， 作为下一次迭代的聚类中心；
? ④重复进行②③步的迭代，不断更新聚类中心直至收敛（聚类中心不再明显改变或达到指定的迭代次数） 。
4. K-means 算法的问题与改进
代码实现
# 手肘法确定 k 值import pandas as pdimport matplotlib.pyplot as pltfrom sklearn.cluster import KMeansdataframe = pd.read_csv("C:\\Users\\mushr\\Desktop\\433\\England18-19.csv",encoding = 'GBK',engine='python')SSE = []for k in range(1,10):estimator = KMeans(n_clusters=k)estimator.fit(dataframe[['rate']])SSE.append(estimator.inertia_)X = range(1,10)plt.xlabel('clusters: k',)plt.ylabel('SSE')plt.plot(X, SSE, 'o-')plt.show()
根据手肘法则，就上图而言 k值 取 2 或者 3 是比较合理的 。
2）轮廓系数法
依据的核心指标是轮廓系数（ ），某个样本点 Xi 的轮廓系数定义为：
其中，a 是 Xi 与同簇的其他样本的平均距离，称为凝聚度，b 是 Xi 与最近簇中所有样本的平均距离，称为分离度 。而最近簇的定义为：
其中 p 是某个簇 Ck 中的样本 。事实上，简单点讲 ， 就是用 Xi 到某个簇所有样本平均距离作为衡量该点到该簇的距离后，选择离 Xi 最近的一个簇作为最近簇 。
求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数 。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好 。那么 ， 很自然地，平均轮廓系数最大的k便是最佳聚类数 。
代码实现
# 轮廓系数法确定 k 值import pandas as pdimport matplotlib.pyplot as pltfrom sklearn.cluster import KMeansfrom sklearn.metrics import silhouette_scoredataframe = pd.read_csv("C:\\Users\\mushr\\Desktop\\433\\England18-19.csv",encoding = 'GBK',engine='python')Scores = []for k in range(2,10):estimator = KMeans(n_clusters=k)estimator.fit(dataframe[['rate']])Scores.append(silhouette_score(df_features[['rate']], estimator.labels_, metric='euclidean'))X = range(2,10)plt.xlabel('k')plt.ylabel('silhouette_score')plt.plot(X, Scores, '-o')plt.show()
如此进行重复的迭代 ， 最终得到的有可能是局部最优解（局部最小的SSE），要想得到全局最优解需要选取合理的初始聚类中心 。那么改如何选取合理的初始聚类中心呢?
针对于随机初始聚类中心的改进算法 K-means++：
? ①从所有样本点中随机选取一个点 P1 作为第一个类簇的聚类中心；
? ②对于数据集中的每一个样本点 Px ，计算 Px 与所有已选定的聚类中心的距离的最小值 Dx；
? ③在确定下一个类簇的聚类中心时，Dx 值更大的样本点被选中的概率更大；
? ④重复 ② ③ 两步直至确定出 k 个聚类中心；
? ⑤依据这 k 个聚类中心运行 K-means 算法 。
K-means++ 算法对初始聚类中心的选取进行优化，将随即选取策略改进为更合理的选取策略 ， 得出的初始聚类中心更加分散，能够有效的减少算法迭代次数，加快运算速度，但仍旧无法解决离群点问题 。

K-means算法思路与代码实现

文章插图
5. K-means 算法思路及实现
创建 k 个点作为起始质心（随机选择）
当任意一个点的簇分配结果发生改变时
? 对数据集中的每个数据点
? 对每个质心
? 计算质心与数据点之间的距离
? 将数据点分配到距其最近的簇
? 对每个簇 ， 计算簇中所有点的均值并将均值作为质心
实现方法一：我是调包侠（废话不多直接导包）
# 实现一: 调用 sklearn 库中的 KMeans 方法import matplotlib.pyplot as pltfrom sklearn.cluster import KMeansfrom sklearn.datasets.samples_generator import make_blobs# 借助 make_blobs 方法生成随机样本数据data, target = make_blobs(n_samples=1000, n_features=2, centers=[[-2,-2],[0,0],[1,1],[2,2]], cluster_std=[0.5,0.2,0.3,0.3], random_state=9)y_pred = KMeans(n_clusters=4, random_state=9).fit_predict(data)plt.scatter(data[:, 0], data[:, 1], c=y_pred)plt.show()
效果：
实现方法二：变身代码搬运工（代码搬自《机器学习实战》）
# 实现二: 代码from numpy import *import matplotlib.pyplot as pltdef loadDataSet(fileName):dataMat = []fr = open(fileName)for line in fr.readlines():# 简单处理，删除每一行首尾的空格并以 \t 分隔currtLine = line.strip().split('\t')# 浮点化fltLine = list(map(float, currtLine))dataMat.append(fltLine)return dataMatdef distEcludean(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 centroidsdef KMeans(dataSet, k, distMeas=distEcludean, createCent=randCent):m = shape(dataSet)[0]clusterAssment = mat(zeros((m, 2)))centroids = createCent(dataSet, k)clusterChanged = Truewhile clusterChanged:clusterChanged = Falsefor i in range(m):minDist = infminIndex = -1for j in range(k):distJI = distMeas(centroids[j, :], dataSet[i, :])if distJI < minDist:minDist = distJIminIndex = jif clusterAssment[i, 0] != minIndex: clusterChanged = TrueclusterAssment[i, :] = minIndex, minDist ** 2# print(centroids,end='\n\n')for cent in range(k):ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]]centroids[cent, :] = mean(ptsInClust, axis=0)return centroids, clusterAssmentdef showCluster(dataSet, k, centroids, clusterAssment):numSamples, dim = dataSet.shapeif dim != 2:print"Sorry! I can not draw because the dimension of your data is not 2!"return 1mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', ' len(mark):print"Sorry! Your k is too large! please contact Zouxy"return 1# draw all samplesfor i in range(numSamples):markIndex = int(clusterAssment[i, 0])plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '
效果（两份数据集不一样，所以图也不同）：
引用及参考
[1]《机器学习实战》 “[美] Peter ”
[2]“机器学习系列：（六）K-Means聚类”
[3]“用人话讲明白快速聚类”
【K-means算法思路与代码实现】[4]“算法理解及代码实现”


    上一篇：海贼无双4怎么用手柄玩 海贼无双3怎么用手柄玩

    下一篇：雨后春笋的意思是什么 标准答案 雨后春笋的意思是什么