python实现k-means聚类算法
作者:chenge_j 发布时间:2022-03-16 22:06:07
k-means聚类算法
k-means是发现给定数据集的k个簇的算法,也就是将数据集聚合为k类的算法。
算法过程如下:
1)从N个文档随机选取K个文档作为质心
2)对剩余的每个文档测量其到每个质心的距离,并把它归到最近的质心的类,我们一般取欧几里得距离
3)重新计算已经得到的各个类的质心
4)迭代步骤(2)、(3)直至新的质心与原质心相等或迭代次数大于指定阈值,算法结束
算法实现
随机初始化k个质心,用dict保存质心的值以及被聚类到该簇中的所有data。
def initCent(dataSet , k):
N = shape(dataSet)[1]
cents = {}
randIndex=[]
#随机生成k个不重复的索引
for i in range(k):
rand = random.randint(0,N)
while rand in randIndex:
rand = random.randint(0, N)
randIndex.append(rand)
#按索引取dataSet中的data作为质心
for i in range(k):
templist = []
templist.append(dataSet[randIndex[i]])
templist.append([dataSet[randIndex[i]]])
cents[i] = templist
return cents
对dataSet中的所有数据进行一次聚类。返回值cents为dict类型的数据,int类型的key,list类型的value。其中cents[i][0]为质心位置,cents[i][1]为存储该簇中所有data的列表。
#计算两个向量的欧氏距离
def calDist(X1 , X2):
sum = 0
for x1 , x2 in zip(X1 , X2):
sum += (x1 - x2) ** 2
return sum ** 0.5
#聚类
def doKmeans(dataSet , k , cents):
#清空上一次迭代后的簇中元素,只记录质心
for i in range(k):
cents[i][1] = []
for data in dataSet:
no = 0#初始化簇标号
minDist = sys.maxint#初始化data与k个质心的最短距离
for i in range(k):
dist = calDist(data , cents[i][0])
if dist < minDist:
minDist = dist
no = i
#找到距离最近的质心
cents[no][1].append(data)
#更新质心
for i in range(k):
for j in range(shape(dataSet)[0]):
cents[i][0] = mean(cents[i][1],axis=0).tolist()
return cents
k-means主方法
#判断两次聚类的结果是否相同
def isEqual(old , new):
for i in range(len(old)):
if(old[i] != new[i][0]):
return 0
return 1
#主方法
def kmeans_main(dataSet,k):
cents = initCent(dataSet, k)
for x in range(1000):
oldcents = []
#拷贝上一次迭代的结果
for i in cents.keys():
oldcents.append(cents[i][0])
newcents = doKmeans(dataSet, k , cents)
#若相邻两次迭代结果相同,算法结束
if isEqual(oldcents , newcents)>0:
break
cents = newcents
return cents
结果测试
数据集(虚构)
2 3 2.54
2 1 0.72
3 5 3.66
4 3 1.71
3.11 5.29 4.13
4.15 2 3.1
3.12 3.33 3.72
1.49 5 2.6
3 5 2.88
3.9 1.78 2.56
-2 3 5
3 1 0.4
-2 1 2.2
-3 0 1.7
-4 1 2
8 -1 0
2 3.2 7.1
1 3 5
2 4 3
0.1 2 5.4
2 0 5.54
2 1 1.72
3 5 2.66
1 8 1.71
5.11 1.29 4.13
7.15 2 7.1
1.12 5.33 4.72
6.49 4 3.6
4 8 6.88
1.9 5.78 6.56
-2 -3 2.5
1 -1 2.4
-2 1 3.2
-1 0 5.7
-2 3 2
1 -1 4
3 4.2 6.1
5 2 5
3 5.7 13
0.9 2.9 1.4
画图方法
def draw(cents):
color = [ 'y', 'g', 'b']
X = []
Y = []
Z = []
fig = plt.figure()
ax = Axes3D(fig)
for i in cents.keys():
X.append(cents[i][0][0])
Y.append(cents[i][0][1])
Z.append(cents[i][0][2])
ax.scatter(X, Y, Z,alpha=0.4,marker='o',color='r', label=str(i))
for i in cents.keys():
X = []
Y = []
Z = []
data = cents[i][1]
for vec in data:
X.append(vec[0])
Y.append(vec[1])
Z.append(vec[2])
ax.scatter(X, Y, Z, alpha=0.4,marker='o', color=color[i], label=str(i),)
plt.show()
测试及结果展示(红点表示质心)
dataSet = loadDataSet("dataSet.txt")
cents = kmeans_main(dataSet , 3)
draw(cents)
来源:http://blog.csdn.net/chenge_j/article/details/71747640
猜你喜欢
- 1、半开放socket利用shutdown()函数使socket双向数据传输变为单向数据传输。shutdown()需要一个单独的参数,该参数
- Table:用于标示删除的数据表的名称。 1:该表必须是一个事实存在的表,对于该处的表必须是一个实际存在于数据库中的表格,必能是由于sele
- 四兄弟的背景在一个名为编程语言的村庄里,有不同姓氏的村民。例如Java、Python、Golang、JavaScript等姓氏,而接下来要介
- 飞机大战(Python)代码分为两个python文件,工具类和主类,需要安装pygame模块,能完美运行(网上好多不完整的,调试得心累。实现
- Python中的函数调用与c++不同的是将this指针直接作为self当作第一个形参进行处理,从而将静态函数与实例方法的调用形式统一了起来。
- 一个Javascript 的类库,用于table内容排序。使用很方便,不用每次都去调用数据库了。特别适合多表查询的排序。加上<tbod
- 什么是并发安全?在高并发场景下,进程、线程(协程)可能会发生资源竞争,导致数据脏读、脏写、死锁等问题,为了避免此类问题的发生,就有了并发安全
- 用XMLHTTP Post Form时的表单乱码有两方面的原因——Post表单数据时中文乱码;服务器Response被XMLHTTP不正确编
- Django生成数据库表时报错 __init__() missing 1 required positional argument:
- 在web运行中很重要的一个功能就是加载静态文件,在django中可能已经给我们设置好了,我们只要直接把模板文件放在templates就好了,
- “Lightbox”是一个别致且易用的图片显示效果,它可以使图片直接呈现在当前页面之上而不用转到新的窗口。lightbox效果网络上有很多j
- 上一篇文章,写了基本框架,可能很多人会觉得晕头转向,这里提供一个简单的例子来予以说明,希望能帮你解开谜团。一、功能介绍通过微信公众平台实现在
- 有时候我们想要的数据合并结果是数据的轴向连接,在pandas中这可以通过concat来实现。操作的对象通常是Series。Ipython中的
- 教程前先给大家看看小编的实现成果吧!图1:图2:图3:教程:实现这个功能我们需要五个php文件:login.php(登录界面,如图2)<
- 程序流程分析图:传播过程:代码展示:创建环境使用<pip install+包名>来下载torch,torchvision包准备数
- 一、效果快放10倍总共分为三部分,左上角的正文,下方的心形和右下角的署名特别需要注意的一点是这种东西不但要装Python,还与分辨率有关(换
- go install编译并安装代码包,对于库,会生成目标库文件,并且放置到GOPATH/pgk目录下。对于可执文件,会生成目标可执行文件,并
- 之前一直傻傻分不清(n,1)和(n,)之间的区别,这里做一下总结,希望度过此文章的小伙伴都能明白。例如如果我们创建一个包含10个整型数的数组
- 上一节我们介绍了服务注册和基本的管道执行流程, 并且讲到了中间件, 这一节我们就来详细谈谈中间件这个东西讲中间件, 其实就是讲Startup
- 让我们看看如何在 Python 中复制数组。 有 3 种复制数组的方法:只需使用赋值运算符。浅拷贝深拷贝1 使用赋值运算符我们可以使用赋值运