5 数据挖掘技术-聚类分析

第5章数据挖掘技术-聚类分析什么是聚类分析?簇（Cluster）:一个数据对象的集合在同一个类中，对象之间具有相似性；不同类的对象之间是相异的。聚类分析把一个给定的数据对象集合分成不同的簇；聚类是一种无监督分类法:没有预先指定的类别；典型的应用作为一个独立的分析工具，用于了解数据的分布；作为其它算法的一个数据预处理步骤；聚类分析的应用市场销售:帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；保险:对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；城市规划:根据类型、价格、地理位置等来划分不同类型的住宅；地震研究:根据地质断层的特点把已观察到的地震中心分成不同的类；文档分类分析WEB日志数据来发现相似的访问模式例子1－Web服务器浏览模式的聚类分析例子1－Web服务器浏览模式的聚类分析通过对浏览模式会话（会话是指用户/服务器访问Web服务器的浏览行为）密度分布的分析并借助于模式匹配，管理员可以对不合理的浏览模式进行调整，以提高Web服务器的工作效率和网络资源的利用效率。另外，对于挖掘出来的噪声浏览模式应引起管理员更多的关注，噪声浏览模式几乎都是不合理的浏览行为，甚至会形成对网站安全的威胁，管理员应核查这些浏览行为的安全问题，以消除全漏洞。例子2－物流配送系统的聚类分析利用聚类分析方法帮助实现物流配送的优化。大多数物流公司会根据公司的业务情况把配送区域划分成几个小区，部分配送车辆完成固定业务之后不是直接回到配送中心，而是到所在小区内的一个指定地点等候，准备完成该小区客户的随机需求。类似这样的配送模式就需要确定合理的配送车辆随机等待地点和合理的配送线路。对于配送车辆随即等待地点的确定，可分析随机业务的历史数据，利用聚类分析方法进行分区并确定各分区重心，其重心就是配送车辆合理的等待地点。在车辆调度方案优化方面，可以把这个地点作为一个固定的客户，利用经典的车辆调度算法进行配送线路的求解。例子3－田径指标变量的聚类分析例如：下表是24名优秀田径运动员的七项全能项目得分间的相关系数，对这七项指标变量进行聚类分析。变量百米栏X1跳高X2铅球X3200米X4跳远X5标枪X6800米X7百米栏X11.0跳高X20.44981.0铅球X30.68380.46661.0200米X40.84660.32980.56751.0跳远X50.81130.54200.59430.81121.0标枪X60.32140.21540.68960.31430.32761.0800米X70.57060.14980.37620.67900.49570.05561.0例子3－田径指标变量的聚类分析相应的树形图如下：1.00.90.80.70.60.5相关系数百米栏X1200米X4跳远X5铅球X3标枪X6800米X7跳高X2变量例子4－中国省级区域经济发展水平的聚类分析选取人均GDP、人均第一产业产值、人均第二产业产值、人均第三产业产值、居民消费水平、人均财政收入、人均邮电业务总量、人均进出口总额8个指标，对我国31个省市区的经济发展水平进行聚类分析.例子4－中国省级区域经济发展水平的聚类分析人均GDP:用其反映区域经济发展的一般水平；人均第一产业产值:用其反映区域农业发展水平；人均第二产业产值:用其反映区域工业化水平；人均第三产业产值:用其反映区域服务业和城镇化水平；居民消费水平:用其反映区域内居民的生活水平和购买能力；人均财政收入:用其反映区域经济实力与公益设施建设能力；人均邮电业务总量:用其反映区域内信息产业和高新技术产业发展水平；人均进出口总额:用其反映区域对外贸易的发展水平与商业竞争能力。由《中国统计年鉴2003》可得到2002年全国31个省市区以上8个指标数值，见表1。采用欧氏距离测度各区域经济发展水平的相似度，分别用类平均法和离差平方和法进行分析。按类平均法分成的四类：｛上海｝｛天津、北京｝｛浙江、广东、黑龙江、山东、辽宁、福建、江苏｝｛其余21省市｝按离差平方和法分成的四类：｛上海｝｛天津、北京｝｛辽宁、福建、江苏、浙江、广东｝｛其余23个省市｝两种聚类方法的分类结果基本上是一致的，并且都可以分为四类，细微差别在黑龙江和山东的分类上.例子4－中国省级区域经济发展水平的聚类分析例子5－聚类分析技术在金融反洗钱中的应用我国反洗钱工作主要是通过可疑交易报告制度完成的，而金融机构的反洗钱的情报收集和分析工作中目前存在主要问题为:工作量大，误报率高;预设标准易于为洗钱分子所规避;无法自动适应洗钱形式的变化等。这就使得洗钱可疑交易行为的识别存在巨大的困难。例子5－聚类分析技术在金融反洗钱中的应用由于洗钱方式多种多样，数据对象表现出来的分布也就各式各样，并不是所有的可疑账户都可以聚成一类。因此，在洗钱行为识别中，簇的数量是未知的。聚类分析中“簇的数量未知”这个特点刚好满足洗钱行为识别的这个要求。由于其聚类分析的自动处理、非监督学习等特性使得其可以动态地适应洗钱手段的变化，也可以在一定程度上规避洗钱犯罪活动的自适应问题。例子5－聚类分析技术在金融反洗钱中的应用采取聚类分析和孤立点探测相结合的方法。首先，通过采集一些与待识别客户身份与业务特征类似的正常客户的样本信息，建立参照组。然后，对样本数据集进行聚类分析，分析结果中将出现聚类数据和离群数据，删除其中的聚类数据。经过上述数据准备处理后，对于剩下样本，采用局部孤立点算法，对每个样本计算其孤立值。最后，根据孤立值的大小对这些样本进行排序。根据孤立值排序的结果也就是每个账户在相关属性上的可疑程度顺序表，监管中心可以根据自身资源情况和这个顺序表决定深入调查的账户对象。什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：簇内相似性高簇间相似性低聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是能发现某些还是所有的隐含模式；数据挖掘对聚类的典型要求可伸缩性：能够在大数据集合样本上就进行聚类。能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候，尽量不需要特定的领域知识；能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的两种数据结构数据矩阵(二模矩阵)相异度矩阵(单模矩阵)npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x0...)2,()1,(:::)2,3()...ndnd0dd(3,10d(2,1)0聚类分析中的数据类型区间标度变量（Interval-scaledvariables）二元变量（Binaryvariables）标称型，序数型和比例型变量（Nominal,ordinal,andratiovariables）混合类型变量（Variablesofmixedtypes）区间标度变量区间标度变量是一个粗略线性标度的连续度量。Eg.重量、高度、经度和纬度坐标、大气温度等数据标准化计算绝对偏差的平均值:其中计算标准度量值或z-score.)...211nffffxx(xnm|)|...|||(|121fnffffffmxmxmxnsffififsmxz计算对象之间的相异度通常使用距离来衡量两个对象之间的相异度。常用的距离度量方法有:明考斯基距离（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维的数据对象,q是一个正整数。当q=1时,d称为曼哈坦距离（Manhattandistance）qqppqqjxixjxixjxixjid)||...|||(|),(2211||...||||),(2211ppjxixjxixjxixjid计算对象之间的相异度当q=2时,d就成为欧几里德距离:距离函数有如下特性：d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)可以根据每个变量的重要性赋予一个权重)||...|||(|),(2222211ppjxixjxixjxixjid2222211||...||2||1),(ppjxixpwjxixwjxixwjid二元变量一个二元变量只有两个状态：0或1二元变量的可能性表（相依矩阵）其中每个对象有p个变量，且p=q+r+s+tObjectiObjectjptrsqsumtstsrqrqsum0101对称的二元变量对称的如果一个二元变量的两个状态是同等价值的，具有相同的权重。即可以任取其中一种状态编码为1或者0.对于对称的二元变量，采用简单匹配系数来评价两个对象之间的相异度.tsrqsrjid),(非对称的二元变量非对称的如果变量的两个状态不是同样重要的，则称该变量是不对称的。根据惯例，将比较重要通常也是出现概率比较小的状态编码为1，将另一种状态编码为0。对于非对称的二元变量，采用Jaccard系数来评价两个对象之间的相异度。srqsrjid),(二元变量的相异度计算实例gender是一个对称的二元变量其它的都是非对称的二元变量将值Y和P编码为1,值N编码为0，根据Jaccard系数计算得：NameGenderFeverCoughTest-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackd标称变量（NominalVariables）标称变量是二元变量的推广，它可以具有多于两个的状态，比如变量map_color可以有red,yellow,blue,green四种状态。有两种计算相异度的方法：方法1:简单匹配方法m是匹配的数目,p是全部变量的数目方法2:使用二元变量为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标称变量。pmpjid),(序数型变量一个序数型变量可以是离散的也可以是连续的离散的序数型变量类似于标称变量，除了它的M个状态是以有意义的序列排序的，比如职称.连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。序数型变量相异度的计算:与区间标度变量的计算方法相类似将xif用它对应的秩代替将每个变量的值域映射到[0.0，1.0]上，使得每个变量都有相同的权重。这通过用zif来替代rif来实现用前面所述的区间标度变量的任一种距离计算方法来计算11fififMrz},...,1{fMifr比例标度型变量（Ratio-scaledvariable）比例标度型变量:总是取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如AeBtorAe-Bt计算相异度的方法:采用与处理区间标度变量相同的方法—不是一个好的选择进行对数变换，对变换得到的值再采用与处理区间标度变量相同的方法yif=log(xif)将其作为连续的序数型数据，将其秩作为区间标度的值来对待。混合类型的变量一个数据库可能包含了所有这6中类型的变量用以下公式计算对象i，j之间的相异度.其中，p为对象中的变量个数如果xif或xjf缺失（即对象i或对象j没有变量f的值），或者xif=xjf=0，且变量f是不对称的二元变量，则指示项δij(f)=0；否则δij(f)=1)(1)()(1),(fijpffijfijpfdjid混合类型的