K-Means算法主要解决的问题如下图所示。我们可以看到，在图的左边有一些点，我们用肉眼可以看出来有四个点群，但是我们怎么通过计算机程序找出这几个点群来呢？于是就出现了我们的K-Means算法
k-means 要解决的问题
算法概要
A，B，C，D，E是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。
步骤如下：
- 随机在图中取K（这里K=2）个种子点
- 然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点）
- 接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）
- 然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A，B，C，下面的种子点聚合了D，E）。
K-means ++
k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远,弥补了初始的k-means算法的种子选择的缺陷。该算法的描述是如下:
- 从输入的数据点集合中随机选择一个点作为第一个聚类中心
- 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
- 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
- 重复2和3直到k个聚类中心被选出来
- 利用这k个初始的聚类中心来运行标准的k-means算法
import random as rand
import math as math
from Point import Point
import numpy as np
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
class clustering:
def __init__(self, geo_locs_ , k_):
self.geo_locations = geo_locs_
self.k = k_
self.clusters = []
self.means = []
self.debug = False
#this method returns the next random node
def next_random(self , index , points , clusters):
#pick next node that has the maximum distance from other nodes
dist = {}
for point_1 in points:
if self.debug:
print('point_1: %f %f' %(point_1.latit , point_1.longit))
for cluster in clusters.values():
point_2 = cluster[0]
if self.debug:
print('point_2:%f %f' % (point_2.latit , point_2.longit))
if point_1 not in dist:
dist[point_1] = math.sqrt(math.pow(point_1.latit - point_2.latit , 2.0) + math.pow(point_1.longit - point_2.longit,2.0))
else:
dist[point_1] += math.sqrt(math.pow(point_1.latit - point_2.latit , 2.0) + math.pow(point_1.longit - point_2.longit , 2.0))
if self.debug:
for key , value in dist.items():
print('(%f , %f) ==> %f' % (key.latit , key.longit , value))
#now let's return the point that has the maxmium distance from previous nodes
count_ = 0
max_ = 0
for key , value in dist.items():
if count_ == 0:
max_ = value
max_point = key
count_ += 1
else:
if value > max_:
max_ = value
max_point = key
return max_point
#this method computes the initial means
def initial_means(self , points):
#pick the first node at random
point_ = rand.choice(points)
if self.debug:
print('poing#0: %f %f' % (point_.latit , point_.longit))
clusters = dict()
clusters.setdefault( 0 , []).append(point_)
points.remove(point_)
#now let's pick k-1 more random points
for i in range(1,self.k):
point_ = self.next_random(i , points , clusters)
if self.debug:
print('point#%d: %f %f' % (i , point_.latit , point_.longit))
clusters.setdefault(i , []).append(point_)
points.remove(point_)
#compute mean of clusters
#self.print_clusters(clusters)
self.means = self.compute_mean(clusters)
if self.debug:
print("initial means:")
self.print_means(self.means)
def compute_mean(self , clusters):
means = []
for cluster in clusters.values():
mean_point = Point( 0.0 , 0.0)
cnt = 0.0
for point in cluster:
mean_point.latit += point.latit
mean_point.longit += point.longit
cnt += 1.0
mean_point.latit = mean_point.latit/cnt
mean_point.longit = mean_point.longit/cnt
means.append(mean_point)
return means
#this method assign nodes to the cluster with the smallest mean
def assign_points(self , points):
if self.debug:
print("assign points")
clusters = dict()
for point in points:
dist = []
if self.debug:
print("point(%f %f)"%(point.latit , point.longit))
#find the best cluster for this node
for mean in self.means:
dist.append(math.sqrt(math.pow(point.latit - mean.latit, 2.0) + math.pow(point.longit - mean.longit , 2.0)))
#let's find the smallest mean
if self.debug:
print(dist)
cnt_ = 0
index = 0
min_ = dist[0]
for d in dist:
if d < min_:
min_ = d
index = cnt_
cnt_ += 1
if self.debug:
print("index:%d" % index)
clusters.setdefault(index , []).append(point)
return clusters
def update_means(self , means, threshold):
#check the curren mean with previous one to see if we should stop
for i in range(len(self.means)):
mean_1 = self.means[i]
mean_2 = means[i]
if self.debug:
print("mean_1(%f , %f)" % (mean_1.latit , mean_1.longit))
print("mean_2(%f , %f)" % (mean_2.latit , mean_2.longit))
if math.sqrt(math.pow(mean_1.latit - mean_2.latit , 2.0) + math.pow(mean_1.longit - mean_2.longit,2.0)) > threshold:
return False
return True
def print_clusters(self , clusters):
cluster_cnt = 1
for cluster in clusers.values():
print("nodes in cluster #%d" % cluster_cnt)
cluster_cnt += 1
for point in cluster:
print("point(%f, %f" % (point.latit , point.longit))
def print_means(self , means):
for point in means:
print("%f %f" % (point.latit , point.longit))
def k_means(self , plot_flag):
if len(self.geo_locations) < self.k:
return -1
points_ = [point for point in self.geo_locations]
#compute the initial means
self.initial_means(points_)
stop = False
while not stop:
#assignment step:assign each node to the cluster with the cloest mean
points_ = [point for point in self.geo_locations]
clusters = self.assign_points(points_)
if self.debug:
self.print_clusters(clusters)
means = self.compute_mean(clusters)
if self.debug:
print("means:")
print(self.print_means(means))
print("update mean:")
stop = self.update_means(means , 0.01)
if not stop:
self.means = []
self.means = means
self.clusters = clusters
if plot_flag:
fig = plt.figure()
ax = fig.add_subplot(111)
markers = ['o','d','x','h',7,4,5,6,'8','p',',','+',',','s','*',3,0,1,2]
colors = ['r','k','b',[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
cnt = 0
for cluster in clusters.values():
latits = []
longits = []
for point in cluster:
latits.append(point.latit)
longits.append(point.longit)
ax.scatter(longits , latits , s = 60 , c = colors[cnt] , marker = markers[cnt])
cnt += 1
plt.show()
return 0
