聚类
通过物品特征来计算距离，并自动分类到不同的群集或组中。
层次聚类算法
对于层次聚类算法，我们不需要预先指定分类的数量，这个算方法会将每条数据都当作是一个分类，每次迭代的时候合并距离最近的两个分类，直到剩下一个分类为止。
聚类的结果：顶层有一个大分类，这个分类下有两个子分类，每个子分类下又有两个子分类，依次内推，层级聚类也因此得名。
在合并的时候，我们会计算两个分类之间的距离，可以采用不同的方法，如下图 A、B、C 三个分类，我们可以采取：
单链聚类
在单链聚类中，分类之间的距离由两个分类相距最近的两个元素决定。如上图中分类 A 和分类 B 的距离由 A1 和 B1 的距离决定，因为这个距离小于 A1 到 B2、A2 到 B1 的距离，这样一来我们会将 A 和 B 进行合并。
全链聚类
在全链聚类中，分类之间的距离由两个分类相距最远的两个元素决定。因此上图中分类 A 和 B 的距离是 A2 到 B2 的距离，最后会将分类 B 和 C 进行合并。
平均链接聚类
在平均链接聚类中，分类之间的距离由分类之间两两元素的平均距离决定。因此上图中会将分类 B 和 C 进行合并。
例：用狗的高度和重量来进行聚类
计算欧几里得距离：
计算过程
第一步：找到最近的两个元素，进行聚类
第二部：在找到距离最近你的两个元素，进行聚类：
第三步：重复上面的步骤
算法实现层次聚类
from queue import PriorityQueue
import math
"""
层次聚类示例代码
"""
def getMedian(alist):
"""计算中位数"""
tmp = list(alist)
tmp.sort()
alen = len(tmp)
if (alen % 2) == 1:
return tmp[alen // 2]
else:
return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2
def normalizeColumn(column):
"""计算修正的标准分"""
median = getMedian(column)
asd = sum([abs(x - median) for x in column]) / len(column)
result = [(x - median) / asd for x in column]
return result
class hClusterer:
"""该聚类器默认数据的第一列是标签，其它列是数值型的特征。"""
def __init__(self, filename):
file = open(filename)
self.data = {}
self.counter = 0
self.queue = PriorityQueue()
lines = file.readlines()
file.close()
header = lines[0].split(',')
self.cols = len(header)
self.data = [[] for i in range(len(header))]
for line in lines[1:]:
cells = line.split(',')
toggle = 0
for cell in range(self.cols):
if toggle == 0:
self.data[cell].append(cells[cell])
toggle = 1
else:
self.data[cell].append(float(cells[cell]))
# 标准化特征列（即跳过第一列）
for i in range(1, self.cols):
self.data[i] = normalizeColumn(self.data[i])
###
### 数据已经读入内存并做了标准化，对于每一条记录，将执行以下步骤：
### 1. 计算该分类和其他分类的距离，如当前分类的下标是1，
### 它和下标为2及下标为3的分类之间的距离用以下形式表示：
### {2: ((1, 2), 1.23), 3: ((1, 3), 2.3)... }
### 2. 找出距离最近的分类；
### 3. 将该分类插入到优先队列中。
###
# 插入队列
rows = len(self.data[0])
for i in range(rows):
for i in range(rows):
minDistance = 99999
nearestNeighbor = 0
neighbors = {}
for j in range(rows):
if i != j:
dist = self.distance(i, j)
if i < j:
pair = (i,j)
else:
pair = (j,i)
neighbors[j] = (pair, dist)
if dist < minDistance:
minDistance = dist
nearestNeighbor = j
nearestNum = j
# 记录这两个分类的配对信息
if i < nearestNeighbor:
nearestPair = (i, nearestNeighbor)
else:
nearestPair = (nearestNeighbor, i)
# 插入优先队列
self.queue.put((minDistance, self.counter,
[[self.data[0][i]], nearestPair, neighbors]))
self.counter += 1
def distance(self, i, j):
sumSquares = 0
for k in range(1, self.cols):
sumSquares += (self.data[k][i] - self.data[k][j])**2
return math.sqrt(sumSquares)
def cluster(self):
done = False
while not done:
topOne = self.queue.get()
nearestPair = topOne[2][1]
if not self.queue.empty():
nextOne = self.queue.get()
nearPair = nextOne[2][1]
tmp = []
## 我从队列中取出了两个元素：topOne和nextOne，
## 检查这两个分类是否是一对，如果不是就继续从优先队列中取出元素，
## 直至找到topOne的配对分类为止。
while nearPair != nearestPair:
tmp.append((nextOne[0], self.counter, nextOne[2]))
self.counter += 1
nextOne = self.queue.get()
nearPair = nextOne[2][1]
## 将不处理的元素退回给优先队列
for item in tmp:
self.queue.put(item)
if len(topOne[2][0]) == 1:
item1 = topOne[2][0][0]
else:
item1 = topOne[2][0]
if len(nextOne[2][0]) == 1:
item2 = nextOne[2][0][0]
else:
item2 = nextOne[2][0]
## curCluster即合并后的分类
curCluster = (item1, item2)
## 对于这个新的分类需要做两件事情：首先找到离它最近的分类，然后合并距离字典。
## 如果item1和元素23的距离是2，item2和元素23的距离是4，我们取较小的那个距离，即单链聚类。
minDistance = 99999
nearestPair = ()
nearestNeighbor = ''
merged = {}
nNeighbors = nextOne[2][2]
for (key, value) in topOne[2][2].items():
if key in nNeighbors:
if nNeighbors[key][1] < value[1]:
dist = nNeighbors[key]
else:
dist = value
if dist[1] < minDistance:
minDistance = dist[1]
nearestPair = dist[0]
nearestNeighbor = key
merged[key] = dist
if merged == {}:
return curCluster
else:
self.queue.put( (minDistance, self.counter, [curCluster, nearestPair, merged]))
self.counter += 1
def printDendrogram(T, sep=3):
"""打印二叉树状图。树的每个节点是一个二元组。这个方法摘自：
http://code.activestate.com/recipes/139422-dendrogram-drawing/"""
def isPair(T):
return type(T) == tuple and len(T) == 2
def maxHeight(T):
if isPair(T):
h = max(maxHeight(T[0]), maxHeight(T[1]))
else:
h = len(str(T))
return h + sep
activeLevels = {}
def traverse(T, h, isFirst):
if isPair(T):
traverse(T[0], h-sep, 1)
s = [' ']*(h-sep)
s.append('|')
else:
s = list(str(T))
s.append(' ')
while len(s) < h:
s.append('-')
if (isFirst >= 0):
s.append('+')
if isFirst:
activeLevels[h] = 1
else:
del activeLevels[h]
A = list(activeLevels)
A.sort()
for L in A:
if len(s) < L:
while len(s) < L:
s.append(' ')
s.append('|')
print (''.join(s))
if isPair(T):
traverse(T[1], h-sep, 0)
traverse(T, maxHeight(T), -1)
filename = '/Users/raz/Dropbox/guide/data/dogs.csv'
hg = hClusterer(filename)
cluster = hg.cluster()
printDendrogram(cluster)
k-means 聚类算法
使用 k-means 算法时需要指定分类的数量，这也是算法名称中“k”的由来。
k-means 聚类过程
- 1、随机选取 k 个元素作为中心点；
- 2、根据距离将各个点分配给中心点；
- 3、计算新的中心点；
- 4、重复2、3，直至满足条件。
例：将一下点分成两个类：
第一步：随机选取中心点
(1, 4) 作为分类 1 的中心点，(4, 2) 作为分类 2 的中心点；
第三步：更新中心点
通过计算平均值来更新中心点，如 x 轴的均值是：( 1 + 1 + 2 ) / 3 = 4 / 3 = 1.33
y 轴是：( 2 + 4 + 3) / 3 = 9 / 3 = 3
因此分类 1 的中心点是( 1.33, 3 )，计算得分类 2 的中心点是( 4, 2.4 )
第四步 重复第二、第三步，直到中心点不发生变化
得到分类 1 的中心点是( 1.2, 2.75 )，计算得分类 2 的中心点是( 4.5, 2.5 )
误差平方和（SSE）
可以使用误差平方和（或称离散程度）来评判聚类结果的好坏，它的计算方法是：计算每个点到中心点的距离平方和。
第二个求和符号是遍历分类中所有的点；
dist 指代距离计算公式（如曼哈顿距离、欧几里距离）；
计算数据点 x 和中心点 cj 之间的距离，平方后相加。
算法实现
import math
import random
"""
K-means算法
"""
def getMedian(alist):
"""计算中位数"""
tmp = list(alist)
tmp.sort()
alen = len(tmp)
if (alen % 2) == 1:
return tmp[alen // 2]
else:
return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2
def normalizeColumn(column):
"""计算修正的标准分"""
median = getMedian(column)
asd = sum([abs(x - median) for x in column]) / len(column)
result = [(x - median) / asd for x in column]
return result
class kClusterer:
"""kMeans聚类算法，第一列是分类，其余列是数值型特征"""
def __init__(self, filename, k):
"""k是分类的数量，该函数完成以下功能：
1. 读取filename的文件内容
2. 按列存储到self.data变量中
3. 计算修正的标准分
4. 随机选取起始点
5. 将各个点分配给中心点
"""
file = open(filename)
self.data = {}
self.k = k
self.counter = 0
self.iterationNumber = 0
# 用于跟踪本次迭代有多少点的分类发生了变动
self.pointsChanged = 0
# 误差平方和
self.sse = 0
#
# 读取文件
#
lines = file.readlines()
file.close()
header = lines[0].split(',')
self.cols = len(header)
self.data = [[] for i in range(len(header))]
# 按列存储数据，如self.data[0]是第一列的数据，
# self.data[0][10]是第一列第十行的数据。
for line in lines[1:]:
cells = line.split(',')
toggle = 0
for cell in range(self.cols):
if toggle == 0:
self.data[cell].append(cells[cell])
toggle = 1
else:
self.data[cell].append(float(cells[cell]))
self.datasize = len(self.data[1])
self.memberOf = [-1 for x in range(len(self.data[1]))]
#
# 标准化
#
for i in range(1, self.cols):
self.data[i] = normalizeColumn(self.data[i])
# 随机选取起始点
random.seed()
self.centroids = [[self.data[i][r] for i in range(1, len(self.data))] for r in random.sample(range(len(self.data[0])), self.k)]
self.assignPointsToCluster()
def updateCentroids(self):
"""根据分配结果重新确定聚类中心点"""
members = [self.memberOf.count(i) for i in range(len(self.centroids))]
self.centroids = [[sum([self.data[k][i] for i in range(len(self.data[0])) if self.memberOf[i] == centroid])/members[centroid] for k in range(1, len(self.data))] for centroid in range(len(self.centroids))]
def assignPointToCluster(self, i):
"""根据距离计算所属中心点"""
min = 999999
clusterNum = -1
for centroid in range(self.k):
dist = self.euclideanDistance(i, centroid)
if dist < min:
min = dist
clusterNum = centroid
# 跟踪变动的点
if clusterNum != self.memberOf[i]:
self.pointsChanged += 1
# 计算距离平方和
self.sse += min**2
return clusterNum
def assignPointsToCluster(self):
"""分配所有的点"""
self.pointsChanged = 0
self.sse = 0
self.memberOf = [self.assignPointToCluster(i) for i in range(len(self.data[1]))]
def euclideanDistance(self, i, j):
"""计算欧几里得距离"""
sumSquares = 0
for k in range(1, self.cols):
sumSquares += (self.data[k][i] - self.centroids[j][k-1])**2
return math.sqrt(sumSquares)
def kCluster(self):
"""开始进行聚类，重复以下步骤：
1. 更新中心点
2. 重新分配
直至变动的点少于1%。
"""
done = False
while not done:
self.iterationNumber += 1
self.updateCentroids()
self.assignPointsToCluster()
#
# 如果变动的点少于1%则停止迭代
#
if float(self.pointsChanged) / len(self.memberOf) < 0.01:
done = True
print("Final SSE: %f" % self.sse)
def showMembers(self):
"""输出结果"""
for centroid in range(len(self.centroids)):
print ("\n\nClass %i\n========" % centroid)
for name in [self.data[0][i] for i in range(len(self.data[0])) if self.memberOf[i] == centroid]:
print (name)
# 对犬种数据进行聚类，令k=3
# 请自行修改文件路径
km = kClusterer('../../data/dogs.csv', 3)
km.kCluster()
km.showMembers()
k-means++
k-means 是 50 年代发明的算法，它的实现并不复杂，但它有一个明显的缺点，在算法一开始需要随机选取 k 个起始点，有时选取的点产生最佳结果，而有时会让结果变得很差。k-means++ 则改进了起始点的选取，其余的和 k-means 一致。
k-means++ 选取起始点的过程：
- 1、随机选取一个点；
- 2、重复一下步骤，直到选完 k 个点：
i.计算每个数据点（dp）到各个中心点距离（D），选取最小的值，记为 D(dp)；
ii.根据 D(dp) 的概率来随机选取一个点作为中心点。
起始点选取总结：
第一个点还是随机的，但后续的点就会尽量选择离现有中心点更远的点。
算法实现
第一步
将：
self.centroids = [[self.data[i][r] for i in range(1, len(self.data))] for r in random.sample(range(len(self.data[0])), self.k)]
修改为：
self.selectInitialCentroids()
第二步实现 selectInitialCentroids
def distanceToClosestCentroid(self, point, centroidList):
result = self.eDistance(point, centroidList[0])
for centroid in centroidList[1:]:
distance = self.eDistance(point, centroid)
if distance < result:
result = distance
return result
def selectInitialCentroids(self):
"""实现k-means++算法中的起始点选取过程"""
centroids = []
total = 0
# 首先随机选取一个点
current = random.choice(range(len(self.data[0])))
centroids.append(current)
# 开始选取剩余的点
for i in range(0, self.k - 1):
# 计算每个点到最近的中心点的距离
weights = [self.distanceToClosestCentroid(x, centroids) for x in range(len(self.data[0]))]
total = sum(weights)
# 转换为权重
weights = [x / total for x in weights]
# 开始随机选取
num = random.random()
total = 0
x = -1
# 模拟轮盘游戏
while total < num:
x += 1
total += weights[x]
entroids.append(x)
self.centroids = [[self.data[i][r] for i in range(1, len(self.data))] for r in centroids]
# -*- coding:utf-8 -*-
'''
Created on 2018年11月29日
@author: KingSley
'''
import math
import random
"""
K-means++ 算法
"""
def getMedian(alist):
"""计算中位数"""
tmp = list(alist)
tmp.sort()
alen = len(tmp)
if (alen % 2) == 1:
return tmp[alen // 2]
else:
return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2
def normalizeColumn(column):
"""计算修正的标准分"""
median = getMedian(column)
asd = sum([abs(x - median) for x in column]) / len(column)
result = [(x - median) / asd for x in column]
return result
class kClusterer:
"""
K-means 聚类算法，第一列是分类，其余列是数值型特征
"""
def __init__(self, filename, k):
"""
k 是分类的数量，该函数完成以下功能：
1. 读取 filename 的文件内容
2. 按列存储到 self.data 变量中
3. 计算修正的标准分
4. 随机选取起始点
5. 将各个点分配给中心点
"""
file = open(filename)
self.data = {}
self.k = k
self.counter = 0
self.iterationNumber = 0
# 用于跟踪本次迭代有多少点的分类发生了变动
self.pointsChanged = 0
# 误差平方和
self.sse = 0
# 读取文件
lines = file.readlines()
file.close()
header = lines[0].split(',')
self.cols = len(header)
self.data = [[] for i in range(len(header))]
# 按列存储数据，如 self.data[0] 是第一列的数据
# self.data[0][10] 是第一列第十行的数据
for line in lines[1:]:
cells = line.split(',')
toggle = 0
for cell in range(self.cols):
if toggle == 0:
self.data[cell].append(cells[cell])
toggle = 1
else:
self.data[cell].append(float(cells[cell]))
self.datasize = len(self.data[1])
self.memberOf = [-1 for x in range(len(self.data[1]))]
# 标准化
for i in range(1, self.cols):
self.data[i] = normalizeColumn(self.data[i])
# 随机选取起始点
random.seed()
self.selectInitialCentroids()
self.assignPointsToCluster()
def showData(self):
for i in range(len(self.data[0])):
print("%20s %8.4f %8.4f" %
(self.data[0][i], self.data[1][i], self.data[2][i]))
def distanceToClosestCentroid(self, point, centroidList):
result = self.eDistance(point, centroidList[0])
for centroid in centroidList[1:]:
distance = self.eDistance(point, centroid)
if distance < result:
result = distance
return result
def selectInitialCentroids(self):
"""实现 k-means++ 算法中的起始点选取过程"""
centroids = []
total = 0
# 首先随机选取一个点
current = random.choice(range(len(self.data[0])))
centroids.append(current)
# 开始选取剩余的点
for i in range(0, self.k - 1):
# 计算每个点到最近的中心点的距离
weights = [self.distanceToClosestCentroid(x, centroids)
for x in range(len(self.data[0]))]
total = sum(weights)
# 转换为权重
weights = [x / total for x in weights]
# 开始随机选取
num = random.random()
total = 0
x = -1
# 模拟轮盘游戏
while total < num:
x += 1
total += weights[x]
centroids.append(x)
self.centroids = [[self.data[i][r] for i in range(1, len(self.data))]
for r in centroids]
def updateCentroids(self):
"""根据分配结果重新确定聚类中心点"""
members = [self.memberOf.count(i) for i in range(len(self.centroids))]
self.centroids = [[sum([self.data[k][i]
for i in range(len(self.data[0]))
if self.memberOf[i] == centroid])/members[centroid]
for k in range(1, len(self.data))]
for centroid in range(len(self.centroids))]
def assignPointToCluster(self, i):
"""根据距离计算所属中心点"""
min = 999999
clusterNum = -1
for centroid in range(self.k):
dist = self.euclideanDistance(i, centroid)
if dist < min:
min = dist
clusterNum = centroid
# 跟踪变动的点
if clusterNum != self.memberOf[i]:
self.pointsChanged += 1
# 计算距离平方和
self.sse += min**2
return clusterNum
def assignPointsToCluster(self):
"""分配所有的点"""
self.pointsChanged = 0
self.sse = 0
self.memberOf = [self.assignPointToCluster(i)
for i in range(len(self.data[1]))]
def eDistance(self, i, j):
"""点 i 到质心 j 的距离计算"""
sumSquares = 0
for k in range(1, self.cols):
sumSquares += (self.data[k][i] - self.data[k][j])**2
return math.sqrt(sumSquares)
def euclideanDistance(self, i, j):
"""计算欧几里得距离"""
sumSquares = 0
for k in range(1, self.cols):
sumSquares += (self.data[k][i] - self.centroids[j][k-1])**2
return math.sqrt(sumSquares)
def kCluster(self):
""" 开始进行聚类，重复以下步骤：
1. 更新中心点
2. 重新分配
直至变动的点少于 1%
"""
done = False
while not done:
self.iterationNumber += 1
self.updateCentroids()
self.assignPointsToCluster()
# 如果变动的点少于 1% 则停止迭代
if float(self.pointsChanged) / len(self.memberOf) < 0.01:
done = True
print("Final SSE: %f" % self.sse)
def showMembers(self):
"""输出结果"""
for centroid in range(len(self.centroids)):
print ("\n\nClass %i\n========" % centroid)
for name in [self.data[0][i] for i in range(len(self.data[0]))
if self.memberOf[i] == centroid]:
print (name)
### 对犬种数据进行聚类，令 k = 3
km = kClusterer('dogs.csv', 3)
km.kCluster()
km.showMembers()
参考原文作者：Ron Zacharski CC BY-NC 3.0] https://github.com/egrcc/guidetodatamining
