k-means聚类以k个(也是要聚类的个数)随机的中心质点(centroid)开始,然后将每个待聚类的项分派到离它最近的簇。分派完之后,中心质点要进行移动:移动到该簇所有点的平均位置上。接着再次进行分配。这个过程反复的执行,直到中心质点的位置不再发生明显变化或者说分配后的点所属的簇不在变化。
具体来说是以下四步:
- (1) Start with k cluster centers (chosen randomly or according to some specific procedure).
- (2) Assign each row in the data to its nearest cluster center.
- (3) Re-calculate the cluster centers as the "average" of the rows in (2).
- (4) Repeat, until the cluster centers no longer change or some other stopping criterion has been met.
代码如下:
require 'mathn'
class Point#点的类:坐标及维度
attr :coords,:n
def initialize(coords)
@coords=coords
@n=coords.size
end
def to_s
@coords.to_s
end
end
class Cluster
attr :points,:n,:centroid#簇类:点的集合,维度,中心质点
def initialize(points)
if points.size==0
raise "ILLEGAL:EMPTY CLUSTER"
end
@points=points
@n=points[0].n
for p in points
if p.n!=@n
raise "ILLEGAL: MULTISPACE CLUSTER"
end
end
@centroid=calculateCentroid()
end
def update(points)
old_centroid=@centroid
@points=points
@centroid=calculateCentroid()
getDistance(old_centroid,@centroid)
end
def calculateCentroid
centroid_coords=[]
for i in 0..@n-1
centroid_coords<<0.0
for p in @points
centroid_coords[i] = centroid_coords[i]+p.coords[i]
end
centroid_coords[i] = centroid_coords[i]/@points.size
end
Point.new(centroid_coords)
end
def to_s
@points
end
end
def kmeans(points,k,cutoff)
initial=[]
clusters=[]
k.times do
initial<<points[rand(points.size-1)]
end
for p in initial
clusters<<Cluster.new([p])
end
while(true)
lists=[]
clusters.each{lists<<[]}
points.each do |p|
smallest_distance = getDistance(p,clusters[0].centroid)
index=0
for i in 0..(clusters.size-2)
distance=getDistance(p,clusters[i+1].centroid)
if distance<smallest_distance
smallest_distance=distance
index=i+1
end
end
lists[index]<<p
end
biggest_shift=0.0
for i in 0..(clusters.size-1)
shift=clusters[i].update(lists[i])
biggest_shift=(biggest_shift>shift)?biggest_shift : shift
end
if biggest_shift<cutoff
break;
end
end
clusters
end
def getDistance(a,b)
if a.n!=b.n
raise "ILLEGAL: NON-COMPARABLE POINTS"
end
ret=0.0
for i in 0..(a.n-1)
ret=ret+(a.coords[i]-b.coords[i])**2
end
Math.sqrt(ret)
end
def makeRandomPoint(n,lower,upper)
coords=[]
0.upto(n-1){coords<<lower+(upper-lower)*rand}
Point.new(coords)
end
num_points, n, k, cutoff, lower, upper = 10, 2, 3, 0.5, -200, 200
# Create num_points random Points in n-dimensional space
points = []
for i in 0..(num_points-1)
points<<makeRandomPoint(n, lower, upper)
end
# Cluster the points using the K-means algorithm
clusters = kmeans(points, k, cutoff)
# Print the results
puts "\nPOINTS:"
points.each {|p|print "P:", p.to_s,"\n"}
puts "\nCLUSTERS:"
clusters.each {|c|puts "C:", c.to_s}
分享到:
相关推荐
传统的k-means算法对初始聚类中心敏感,聚类结果随不同的初始输入而波动。为消除这种敏感性,提出一种优化初始聚类中心的方法,此方法计算每个数据对象所在区域的密度,选择相互距离最远的k个处于高密度区域的点作为...
k-means 算法
如果你想讲解关于k-means算法,却没有相应的ppt,那你来对了。我在一次面试的过程中也遇到了相似的情况,我精心做了一份关于k-means算法的ppt。如果你需要可以使用,但是使用的时候主要不要照抄哦。自己适度的改一改...
基于Matlab实现: 模式识别 K-Means算法 实现模式分类 模式识别 K-均值算法 实现模式分类
关于k-means算法的源程序代码.%%%%%%函数说明%%%%%% %输入: % sample--样本集; % k--聚类数目; %输出: % y--类标; % cnew--聚类中心; % n--迭代次数; function [y cnew n]=k_means(sample,k)
基于 K-means 算法的校园微博热点话题发现系统 一、研究目的 微博由其 “短平快 ” 的信息能力和快速传播能力 ,已广泛流行于高校学生的常生活中。但微博上的负面舆情信息给社会 、学校和个人带来巨大的危害 。由于...
从网上找的代码自己改了下,写了了个短小的人工智能作业K-MEANS算法
K-means算法讲解
现有的基于密度优化初始聚类中心的k-means算法存在聚类中心的搜索范围大、消耗时间久以及聚类结果对孤立点敏感等问题,针对这些问题,提出了一种基于平均密度优化初始聚类中心的k-means算法adk-means。该算法将数据...
基于改进K-Means算法的入侵检测方法,王倩,,近年来数据挖掘技术在入侵检测领域的应用越来越多,K-Means算法是聚类算法中一种高效的划分算法,应用广泛,但是基于K-Means聚类算法�
K-means算法源码 This directory contains code implementing the K-means algorithm. Source code may be found in KMEANS.CPP. Sample data isfound in KM2.DAT. The KMEANS program accepts input consisting of ...
一个聚类算法(k-means)实例,对想实践一下K_means算法的朋友很实用
k-means算法详解,内含k-means算法基于mapreduce的实现
K-means算法简介及代码过程
这是一个基于matlab语言的K-means算法的改进程序,代码完整易懂,里面包含有实际的数据集,能有利于对K-means算法感兴趣的研究学者或者开发人员
基于K-means算法的遥感图像分类的matlab实现
国外实现k-means算法,用Java写的,想学习的朋友请下载