聚类是一个把数据对象划分为多个组或多个簇的过程。同一个簇内的对象有很高的相似性，而不同簇之间的对象有很高的相异性。

划分方法

k-均值

在数据集中随机选取k个对象，每个对象代表一个簇的初始均值或中心。其余对象根据与各个簇中心的欧氏距离，分配到最近的簇。根据簇中的点重新计算簇的中心，然后重复上述算法直到收敛。 结果可能收敛于局部最优解，也就是结果会依赖于初始时随机中心的选择。算法复杂度为 O(nkt)。 根据数据类型，也可以使用 k-众数等方法

k-中心点

上述的k-均值方法有一个很大的问题就是，假设数据都是比较理想的，而一旦有离群点outlier，那么就会严重影响聚类结果。 因此，k-中心点使用实际的对象而不是均值来代表簇。划分方法基于绝对误差absolute-error criterion： $$E = \sum_{i=1}^{k} \sum_{p \in C_{j}} dist(p,o_{i})$$

k-中心点的每次迭代所需要的时间复杂度为 O(k(n-k)²)，因此不适用于较大的数据集。

层次方法

将数据划分为不同层次上的组群，比如不同粒度上的划分。

BIRCH

利用层次结构的平衡迭代规约和聚类Balanced Iteration Reducing and Clustering using Hierarchies 使用聚类特征来概括一个簇，使用聚类特征树来表示聚类的层次结构，有较好的伸缩性，并支持动态聚类。

聚类特征：

CF = <n, LS, SS>

其中，LS是n个点的线性和，SS是点的平方和，聚类特征本质上是簇的统计汇总，不同簇之间的聚类特征是可加的。

聚类特征树： 是一棵高度平衡的树，存储了层次聚类的聚类特征。非叶子结点存储了子女的聚类特征总和。聚类特征树有两个参数，分支因子B（定义了每个非叶结点的子女的最大数目）和阈值T（存储在树的叶节点中的子簇的最大直径）

Chameleon

使用动态建模的多阶段层次聚类。 在chameleon中，簇的相似度依据 1.簇中对象的连接情况 2.簇的临近性

本质上是一个从下而上的层次聚类算法，主要有以下两步：

1）图划分算法：将数据对象（k-最近邻图）划分为大量相对较小的子簇

2）凝聚层次聚类算法：基于子簇的相似度反复合并上步生成的子簇

概率层次聚类

通过概率模型度量簇之间的距离。 很多时候我们收集到的数据不会很完整，因此可以使用概率模型来尽可能准确的估计。

基于密度的方法

为了发现任意形状的簇，可以把簇看做数据空间中被稀疏区域分开的稠密区域。

DBSCAN

Density-Based Spatial Clustering of Application with Noise

对于DBSCAN，有几个概念： 核心对象： 如果一个对象的Eps邻域至少包含MinPts个对象，则该对象是核心对象 直接密度可达： 给定一个对象集合D，如果p在q的Eps邻域内，而q是一个核心对象，则称对象p从对象q出发时是直接密度可达的 密度可达： 如果存在一个对象链 p₁, …,p_n，满足p₁ = p 和p_n = q，p_i是从p_i+1关于Eps和MinPts直接密度可达的，则对象p是从对象q关于Eps和MinPts密度可达的。密度可达不是等价关系 密度相连： 如果存在对象O∈D，使对象p和q都是从O关于Eps和MinPts密度可达的，那么对象p到q是关于Eps和MinPts密度相连的

DBSCAN算法： 1. 数据集中所有的对象都标记 unvisited 2. DBSCAN随机选择一个未访问过的对象p，标记为 visited ，检查其Eps邻域是否包含MinPts个对象，是则创建一个以p为核心对象的簇，并把Eps邻域中所有的对象都加入，否则标记为噪声 3. DBSCAN从剩下的对象中随机选择未访问过的对象，重复上述步骤，直到所有对象被访问

OPTICS

为了克服在聚类中使用一组全局参数的缺点。

和DBSCAN一样，也先引入几个概念： 核心距离： 最小的值Eps’， 也就是使p成为核心对象的最小半径阈值 可达距离： 使p从q密度可达的最小半径值。max{core-distance(q), dist(p, q)}

DENCLUE

Density-based clustering

在DBSCAN和OPTICS中，密度通过统计被半径参数Eps定义的邻域中的对象个数来计算，这种密度估计方法对所使用的半径值非常敏感。 为了解决这个问题，可以使用核密度估计，概率密度函数的近似核密度为：

$$f_h(x) = \frac{1}{nh} \sum_{i=1}^{n}K( \frac{x-x_i}{h})$$ $$E = \sum_{i=1}^{k} \sum_{p \in C_{j}} dist(p,o_{i})$$

\(K( )\)为核函数，需要满足\(\int_{-∞}^{+∞}K(u)du = 1\)和 \(K(-u) = K(u)\)常用的核函数为标准高斯函数

基于网格的方法

使用多分辨率的网格结构，优点是处理度快。

STING

优点： 1. 基于网格的计算是独立于查询的，因为存储在每个单元中的统计信息提供了单元中数据汇总信息 2. 网格结构有利于并行处理和增量更新 3. 效率高，处理的时间复杂度为O(n)

CLIQUE

使用稠密单元关于维度的单调性

聚类评估

估计聚类趋势

霍普金斯统计量 Hopkins Statistic

用于检验空间分布的变量的空间随机性 1. 均匀地从D的空间中抽取n个点p₁, …, p_n。对于每个点p_i，找出p_i在D中的最近邻，并令 x_i = min{ dist(p_i, v) } 2. 均匀地从D的空间中抽取n个点q₁, …, q_n。对于每个点q_i，找出q_i在D - {q_i}中的最近邻，即 y_i = min{ dist(q_i, v) } 3. 计算霍普金斯统计量 H

$$H = \frac{ \sum_{i=1}^{n}y_i}{ \sum_{i=1}^{n}x_i + \sum_{i=1}^{n}y_i}$$

确定聚类中的簇数

测定聚类质量

轮廓系数

$$a(o) = \frac{ \sum_{o’ \in C_i, o \neq o’} dist(o,o’)}{|C_i| - 1}$$

$$b(o) = min_{C_j:i \le j \le k, j \neq i} { \frac{ \sum_{o’ \in C_i, o \neq o’} dist(o,o’)}{|C_i| - 1} }$$

$$s(o) = \frac{b(o) - a(o)}{max {a(o), b(o) }}$$

轮廓系数的值在-1到1之间。a(o)的值反映o所属簇的紧凑性，越小越紧凑。b(o)表示o与其他簇的分离程度，越大越分离。轮廓系数接近1时，包含o的簇紧凑，并且远离其他簇，是比较理想的情况。