一组属性组成的数据记录可以用一个N维向量表示。我们假若用这样一幅二维图像表示数据集，聚类便是努力使相邻的样本聚合到同一个簇。
这幅图的样本分布就没那么明显了
《数据挖掘》一书介绍了在聚类分析中的四类方法。这里要讲的三种都属于基于划分（Partition）的方法，对于要生成的簇数k，划分会生成k个簇（不排除空簇），使得同簇内的对象相似，而不同簇的相异。形心
我们用一个簇的形心，类似一个抽象几何体的中心点来表示一个簇，则属于该簇的所有点与其形心都有一个距离值，一个簇的质量（类似物理上的质量概念）可以用它的簇内变差（每个样例点与形心的欧几里德距离）度量，定义：
K-均值
K均值（K-Means）的算法把簇的形心定义为簇内点的均值。伪代码如下：
function K-Means-Clustering(examples, k) returns a set of k clusters select k initial centroids from examples randomly //选取初始点 do for instance in examples instance.cluster = cluster with argmin(dist(ci, instance)) //选择最近形心 for c in clusters c.ci = average(for e in c) //更新形心 while nothing change any more return clusters这个过程是迭代的，首先随机选出k个样例作为k个簇的起始中心点，然后为每个对象分配到最近（最相似）的簇。这个算法循环地努力优化簇内变差，每一次的迭代，中心点都会被重新计算，然后下一次分配。
这个算法很有启发性，但也有很明显的局限。因为其起始点的随机性，比如说第一幅图中四个明显区分开的聚簇，如果我们初始选择的中心点有几个都在同一个聚簇，那结果会很难看。又或者如下图的例子：
编程细节上如何结束迭代？我们都知道计算机在浮点数运算的时候精度是一个很大的问题，什么条件下判断聚簇方案在经过一次迭代后没有发生变化从而结束循环？《集体智慧编程》一书中给出的方案是为每个样例记录其上一次分到的类，若一次迭代中没有任何样例的聚簇发生变化，则终止。在赛时我还没看这本书，用的是记录每次中心点的位置，当中心点没有发生变化（具体表现是前后的改变距离小于一个很小的浮点数）时结束。现在看来是前一个方法准确。
对象总数为n，k是簇数，t为迭代次数，则K均值的复杂度是
K众数
当我们用向量表示一个样例，其每个维我们假定为连续值。那么当我们需要面对离散值，或者说标称属性呢？离散的情况使得均值无法计算，这时候我们采用计算众数作为中心点。同时欧几里德距离要换成标称距离，也就是转换离散值为连续值。通过统计频率的方法来更新。决策树分类时美国国会投票的例子就可以用这个方法。我的转换方法是yes和no对应正负一，unknown对应0。
K众数对美国国会数据聚类代码：
#K-mode
import random
import copy
from math import *
class instance():
def __init__(self, party, votes):
self.party = party
self.votes = votes
self.classification = None
dataFile = open('dataset.txt', 'r')
datas = dataFile.readlines()
database = []
for line in datas:
line = line[:-2]
attrs = line.split(',')
member = instance(attrs[0], attrs[1:])
database.append(member)
def normDistance(vector1, vector2):
total = 0
normDict = {"y" : 1, "?" : 0, "n" : -1}
for i in range(0, len(vector1.votes)):
total += pow(normDict[vector1.votes[i]] - normDict[vector2.votes[i]], 2)
return sqrt(total)
def kMode(dataSet, k):
selectIndex = [2, 8]
centroids = []
for i in selectIndex:
cent = copy.deepcopy(dataSet[i])
centroids.append(cent)
clusterChanged = True
times = 0
while clusterChanged:
clusterChanged = False
times += 1
for record in dataSet:
minIndex = 0
minDist = 1000000000000
for i in range(k):
dist = normDistance(centroids[i], record)
if dist < minDist:
minDist = dist
minIndex = i
if record.classification != minIndex:
record.classification = minIndex
clusterChanged = True
counter = []
for i in range(k):
init = []
for j in range(len(centroids[0].votes)):
init.append({"y" : 0, "?" : 0, "n" : 0})
counter.append(init)
for record in dataSet:
for i in range(len(record.votes)):
counter[record.classification][i][record.votes[i]] += 1
for i in range(k):
for j in range(len(centroids[i].votes)):
maxVote = 0
for op in counter[i][j]:
if counter[i][j][op] > maxVote:
maxVote = counter[i][j][op]
maxOption = op
centroids[i].votes[j] = maxOption
print "iteration time: %d" % times
return centroids
cen = kMode(database, 2)
for i in range(2):
print "cluster %d" % i
stat = {"democrat" : 0, "republican" : 0}
for record in database:
if record.classification == i:
stat[record.party] += 1
print stat
print ""
聚类结果还是说得过去的。。。=-=
K众数（K-modes）实际只是K均值的一个变体，其思路是一致的。在混合数值和标称值的数据中，两种方法实际可以结合使用。
K中值
不要和基于代表对象的K中心点混淆。K中值这个算法虽然《数据挖掘》一书中没提到，但大家在发现前面的问题后其实很容易可以想到。在数字图像处理中，类似的情况是椒盐噪声的去除，椒盐噪声一定程度上可以类比成离群值。如果我们使用均值滤波来去除，其效果一定没有中值滤波好，正是因为均值滤波中噪声会对最终结果有一定贡献率，而中值则是直接从样本中选取样例。
K中值在重新计算中心点的时候，使用的是曼哈顿中值，即
新中心点的每一维的值，都是其簇内样例中对应维的中值。K中值能够减少K均值的敏感性。
没有评论 :
发表评论