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聚类算法之凝聚层次聚类实例分析

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

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聚类算法之基本K均值实例详解

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

Python聚类算法之DBSACN实例分析

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

Python中的默认参数实例分析

本文研究的主要是Python中的默认参数的相关内容,具体如下. 熟悉C++语言的可以知道,C++语言中的默认参数是写在函数声明中的,为语法糖,与函数的调用无关,是在函数调用的时候由编译器补齐参数然后进行调用. 而Python中的默认参数与其有相当大的不一样,如下例中的代码执行结果会是什么呢? def test_parameter(a, dfp=[]): dfp.append(a) print(dfp) test_parameter(1) test_parameter(2) test_parame

python进程与线程小结实例分析

传统方式是调用2个方法执行1个任务,方法按顺序依次执行 # -*- coding:utf-8 -*- import threading import time def run(n): print('task',n) time.sleep(3) if __name__ == '__main__': run('t1') run('t2') 多线程例子 2个线程同时并发执行1个任务 # -*- coding:utf-8 -*- import threading import time def run(

python shutil文件操作工具使用实例分析

这篇文章主要介绍了python shutil文件操作工具使用实例分析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 python中的shutil是一种高层次的文件操作工具,主要强大之处在于对文件的复制与删除操作更友好 一:shutil. copyfileobj(fsrc,fdst [23]) 将 fsrc 的内容复制到 fdst.如果给出整数长度,则为缓冲区大小.注意,fsrc.fdst,必须是已经打开的文件,而不能传入文件名的字符串 def

Python lambda函数基本用法实例分析

本文实例讲述了Python lambda函数基本用法.分享给大家供大家参考,具体如下: 这里我们简单学习一下python lambda函数. 首先,看一下python lambda函数的语法,如下: f=lambda [parameter1,parameter2,--]:expression lambda语句中,冒号前是参数,可以有0个或多个,用逗号隔开,冒号右边是返回值.lambda语句构建的其实是一个函数对象. 1>无参数 f=lambda :'python lambda!' >>&

Python反转序列的方法实例分析

本文实例讲述了Python反转序列的方法.分享给大家供大家参考,具体如下: 序列是python中最基本的数据结构,序列中每个元素都有一个跟位置相关的序号,也称为索引.对于一个有N个元素的序列来说, 从左到右索引:0,1,2,--N-1 从右到左索引:-1,-2,-3---N 1>列表反转 >>> l=[1,2,3,4] >>> ll=l[::-1] >>> l [1, 2, 3, 4] >>> ll [4, 3, 2, 1] &

python私有属性和方法实例分析

本文实例分析了python的私有属性和方法.分享给大家供大家参考.具体实现方法如下: python默认的成员函数和成员变量都是公开的,并且没有类似别的语言的public,private等关键词来修饰. 在python中定义私有变量只需要在变量名或函数名前加上 "__"两个下划线,那么这个函数或变量就会为私有的了. 在内部,python使用一种 name mangling 技术,将 __membername替换成 _classname__membername,所以你在外部使用原来的私有成

python开发之list操作实例分析

本文实例分析了python开发之list操作.分享给大家供大家参考,具体如下: 对python中list的操作,大家可以参考<Python list操作用法总结> 以下是我个人的笔记: #python list ''' 创建list有很多方法: 1.使用一对方括号创建一个空的list:[] 2.使用一对方括号,用','隔开里面的元素:[a, b, c], [a] 3.Using a list comprehension:[x for x in iterable] 4.Using the typ