基于多目标决策的聚类算法有效性评价.docx
《基于多目标决策的聚类算法有效性评价.docx》由会员分享，可在线阅读，更多相关《基于多目标决策的聚类算法有效性评价.docx（25页珍藏版）》请在冰点文库上搜索。
基于多目标决策的聚类算法有效性评价
基于多目标决策的聚类算法有效性评价
张勇,彭怡,李君
1.电子科技大学经济与管理学院，四川，成都，610054
石勇
2.中国科学院虚拟经济与数据科学研究中心，北京100190
3.美国内布拉斯加大学信息科学与技术学院，奥马哈，NE68182
摘要：
聚类结果有效性评价是聚类分析中的一个重要研究方向，同时也是制约着聚类分析发展的瓶颈问题之一。
单一的聚类有效性评价函数存在针对性太强、普适性太弱的局限，如何准确地评价任意特征数据集的聚类结果质量，一直是困扰学界的难题。
针对这一局限性，本文通过分析数据集结构属性特征、聚类算法和聚类有效性评价函数三者之间的相互关系，提出了一个基于多目标决策的聚类算法综合评价模型，同时，引入了专家支持系统以实现对模型的指导。
模型根据聚类算法的外部有效性评价函数、相对有效性评价函数划分为两个层面，分别以获取数据集最优聚类算法和最优聚类数目为目标导向。
最后，通过对两个UCI数据集的实验分析，结果显示本文所提出的模型具有广泛的适用性和很高的准确度，能够应用于诸如应急管理、信用风险和软件缺陷检测等领域的数据聚类分析问题中。
关键词：
聚类分析，聚类评价，多目标决策，Promethee，决策支持系统
AnClusteringValidityModelbasedonMultipleCriteriaDecisionMaking
SchoolofManagementandEconomics,UniversityofElectronicScienceandTechnologyofChina,Chengdu,P.R.China,610054
Abstract:
Clusteringresultsvalidationisoneofthemajorproblemswhichrestrictthedevelopmentofclusteringanalysis.Asinglevalidationfunctionwhichrespectstothespecificdatasethasthelimitationsingeneralapplicationandhowtoevaluatetheclusteringresultsofadatasetwitharbitrarilyfeaturespreciselystillremainsachallenge.Inthispaper,anintegratedclustervaliditymodelbasedonMultipleCriteriaDecisionMakinghasbeenproposed.Accordingtothevariousclustervalidityindices,themodelliesintwolevelswiththegoalsoffindingtheoptimalclusteringalgorithmandoptimalclusternumberrespectively.Finally,anexperimentontwoUCIdatasetshasbeenconductedandtheresultsshowhighlyconsistentwiththerealsituation,sothemodelcouldbeappliedincomprehensivefieldssuchasemergencymanagement,creditrisksassessment,softwaredefectdetection.
Keywords:
ClusteringAnalysis,ClusterValidity,MultipleCriteriaDecisionMaking,Promethee,DecisionSupportSystem
资助项目：
国家自然科学基金（70901011）;中央高校基本科研业务费专项资金
1引言
在数据挖掘过程中，例如从基础数据中发现群组或识别有价值的分布和模式，聚类是最有用的任务之一。
因此，聚类分析主要集中在揭示模式组成为“可见”群组，方便我们发掘其中的相似点和不同点，并从中得出有用的推论[1]。
每个群组即为一个簇，簇内的对象具有尽可能大的相似性，不同簇之间的对象具有尽可能大的相异性。
聚类分析既可以作为独立的数据挖掘工具，用来获知数据集的分布情况，分析其中的结构特点，以便对某些特定的簇类作进一步处理；也可以作为其他数据挖掘算法（如关联规则和分类等）的预处理手段[2]。
聚类分析在信用风险评估、空间数据处理、图像分析与检测、灾害事件应急管理中应用广泛[3]。
聚类算法多种多样，主要可以分为以下四类：
划分方法（partitioningmethods），层次的方法（hierarchicalmethods），基于密度的方法（density-basedmethods），基于模型的方法（model-basedmethods）[4]。
为了给出数据集的划分，这些算法需要一些先验条件：
数据集的特征（簇类的几何分布和密度分布）和输入参数值，不同条件，会得出不同的结果。
聚类过程是一个寻找最优划分的过程，即根据聚类质量的评价准则或方法不断对划分进行优化，最终得到最优解。
由于聚类是无指导的学习过程事先对数据的结构是未知的，是一种无监督的学习，不能利用任何先验知识，因此，无论采用哪种聚类算法，最终的结果都需要进行合理性和有效性验证以及质量评价[5]。
事实上，要使聚类分析在工程应用中发挥更大的贡献，就不得不更多关注聚类评价中的最优聚类数目以及聚类结果质量问题[6]。
一般而言，有三大类研究聚类评价的方法：
外部指标，内部指标和相对指标[7]。
传统的聚类结果有效性评价方法，无论是使用外部评价指标、内部指标，还是使用相对评价指标，都是采取其中某一种特定的评价函数来对聚类分析结果进行质量评价。
单一的有效性评价函数由于存在针对性太强、普适性太弱的局限，在实际应用中需要功能性更完整的（整合的）聚类质量评价模型来解决，以提高聚类有效性评价的整体适用性和准确度[1,5]。
针对这个问题，本文的研究思路是：
采用多个聚类有效性评价函数，对某个数据集的聚类结果质量进行评价，然后使用其他技术方法来综合这些评价函数的结果。
文章接下来的结构安排如下：
.第二部分是文献综述，总结归纳了目前聚类有效性评价领域的研究热点方向；第三部分提出了综合模型，结合前面的问题和分析结论提出一个解决方案；第四部分是实验，通过利用2个UCI数据的实验分析来阐述模型具体过程和验证模型结果的有效性；最后，则是本文的结论部分。
2文献综述
目前，关于聚类分析结果质量有效性评价的研究可以归纳为以下四个方面：
新有效性评价函数的研究：
由于聚类分析结果有效评价方法的特殊性，不同的数据集需要特定的评价函数来评价，因此，为了评价新类型的数据集，学者们在不断研究新的评价函数，其个数在持续增长，光相对指标就有超过40个[8]。
例如，2008年，吕宗磊等人提出了一种新的基于模态逻辑的聚类结果评价方法，通过把相似性定义成数据集上的二元关系聚类被描述成Kripke结构[9]。
GangChen（2009）等人通过引入高斯核函数到评价指标中，提出了一种对噪音不敏感的聚类有效性评价指标[10]。
模糊聚类有效性评价的研究：
模糊聚类分析适用于数据集簇类结构区分不明确的情况。
现有的模糊聚类有效性函数大致可以分为基于数据集模糊划分和基于数据集几何结构两类[11]。
2008年，陈舵等人根据模糊集基本理论，提出聚类模糊集概念，定义聚类模糊度，深入分析该度量在聚类评价中的作用，在此基础上，设计了一种新的基于模糊度和贴近度的模糊聚类有效性函数DS（U；f）[12]。
HoelLeCapitaine和CarlFr´elicot（2010）提出了一个基于模糊综合算子的、结合重叠度量和划分度量的聚类有效性指标[13]。
对原有聚类有效评价函数的改进：
随着学者们研究的深入，针对一些新的问题和发现，同时提出了一些对传统有效性评价函数的改进算法。
1985年，L.Hubert和P.Arabie两人针对Rand系数中的“不能做机会校正”的问题，提出了一种修正的Rand系数ARI[14]。
M.Halkidi和M.Vazirgiannis（2001）提出一种基于他们自己提出的SD指标的新的聚类有效性评价函数[15]。
多种函数的对比和综述：
MariaHalkidi（2001）等人总结归纳了数据挖掘聚类算法和聚类结果有效性评价分析技术，并提出了一些未来的发展趋势[16]。
LucasVendramin（2010）对相对聚类有效评价指标作了一个比较性的综述，总结归纳了众多相对有效性评价指标，并做了复杂度分析和基于数据的对比验证分析[8]。
然而，不管是已知的聚类有效性评价函数，还是最新提出新的评价函数，抑或是原有聚类算法的改进，都集中在单个有效性评价函数上，仍缺乏针对性强、普适性广的综合研究。
3综合模型
通过研究分析，本文提出了一个基于多目标决策（MCDM）的聚类结果有效性评价模型CVM（ClusteringValidityModelbasedonMultipleCriteriaDecisionMaking），同时引入专家决策支持系统，结合专家知识背景和相关经验来实现对模型中无监督学习的有监督、有约束的指导，通过信息的反馈和交互，提升评价结果的整体质量。
模型主要分为两个大的部分，分别以以下两个不同的目标为导向：
寻求在给定数据集上（已知类标签或数据结构）的最优聚类算法；
寻找在给定数据集上使用（一个或多个）聚类算法得出的最优聚类数目。
通过外部有效性评价指标，用MCDM算法优选出适合已知类标签的数据集的相似（结构、大小、特征、类型，但是类标签未知）数据集的最优聚类算法；通过相对有效性指标，在指定的聚类算法下，使用MCDM算法确定多个指标下最优的数据集类标数目。
本文实验部分在模型中假设通过最优聚类算法这一步选出来的算法是最优的，然后作为下一步最优聚类数目的使用。
模型的整体架构和具体操作过程如图1所示。
图1基于多目标决策的聚类有效性综合评价模型框架
3.1最优聚类算法
在应急管理、灾害事件管理、软件缺陷检测、信用风险评估等领域中，存在某些既包含历史数据，又不断产生新数据的数据流，这些流数据具有结构和特征上的相似性。
对于历史数据，我们通过统计实证分析，能够准确获知其簇类标号；但是，对于新数据，虽然在数据结构和特征上与历史数据类似，我们却并不能够及时准确的分析出其类标号。
对于这种流数据的挖掘通常是使用分类算法，由已知类标号的训练数据集预测测试数据集的类标号；这里，本文提出了另一种思路，即可由多种聚类算法来对“训练数据集”进行处理，选择出准确度最高的算法和参数来处理“预测数据集”，这样就不用再去进行多种聚类算法的比较，而且能够得出比较好的结果，同时又节约了计算成本和时间成本。
尤其是当需要分析的数据集非常巨大的时候，例如包含海量信息的数据库或数据仓库，效果更加突出、明显。
外部度量：
指聚类分析的评价函数是针对基准问题的，其簇的个数及每个数据项的正确的分类均为已知。
在这种情况下忽略划分的期望特征，只注重所得簇的分配的有效性，评价变得很直接[5]。
本文实验部分选取了8种最常用的外部有效性评价指标，分别是：
Purity（P）,Entropy（ET）,F_measure（F_m）[5],Rand_index（RI）,adjusted_Rand_index（aRI）,Jacard_coefficient（J）,FM[8],dissimilar（Dis）[4]，括号内是简写。
3.2最优聚类数目
聚类评价指标除了评估聚类算法结果质量的优劣之外，另一个主要目的和功能就是检验一个聚类算法在特定数据集上的聚类效率[18]，得出聚类算法的最优参数（如聚类数目），作为算法本身的优化标准。
特别是在基于智能优化算法的聚类方法中，度量标准直接或稍作修改即可作为算法的优化函数，指导数据集的划分过程[3]，这是处理聚类问题的一个热点。
正如引言部分的分析，聚类评价指标存在数据集和聚类算法的强针对性，在分析某一非特定数据集的最优聚类数目时，就需要综合考虑多种不同的评价指标。
然而，这些指标的处理结果往往是不一致，甚至是互相冲突和矛盾的。
因此需要一种能够解决这一问题的技术手段，而多目标决策正好是符合要求的方法。
相对度量是在确定聚类算法的基础上，采用预定义的评价标准针对该算法不同的参数设置进行算法测试，最终选择最优的参数设置和聚类模式[5]。
本文实验部分选取了10种具有代表性的相对有效性评价指标，分别是：
Hubert（H）,normalized_Hubert（nH）,Dunn,DB,SD,S_Dbw[17],CS[6],silhouette（sil）,PBM,C-index（CI）[7]，括号内是简写。
3.3多目标决策（MCDM）
多目标决策（Multi-CriteriaDecisionMaking,MCDM）方法是对多个不一致、甚至是相互矛盾的目标方案进行科学、合理的选择，然后辅助支持来做出决策的理论和方法，它属于运筹学和最优化理论的分支之一。
多目标最优化问题最早是由意大利经济学家L.帕雷托在1896年提出来的，他把许多本质上是不可比较的目标化成一个单一的最优化目标。
多目标决策方法在20世纪70年代中后期迅速发展起来，成为了决策分析科学、管理科学中的热点研究问题[19]。
为了使多目标决策的结果更加准确，通常需要利用专家、决策者在其操作过程中给予一定的指导，即为模型添加人工的约束和准则，并获得信息的实时反馈，常见的表现形式就是评价指标赋权。
引入多目标决策方法和专家决策支持系统到聚类结果有效性评价当中，可以解决特定数据集的最优聚类算法选择和最优聚类数目评估问题。
PrometheeII
本文实验部分采用的多目标决策算法主要是PROMETHEEII，同时使用了另一个著名的算法TOPSIS[20]来进行对比。
PROMETHEEI（部分排序）和PROMETHEEII（完整排序）是由J.P.Brans第一次提出的，具体发表在1982年在加拿大魁北克市拉瓦尔大学由R.Nadeau和M.Landry主办的一次会议上（L’IngéniériedelaDécision.Elaborationd’instrumentsd’AideàlaDécision）[21].。
PROMETHEEII算法的具体步骤如下[22]：
Step1:
先验假设
向量A={a1,..,an}是n个决策对象的集合，C={c1,..,cm}是m个标准，也就是评价指标。
评价指标又分为效益性指标（数值越大越好）和成本型指标（数值越小越好）。
这样，与问题相关的基础数据就构成了一个n×m的决策矩阵，矩阵中每行对应每个决策对象，每列对应每个评价指标。
Step2:
成对比较
首先，每个指标上的决策对象都需要进行成对比较：
（1）
dk（ai,aj）是两个决策对象在指标ck上的差值。
Step3:
偏好度
偏好函数是把差值转换为非指标化的偏好度：
（2）
这里
是一个正的非递减偏好函数，它满足Pj（0）=0。
在原始PROMETHEE定义中有六种不同类型的偏好函数，其中最常用的是下面的线性函数：
（3）
这里的qj和pj分别代表无差异阈值和偏好阈值。
Step4:
多目标偏好度
当决策者关联偏好函数到每个决策指标的时候，每对决策对象之间的比较就可以在所有指标上进行了。
多目标偏好度的计算公式如下：
（4）
这里wk代表指标ck.的权重，并且满足条件：
和
.显而易见，这样的导致的直接结果就是：
（5）
Step5:
多目标偏好流
为了得到每个决策对象与其他对象比较，需要计算以下两个指标：
（6）
这里的正偏好流
量化决策对象ai怎样全局地偏好优先于其他对象，负偏好流
量化其他对象怎样全局地偏好优先于决策对象ai。
一个理想的决策对象是其正偏好流为1，负偏好流为0。
两种不同的偏好流导致两种不同决策对象比较，PrometheeI部分排序就是根据两种偏好排序的交集定义。
决策对象ai好于aj，当
并且
的时候。
这正负两种偏好里整合得到净偏好流：
（7）
它满足条件：
（8）
PrometheeII完整排序就是根据决策对象净偏好流的递减关系来进行的。
3.4专家支持系统
由于聚类分析是一种无监督学习，在对数据进行分析时候，缺少先验知识的约束。
因此，在模型处理过程中，需要一些决策者、领域专家提供相关决策支持，与模型的运作通过模型提供的反馈信息进行互动和“交流”，以指导模型更好的计算出结果。
专家支持系统有以下作用和好处：
通过对数据集先验知识的了解，人工约束决策过程；
通过专业领域背景知识和经验，指导决策过程；
接受其他模块传递来的反馈信息，掌握模型动态；
通过对反馈信息的处理，与模型互动，调节优化模型结果。
3.4.1相关分析
相关系数作为最常用的统计分析手段之一，可以反映数据集中各个评价指标之间存在的内部或外部相关性，是模型中有效性评价指标的客观信息反馈，能够用以帮助决策者、领域专家更好的了解各指标间依赖程度和影响程度，从而更好地给出各指标间的权重，指导模型做出更加准确的决策。
最常用的相关系数是皮尔逊相关系数（Pearson'scorrelation），其计算公式如下[23]：
（9）
这里E是期望值，cov表示方差，corr是广泛使用的定义，表示皮尔逊相关系数。
相关系数为1表示完全正相关，-1表示完全负相关，0表示不相关。
3.4.2权重
权重，反映了各个有效性评价指标间的相对重要程度。
在本文模型中，权重的确定规则是：
外部有效性评价指标在各个数据集中使用统一的权重，而相对有效性评价指标在各个数据集中的权重则单独给定。
这是由于外部有效性评价指标根据聚类算法结果与真实数据集划分的接近度来确定的，在不同结构特征数据集之间也具有高度的一致性，所以可以直接使用统一权重，以省去大量不必要的重复设定和计算。
在相对有效性指标评价中，由于各评价指标对模型评价的重要性和指导性，会随着数据集的数值属性特征和结构不同而不同，因此，需要根据实际情况，针对每个数据集，结合先验知识（已知约束条件）、模型反馈信息（相关系数）和专家经验知识进行重新打分，以得出合理的权重。
在实际情况中，要找到适合一般数据集的最优评价指标需要耗费大量的时间和计算成本；尤其是面临包含海量数据的大型数据库进行聚类分析的时候，更是不可能完成的任务。
同时，每一个指标都不存在特别的优劣关系（尤其是相对评价指标），都有其针对的最适合数据集的属性特征和结构类型。
即使是改进的指标，也是针对某些数据特征的情况，并不具有完全级别高于属性。
所以，即使模型中得出两个指标的相关度较高，也有都保留的必要，只是在权重设定的时候，需要做出调整，这一点需要特别指出。
专家系统中的专家包括对数据集充分熟悉和了解的人员（如数据使用者、决策者、具有领域背景的专家），掌握聚类算法和聚类结果有效性评价函数相关领域知识的专家。
他们具有丰富的专业知识和行业经验，能够指导模型快速、准确地得出结果。
由于针对的属性特征不一样，一般情况下，特定数据集各个有效性评价指标之间的相关权重是不一致的，通常会具有较为明显的差异。
当然，也不排除各个指标权重都相差不大的极端情况，即等权重，这样得出的结果就类似于多数投票的结果。
3.4.3敏感性分析
显而易见，权重在多目标决策分析模块中扮演者非常重要的角色，它直接影响着模型的最终结果。
当权重一确定，最终的排序结果也就立马得出来了。
在这个模块中，本模型设计的专家系统能够为决策者提供额外的信息，即通过对权重的敏感性分析，反映模型结果的变化趋势。
对模型权重的敏感性分析，能够直观的反映出权重在对模型最终结果产生的影响。
在大多数情况下，决策者对立即给出精确的权重值是怀有犹豫的，这种犹豫是因为诸如无法决断、不精确、不确定性、缺少控制等现实环境中的因素导致的。
然而，决策者通常具有不同权重量级的排序概念，因此，即使会有犹豫，他可以给出包含正确权重值的权重区间。
这些区间可以表示为[21]：
（10）
敏感性分析是指从定量分析的角度研究有关因素发生某种变化对某一个或一组关键指标影响程度的一种不确定分析技术。
其实质是通过逐一改变相关变量数值的方法来解释关键指标受这些因素变动影响大小的规律。
4实验
根据第三部分提出的计算模型，本文将在这部分结合具体的实验阐述和解释其中的详细流程，实验将同时在最优聚类算法和最优聚类数目两个方面展开。
4.1数据介绍
本文选取了数据挖掘领域知名度最高的两个UCI数据集。
这些数据集来自UCI的分类数据库，即表明其数据结构特征和类标号都是已知的，旨在对模型进行验证。
当然，本文模型也能适用于其他一般情况下的数据集，无论其数据特征和结构是否已知。
这两个个UCI数据集分别是:
IRIS,WINE。
这些数据集包含的数据都是数值形式的或者可数值化的，其数据结构描述如表1。
表1实验数据集的描述
DataSet
Dimensionality
NumberofRecords
NumberofClusters
IRIS
4
150
3
WINE
13
178
3
4.2聚类算法
本文中，我们将采用七种不同的聚类算法来分析和处理实验数据集。
这七种算法分别是Cobweb（Cob）,EM,FarthestFirst（FF）,HierarchicalCluster（HC）,K-means（Km）,MakeDensityBasedclustererK-means（MD-K）和Fuzzyc-Means（Fc-M）。
小括号中是聚类算法名称的简写。
其中Fuzzyc-Means本文只采用其crisp的结果，而不考虑其模糊度矩阵。
这7种算法包括了基于划分的聚类算法，基于密度的聚类算法，基于模型的聚类算法，层次聚类算法等，涵盖了主要聚类算法的典型类别。
在本文中，使用开源的数据挖掘软件WEKA来运行这些聚类算法对数据集进行处理。
由于篇幅限制，实验接下来的内容将以数据集WINE作为展示模型步骤的主要分析数据集。
数据集IRIS的处理方法类似。
4.3相关系数
由前面理论部分知道，外部评价指标只是一种事后有效性评价方法，模式比较固定，思路清晰明确而单一，不同的指标之间差异性存在，但是在针对特定数据集或者聚类算法上却没有什么要求，其稳定性和通用较强。
因此，只需要对指标本身之间的相关性和权重进行考虑，所有数据集可以使用统一的权重。
在外部有效性评价指标这一块，本文的所采用的相关系数也正是通过对这两个个UCI数据集分别进行计算，然后取平均值而得，结果见表2。
表2各个外部有效性评价函数指标间的相关系数
P
ET
F_m
RI
aRI
J
FM
Dis
P
1.000
ET
-0.941
1.000
F_m
0.889
-0.780
1.000
RI
0.830
-0.731
0.982
1
升级会员 