聚类把数据对象集划分成多个组成或簇的过程，使得簇中的对象彼此相似，但与其他簇中的对象不相似。

聚类主要有以下应用场景：

Data summarization, compression and reduction.

Outlier detection

Collaborative filtering, recommendation system and customer segmentation: find like-minded user or similar products

Dynamic trend detection

Multimedia data, biological data, social network analysis

聚类过程一般步骤如下：

数据处理：包括清洗、特征标准化和降维；

特征工程：从最初的特征中选择最有效的特征，并将其存储于向量中，并根据需要进行转换；

聚类：选择合适特征类型的某种距离函数（或构造新的距离函数）进行接近程度的度量，执行聚类（分组）过程；

评估：对聚类结果进行评估

1. 距离度量

设  X₁ = ( X_11， X₂₂ , . . . , X_{1 n}) 和  X₂ = (  X_21，X₂₂, . . . , X_2n) 是两个被n 个数值属性描述的对象。

（1）欧氏距离

（2）曼哈顿距离

曼哈顿距离也称作“城市街区距离”

（3）闵可夫斯基距离

闵可夫斯基距离（Minkowski distance）是欧几里得距离和曼哈顿距离的推广，又称L p范数，p = 1时，表示曼哈顿距离（L 1范数）；p = 2 时，表示欧几里得距离（L 2 范数）。

（4）上确界距离

上确界距离又称切比雪夫距离（Chebyshev distance），L ∞ 范数，L m a x 范数，是h → ∞时的闵可夫斯基距离。

（5）夹角余弦

余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个样本差异的大小。余弦值越接近1，说明两个向量夹角越接近0度，表明两个向量越相似。

2. 主要聚类算法

3. 划分方法

假设数据集D = { x 1 , x 2 , . . . , x m }划分方法把D中的对象分配到k kk个簇C 1 , C 2 , . . . , C k 中，使得对于1 ≤ i , j ≤ k , C i ⊂ D 且 C i ∩ C j = ∅

3.1 K-means

K-means（K-均值）针对聚类算法的划分，最小化平方误差

其中，d i s t ( x , c i 表示簇中的点与形心的欧氏距离，c i为簇C i  的形心（centroid）。

簇的形心为簇的中心点，可用簇的均值（或中心点等多种形式）定义：

算法流程如下：

从数据集D DD中随机选择k kk个对象作为簇的初始均值（形心）c i , i = { 1 , 2 , . . . , k }

根据样本x j , j = { 1 , 2 , . . . , m } }与c i , i = { 1 , 2 , . . . , k }的距离，将x i 划入最近形心所在簇

重新计算每个簇的均值，并更新（即重新选择簇的形心）

until 簇均值不再发生变化

k-means算法的复杂度是O ( m k t ) ，m 是样本数目，k是簇的数目，t 是迭代次数。通常k < < n , t < < n

k-means算法不适合发现非凸形的簇，或者大小差别很大的簇；此外对噪声和离群点敏感。

k-means算法由于k个均值的选择、相异度的计算、簇均值的计算策略上的不同有一些变种：

k-modes（k-众数）：使用簇众数代替簇均值来聚类标称数据，使用新的相异性度量，并使用基于频率的方法来更新簇的众数。

K-Medians：Handing outliers.

K-Means++：Choosing better initial centroid estimates.

** Kernel K-Means**：Detect non-convex clusters: project data onto high-dimensional kernel space

3.2 K-medoids

K-medoids（K-中心点）选择实际对象来代表簇，每个簇使用一个代表对象，其余对象被分配到最近的代表对象所在的簇中，以最小化绝对误差（absolute-error）:

其中dist(x,o i)表示簇中的点与代表对象的曼哈顿距离，o i为簇C i 的代表对象。

算法流程如下：

从数据集D中随机选择k kk个对象作为簇的代表对象 o i , i = { 1 , 2 , . . . , k }

repeate

根据样本x j , j = { 1 , 2 , . . . , m }}与o_i , i = { 1 , 2 , . . . , k } 的距离，将x i 划入最近的代表对象所在簇

随机选择一个非代表对象 ，计算代价函数

if S < 0 , 代替 o_i ，形成新的k 个代表对象的集合

until 不再发生变化

k-medoids在数据存在噪声和离群点时，比k-means更鲁棒。

k-medoids算法的复杂度是O ( t k ( m − k ) ²，当m 和k 的值较大时，计算开销远高于k-means，难以应用于大数据集。

CLARA（Clustering LARge Application）

基于抽样的方法来处理大型数据集，有效性依赖于样本的大小

CLARANS（Clustering Large Application based upon RANdomized Search）

在使用样本得到聚类的开销和有效性之间权衡