第9章 聚类分析

第九章聚类分析一、聚类分析含义将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为聚类，由聚类所组成的簇是一组对象的集合，这些对象与同一簇中的对象彼此相似，与其它簇中的对象相异。与分类不同，它要划分的类是未知的。二、聚类分析中的数据类型及转换1、数据矩阵：用p个变量（也称为度量或属性）来表现n个对象，例如用年龄、身高、性别等属性来表现对象“人”。构成一个n*p的矩阵。2、相异度矩阵：存储n个对象两两之间的近似程度性，表现形式是一个n*n的矩阵。这里d(i,j)是对象i和对象j之间相异性的量化表示3、区间标度度量一个粗略线性标度的连续度量。（如重量，温度等）

实现度量值的标准化：将原来的度量值转换为无单位的值。为什么这么做?

选用的度量单位会直接影响聚类结果。例如千克改位克。一般，所用的单位越小，变量的值域就越大，对聚类的影响也越大。为了避免数据对度量单位的依赖，数据应当标准化。给定变量f，变换方法：（1）计算平均的绝对偏差Sf（2）计算标准化度量值，或z-score:注意：在特定的应用中，是否要数据标准化和如何标准化是用户自己的事情4、已标准化数据后怎么计算两个对象的相似度三种常用的距离计算公式

（1）欧几里德距离（2）曼哈坦距离（2）明斯基距离5、其它类型变量的相异度计算（1）二元变量变量的取值只有两个状态，如性别，表示是否吸烟，医疗检查正常还是不正常等。

i和j是两个变量：q是两个变量中都为1的个数

l是两个变量中都为0的个数

s是i变量中为0，j中为1的个数

r是i变量中为1，j中为0的个数

p=q+r+s+t二元变量权重相同(对称的，如性别）即：分子为两者相异的总数，分母为二元变量总数二元变量权重不同(非对称的）例如，一个疾病化验结果正常和不正常，对一个群体，正常者总是大多数，我们用1表现几率小的情况，0表示另一种情况。评价系数，Jaccard系数

即：两个相异的数量作为分子，相异的数量加两个为1的数量作为分母。（同对称二元变量相比，两个同为0的数量不出现在分母中）例：假定一个病人记录表如下：姓名发烧咳嗽检查1检查2检查3检查4张明是否不正常正常正常正常王枚是否不正常正常不正常正常李力是是正常正常正常正常….….….….….....…..例：假定一个病人记录表如下：姓名发烧咳嗽检查1检查2检查3检查4张明是否不正常正常正常正常王枚是否不正常正常不正常正常李力是是正常正常正常正常….….….….….....…..例：假定一个病人记录表如下：姓名发烧咳嗽检查1检查2检查3检查4张明是否不正常正常正常正常王枚是否不正常正常不正常正常李力是是正常正常正常正常….….….….….....…..从左边的计算知道：（1）李力和王枚不大可能有相同疾病，因为相异很高；（2）张明和王枚最可能得相同的疾病（2）枚举变量

可以有若干个不同取值，比如反映产品颜色的color可以是{红、黄、绿、兰、粉红}

假设一个枚举变量的状态数目是M。这些状态可以映射到字母、符号或一组整数(1,2,…,M)。p是全部变量的数目m是匹配的数目。（3）序数型变量是枚举但有序，比如{金牌、银牌、铜牌}

区间标度度量值划成了区间，比如年龄分成了年龄段{10

岁以下，11..20,21..30,..}等。一个序数型变量的值可以映射为秩。例如一个变量f可以有Mf个状态，可以映射到一个有序排列{1，2，…,Mf}。如何处理序数型变量？假设f是用于描述n个对象的一组序数型变量之一，关于f的相异度计算包括如下步骤：

1）第i个对象的f值为xif，变量f有Mf个有序的状态，对应于序列1，…，Mf。用对应的秩rif代替xif，rif{1，..，Mf}2）既然每个序数型变量可以有不同数目的状态，经常必须将每个变量的值映射到[0.0，1.0]上，以便每个变量都有相同的权重。可以通过用zif代替rif来实现3)相异度的计算可以采用前面的任意一种距离度量方法（4）比例标度型非线性的取正的数据，如指数型数据。对数变换，对象i的f变量的值xif被变换成yif

，yif

=log(xif)将xif看成序数型数据6、混合类型的变量真实数据库的元组的变量往往是混合的。处理方法为：（1）将变量按类型分组，对每种类型的变量进行单独的聚类分析。如果这些分析得到的结果是兼容的，则该方法是可行的。实际应用中，这种情况比较少见。（2）将所有变量一起处理，只进行一次聚类。将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间[0.0，1.0]上。假设数据集包含p个不同类型的变量，对象i和j之间的相异度d(i，j)定义为：

其中，如果xif或xjf缺，或者xif=xjf=0，且变量f是不对称的二元变量，则指示项=0；否则等于1。变量f对i和j之间相异的计算方式与其具体类型相关：如果f是二元变量或枚举变量：如果xif=xjf,,否则为1。如果f是区间标度变量：如果f是虚数型或者比例标度型变量：计算秩rif，在变换zif三、划分方法划分方法:将一个包含n个数据对象的数据库组织成k个划分（k<=n），其中每个划分代表一个簇。给定一个k，要构造出k个簇，并满足采用的划分准则：k-平均

:由簇的中心来代表簇；k-中心点:

每个簇由簇中的某个数据对象来代表。K-平均算法：把n个对象分为k个簇，是簇内具有较高的相似度，而簇间的相似度较底。相似度的计算根据一个簇中对象的平均值（重心）来进行。

流程：首先，随机的抽取k个对象，每个对象初始地代表一个簇的平均值。对剩余的每个对象，根据与各个簇中心的距离，将它赋给最近的簇。然后重新计算各个簇的平均值。过程不断反复，直到准则函数收敛。一般采用平方误差准则：这里，p是空间的点，表示给定的对象，mi是簇Ci的平均值。例子初始点初始点K-中心点：首先为每个簇随意选择一个代表；剩余的对象根据其与代表对象的距离分配给最近的一个簇。然后反复地用非代表对象代替代表对象，以改进聚类质量。质量用一个代价函数估算。该函数计算对象与参照对象之间的平均相异度。（比如：代替后的点的平方误差函数-原来的平方误差函数)描述：1）随机选择k个对象作为初始的中心点；2）repeat3）指派每个剩余的对象给离它最近的中心点所代表的簇；4）随机地选择一个非中心点对象Orandom;5)计算用Orandom代替Oj的总代价S;6)ifS<0thenOrandom代替Oj

,形成新的k个中心点的集合；7)until不发生变化；

判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：1）p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Oi更近，p重新分配给OiOiOjpOrandom

判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：1）p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Oi更近，p重新分配给Oi。2)p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Orandom更近，p重新分配给Orandom

。OiOjpOrandom

判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：1）p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Oi更近，p重新分配给Oi。2)p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Orandom更近，p重新分配给Orandom

。3)p当前隶属于中心点对象Oi。如果Oj被Orandom代替作为中心点后，而p仍然离Oi更近，那么对象的隶属关系不变。OiOjpOrandom

判定一个非代表对象Orandom是否是一个代表对象Oj的更好替代，对每个非中心点对象p,考虑下面四种情况：1）p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Oi更近，p重新分配给Oi。2)p当前隶属于中心点对象Oj。如果用Orandom代替它后，p离Orandom更近，p重新分配给Orandom

。3)p当前隶属于中心点对象Oi。如果Oj被Orandom代替作为中心点后，而p仍然离Oi更近，那么对象的隶属关系不变。4)p当前隶属于中心点对象Oi。如果Oj被Orandom代替作为中心点后，而p离Orandom更近，那么p重新分配给Orandom