实现kMeans聚类

---

kMeans算法介绍

概要

kMeans算法是一种无监督学习聚类算法。优点是易于实现，缺点是可能收敛到局部最小值，且在大规模数据集上收敛较慢，它适用于数值型数据。kMeans算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，簇间相似度较低。

原理

1. 随机选择k个点作为聚类中心（质心）;
2. 计算每一个样本点与k个聚类中心的距离，并将该样本点归入最近的簇;
3. 计算每个簇的所有点的均值，将该均值作为新的聚类中心;
4. 重复2、3步，直到所有聚类中心不再改变。

数据集分析

这是一个包含2800个样本，每个样本有5个属性的数据集。

为了最终的聚类结果准确率测试，我们还提供了每个样本组合而成的验证集。如下所示：

---

预期目的

1. 针对数据集实现kMeans聚类，得到聚类结果和聚类中心。

2. 结合验证集中，分析聚类结果的正确率。

---

数据加载

使用第三方包pyexcel-xls
安装方法：$ pip install pyexcel-xls

#!/usr/bin/python
# -*- coding:utf-8 -*-

from pyexcel_xls import get_data

def readXls(filePath):
    dataSet = []
    xls_data = get_data(filePath)
    for sheet_n in xls_data.keys():
        if sheet_n == u'Sheet1':
            dataSet = xls_data[sheet_n]
    return mat(dataSet)

---

距离度量

使用Euclidean Distance

dist(X,Y)=∑i=1n(xi−yi)2√

def calculateDist(vec1, vec2):
    return sqrt(sum(power(vec1 - vec2, 2)))

---

生成”随机”聚类中心

1. 随机：并非绝对随机，而是在所有样本每个属性的最小与最大值范围内生成的相对随机的一个值，作为聚类中心;
2. 参数：样本集dataSet和聚类中心个数k;

def createRandCentroids(dataSet, k):
    n = shape(dataSet)[1]   # return the length of row
    centroids =  mat(zeros((k,n)))
    for j in range(n):
        colMinJ = min(dataSet[:,j])
        colMaxJ = max(dataSet[:,j])
        colRangeJ = colMaxJ - colMinJ        
        centroids[:,j] = colMinJ + random.rand(k, 1) * colRangeJ   
    return centroids

---

kMeans算法实现

def kMeans(dataSet, centroids, distMeas = caculateDist):
    m = shape(dataSet)[0]
    k = shape(centroids)[0]  # return k
    clusterRes = mat(zeros((m, 2)))  # store the allocation of cluster
    allocateFinished = True
    while allocateFinished:
        allocateFinished = False
        for i in range(m):
            dist = {}
            for j in range(k):
                dist[distMeas(centroids[j,:], dataSet[i,:])] = j
            if clusterRes[i,0] != dist.get(min(dist.keys())):
                allocateFinished = True
            clusterRes[i,:] = [dist.get(min(dist.keys())),min(dist.keys())]
        for i in range(k):
            #centroids[i,:] = [ mean(dataSet[j,:], axis=0) for j in range(m) if clusterRes[j,0] == i]
            for j in range(m):
                if clusterRes[j,0] == i:
                    centroids[i,:] = mean(dataSet[j,:],axis=0)

    # print 'Final Centroids:\n',centroids
    # print 'Final clusterRes:',clusterRes
    return centroids, clusterRes

---

结果分析

1. 使用thyroid_test_data.xlsx数据集时：
   

2. 使用thyroid_train_data.xlsx数据集时：
   

3. 由于并非每次聚类都会收敛到全局最小值而有可能收敛到局部最小值，就会产生很差的聚类效果：
   

4. 二分kMeans可以通过选择能最大程度降低SSE的簇进行新簇划分的思想可以解决kMeans收敛到局部最小值的问题，但由于验证集中只有两个簇，针对这个样本集来说，我做的不就是k=2的kMeans聚类。因此，对于这个数据集没有使用二分kMeans的必要。

---