大数据/分布式系统

机器学习笔记（Chapter 10 - K-均值聚类算法）

聚类是一种无监督学习，将相似的对象归到同一个簇中，类似全自动分类，即类别体系也是自动构建的。聚类方法几乎可以应用于所有对性，簇内的对象越相似，聚类效果越好。K-均值聚类算法可以发现k个不同的簇，且每个簇的中心采用簇中所含值的均值构成。聚类与分类的区别在于，分类的目标事先已知，而聚类未知。

K-均值聚类

  • K-均值聚类算法的优点在于容易实现，缺点在于可能收敛到局部最小值，并且在大规模数据上收集较慢。适用于数值型数据。
  • K-均值聚类算法发现给定数据集的k个簇，这里的k是用户指定的，其的工作流程如下：首先随机确定k个初始点作为质心（注意这里的k个初始点不一定是数据集中的点，但一定在数据集的range内），然后对数据集中的每个点，寻找距离这个点最近的质心，并将其分配给这个质心对应的簇，该步完成后将每个簇的质心修改为该簇所有点的平均值。伪代码表示如下：
    • 创建k个点作为起始质心（通常随机选择）
    • 当任意一个点的簇分配结果发生改变时：
    •     对数据集中的每个点：
    •         对每个质心：
    •             计算质心与数据点之间的距离
    •         将数据点分配到距离其最近的簇
    •     对每一个簇，计算簇中所有点的均值并将均值作为质心。
  • K-均值算法要寻找最近的质心，因此需要进行某种距离计算，数据集上K-均值算法的性能会受到所选距离计算方法的影响。函数rendCent用于对数据集dataSet随机初始化k个簇质心，随机质心的大小在测试数据集的最小值和最大值之间。distEclud用于计算两个点之间的欧式距离，也可以切换成其他距离函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from numpy import *

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

def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2)))

def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        centroids[:,j] = minJ + rangeJ * random.rand(k,1)
    return centroids
  • 函数kMeans接受四个输入参数，用户需要指定数据集和划分的簇数k。kMeans函数一开始确定数据中数据点总数，clusterAssment记录簇分配结果，第一列记录簇索引值，第二列存储误差（当前点到簇的质心的距离）。按照计算质心->分配->重新计算的过程反复迭代，直到所有数据点的簇分配结果不再改变为止。选项axis=0表示沿着矩阵的列方向计算均值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def kMeans(dataSet, k, distMeas = distEclud, createCent = randCent):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroids = createCend(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            minDist = inf; minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j,:], dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI; minIndex = j
            if clusterAssment[i,0] != minIndex: clusterChanged = True
            clusterAssment[i,:] = minIndex, minDist**2
        #print centroids
        for cent in range(k):
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]
            centroids[cent,:] = mean(ptsInClust, axis=0)
    return centroids, clusterAssment

>>> import kMeans
>>> datMat = mat(kMeans.loadDataSet('testSet.txt'))
>>> myCentroids, clustAssing = kMeans.kMeans(datMat, 4)
[[-2.46154315  2.78737555]
 [-3.38237045 -2.9473363 ]
 [ 2.80293085 -2.7315146 ]
 [ 2.6265299   3.10868015]]

二分K-均值算法

  • 后处理：在K-均值聚类中簇的数目k是用户定义参数，可以利用clusterAssment中的误差值评价聚类分簇的正确性和质量。考虑下图的聚类结果，K-均值聚类算法收敛但聚类效果较差的原因是K-均值算法收敛到了局部最小值，而非全局最小值。可以使用SSE（误差平方和，clusterAssment[:,1]的和）评价聚类好坏，SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。因为对误差取平方，因此更加重视远离质心的点。增加簇的个数必然降低SSE的值，但不符合聚类目标。一种方法是对聚类生成的簇进行后处理，将具有最大SSE值得簇划分为两个簇，具体实现只要将属于最大簇的数据点用K-均值聚类，设定簇数k=2即可。为了保证簇总数不变，可以合并最近的质心，或者合并两个使得SSE值增幅最小的质心。
  • 二分K-均值类似后处理的切分思想，初始状态所有数据点属于一个大簇，之后每次选择一个簇切分成两个簇，这个切分满足使SSE值最大程度降低，直到簇数目达到k。另一种思路是每次选择SSE值最大的一个簇进行切分。前者伪代码如下。
    • 将所有点看成一个簇
    • 当簇数目小于k时
    • 对于每一个簇：
    •     计算总误差
    •     在给定的簇上面进行K-均值聚类（k=2）
    •     计算将该簇一分为二后的总误差
    • 选择使得误差最小的那个簇进行划分操作
  • 函数biKmeans是上面二分K-均值聚类算法的实现，首先创建clusterAssment储存数据集中每个点的分类结果和平方误差，用centList保存所有已经划分的簇，初始状态为整个数据集。while循环不停对簇进行划分，寻找使得SSE值最大程度减小的簇并更新，添加新的簇到centList中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def biKmeans(dataSet, k, distMeas=distEclud):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroid0 = mean(dataSet, axis = 0).tolist()[0]
    centList = [centroid0]
    for j in range(m):
        clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
    while (len(centList) < k):
        lowestSSE = inf
        for i in range(len(centList)):
            ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
            sseSplit = sum(splitClustAss[:,1])
            sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
            print "sseSplit, and notSplit: ", sseSplit, sseNotSplit
            if (sseSplit + sseNotSplit) < lowestSSE:
                bestCentToSplit = i
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSE = sseSplit + sseNotSplit
        bestClustAss[nonzero(bestClustAss[:,0].A==1)[0], 0] = len(centList)
        bestClustAss[nonzero(bestClustAss[:,0].A==0)[0], 0] = bestCentToSplit
        print "The bestCentToSplit is: ", bestCentToSplit
        print "The len of bestClustAss is: ", len(bestClustAss)
        centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]
        centList.append(bestNewCents[1,:].tolist()[0])
        clusterAssment[nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:] = bestClustAss
            # 按顺序更新
    return mat(centList), clusterAssment
  • 运行上述函数多次，聚类会收敛到全局最小值，而kMeans函数偶尔会陷入局部最小值。
1
2
3
4
5
6
7
8
9
>>> datMat3 = mat(kMeans.loadDataSet('testSet2.txt'))
>>> centList, myNewAssments = kMeans.biKmeans(datMat3,3)
sseSplit, and notSplit:  453.033489581 0.0
The bestCentToSplit is:  0
The len of bestClustAss is:  60
sseSplit, and notSplit:  12.7532631369 423.876240137
sseSplit, and notSplit:  77.5922493178 29.1572494441
The bestCentToSplit is:  1
The len of bestClustAss is:  40

对地图上的点进行聚类

  • 使用Yahho！PlaceFinder API收集数据，筛选出目标地点的经纬度，用matplotlib构建一个二位数据图，包含簇、位置和地图。将俄勒冈州的70个地点聚类，地址列表为portlandClubs,txt。可以在Yahoo开发者网络进行注册，创建一个桌面应用以获取appid。书上给出的yahooAPI的baseurl已经改变，并且yahoo目前的placefinder需要OAuth2验证，要使用该api，须在header里或者get方法中加入六个必须的参数。github上有oauth2供python使用，但是yahoo的BOOS GEO好像OAuth2验证出了问题，虽然写了新的placeFinder调用api的代码，仍然会有403错误，yahoo单方面的问题。几个链接，要vpn：yahoo BOSS GEO的OAuth说明，yahoo placeFinder指南。上面的代码来自书上，下面的是适用于新的api的代码，但会返回403。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import urllib
import json
def geoGrab(stAddress, city):
    apiStem = 'http://where.yahooapis.com/geocode?'
    params = {}
    params['flags'] = 'J'
    params['appid'] = 'ppp68N8t'
    params['location'] = '%s %s' % (stAddress, city)
    url_params = urllib.urlencode(params)
    yahooApi = apiStem + url_params
    print yahooApi
    c = urllib.urlopen(yahooApi)
    print c.read()
    return json.loads(c.read())

from time import sleep
def massPlaceFind(fileName):
    fw = open('places.txt', 'w')
    for line in open(fileName).readlines():
        line = line.strip()
        lineArr = line.split('\t')
        retDict = geoGrab(lineArr[1], lineArr[2])
        if retDict['ResultSet']['Error'] == 0:
            lat = float(retDict['ResultSet']['Results'][0]['latitude'])
            lng = float(retDict['ResultSet']['Results'][0]['longitude'])
            print "%s\t%f\t%f" % (lineArr[0], lat, lng)
            fw.write('%s\t%f\t%f' % (line, lat, lng))
        else:
            print "error fetching"
        sleep(1)
    fw.close()

# Upper codes are from the book.

# pst.py(codes for new apis)
import urllib2
import oauth2 as oauth
import time

OAUTH_CONSUMER_KEY = "dj0yJmk9OTRRNmJWaEQwSWhPJm********RHdzROekV5TjJFbWN\
HbzlNQS0tJnM9Y29uc3VtZXJzZWNyZXQmeD03OQ--"
OAUTH_CONSUMER_SECRET = "8caf5cfb4e8****2c30418f26805f99aa8e49728"
def oauth_request(url, params,method="GET"):
    params['oauth_version'] = "1.0" #,
    params['oauth_nonce'] = oauth.generate_nonce() #,
    params['oauth_timestamp'] = int(time.time())
    consumer = oauth.Consumer(key=OAUTH_CONSUMER_KEY,
                              secret=OAUTH_CONSUMER_SECRET)
    params['oauth_consumer_key'] = consumer.key
    req = oauth.Request(method=method, url=url, parameters=params)
    req.sign_request(oauth.SignatureMethod_HMAC_SHA1(), consumer, None)
    return req
if __name__ == "__main__":
    url = "http://yboss.yahooapis.com/geo/placefinder?"
    req = oauth_request(url, params={"q": "lianyungang"})
    # This one is a bit nasty. Apparently the BOSS API does not like
    # "+" in its URLs so you have to replace "%20" manually.
    # Not sure if the API should be expected to accept either.
    # Not sure why to_url does not just return %20 instead...
    # Also, oauth2.Request seems to store parameters as unicode and forget
    # to encode to utf8 prior to percentage encoding them in its to_url
    # method. However, it's handled correctly for generating signatures.
    # to_url fails when query parameters contain non-ASCII characters. To
    # work around, manually utf8 encode the request parameters.
    req['q'] = req['q'].encode('utf8')
    req_url = req.to_url().replace('+', '%20')
    print req_url
    result = urllib2.urlopen(req_url)
  • github附书代码里有生成好的place.txt，直接拿来使用。下面代码中，distSLC用球面余弦定理计算地球表面两个点之间的距离，clusterClubs将文件中的地点进行聚类并画出结果。为了画出这些簇，首先创建一幅图和一个矩形，然后用该矩形决定绘制图的哪一部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def distSLC(vecA, vecB):
    a = sin(vecA[0,1]*pi/180) * sin(vecB[0,1]*pi/180)
    b = cos(vecA[0,1]*pi/180) * cos(vecB[0,1]*pi/180) *\
     cos(pi*(vecB[0,0]-vecA[0,0])/180)
    return arccos(a+b)*6371.0

import matplotlib
import matplotlib.pyplot as plt
def clusterClubs(numClust=5):
    datList = []
    for line in open('places.txt').readlines():
        lineArr = line.split('\t')
        datList.append([float(lineArr[4]), float(lineArr[3])])
    datMat = mat(datList)
    myCentroids, clustAssing = biKmeans(datMat, numClust, distMeas = distSLC)
    fig = plt.figure()
    rect = [0.1, 0.1, 0.8, 0.8]
    scatterMarkers = ['s', 'o', '^', '8', 'p', 'd', 'v', 'h', '>', '<']
    axprops = dict(xticks=[], yticks=[])
    ax0 = fig.add_axes(rect, label = 'ax0', **axprops)
    imgP = plt.imread('Portland.png')
    ax0.imshow(imgP)
    ax1 = fig.add_axes(rect, label = 'ax1', frameon = False)
    for i in range(numClust):
        ptsInCurrCluster = datMat[nonzero(clustAssing[:,0].A == i)[0],:]
        markerSytle = scatterMarkers[i%len(scatterMarkers)]
        ax1.scatter(ptsInCurrCluster[:,0].flatten().A[0], \
            ptsInCurrCluster[:,1].flatten().A[0],\
            marker = markerSytle, s=90)
    ax1.scatter(myCentroids[:,0].flatten().A[0], myCentroids[:,1].flatten().A[0],\
        marker = '+', s=300)
    plt.show()
  • 运行结果如下，分别是划分为5个簇、7个簇的情况。多次运行可以找到最佳的分簇数目和方法。

K-均值聚类算法总结

无监督学习指事先不知道要寻找的内容，没有目标变量。聚类将数据点归到多个簇中，可以使用多种方法计算相似度，实际使用时也应多次运行取较优结果。K-均值算法是一种广泛使用的聚类算法，k是用户指定的要创建的簇的数目，该算法非常有效但容易受到初始簇质心的影响。可以使用二分K-均值聚类算法获得更好的效果。

参考文献： 《机器学习实战 - 美Peter Harrington》

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2016/02/21/machinelearning10/) 、作者信息（Forec）和本声明。

分享到