聚类分析算法

什么是聚类

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

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

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

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

相似性度量

对象之间的相似性是聚类分析的核心。对象之间的距离越近表示它们越相似。若每个对象用$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$-均值（$k-means$）算法是一种基于距离的聚类算法，采用欧几里得距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。

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

$K-means$算法描述

1. 选择k个样品作为初始凝聚点，或者将所有样品分成k个初始类，然后将这k个类的重心(均值)作为初始凝聚点
2. 对除凝聚点之外的所有样品逐个归类，将每个样品归入凝聚点离它最近的那个类（通常采用欧氏距离），该类的凝聚点更新为这一类目前的均值，直至所有样品都归了类
3. 重复步骤2，直至所有的样品都不能再分配为止

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

聚类分析终止的条件：

1. 当前的迭代次数等于指定的迭代次数（spss默认为10）时终止聚类
2. 类中心点偏移程度。新确定的类中心点距上个类中心点的最大偏移量小于指定的量（spss默认为0.02）时终止聚类

例题

设有五个样本分别是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}