聚类分析算法

聚类分析是将数据对象的集合分成相似对象类的过程。使得同一簇（或类）中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性。

簇是数据对象（如数据点）的集合，这些对象与同一簇中的对象彼此相似，而与其他簇的对象相异。

例：对客户数据中的“年龄”和“收入”进行聚类处理

孤立点可以用来分析极低或极高收入客户的消费行为。

对象之间的相似性是聚类分析的核心。对象之间的距离越近表示它们越相似。若每个对象用$m$个属性来描述（称为描述属性），即对象$o_i$表示为$o_i=(o_{i1},o_{i2},…,o_{im})$，常用的距离度量如下：

曼哈顿距离：$dist(o_i,o_j) = \sum_{k=1}^{m}|o_{ik}-o_{jk}|$

欧几里得距离：$dist(o_i,o_j) = \sqrt {\sum_{k=1}^{m} (o_{ik}-o_{jk})^2}$

闵科夫斯基距离：$dist(o_i,i_j) = \sqrt[q]{\sum_{k=1}^{m}|o_{ik}-o_{jk}|^q}$

其实仔细观察上面三个公式，曼哈顿距离和欧式距离就是闵科夫斯基距离的两种特殊情况，分别取$q=1$和$q=2$

通常相似度函数$sim(o_i,o_j)$与距离成反比，在确定好距离函数后，可设计相似度函数如下：

$$ Sim(o_i,o_j)=\frac{1}{1+dist(o_i,o_j)} $$

$k$-均值（$k-means$）算法是一种基于距离的聚类算法，采用欧几里得距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。

$k-means$算法不适合离散型属性，但对于连续型属性具有较好的聚类效果

最终的聚类结果在一定程度上依赖于初始凝聚点或初始分类的选择。经验表明，聚类过程中的绝大多数重要变化均发生在第一次再分配中

聚类分析终止的条件：

设有五个样本分别是1,2,6,8,11，采用K均值法聚类，指定K=2

（1）我们随意将这些样品分成$G_1^{(0)}=\{1,6,8\}$和$G_2^{(0)}=\{2,11\}$两类，则这两个初始类的均值分别是5和6.5

（2）计算1到两个类的欧氏距离

$$ \begin{align} & d(1,G_1^{(0)})=|1-5|=4\\ & d(1,G_2^{(0)})=|1-6.5|=5.5\\ \end{align} $$

由于1到$G_1^{(0)}$的距离小于到$G_2^{(0)}$的距离，因此1不用重新分配，计算6到两个类的距离

$$ \begin{align} & d(6,G_1^{(0)})=|6-5|=1\\ & d(6,G_2^{(0)})=|6-6.5|=0.5\\ \end{align} $$

故6应重新分配到$G_2^{(0)}$中，修正后的两个类为$G_1^{(1)}=\{1,8\},G_2^{(1)}=\{2,6,11\}$，新的类均值分别为4.5和6.3，计算

$$ \begin{align} & d(8,G_1^{(1)})=|8-4.5|=3.5\\ & d(8,G_2^{(1)})=|8-6.3|=1.7\\ \end{align} $$

结果8重新分配到$G_2^{(1)}$中，两个新类为$G_1^{(2)}=\{1\},G_2^{(2)}=\{2,6,8,11\}$，其类均值分别为1和6.75，再计算

$$ \begin{align} & d(2,G_1^{(2)})=|2-1|=1 \\ & d(2,G_2^{(2)})=|2-6.75|=4.75 \\ \end{align} $$

重新分配2到$G_1^{(2)}$中，两个新类为$G_1^{(3)}=\{1,2\},G_2^{(3)}=\{6,8,11\}$，其均值分别为1.5和8.3

（3）再次计算每个样品到类均值的距离，结果列于下表

可见，每个样品都已被分给了类均值离他更近的类。因此，最终得到的两个类为{1,2}和{6,8,11}

聚类分析是研究如何在没有训练的条件下把样本划分为若干类。
在分类中，对于目标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来。
聚类需要解决的问题是将已给定的若干无标记的模式聚集起来使之成为有意义的聚类，聚类是在预先不知道目标数据库到底有多少类的情况下，希望将所有的记录组成不同的类或者说聚类，并且使得在这种分类情况下，以某种度量（例如：距离）为标准的相似性，在同一聚类之间最小化，而在不同聚类之间最大化。
与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据样本有类别标记。

Catalog