python实现kMeans算法的详解

  • 更新时间:2022-07-11 08:25:11
  • 编辑:唐幼南

聚类是一种无监督的学习,将相似的对象放到同一簇中,有点像是全自动分类,簇内的对象越相似,簇间的对象差别越大,则聚类效果越好。本文主要为大家详细介绍了python实现kMeans算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,希望能帮助到大家。

1、k均值聚类算法

k均值聚类将数据分为k个簇,每个簇通过其质心,即簇中所有点的中心来描述。首先随机确定k个初始点作为质心,然后将数据集分配到距离最近的簇中。然后将每个簇的质心更新为所有数据集的平均值。然后再进行第二次划分数据集,直到聚类结果不再变化为止。

伪代码为

随机创建k个簇质心
当任意一个点的簇分配发生改变时:
对数据集中的每个数据点:
对每个质心:
计算数据集到质心的距离
将数据集分配到最近距离质心对应的簇
对每一个簇,计算簇中所有点的均值并将均值作为质心

python实现

import numpy as np
import matplotlib.pyplot as plt

def loadDataSet(fileName): 
 dataMat = [] 
 with open(fileName) as f:
  for line in f.readlines():
   line = line.strip().split('\t')
   dataMat.append(line)
 dataMat = np.array(dataMat).astype(np.float32)
 return dataMat


def distEclud(vecA,vecB):
 return np.sqrt(np.sum(np.power((vecA-vecB),2)))
def randCent(dataSet,k):
 m = np.shape(dataSet)[1]
 center = np.mat(np.ones((k,m)))
 for i in range(m):
  centmin = min(dataSet[:,i])
  centmax = max(dataSet[:,i])
  center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1)
 return center
def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent):
 m = np.shape(dataSet)[0]
 clusterAssment = np.mat(np.zeros((m,2)))
 centroids = createCent(dataSet,k)
 clusterChanged = True
 while clusterChanged:
  clusterChanged = False
  for i in range(m):
   minDist = np.inf
   minIndex = -1
   for j in range(k):
    distJI = distMeans(dataSet[i,:],centroids[j,:])
    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[np.nonzero(clusterAssment[:,0].A == cent)[0]]
   centroids[cent,:] = np.mean(ptsInClust,axis = 0)
 return centroids,clusterAssment



data = loadDataSet('testSet.txt')
muCentroids, clusterAssing = kMeans(data,4)
fig = plt.figure(0)
ax = fig.add_subplot(111)
ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A)
plt.show()

print(clusterAssing)

2、二分k均值算法

K均值算法可能会收敛到局部最小值,而非全局最小。一种用于度量聚类效果的指标为误差平方和(SSE)。因为取了平方,更加重视原理中心的点。为了克服k均值算法可能会收敛到局部最小值的问题,有人提出来二分k均值算法。
首先将所有点作为一个簇,然后将该簇一分为二,然后选择所有簇中对其划分能够最大程度减低SSE的值的簇,直到满足指定簇数为止。

伪代码

将所有点看成一个簇
计算SSE
while 当簇数目小于k时:
for 每一个簇:
计算总误差
在给定的簇上进行k均值聚类(k=2)
计算将该簇一分为二的总误差
选择使得误差最小的那个簇进行划分操作

python实现

 

import numpy as np
import matplotlib.pyplot as plt

def loadDataSet(fileName): 
 dataMat = [] 
 with open(fileName) as f:
  for line in f.readlines():
   line = line.strip().split('\t')
   dataMat.append(line)
 dataMat = np.array(dataMat).astype(np.float32)
 return dataMat


def distEclud(vecA,vecB):
 return np.sqrt(np.sum(np.power((vecA-vecB),2)))
def randCent(dataSet,k):
 m = np.shape(dataSet)[1]
 center = np.mat(np.ones((k,m)))
 for i in range(m):
  centmin = min(dataSet[:,i])
  centmax = max(dataSet[:,i])
  center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1)
 return center
def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent):
 m = np.shape(dataSet)[0]
 clusterAssment = np.mat(np.zeros((m,2)))
 centroids = createCent(dataSet,k)
 clusterChanged = True
 while clusterChanged:
  clusterChanged = False
  for i in range(m):
   minDist = np.inf
   minIndex = -1
   for j in range(k):
    distJI = distMeans(dataSet[i,:],centroids[j,:])
    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[np.nonzero(clusterAssment[:,0].A == cent)[0]]
   centroids[cent,:] = np.mean(ptsInClust,axis = 0)
 return centroids,clusterAssment

def biKmeans(dataSet,k,distMeans = distEclud):
 m = np.shape(dataSet)[0]
 clusterAssment = np.mat(np.zeros((m,2)))
 centroid0 = np.mean(dataSet,axis=0).tolist()
 centList = [centroid0]
 for j in range(m):
  clusterAssment[j,1] = distMeans(dataSet[j,:],np.mat(centroid0))**2
 while (len(centList)<k):
  lowestSSE = np.inf
  for i in range(len(centList)):
   ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,0].A == i)[0],:]
   centroidMat,splitClustAss = kMeans(ptsInCurrCluster,2,distMeans)
   sseSplit = np.sum(splitClustAss[:,1])
   sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A != i)[0],1])
   if (sseSplit + sseNotSplit) < lowestSSE:
    bestCentToSplit = i
    bestNewCents = centroidMat.copy()
    bestClustAss = splitClustAss.copy()
    lowestSSE = sseSplit + sseNotSplit
  print('the best cent to split is ',bestCentToSplit)
#  print('the len of the bestClust')
  bestClustAss[np.nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList)
  bestClustAss[np.nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit

  clusterAssment[np.nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:] = bestClustAss.copy()
  centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]
  centList.append(bestNewCents[1,:].tolist()[0])
 return np.mat(centList),clusterAssment

data = loadDataSet('testSet2.txt')
muCentroids, clusterAssing = biKmeans(data,3)
fig = plt.figure(0)
ax = fig.add_subplot(111)
ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A,cmap=plt.cm.Paired)
ax.scatter(muCentroids[:,0],muCentroids[:,1])
plt.show()

print(clusterAssing)
print(muCentroids)

代码及数据集下载:K-means

相关推荐:

让Mahout KMeans聚类分析运行在Hadoop上

cvKMeans2均值聚类分析+代码解析+灰度彩色图像聚类

实例详解Python实现简单网页图片抓取

以上就是python实现kMeans算法的详解的详细内容,更多请关注码农之家其它相关文章!

相关教程

  • 怎么在win系统下读取python文件夹

    在本篇文章里小编给各位分享的是关于win系统下读取python文件夹的相关实例内容,以及代码,需要的朋友们学习下。

    发布时间:2019-07-06

  • Python的重新加载知识点总结

    为防止两个模块互相导入的问题,Python默认所有的模块都只导入一次,如果需要重新导入模块,Python2 7可以直接用reload(),Python3可以用下

    发布时间:2019-12-12

  • Python实现数据可视化监控爬虫状态

    今天主要是来说一下怎么可视化来监控你的爬虫的状态。文中通过实例代码给大家分析了Python实现数据可视化看如何监控你的爬虫状态,感兴趣的朋友一起看看吧

    发布时间:2019-06-06

  • python读取线的shp文件实例分析

    今天小编就为大家分享一篇对python 读取线的shp文件实例详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧

    发布时间:2019-06-08

  • 如何使用Python实现微信中找回好友、群聊用户撤回的消息功能

    这篇文章主要介绍了Python实现微信中找回好友、群聊用户撤回的消息功能,结合实例形式分析了Python基于微信itchat模块实现针对撤回消息的查看功能相关操作技巧,需要的朋友可以参考下

    发布时间:2020-01-22

  • python进入的方法步骤

    运行Python之前,确保你已经成功安装Python。在桌面的左下角点击搜索图标,在搜索框中输入cmd,再回车,进入命令行;在命令行中输入Python,再回车,进入Python。

    发布时间:2019-06-28

  • Python画高斯分布图形实例代码

    今天小编就为大家分享一篇Python画图高斯分布的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧

    发布时间:2020-03-17

  • python如何遍历指定路径下所有文件(按按照时间区间检索)

    这篇文章主要给大家介绍了关于python如何遍历指定路径下所有文件(按按照时间区间检索)的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2021-04-09

  • Python爬虫采集遇到403问题怎么办

    在python写爬虫的时候,html.getcode()会遇到403禁止访问的问题,这是网站对自动化爬虫的禁止。这篇文章主要介绍了Angular2进阶之如何解决爬虫出现403问题的办法,小编觉得挺不错的,现在分享给大

    发布时间:2020-02-16

用户留言