python中实现k-means聚类算法详解

算法优缺点:

优点:容易实现
缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢
使用数据类型:数值型数据

算法思想

k-means算法实际上就是通过计算不同样本间的距离来判断他们的相近关系的,相近的就会放到同一个类别中去。

1.首先我们需要选择一个k值,也就是我们希望把数据分成多少类,这里k值的选择对结果的影响很大,Ng的课说的选择方法有两种一种是elbow method,简单的说就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好。另一种则是根据具体的需求确定,比如说进行衬衫尺寸的聚类你可能就会考虑分成三类(L,M,S)等

2.然后我们需要选择最初的聚类点(或者叫质心),这里的选择一般是随机选择的,代码中的是在数据范围内随机选择,另一种是随机选择数据中的点。这些点的选择会很大程度上影响到最终的结果,也就是说运气不好的话就到局部最小值去了。这里有两种处理方法,一种是多次取均值,另一种则是后面的改进算法(bisecting K-means)

3.终于我们开始进入正题了,接下来我们会把数据集中所有的点都计算下与这些质心的距离,把它们分到离它们质心最近的那一类中去。完成后我们则需要将每个簇算出平均值,用这个点作为新的质心。反复重复这两步,直到收敛我们就得到了最终的结果。

函数

loadDataSet(fileName)

从文件中读取数据集

distEclud(vecA, vecB)

计算距离,这里用的是欧氏距离,当然其他合理的距离都是可以的

randCent(dataSet, k)

随机生成初始的质心,这里是虽具选取数据范围内的点

kMeans(dataSet, k, distMeas=distEclud, createCent=randCent)

kmeans算法,输入数据和k值。后面两个事可选的距离计算方式和初始质心的选择方式

show(dataSet, k, centroids, clusterAssment)

可视化结果

#coding=utf-8
from numpy import *
def loadDataSet(fileName):
 dataMat = []
 fr = open(fileName)
 for line in fr.readlines():
 curLine = line.strip().split('\t')
 fltLine = map(float, curLine)
 dataMat.append(fltLine)
 return dataMat
#计算两个向量的距离,用的是欧几里得距离
def distEclud(vecA, vecB):
 return sqrt(sum(power(vecA - vecB, 2)))
#随机生成初始的质心(ng的课说的初始方式是随机选K个点)
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(array(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)))#create mat to assign data points
     #to a centroid, also holds SE of each point
 centroids = createCent(dataSet, k)
 clusterChanged = True
 while clusterChanged:
 clusterChanged = False
 for i in range(m):#for each data point assign it to the closest centroid
  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):#recalculate centroids
  ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
  centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean
 return centroids, clusterAssment
def show(dataSet, k, centroids, clusterAssment):
 from matplotlib import pyplot as plt
 numSamples, dim = dataSet.shape
 mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
 for i in xrange(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', '<b', 'pb']
 for i in range(k):
 plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)
 plt.show()
def main():
 dataMat = mat(loadDataSet('testSet.txt'))
 myCentroids, clustAssing= kMeans(dataMat,4)
 print myCentroids
 show(dataMat, 4, myCentroids, clustAssing) 

if __name__ == '__main__':
 main()

这里是聚类结果,还是很不错的啦

但是有时候也会收敛到局部最小值,就像下面这样,就是不幸收敛到局部最优了

总结

以上就是本文关于python中实现k-means聚类算法详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:

Python内存管理方式和垃圾回收算法解析

Python数据结构与算法之列表(链表,linked list)简单实现

Python算法之求n个节点不同二叉树个数

有什么问题可以随时留言,小编会及时回复大家的。感谢朋友们对本站的支持!

时间: 2017-11-08

Python聚类算法之基本K均值实例详解

本文实例讲述了Python聚类算法之基本K均值运算技巧.分享给大家供大家参考,具体如下: 基本K均值 :选择 K 个初始质心,其中 K 是用户指定的参数,即所期望的簇的个数.每次循环中,每个点被指派到最近的质心,指派到同一个质心的点集构成一个.然后,根据指派到簇的点,更新每个簇的质心.重复指派和更新操作,直到质心不发生明显的变化. # scoding=utf-8 import pylab as pl points = [[int(eachpoint.split("#")[0]), in

python实现k均值算法示例(k均值聚类算法)

简单实现平面的点K均值分析,使用欧几里得距离,并用pylab展示. 复制代码 代码如下: import pylab as pl #calc Euclid squiredef calc_e_squire(a, b):    return (a[0]- b[0]) ** 2 + (a[1] - b[1]) **2 #init the 20 pointa = [2,4,3,6,7,8,2,3,5,6,12,10,15,16,11,10,19,17,16,13]b = [5,6,1,4,2,4,3,1,

Python聚类算法之DBSACN实例分析

本文实例讲述了Python聚类算法之DBSACN.分享给大家供大家参考,具体如下: DBSCAN:是一种简单的,基于密度的聚类算法.本次实现中,DBSCAN使用了基于中心的方法.在基于中心的方法中,每个数据点的密度通过对以该点为中心以边长为2*EPs的网格(邻域)内的其他数据点的个数来度量.根据数据点的密度分为三类点: 核心点:该点在邻域内的密度超过给定的阀值MinPs. 边界点:该点不是核心点,但是其邻域内包含至少一个核心点. 噪音点:不是核心点,也不是边界点. 有了以上对数据点的划分,聚合可

Python聚类算法之凝聚层次聚类实例分析

本文实例讲述了Python聚类算法之凝聚层次聚类.分享给大家供大家参考,具体如下: 凝聚层次聚类:所谓凝聚的,指的是该算法初始时,将每个点作为一个簇,每一步合并两个最接近的簇.另外即使到最后,对于噪音点或是离群点也往往还是各占一簇的,除非过度合并.对于这里的"最接近",有下面三种定义.我在实现是使用了MIN,该方法在合并时,只要依次取当前最近的点对,如果这个点对当前不在一个簇中,将所在的两个簇合并就行: 单链(MIN):定义簇的邻近度为不同两个簇的两个最近的点之间的距离. 全链(MAX

Python机器学习算法之k均值聚类(k-means)

一开始的目的是学习十大挖掘算法(机器学习算法),并用编码实现一遍,但越往后学习,越往后实现编码,越发现自己的编码水平低下,学习能力低.这一个k-means算法用Python实现竟用了三天时间,可见编码水平之低,而且在编码的过程中看了别人的编码,才发现自己对numpy认识和运用的不足,在自己的代码中有很多可以优化的地方,比如求均值的地方可以用mean直接对数组求均值,再比如去最小值的下标,我用的是argsort排序再取列表第一个,但是有argmin可以直接用啊.下面的代码中这些可以优化的并没有改,

Python实现希尔排序算法的原理与用法实例分析

本文实例讲述了Python实现希尔排序算法的原理与用法.分享给大家供大家参考,具体如下: 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 希尔排序的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高

Python中xrange与yield的用法实例分析

本文实例分析了Python中xrange与yield的用法.分享给大家供大家参考,具体如下: range和xrange Python提供了生成和返回整数序列的内置函数range及xrange,虽然这两个函数在功能上是差不多的,但其实现原理还是有差别的.range(n, m)返回的是一个从n到(m-1)的连续的整数列表,而xrange(n, m)返回的却是一个特殊的目的对象,即xrange对象本身. >>> range(1, 5) [1, 2, 3, 4] >>> xra

Python面向对象之继承和组合用法实例分析

本文实例讲述了Python面向对象之继承和组合用法.分享给大家供大家参考,具体如下: 面向对象的组合用法 软件重用的重要方式除了继承之外还有另外一种方式,即:组合 组合指的是,在一个类中以另外一个类的对象作为数据属性,称为类的组合 圆环是由两个圆组成的,圆环的面积是外面圆的面积减去内部圆的面积.圆环的周长是内部圆的周长加上外部圆的周长. 这个时候,我们就首先实现一个圆形类,计算一个圆的周长和面积.然后在"环形类"中组合圆形的实例作为自己的属性来用 # -*-coding:utf-8 -

Python编程之event对象的用法实例分析

本文实例讲述了Python编程中event对象的用法.分享给大家供大家参考,具体如下: Python提供了Event对象用于线程间通信,它是由线程设置的信号标志,如果信号标志位为假,则线程等待直到信号被其他线程设置成真.这一点似乎和windows的event正好相反. Event对象实现了简单的线程通信机制,它提供了设置信号,清除信号,等待等用于实现线程间的通信. 1.设置信号 使用Event的set()方法可以设置Event对象内部的信号标志为真.Event对象提供了isSet()方法来判断其

Python编程之字符串模板(Template)用法实例分析

本文实例讲述了Python编程之字符串模板(Template)用法.分享给大家供大家参考,具体如下: #coding=utf8 ''''' 字符串格式化操作符,需要程序员明确转换类型参数, 比如到底是转成字符串.整数还是其他什么类型. 新式的字符串模板的优势是不用去记住所有相关细节, 而是像shell风格的脚本语言里面那样使用美元符号($). 由于新式的字符串引进Template对象, Template对象有两个方法:substitute().safe_substitute(). substit

Python分支语句与循环语句应用实例分析

本文实例讲述了Python分支语句与循环语句应用.分享给大家供大家参考,具体如下: 一.分支语句 1.if else语句 语法: if 条件判断: 执行的语句块1 else : 执行语句块2 当满足条件的时候则执行语句块1 ,不满足条件就执行语句块2 注意:1.条件判断后面要加冒号":": 2.执行语句块需要缩进[4个空格]. else 与 if对齐,else后面要加":",语句块缩进4个空格 ''' 从控制台输入年龄,如果年龄小于18岁,打印"未成年人禁

Python从函数参数类型引出元组实例分析

本文实例讲述了Python从函数参数类型引出元组.分享给大家供大家参考,具体如下: 自定义函数:特殊参数 def show(name="jack", *info): print(name) #jack print(info) #(22, '男') show("jack",22,"男") 可以看出22,"男"全部归为了函数的第二个参数*info. 我们可以看到打印这个info参数结果是:小括号包起来的形式. 函数的特殊参数升级