聚类分析算法

什幺是聚类

 

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

 

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

 

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

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

 

相似性度量

 

对象之间的相似性是聚类分析的核心。对象之间的距离越近表示它们越相似。若每个对象用$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个类的重心(均值)作为初始凝聚点

 

    1. 对除凝聚点之外的所有样品逐个归类,将每个样品归入凝聚点离它最近的那个类(通常采用欧氏距离),该类的凝聚点更新为这一类目前的均值,直至所有样品都归了类

 

    1. 重复步骤2,直至所有的样品都不能再分配为止

 

 

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

 

聚类分析终止的条件:

 

 

    1. 当前的迭代次数等于指定的迭代次数(spss默认为10)时终止聚类

 

    1. 类中心点偏移程度。新确定的类中心点距上个类中心点的最大偏移量小于指定的量(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}

发表评论

电子邮件地址不会被公开。 必填项已用*标注