聚类是机器学习中一种重要的无监督算法，它可以将数据点归结为一系列特定的组合。理论上归为一类的数据点具有相同的特性，而不同类别的数据点则具有各不相同的属性。在数据科学中聚类会从数据中发掘出很多分析和理解的视角，让我们更深入的把握数据资源的价值、并据此指导生产生活。
K均值聚类
这一最著名的聚类算法主要基于数据点之间的均值和与聚类中心的聚类迭代而成。它主要的优点是十分的高效，由于只需要计算数据点与剧类中心的距离，其计算复杂度只有O(n)。其工作原理主要分为以下四步：
1.首先我们需要预先给定聚类的数目同时随机初始化聚类中心。我们可以初略的观察数据并给出较为准确的聚类数目；
2.每一个数据点通过计算与聚类中心的距离了来分类到最邻近的一类中；
3.根据分类结果，利用分类后的数据点重新计算聚类中心；
4.重复步骤二三直到聚类中心不再变化。（可以随机初始化不同的聚类中心以选取最好的结果）
python实现
1 point.py
class Point:
def __init__(self, latit_, longit_):
#self.id = id_ #an id which uniquely identifies a point
self.latit = latit_
self.longit = longit_
2 clustering.py
import randomas rand
import mathas math
from pointimport Point
#import pkg_resources
#pkg_resources.require("matplotlib")
import numpyas np
from mpl_toolkits.mplot3dimport Axes3D
import matplotlib.pyplotas plt
class clustering:
def __init__(self, geo_locs_, k_):
self.geo_locations = geo_locs_
self.k = k_
self.clusters = []#clusters of nodes
self.means = []#means of clusters
self.debug =True #debug flag
#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
print 'index: %d ' % (index)
dist = {}
for point_1in points:
#if self.debug:
#print 'point_1: %f %f' % (point_1.latit, point_1.longit)
#compute this node distance from all other points in cluster
for clusterin clusters.values():
point_2 = cluster[0]
#if self.debug:
# print 'point_2: %f %f' % (point_2.latit, point_2.longit)
if point_1not 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 maximum distance from previous nodes
count_ =0
max_ =0
for key, valuein 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 'point#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 iin 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.append([point_])
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 clusterin clusters.values():
mean_point = Point(0.0,0.0)
cnt =0.0
for pointin cluster:
#print "compute: point(%f,%f)" % (point.latit, point.longit)
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 pointin points:
dist = []
if self.debug:
print "point(%f,%f)" % (point.latit, point.longit)
#find the best cluster for this node
for meanin 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 din 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 current mean with the previous one to see if we should stop
for iin 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
#debug function: print cluster points
def print_clusters(self, clusters):
cluster_cnt =1
for clusterin clusters.values():
print "nodes in cluster #%d" % cluster_cnt
cluster_cnt +=1
for pointin cluster:
print "point(%f,%f)" % (point.latit, point.longit)
#print means
def print_means(self, means):
for pointin means:
print "%f %f" % (point.latit, point.longit)
#k_means algorithm
def k_means(self, plot_flag):
if len(self.geo_locations)
return -1 #error
points_ = [pointfor pointin 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 closest mean
points_ = [pointfor pointin 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
#plot cluster for evluation
if plot_flag:
fig = plt.figure()
ax = fig.add_subplot(111)
markers = ['o','d','x','h','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 clusterin clusters.values():
latits = []
longits = []
for pointin 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
3 main.py
import randomas rand
from clusteringimport clustering
from pointimport Point
import csv
geo_locs = []
#loc_ = Point(0.0, 0.0) #tuples for location
#geo_locs.append(loc_)
#read the fountains location from the csv input file and store each fountain location as a Point(latit,longit) object
f =open('./drinking_fountains.csv','r')
reader = csv.reader(f,delimiter=",")
for linein reader:
loc_ = Point(float(line[0]),float(line[1]))#tuples for location
geo_locs.append(loc_)
#print len(geo_locs)
#for p in geo_locs:
# print "%f %f" % (p.latit, p.longit)
#let's run k_means clustering. the second parameter is the no of clusters
cluster = clustering(geo_locs,8 )
flag = cluster.k_means(True)
if flag == -1:
print "Error in arguments!"
else:
#the clustering results is a list of lists where each list represents one cluster
print "clustering results:"
cluster.print_clusters(cluster.clusters)
4 drinking_fountains.csv 示例数据
1,1
2,2
3,3
4,4
5,5
6,6
7,7
8,8
9,9
10,10
11,11
12,12
13,13
14,14
15,15
运行main.py ,图片如下：
