聚类算法之K均值算法(k-means)的Python实现

K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函悉梁亮数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最优分类，使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

通常，人们根据样本间的某种距离或者相似性来定义聚类，即把相似的（或距离近的）样本聚为同一类，而把不相似的（或距离远的）样本归在其他类。

所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子渣虚集的元素相异度尽可能高。其中每个子集叫做一个簇。

k-means算法是一种很常见的聚类算法，它的基本思想是：通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

看起来还不错

分析一个公司的客户分类，这样可以对不同的客户使用不同的睁宽商业策略，或是电子商务中分析商品相似度，归类商品，从而可以使用一些不同的销售策略，等等。

k-means算法实际上就是通过计算不同样本间的距离来判断他们的帆让相近关系的，相近的就会放到同一个类别中去。

1.首先我们需要选择一个k值，也就是我们希望把数据分成多少类，这里k值的选择对结果的影响很大，Ng的课说的选择方法有两种一种是elbow method，简单的说就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好。另一种则是根据具体的需求确定，比如说进行衬衫哪销尺寸的聚类你可能就会考虑分成三类（L,M,S）等

2.然后我们需要选择最初的聚类点（或者叫质心），这里的选择一般是随机选择的，代码中的是在数据范围内随机选择，另一种是随机选择数据中的点。这些点的选择会很大程度上影响到最终的结果，也就是说运气不好的话就到局部最小值去了。李轿游这里有两种处理方法，一种是多次取均值，另一种则是后面的改进算法（bisecting K-means）

3.终于我们开始进入正题了，接下来我们会把数据集中所有的点都计算下与这些质心的距离，把它们分到离它们质心最近的那一类中去。完成后我们则需要将每个簇算出平均值，用这个点作为新的质心。反复重复这两步，直到收敛我们就得到了最终的结果。

下面是一个k-means聚类算法在python2.7.5上面的具体实现，你需要先安装Numpy和Matplotlib：

from numpy import *

import time

import matplotlib.pyplot as plt

# calculate Euclidean distance

def euclDistance(vector1, vector2):

return sqrt(sum(power(vector2 - vector1, 2)))

# init centroids with random samples

def initCentroids(dataSet, k):

numSamples, dim = dataSet.shape

centroids = zeros((k, dim))

for i in range(k):

index = int(random.uniform(0, numSamples))

centroids[i, :] = dataSet[index, :]

return centroids

# k-means cluster

def kmeans(dataSet, k):

numSamples = dataSet.shape[0]

# first column stores which cluster this sample belongs to,

# second column stores the error between this sample and its centroid

clusterAssment = mat(zeros((numSamples, 2)))

clusterChanged = True

## step 1: init centroids

centroids = initCentroids(dataSet, k)

while clusterChanged:

clusterChanged = False

## for each sample

for i in xrange(numSamples):

minDist = 100000.0

minIndex = 0

## for each centroid

## step 2: find the centroid who is closest

for j in range(k):

distance = euclDistance(centroids[j, :], dataSet[i, :])

if distance <minDist:

minDist = distance

minIndex = j

## step 3: update its cluster

if clusterAssment[i, 0] != minIndex:

clusterChanged = True

clusterAssment[i, :] = minIndex, minDist**2

## step 4: update centroids

for j in range(k):

pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]

centroids[j, :] = mean(pointsInCluster, axis = 0)

print 'Congratulations, cluster complete!'

return centroids, clusterAssment

# show your cluster only available with 2-D data

def showCluster(dataSet, k, centroids, clusterAssment):

numSamples, dim = dataSet.shape

if dim != 2:

print "Sorry! I can not draw because the dimension of your data is not 2!"

return 1

mark = ['or'凯渗, 'ob', 'og', 'ok', '^r', '+r', 'sr'皮改, 'dr', '<r'燃孙判, 'pr']

if k >len(mark):

print "Sorry! Your k is too large! please contact Zouxy"

return 1

# draw all samples

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']

# draw the centroids

for i in range(k):

plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)

plt.show()

---