聚类介绍
聚类在机器学习，数据挖掘，模式识别，图像分析以及生物信息等领域有广泛的应用。聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性，常见的包括在坐标系中更加短的空间距离（一般是欧式距离）等。
聚类的应用
在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。诸如此类，聚类有着广泛的实际应用。
K-Means聚类算法简介
K-Means是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值是因为它可以发现 K 个不同的簇, 且每个簇的中心采用簇中所含值的均值计算而成。簇个数 K 是用户指定的, 每一个簇通过其质心（centroid）, 即簇中所有点的中心来描述。聚类与分类算法的最大区别在于, 分类的目标类别已知, 而聚类的目标类别是未知的。
K-Means聚类算法步骤
K-Means聚类步骤是一个循环迭代的算法，具体·步骤如下：
- 1、先随机选取K个对象作为初始的聚类中心，随机选择K个初始中心点；
- 2、计算每个对象与各个种子聚类中心之间的距离，按照距离初始中心点最小的原则，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。
- 3、一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：
1）没有（或最小数目）对象被重新分配给不同的聚类。 2）没有（或最小数目）聚类中心再发生变化。 3）误差平方和局部最小。
因此得到相互分离的球状聚类，在这些聚类中，均值点趋向收敛于聚类中心。 一般会希望得到的聚类大小大致相当，这样把每个观测都分配到离它最近的聚类中心（即均值点）就是比较正确的分配方案。
K-Means的数学描述
聚类是把相似的物体聚在一起，这个相似度（或称距离）是用欧氏距离来衡量的。
K-Means伪代码
function K-Means(输入数据，中心点个数K) 获取输入数据的维度Dim和个数N 随机生成K个Dim维的点 while(算法未收敛) 对N个点：计算每个点属于哪一类。 对于K个中心点： 1，找出所有属于自己这一类的所有数据点 2，把自己的坐标修改为这些数据点的中心点坐标 end 输出结果： end
K-Means优缺点
优点:
- 属于无监督学习，无须准备训练集
- 原理简单，实现起来较为容易
- 结果可解释性较好
缺点:
- 聚类数目k是一个输入参数。选择不恰当的k值可能会导致糟糕的聚类结果。这也是为什么要进行特征检查来决定数据集的聚类数目了。
- 可能收敛到局部最小值, 在大规模数据集上收敛较慢
- 对于异常点、离群点敏感
K-Means算法实现
from collections import defaultdict from random import uniform from math import sqrt def point_avg(points): """ Accepts a list of points, each with the same number of dimensions. NB. points can have more dimensions than 2 Returns a new point which is the center of all the points. """ dimensions = len(points[0]) new_center = [] for dimension in xrange(dimensions): dim_sum = 0 # dimension sum for p in points: dim_sum += p[dimension] # average of each dimension new_center.append(dim_sum / float(len(points))) return new_center def update_centers(data_set, assignments): """ Accepts a dataset and a list of assignments; the indexes of both lists correspond to each other. Compute the center for each of the assigned groups. Return `k` centers where `k` is the number of unique assignments. """ new_means = defaultdict(list) centers = [] for assignment, point in zip(assignments, data_set): new_means[assignment].append(point) for points in new_means.itervalues(): centers.append(point_avg(points)) return centers def assign_points(data_points, centers): """ Given a data set and a list of points betweeen other points, assign each point to an index that corresponds to the index of the center point on it's proximity to that point. Return a an array of indexes of centers that correspond to an index in the data set; that is, if there are N points in `data_set` the list we return will have N elements. Also If there are Y points in `centers` there will be Y unique possible values within the returned list. """ assignments = [] for point in data_points: shortest = () # positive infinity shortest_index = 0 for i in xrange(len(centers)): val = distance(point, centers[i]) if val < shortest: shortest = val shortest_index = i assignments.append(shortest_index) return assignments def distance(a, b): """ """ dimensions = len(a) _sum = 0 for dimension in xrange(dimensions): difference_sq = (a[dimension] - b[dimension]) ** 2 _sum += difference_sq return sqrt(_sum) def generate_k(data_set, k): """ Given `data_set`, which is an array of arrays, find the minimum and maximum for each coordinate, a range. Generate `k` random points between the ranges. Return an array of the random points within the ranges. """ centers = [] dimensions = len(data_set[0]) min_max = defaultdict(int) for point in data_set: for i in xrange(dimensions): val = point[i] min_key = 'min_%d' % i max_key = 'max_%d' % i if min_key not in min_max or val < min_max[min_key]: min_max[min_key] = val if max_key not in min_max or val > min_max[max_key]: min_max[max_key] = val for _k in xrange(k): rand_point = [] for i in xrange(dimensions): min_val = min_max['min_%d' % i] max_val = min_max['max_%d' % i] rand_point.append(uniform(min_val, max_val)) centers.append(rand_point) return centers def k_means(dataset, k): k_points = generate_k(dataset, k) assignments = assign_points(dataset, k_points) old_assignments = None while assignments != old_assignments: new_centers = update_centers(dataset, assignments) old_assignments = assignments assignments = assign_points(dataset, new_centers) return zip(assignments, dataset) # points = [ # [1, 2], # [2, 1], # [3, 1], # [5, 4], # [5, 5], # [6, 5], # [10, 8], # [7, 9], # [11, 5], # [14, 9], # [14, 14], # ] # print k_means(points, 3)
