聚类分析——K-means算法

分类与聚类

分类： 类别是已知的，通过对已知分类的数据进行训练和学习，找到这些不同类的特征，再对未分类的数据进行分类。属于监督学习。

聚类： 事先不知道数据会分为几类，通过聚类分析将数据聚合成几个群体。聚类不需要对数据进行训练和学习。属于无监督学习。

k均值(k-means)算法

所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个元素映射到一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给定类别数量，是无监督学习的一种。目前聚类广泛应用于统计学、生物学、数据库技术和市场营销等领域，相应的算法也非常的多。本文仅介绍一种最简单的聚类算法——k均值（k-means）算法。

计算简介

k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点。
算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。

算法描述

输入：簇的数目k和包含n个对象的数据库。
输出：k个簇，使平方误差准则最小。

算法步骤：

为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心。
将样本集中的样本按照最小距离原则分配到最邻近聚类
使用每个聚类中的样本均值作为新的聚类中心。
重复步骤2.3直到聚类中心不再变化。

优缺点

优点：

原理简单，速度快
扩展性良好(大部分的计算都可以并行计算)
对大数据集有比较好的伸缩性

缺点：

需要指定聚类数量K(要生成的簇的数目)
对异常值敏感，因为算法并没有办法剔除异常值
对初始值敏感，对于不同的初始值，可能会导致不同结果
在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用

二维数据聚类实例

K-means算法

二维样本数据集，python3实现过程如下：

#coding=utf-8

import numpy as np
import matplotlib.pyplot as plt

#load data
def loadDataSet(fileName):
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines(): #for each line
        curLine = line.strip().split('\t')
        fltLine = list(map(float,curLine))
        dataMat.append(fltLine)
    return dataMat

# 簇
k = 4

#distance func
def distEclud(vecA,vecB):
    return np.sqrt(np.sum(np.power(vecA - vecB, 2)))  # la.norm(vecA-vecB) 向量AB的欧式距离

#init K points randomly
def randCent(dataSet, k):
    n = np.shape(dataSet)[1]
    centroids = np.mat(np.zeros((k,n)))#create centroid mat
    for j in range(n):#create random cluster centers, within bounds of each dimension
        minJ = np.min(dataSet[:,j])
        rangeJ = float(np.max(dataSet[:,j]) - minJ)
        centroids[:,j] = np.mat(minJ + rangeJ * np.random.rand(k,1))
    return centroids

#K-均值算法:
def kMeans(dataSet,k,distMeas=distEclud,createCent=randCent):
    #参数：dataset,num of cluster,distance func,initCen
    m=np.shape(dataSet)[0]
    clusterAssment=np.mat(np.zeros((m,2)))#store the result matrix,2 cols for index and error
    centroids=createCent(dataSet,k)
    clusterChanged=True
    while clusterChanged:
        clusterChanged=False
        for i in range(m):#for every points
            minDist = float('inf');
            minIndex = -1 #init
            for j in range(k):#for every k centers，find the nearest center
                distJI=distMeas(centroids[j,:],dataSet[i,:])
                if distJI<minDist:#if distance is shorter than minDist
                    minDist=distJI;
                    minIndex=j# update distance and index(类别)
            if clusterAssment[i,0] != minIndex:
                clusterChanged = True
                #此处判断数据点所属类别与之前是否相同（是否变化，只要有一个点变化就重设为True，再次迭代）
            clusterAssment[i,:] = minIndex,minDist**2
        #print(centroids)
        # update k center
        for cent in range(k):
            ptsInClust=dataSet[np.nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:] = np.mean(ptsInClust,axis=0)
    return centroids,clusterAssment

def plotDataSet(filename):
        # 导入数据
    datMat = np.mat(loadDataSet(filename))
        # 进行k-means算法其中k为4
    myCentroids, clustAssing = kMeans(datMat, k)
    fig = plt.figure()
    ax = fig.add_subplot(111)
    scatterMarkers=['s', 'o', '^', 'p', '8', 'd', 'v', 'h', '>', '<']

    for i in range(k):
        x1 = [];  y1 = []
        markerStyle = scatterMarkers[i % len(scatterMarkers)]
        for j in range(len(datMat)):
            if clustAssing[j][:,0] == i:
               x1.append(datMat[j][:,0])
               y1.append(datMat[j][:,1])
        ax.scatter(x1, y1, alpha=1,marker=markerStyle ,s=50)
        ax.scatter([myCentroids[:, 0]], [myCentroids[:, 1]], s=120, marker='+',c='b')
    plt.title('K-means')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.show()

if __name__ =="__main__":
    plotDataSet('testSet.txt')

聚类结果显示。将聚类划分为不同簇的数据，用不同的颜色和符号进行显示，同时画出最终的聚类中心。

Scikit-learn中K-means算法

Scikit-learn中有很多种K-means算法，这里使用传统的K-means，同样以二维样本数据集为例。

# coding:utf-8

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

def loadDataSet(fileName):
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines(): #for each line
        curLine = line.strip().split('\t')
        fltLine = list(map(float,curLine))
        dataMat.append(fltLine)
    return dataMat

data = np.array(loadDataSet('testSet.txt'))

k = 4  # 簇
fig = plt.figure()
ax = fig.add_subplot(111)

estimator = KMeans(n_clusters=4, random_state=9)
# fit_predict表示拟合+预测，也可以分开写
res = estimator.fit_predict(data)
# 各个类别的聚类中心值
centroids = estimator.cluster_centers_
# 预测类别标签结果
lable_pred = estimator.labels_
# 聚类中心均值向量的总和
inertia = estimator.inertia_

scatterMarkers=['s', 'o', '^', 'p', '8', 'd', 'v', 'h', '>', '<']
for i in range(k):
    markerStyle = scatterMarkers[i % len(scatterMarkers)]
    x1 = []; y1=[]
    for j in range(len(data)):
        if lable_pred[j] == i:
            x1.append(data[j, 0])
            y1.append(data[j, 1])
    # ax.scatter(data[:, 0], data[:, 1], c=res, marker=markerStyle)
    ax.scatter(x1, y1,alpha=1, marker=markerStyle ,s=50)
    ax.scatter(centroids[:,0], centroids[:,1],marker='+',s=120,c='b')
plt.title('sklearnKMeans')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()

聚类效果用散点图如下图所示。

应用场景

1.文档分类器

根据标签、主题和文档内容将文档分为多个不同的类别。这是一个非常标准且经典的K-means算法分类问题。首先，需要对文档进行初始化处理，将每个文档都用矢量来表示，并使用术语频率来识别常用术语进行文档分类，这一步很有必要。然后对文档向量进行聚类，识别文档组中的相似性。这里是用于文档分类的K-means算法实现案例。

2.物品传输优化

使用K-means算法的组合找到无人机最佳发射位置和遗传算法来解决旅行商的行车路线问题，优化无人机物品传输过程。这是该项目的白皮书。

3.识别犯罪地点

使用城市中特定地区的相关犯罪数据，分析犯罪类别、犯罪地点以及两者之间的关联，可以对城市或区域中容易犯罪的地区做高质量的勘察。这是基于德里飞行情报区犯罪数据的论文。

4.客户分类

聚类能过帮助营销人员改善他们的客户群（在其目标区域内工作），并根据客户的购买历史、兴趣或活动监控来对客户类别做进一步细分。这是关于电信运营商如何将预付费客户分为充值模式、发送短信和浏览网站几个类别的白皮书。对客户进行分类有助于公司针对特定客户群制定特定的广告。

5.球队状态分析

分析球员的状态一直都是体育界的一个关键要素。随着竞争越来愈激烈，机器学习在这个领域也扮演着至关重要的角色。如果你想创建一个优秀的队伍并且喜欢根据球员状态来识别类似的球员，那么K-means算法是一个很好的选择。具体细节和实现请参照这篇文章。

6.保险欺诈检测

机器学习在欺诈检测中也扮演着一个至关重要的角色，在汽车、医疗保险和保险欺诈检测领域中广泛应用。利用以往欺诈性索赔的历史数据，根据它和欺诈性模式聚类的相似性来识别新的索赔。由于保险欺诈可能会对公司造成数百万美元的损失，因此欺诈检测对公司来说至关重要。这是汽车保险中使用聚类来检测欺诈的白皮书。

7.乘车数据分析

面向大众公开的Uber乘车信息的数据集，为我们提供了大量关于交通、运输时间、高峰乘车地点等有价值的数据集。分析这些数据不仅对Uber大有好处，而且有助于我们对城市的交通模式进行深入的了解，来帮助我们做城市未来规划。这是一篇使用单个样本数据集来分析Uber数据过程的文章。

8.网络分析犯罪分子

网络分析是从个人和团体中收集数据来识别二者之间的重要关系的过程。网络分析源自于犯罪档案，该档案提供了调查部门的信息，以对犯罪现场的罪犯进行分类。这是一篇在学术环境中，如何根据用户数据偏好对网络用户进行 cyber-profile的论文。

9.呼叫记录详细分析

通话详细记录（CDR）是电信公司在对用户的通话、短信和网络活动信息的收集。将通话详细记录与客户个人资料结合在一起，这能够帮助电信公司对客户需求做更多的预测。在这篇文章中，你将了解如何使用无监督K-Means聚类算法对客户一天24小时的活动进行聚类，来了解客户数小时内的使用情况。

10.IT警报的自动化聚类

大型企业IT基础架构技术组件（如网络，存储或数据库）会生成大量的警报消息。由于警报消息可以指向具体的操作，因此必须对警报信息进行手动筛选，确保后续过程的优先级。对数据进行聚类可以对警报类别和平均修复时间做深入了解，有助于对未来故障进行预测。

参考：

K-Means算法的10个有趣用例