I-Miner环境下多种聚类质量评价方法的实现

I-Miner环境下多种聚类质量评价方法的实现随着存储技术的进步和人们对海量信息的需求，数据挖掘取得了极大的发展。通过数据挖掘，人们可以从大量的数据库中提取对其有用的信息，并可以根据这些信息作出预测。数据挖掘技术集数理理论、专家系统、人工智能、神经网络、图形图象设计等多门学科于一身,其发展速度必将大大影响全球信息化的进程,对其进行系统、深入、全面、详尽地研究是信息化发展的客观需要。聚类分析是数据挖掘技术的重要手段和工具,在工程和技术等领域具有广泛的应用背景。它可以发现隐含在数据集中的簇，标识出感兴趣的分布或模式。聚类问题是将一组对象分成若干簇或聚类，使簇类的对象尽可能具有最大的相似性，不同簇之间的对象尽可能具有最大的相异性。聚类过程可以看成是一种无监督的学习过程。即依靠聚类算法进行的聚类分析大都是靠假设和猜测进行的。正是由于聚类分析的这种假设性和结果的不确定性使得在数据挖掘领域迫切需要一种客观公正的质量评价方法来评判聚类结果的有效性。目前常用的聚类有效性评价算法有外部评价法、内部评价法、相对评价法和模糊评价法等。本文通过重点学习聚类评价算法的原理，并利用S语言实现了外部评价法中的F-measure、Rand指数与Jaccard系数算法以及相对评价法中的SD有效性指数、基于聚类分布的有效性度量Ocq、基于多代表点的有效性指数CDbw算法。最后，在对大量的数据集(包括web文档)进行聚类分析的基础上，用实现的算法对聚类的结果进行评价，并对评价的结果进行分析和对比。关键词：数据挖掘;聚类分析;聚类评价第1章绪论1.1引言人们希望从海量的数据库中获取有用的信息是数据挖掘的初衷，而聚类分析则是数据挖掘过程中的一种重要手段和工具，它可以发现隐含在数据集中的相似性和相异性。聚类的过程就是按照相似性准则把数据划分成各种不同的类别，这个过程是一种无监督的学习过程，它没有一个标准来指导该如何划分或者说划分的结果是否合理，一切都是在假设和猜测中进行。因此，迫切需要一种客观公正的质量评价法来评判聚类结果的有效性，这种评价应该涵盖以下三方面：聚类质量的度量、聚类算法适合某种特定数据集的程度以及某种划分的最佳聚类数目。这就是数据挖掘领域的一个延伸：聚类的有效性评价。1.2国内外研究现状目前常用的聚类有效性评价方法有外部评价法、内部评价法、相对评价法和模糊评价法。外部评价法有F-measure和Rand指数、Jaccard系数等几种评价指标；内部评价方法有Cophenetic相关系数和Hubert’s统计等方法；相对评价法则有SD有效性指数、聚类有效性度量、基于多代表的有效性指数CDbw等评价方法；模糊评价法则是由划分系数、划分熵、划分模糊度指数等方法。当前的聚类评价算法的研究基本上都是在以上四种方法基础上进行的，由于大多数聚类算法中，需要用户输入希望产生的簇的个数，这样的话，聚类结果带有一定的主观和人为误差。聚类评价就是对聚类结果进行评价，最后给出一个合适的聚类参数。然而，聚类评价方法往往与特定的问题和所采用的聚类算法等因素有关，对于不同的数据集采用的聚类算法不一样，最后所采用的评价方法也不一样。由于聚类分析广泛应用于医疗、分子学、天体物理学和市场学各个方面，找到一个合适的聚类算法对提取人们所需要的信息显得十分重要，因此，研究聚类评价算法对于数据挖掘领域而言是十分必要和重要的，好的聚类评价方法可以为人们提供直接的聚类分析模型，从而更好的揭示大量数据库中数据的相似性和分离性。找到一个更加成熟的聚类有效性度量方法仍然是该研究领域的热点和方向。1.3本文研究内容本文主要是在学习数据挖掘原理的基础上，重点学习聚类评价方法，并掌握数据挖掘工具I-Miner，然后用S语言实现(外部评价法)F-meaure算法、Rand指数与(相对评价法)Jaccard系数算法以及SD有效性指数算法、基于聚类分布的有效性度量算法、基于多代表的有效性指数CDbw算法。然后，在对用大量的数据集(包括web文档)进行聚类后，通过以上聚类评价算法对聚类的结果进行分析和测试，进而对比各种评价算法的结果。各章节安排如下：第1章:绪论,介绍该论文研究背景和国内外研究现状第2章:介绍数据挖掘的背景和概念，然后引入聚类分析的概念，同时对聚类方法做介绍，重点讲述了k-means算法。最后介绍了聚类评价的概念和当前聚类评价算法的概况以及本文所要实现的聚类评价算法。第3章:主要介绍数据挖掘工具I-Miner以及S语言和S-PLUS第4章:首先介绍建立聚类过程的模型以及评价过程的建立。然后详细介绍了内部评价法里的F-measure算法、Rand指数和Jaccard系数算法以及相对评价法里的SD有效性指数算法、基于聚类分布有效性度量指数Ocq算法、基于多代表点的有效性指数CDbw算法的原理、实现步骤、流程图等内容。第5章:介绍本文实现的各种算法的程序运行情况和不同数据集进行测试后的结果以及各种算法内部与相互间的对比情况。第2章数据挖掘2.1数据挖掘2.1.1数据挖掘的背景及概念随着网络和存储技术迅猛发展，数据的传播和积累速度不断提高，却发现新的数据处理和提炼技术非常匮乏。面对日益庞大的数据资源，人们迫切需要更强有力的工具来“挖掘”其中有用的信息。数据挖掘就是针对这一需求而发展起来的一门新兴学科。数据挖掘(DataMining)，又称为数据库中的知识发现(KnowledgeDiscoveryinDatabase,KDD)，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程，简单的说，数据挖掘就是从大量数据中提取或“挖掘”知识。并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查找个别的记录，或通过因特网的搜索引擎查找特定的Web页面，则是信息检索（informationretrieval）领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。2.1.2数据挖掘的功能1.分类首先从数据中选出已经分好类的训练集，在该训练集上运用数据挖掘分类的技术，建立分类模型，对于没有分类的数据进行分类。注意:类的个数是确定的，预先定义好的.例如:a.信用卡申请者，分类为低、中、高风险b.分配客户到预先定义的客户分片2.估值估值与分类类似，不同之处在于，分类描述的是离散型变量的输出，而估值处理连续值的输出；分类的类别是确定数目的，估值的量是不确定的。一般来说，估值可以作为分类的前一步工作。给定一些输入数据，通过估值，得到未知的连续变量的值，然后，根据预先设定的阈值，进行分类。例如：银行对家庭贷款业务，运用估值，给各个客户记分。然后，根据阈值，将贷款级别分类。例如：a.根据购买模式，估计一个家庭的孩子个数b.根据购买模式，估计一个家庭的收入c.估计realestate的价值3.预言通常，预言是通过分类或估值起作用的，也就是说，通过分类或估值得出模型，该模型用于对未知变量的预言。从这种意义上说，预言其实没有必要分为一个单独的类。预言其目的是对未来未知变量的预测，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预言准确性是多少。4.相关性分组或关联规则对有关联性的数据或者有因果关系的数据进行分类和分组，例如：a.超市中客户在购买A的同时，经常会购买B，即A=>B(关联规则)b.客户在购买A后，隔一段时间，会购买B（序列分析）5.聚类聚类是对记录分组，把相似的记录在一个聚集里。聚集和分类的区别是聚集不依赖于预先定义好的类，不需要训练集。聚集通常作为数据挖掘的第一步。例如，"哪一种类的促销对客户响应最好？"，对于这一类问题，首先对整个客户做聚集，将客户分组在各自的聚集里，然后对每个不同的聚集，回答问题，可能效果更好。6.描述和可视化通过图形等形式对数据挖掘结果的表示。2.1.3数据挖掘的结构和流程数据挖掘是指一个完整的过程,该过程从大型数据库中挖掘先前未知的,有效的,可实用的信息,并使用这些信息做出决策或丰富知识.图2-1反映了数据挖掘的整体结构图2-1数据挖掘的系统结构数据挖掘的过程包括了对数据的选择、数据的预处理、数据的转换和数据的分析几个阶段，图2-2描述了数据挖掘的基本过程和主要步骤:图2-2数据挖掘的流程2.1.5数据挖掘的应用1.金融领域的数据挖掘①为多维数据分析和数据挖掘设计和构造数据仓库。例如，人们希望按地区、部门、以及其他因素查看债务和税收变化，同时希望提供最大、最小、综合、平均值趋势和其他统计信息。②贷款偿还预测和顾客信用政策分析。例如，与贷款偿还风险相关的因素包括贷款率、负债率、偿还收入比、顾客收入水平和信用史等。分析顾客偿还史信息可以发现偿还收入比。于是银行可以据此调整贷款发放政策③针对定向销售的顾客分类与聚类。例如，可以使用分类识别可能影响顾客关于银行业务决策的最重要的因素。使用多维聚类技术可以识别对贷款偿有类似行为的顾客。这些可能帮助识别顾客群，把新顾客归到一个合适的群，推动定向销售2.商品销售商业部门把数据视作一种竞争性的财富可能比任何其他部门显得更为重要，为此需要把大型市场营销数据库演变成一个数据挖掘系统。科拉福特(Kraft)食品公司(KGF)是应用市场营销数据库的公司之一，该公司搜集了购买它商品的3000万个用户的名单，这是(KGF)通过各种促销手段得到的。KGF定期向这些用户发送名牌产品的优惠券，介绍新产品的性能和使用情况。该公司体会到了解自己商品的用户越多，则购买和使用这些商品的机会也就越多，公司的营业状况也就越好。3.远程通讯及其他许多远程通讯的大公司近来突然发现它们面临极大的竞争压力，这在几年前是不存在的。在过去，业务上并不需要他们密切注视市场动向，因为顾客的挑选余地有限，但是这种情况近来发生很大变化。各公司当前都在积极收集大量的顾客信息、，向他们现有的客户提供新的服务，开拓新的业务项目，以扩大他们的市场规模。从这些新的服务中，公司在短期内就可以取得更大的效益。不仅如此，在电信业、零售业、生物学、加工制造等领域均有数据挖掘的应用。2.2聚类分析2.2.1聚类分析的概念把一个数据集(通常是多元的)分解或划分为成组，使同一组中的点彼此相似，但与其他组中的点尽可能不同,这就是聚类分析。从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。就数据挖掘功能而言，聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理步骤。作为数据挖掘的一个很重要的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，它是模糊集理论的重要应用，主要是将实际中模糊性问题同过数学手段实现一定的归类分析。同时它又是一种数据简化技术，它把基于相似数据特征的变量和个案组合在一起，这对发现基于相似特征(如人口统计信息、财政信息或购买行为客户细分)非常应用2.2.2聚类算法聚类分析是数据挖掘中的一个很活跃的研究领域，并提出了许多聚类算法。这些算法可以被分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。1划分方法(PAM:PArtitioningmethod)首先创建k个划分，k为要创建的划分个数；然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括k-means,k-medoids,CLARA(ClusteringLARgeApplication),CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch)。这里重点介绍一下k-means算法，本文所采用的聚类算法均为k-means.K-Means算法试图确定最小化平方误差函数的k个划分。当结果簇是紧凑的，并且簇与簇之间明显分离时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和有效率的。因为它的计算复杂度是O（nkt）,其中n是对象的总数，k是簇个数，t是迭代的次数。通常地，k<<n,并且t<<n。该方法经常终止于局部最优解。然而，只有当簇均值有定义的情况下K-Means方法才能使用。图2-1为k-means算法的流程图图2-1k-means算法流程图2层次方法(hierarchicalmethod)创建一个层次以分解给定的数据集。该方法可以分为自上而下（分解）和自下而上（合并）两种操作方式。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。典型的这类方法包括：第一个是BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)方法，它首先利用树的结构对对象集进行划分；然后再利用其它聚类方法对这些聚类进行优化。第二个是CURE(ClusteringUsingREprisentatives)方法，它利用固定数目代表对象来表示相应聚类；然后对各聚类按照指定量（向聚类中心）进行收缩。第三个是ROCK方法，它利用聚类间的连接进行聚类合并。最后一个CHEMALOEN，它则是在层次聚类时构造动态模型。3基于密度方法，根据密度完成对象的聚类。它根据对象周围的密度（如DBSCAN）不断增长聚类。典型的基于密度方法包括：DBSCAN(Densit-basedSpatialClusteringofApplicationwithNoise):该算法通过不断生长足够高密度区域来进行聚类；它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集。OPTICS(OrderingPointsToIdentifytheClusteringStructure):并不明确产生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。4基于网格方法首先将对象空间划分为有限个单元以构成网格结构；然后利用网格结构完成聚类。STING(STatisticalINformationGrid)就是一个利用网格单元保存的统计信息进行基于网格聚类的方法CLIQUE(ClusteringInQUEst)和Wave-Cluster则是一个将基于网格与基于密度相结合的方法。5基于模型方法它假设每个聚类的模型并发现适合相应模型的数据。统计方法COBWEB:是一个常用的且简单的增量式概念聚类方法。它的输入对象是采用符号量（属性-值）对来加以描述的。采用分类树的形式来创建一个层次聚类。CLASSIT方法:它是COBWEB的另一个版本。它可以对连续取值属性进行增量式聚类。它为每个结点中的每个属性保存相应的连续正态分布（均值与方差）；并利用一个改进的分类能力描述方法，即不像COBWEB那样计算离散属性（取值）和而是对连续属性求积分。但是CLASSIT方法也存在与COBWEB类似的问题。因此它们都不适合对大数据库进行聚类处理.2.3聚类评价尽管有了聚类算法，我们可以对庞大的数据进行抽取和分析并得到我们认为有用的信息，然而，我们所采用的聚类算法是否对某一数据集的聚类结果是假设中最好的，我们还无法得知，或者说我们有可能用了一个并不适宜的算法对一个数据集进行了分析，这样得到的结果显然是不行的。因此，问题就产生了——如何对聚类结果进行评价？这成为了聚类分析领域所延伸的另一个热点。目前较为普遍的聚类评价方法有四种：外部评价发、内部评价发、相对评价法、模糊评价法。外部评价法意味着评判聚类算法的结果是基于一种预先指定的结构，这种结构反映了我们对数据集的聚类结构的直观认识，这里介绍两种:F-measure该算法通过查准率和查全率两个参数来评判聚类结果，即看聚类后的分类中数据点的相似性与聚类前相比差异性有多大，越接近的则聚类结果就越好Rand指数和Jaccard系数该算法通过比较数据集的划分矩阵和聚类结果矩阵，并统计两个矩阵中数据点对个数的多少来判定聚类结果的好坏内部评价方法是利用数据集的固有特征和量值来评价一个聚类算法的结果，数据集的结构是未知的，这里介绍两种:Cophenetic相关系数该评价法主要是针对层次聚类算法，其产生图可用Cophenetic矩阵表示，通过度量临近矩阵与Cophenetic矩阵的相似性来判定聚类结果Hubert’SG统计该评价法对包含k个簇的单个聚类结果C通过比较聚类后的矩阵和临近矩阵之间的一致性程度进行。相对评价法是根据预定义的评价标准，针对聚类算法不同的参数设置进行测试，这里介绍三种相对评价法:SD有效性指数它是基于聚类平均散布性和聚类总体分离性的一种相对度量方法，聚类平均散布性揭示聚类后聚类内数据的分散程度，而聚类总体分离性则是揭示聚类后聚类间的数据的离散程度。基于聚类分布的有效性度量用聚类结果分布的自然属性来评价聚类内的同一性和聚类间的分离性与最大化聚类内相似性和最小化聚类间相似性这一聚类目标是相符的。聚类密集型越小，聚类内成员越接近。聚类临近性越小，聚类间成员越分散。聚类分布的有效性度量正是综合了这两者，最后所得到的是一个基于聚类分布的综合质量评价，这个评价值越高，聚类的结果就越好基于多代表的CDbw通过多个点来表达聚类结构，这显然比只用中心点表达聚类结构方法好的多。CDbw依赖于聚类密集性(聚类内的密度)和聚类分离性(聚类间距离与密度综合)，有效性指数越大聚类的效果越好模糊评价法是寻求数据集中大多数矢量在一个簇中有高的隶属度聚类模式。模糊有效性指数主要分为两大类:第一类指数只涉及隶属度值，如划分系数.第二类指标同时设计隶属度和数据集结构信，如Xie-Beni(XB)指数。第3章数据挖掘工具I-Miner3.1I-Miner软件3.1.1I-Miner简介I-Miner（InsightfulMiner的简称）是一个企业级的数据挖掘工具。数据挖掘是统计学的一种应用形式，它体现为探索性数据分析和预测性模型，以此来发掘大数据中隐藏的模式和趋势；它往往是以半自动的方式被使用。由于企业在数据获取收集方面的不断进步，用户可能已经发现自己身处庞大的数据体系之中，这些数据可能保存在关系型数据库、数据仓库或者数据集市中。I-Miner允许你以各种方式探索这些数据。并带给你直观易用的图表。还可以使用I-Miner的易用的可视化编程环境，创建并运行你自己的个性化分析。3.1.2I-Miner功能I-Miner设计目标之一是，使得它可以与你已经在用的软件无缝衔接。你可以针对很多数据源数据进行读入输出，包括如Excel和Lotus等电子表格、Access类的数据库、SAS和SPSS类的统计软件以及如Oracle/DB2/SQLServer等流行的关系型数据库。一旦访问到了数据，用户就可以使用I-Miner的数据清洗和数据操纵等工具为你的分析建模准备数据了。用户可以使用各种图、表以及描述性统计探索你的数据，然后拟合各种统计模型；包括分类型的和回归型的决策树以及线性回归、Logistic回归等模型。我们还可以使用提升图一类的标准工具评估模型性能。图3-1为利用该软件建立数据挖掘模型的一个界面:图3-1I-Miner建立数据挖掘模型图通过I-Miner,我们还可以利用其提供聚类分析算法对数据集进行聚类，聚类的模型建立过程如图3-2:图3-2I-Miner建立聚类分析模型图3.1.3S语言及I-Miner扩展功能S语言是由AT&T贝尔实验室开发的一种用来进行数据探索、统计分析、作图的解释型语言。它的丰富的数据类型（向量、数组、列表、对象等）特别有利于实现新的统计算法，其交互式运行方式及强大的图形及交互图形功能使得我们可以方便的探索数据。目前S语言的实现版本主要是S-PLUS。它基于S语言，并由MathSoft公司的统计科学部进一步完善。I-Miner使用S-PLUS语言的一个子集用于其脚本。语言的最基本形式(算术运算、数据集取子集等等)被用于S-PLUS过滤行、S-PLUS分拆以及S-PLUS创建列等组件，而更深层次的S-PLUS代码被用于S-PLUS脚本组件。它极大地拓展了I-Miner的功能，在用户的实际需求下，通过编写脚本，来完成I-Miner本身没有的功能。I-Miner缺省安装了S-PLUS库，使得用户可以使用这些节点的S-PLUS表达式，并且在探索器框中有S-PLUS节点页。为了更广泛使用I-Miner的S-PLUS节点，用户可以使用S-PLUSEnterpriseDeveloper的好处，它提供了很多I-Miner不包含的特征，比如S-PLUS图形用户界面、工作台开发环境、S-PLUS控制台应用(sqpe)、S-PLUS嵌入Excel、S-PLUS嵌入SPSS，以及自动应用和其它接口(包括OLE、DDE、COM等)。图3-3I-Miner环境下利用S-PLUS节点运行S语言编写的程序图3-3I-Miner下扩展S-PLUS功能图3.2S-PLUS软件3.2.1S-PLUS简介S-PLUS是Insightful公司的旗舰产品、是市场上最有权威的数据分析软件之一，她提供了弹性的、互动的环境来分析、可视及展示数，并且提供了最全面的包括稳健性方法在内的各种先进的模型。S-PLUS的基础是前面所介绍的S语言。Insightful公司与多个领域的顶尖研究者紧密合作，因此各种统计方法上的进展都会很快被扩展到S-PLUS中。S-PLUS最大的优势在于它可以交互地从各方面发现数据中的信息，并由于S语言的扩展性使得它可以很容易地实现一个新的统计方法。而且S-PLUS的数据可以直接来源于Excel，Lotus，Access，SAS，SPSS等软件，其兼容性极好。另外，S-PLUS拥有独一无二的可视化交互式图形显示，其中包括著名的Trellis图形分析。S-PLUS的图形是面向对象的，因此用户可以修改每个细节，来产生适合报告用的图形。S-PLUS提供广泛的2D及3D图形种类，包含了非常广泛的图形库。用户可以轻易的调整图形的属性，包括线条、颜色、字型等。创新的S-PLUSGraphlets技术可以产生互动式的图形，让使用者能够对图形逐层下探观察数据，或是连接到Web网页，让读者可以即时地与用户的数据互动。3.2.2S-PLUS操作界面下面的图为S-PLUS的操作界面，其中ObjectExplorer窗口可以看到目前有的数据、函数、图形等的总览。在ObjectExplorer窗口中不仅可以观察数据，也可以对数据进行编辑。CommandWindow窗口事实上是S-PLUS的核心。每一个通过菜单或者按钮完成的命令都可以在CommandWindow中通过命令来实现。而且，有很多函数只能在CommandWindows窗口中运行。例如，需要编程的函数、个性化的函数和一些逻辑操作都只能在CommandWindows窗口中运行。图3-4S-PLUS操作界面3.2.3S-PLUS功能S-PLUS下运行S语言程序S-PLUS的基本语言为S语言，它为S语言提供了可靠的运行环境。下图为在S-PLUS环境下运行的一个S语言编写的聚类评价算法的程序的运行情况。图3-5S-PLUS下S程序运行情况S-PLUS画图S-PLUS拥有非常强大的画图功能，利用它我们可以绘制2D、3D图、散点图、交互图和其他高级图形，这里我们以2D图为例，S-PLUS提供了这样的功能:我们可以导入一个数据集(二维的)，然后利用画图功能，可以选择绘制线性回归图还是其他图形，并且图形的参数有多种设定，我们可以根据需要选择是否绘制点图还是线图。下面是我们对一个二维的数据集在S-PLUS下绘制的回归图形，一个是参数设定界面，一个是绘制结果界面。图3-6S-PLUS下绘制图形设置参数界面图3-7S-PLUS下回归图形绘制界面第四章聚类评价算法4.1聚类评价的模型聚类评价是对数据集通过一定的聚类算法进行聚类后，然后对聚类的结果的质量进行评价的过程。因此，评价的模型应该是先建立聚类的模型，再建立评价的模型。本文所采用的聚类算法为k-means。图4-1揭示了聚类评价的整体流程：图4-1聚类评价的流程4.1.1聚类过程的建立图4-2为聚类过程的建立，从数据集的读取、修改、聚类分析、存储结果都可以在I-Miner环境下实现。图4-2聚类模型建立4.1.2评价过程的建立在聚类的基础上，利用聚类的结果我们可以对其进行聚类评价，本文所采用的评价算法包括F-measure、Rand与Jaccard、SD有效性指数、基于聚类有效性分布Ocq、基于多代表点有效性CDbw，同样在I-Miner下建立，并利用了I-Miner的扩展功能S-PLUS，下图给出此评价模型的建立。图4-3评价模型建立4.2F-measure算法4.2.1算法原理F-measure组合了信息检索中查准率（precision）与查全率（recall）的思想来进行聚类评价。一个聚类j及与此相关的分类i的precision与recall定义为：(1)(2)其中Nij是在聚类j中分类i的数目，Nj是聚类j中所有对象的数目，Ni是分类i中所有对象的数目。则分类i的F-measure定义为：(3)对分类i而言，那个聚类的F(i)最高就代表该i的映射，同样对于不同的聚类c而言，都应该有一个综合的F-measure值，如果那个聚类c的F值最高，我们就认为当聚类个数为c时聚类效果最好(3)4.2.2算法实现步骤:S1:导入聚类文件，读取文件的行数rowS2:k=1,c=0,p=0,Nij=0Nj=0,Ni=0S3:读取第k行的聚类数j，分类数i,S4:聚类j中分类i的数目Nij=Nij+1S5:聚类j中对象的数目Nj=Nj+1S6:分类i中所有对象的数目Ni=Ni+1S7:若j>c，则c=j,否则转S8S8:若i>p,则p=i,否则转S9S9:k+1S10:若k<=row,返回到S3S12:i=1S13:max=0S14:j=1S15:计算分类i的F-measure评价值Fij矩阵中S16:若Fij>max,max=FijS17:j+1S18:若j<=c,转S14,否则转S19S19:Fi1=maxS20:i+1S21:若i<=p，max=0，转S13，否则转S22S22:i=1,count=0,F=0S23:F=F+Fi1*Ni,count=count+NiS24:若i<p，i=i+1,转S23,否则转S25S25:总评价值F=F/countS26:退出4.2.3算法流程图图4-4F-measure算法流程图4.3Rand与Jaccard算法4.3.1算法原理设数据集X的一个聚类结构为，数据集已知的划分为，可通过比较C和P以及邻近矩阵与P来评价聚类的质量。对数据集中任一对点(Xv,Xu)，计算下列项:SS：如果两个点属于C中同一簇，且P中同一组；SD：如果两个点属于C中同一簇，但P中不同组；DS：如果两个点不属于C中同一簇，而P中属同一组；DD：如果两个点不属于C中同一簇，且P中不同组。设a、b、c、d分别表示SS、SD、DS、DD的数目，则为数据集中所有对的最大数，即，N为数据集中点的总数。则C与P之间的相似程度可由如下有效性指数定义Rand指数：.(4)Jaccard系数：.(5)上述两指数取值范围均为[0,1]，当m=s时，有最大值。4.3.2算法实现步骤S1:导入F-measure算法中间过程产生的Nij文件，读取行数row,列数colS2:a=0,b=0,c=0,d=0S3:i=1S4:j=1S5:a=(Nij-1)*Nij/2+aS6:若j<=col，j=j+1,转S3,否则转S5S7:若i<=row,i=i+1,转S3,否则转S7S8:j=1,p=0S9:i=1,sum=0S10:sum=sum+(Nij-1)*Nij/2,p=p+NijS11:若i<=row,i=i+1,转S10,否则转S11S12:p=p*(p-1)/2,b=b+p-sumS13:若j<=col，j=j+1,p=0,转S9,否则转S14S14:i=1,p=0S15:j=1,sum=0S16:sum=sum+(Nij-1)*Nij/2,p=p+NijS17:若j<=col，j=j+1,转S16,否则转S17S18:p=p*(p-1)/2,c=c+p-sumS19:若i<=row,i=i+1,p=0,转S15,否则转S20S20:sum=row*(row-1)/2,d=sum-a-b-cS21:R=(a+d)/M,J=a/(a+b+c)S22:输出R,JS23:结束4.3.3算法流程图图4-4Rand与Jaccard算法流程图4.4SD算法4.4.1算法原理SD有效性指数是基于聚类平均散布性（Averagescatteringforclusters）和聚类间总体分离性（Totalseparationbetweenclusters）的一种相对度量方法。已知数据集X的方差为，其第p维方差定义为(6)其中是第p维均值.(7)聚类i的方差为，其第p维方差定义为.(8)则聚类的平均散布性定义为.(9)聚类的平均散布性所反映的是聚类内的数据代表点的分布，聚类的平均散布性的值越小，说明聚类内的数据代表点的分布越集中，聚类的效果也就越好。聚类间总体分离性定义为(10)聚类的总体分离性所反映的是聚类间的数据代表点的分布情况，它的值越大表明不同聚类间的数据代表点的越靠近，反而，如果聚类总体分离性的值越小则说明聚类间的数据代表点的分布就越远离。其中，，分别是聚类中心间的最大和最小距离，c为聚类个数。最后可得到质量指数.(11)其中加权因子，cmax为输入聚类的最大数目。SD的值所反映的是基于聚类平均散布性和聚类间总体分离性的综合指标。SD计算是要分别在Cmax取不同值的情况下进行，因此，最后得到的SD是Cmax不同时，聚类个数c从指定最小值Cmin到Cmax的值，SD取最小值时所对应的划分个数即为最优的聚类划分数目。4.4.2算法实现步骤S1:导入数据集合聚类后的文件，并获取聚类个数cS2:计算数据集方差σ(X)S3:计算每个聚类的均值和方差σ(Vi),然后可以计算聚类的平均散布性Scat(c)S4:,设定聚类中心间的最大距离Dmax=0和最小距离Dmin=1000S5:i=1,j=1S6:若j!=i转S7S7:计算聚类i和聚类j的中心点的距离S8:若j<c，j=j+1，转S6S9:若d<Dmin则Dmin=d,否则转S10S10:Dmax=dS11:计算总体分离性Dis=Dis+1/dS12:若i<c，i=i+1,转S6S13:Dis=Dis*Dmax/Dmin，可以计算出SDS14:S15:退出4.4.3算法流程图图4-4SD算法流程图4.5Ocq算法4.5.1算法原理用聚类结果分布的自然属性来评价聚类内（Intra-cluster）的同一性和聚类间（Inter-cluster）的分离性与最大化聚类内相似性和最小化聚类间相似性这一聚类目标是相符的。聚类密集性是一种有关聚类内方差的测量，方差越小说明数据集的同一性越高。给定一个数据集X，其簇内方差被定义为(12)其中是矢量与之间的距离，N是X的总个数，是X的均值(13)对聚类输出结果c1,c2,…,cC，聚类密集性被定义为(14)其中C为聚类个数，var(ci)是簇ci的方差。因为每个聚类内的成员应尽可能地接近，所以聚类密集性越小越好。但是在极端情况下，当每个输入矢量被分为单独的类时，聚类密集性有最小值0。聚类邻近性被定义为:(15)其中σ为高斯常数，为简化计算，取2σ2=1.0。是聚类ci的中心，为聚类ci中心与cj中心之间的距离。因为各聚类应有效地分开，且聚类邻近性反比于聚类间距离，所以聚类邻近性越小越好。然而，当整个输入矢量被聚为一个类时，聚类邻近性有最小值0。为了评价一个聚类系统的综合质量，可将上述聚类密集性与聚类邻近性组合为一种评价方法，称作聚类综合质量（Overallclusterquality），它被定义为(16)其中是平衡聚类密集性与聚类邻近性的权值，例如，Ocq(0.5)表示两种评价有相等的权值。显然，聚类综合质量越大越好。4.5.2算法实现步骤S1:导入数据集文件和聚类后的文件，并获取聚类个数cS2:计算数据集的方差Var(X)S3:根据聚类文件计算每个聚类i的均值和方差Var(ci)S4:i=1,Cmp=0S5:聚类密集性Cmp=Var(ci)/Var(X)+CmpS6:若i<c，i=i+1,转S5，否则转S7S7:Cmp=Cmp/cS8:i=1,j=1,Prox=0S9若j!=i，转S10S10:计算聚类i,j中心点距离d,Prox=Prox+exp(d)S11:若j<c,j=j+1,转S9,否则，转S12S12:若i<c,j=1,i=i+1,转S9,否则转S13S13:Prox=Prox/(c*(c-1))，然后计算聚类综合质量OcqS14:输出OcqS15:结束4.5.3算法流程图图4-5Ocq算法流程图4.6CDbw算法4.6.1算法原理用多个具有代表性的点表达聚类结构，这比只用单个中心点表达聚类结构的方法要好，可适用于非球形聚类。CDbw依赖于聚类密集性（聚类内密度）和聚类分离性（聚类间距离与密度综合）。让表示一个数据集X被聚类成c个凸簇，其中表示第i簇中代表点的集合，vij为第j个代表点，ri为代表点的总数，则第i簇的平均标准方差被定义为:(17)其中NI为第I簇中数据个数，D为XK与MI之间的距离，XK为第I簇中数据，MI为均值。聚类内平均密度（intra-clusterdensity）被定义为聚类中属于代表点邻域的数据点的百分数，它越高表明聚类越密集。其定义如下(18)其中对应第i簇中第j个代表点vij以一指定因子向簇的中心收缩后的位置。项被定义为.(19)它表示第i簇代表点的邻域中点的数目，的邻域定义为以为中心、簇的平均方差stdev(Vi)为半径的超球体，故函数被定义为(20)在每个点被分为一个簇的极端情况下，即c=n时，stdev(Vi)=0，=1，于是，Intra_dens(n)=1。聚类间密度（Inter-clusterDensity）用于度量聚类周围区域的平均密度，显然，此密度越低越好。当一个数据集被分为2类以上（即c>1）时，其聚类间密度定义为,(21)其中close_rep(i)和close_rep(j)是第i和j簇间最近的代表点，uij为close_rep(i)和close_rep(j)连线的中点，项density(uij)被定义为.(22)它表示在第i和j簇中属于uij邻域的点的百分数，uij的邻域定义为以uij为中心、平均方差为半径的超球体，故函数被定义为(23)很显然，如果一个数据点到uij的距离小于簇的平均标准方差，它必然属于uij的邻域。在每个点被分为一个簇的极端情况下，即c=n时，stdev(Vi)=0，=0，于是，Inter_dens(n)=0。聚类分离性（Clusters’Separation）与最近聚类间的距离和聚类间密度有关。希望聚类间的距离大而密度低，故聚类分离性定义为.(24)最后，有效性指数CDbw定义为(25)4.6.2算法实现步骤S1:导入数据集和聚类后文件并获取聚类个数c和每个聚类i的对象的个数p(i)S2:根据聚类文件计算每个聚类i的标准方差Stdev(Vi)S3:i=1S4:j=1S5:k=1S6:计算第i簇的第j个代表点与第i簇第k数据点的距离dS7:若d<=Stdev(Vi)，转S8,否则转S9S8:density(Vij)=density(Vij)+1S9:若k<p(i),k=k+1,转S6，否则，转S10S10:若j<p(i),i=i+1,转S6,否则转S11S11:若i<c,i=i+1,转S4,否则,转S12S12:聚类内平均密度Intra_dens=Intra_dens+density(Vij)/Stdev(Vi)S13:计算第i簇和第j簇代表点最近距离保存在Lij中,两点的中点保存在Uij中S14:i=1S15:j=1S16:若j!=i转S17S17:k=1S18:计算第i,j簇的第k个代表点与Uij的距离dS19:若d<=(Stdev(Vi)+Stdev(Vj))/2转S20，否则，转S21S20:Density(Uij)=Density(Uij)+1S21:若k<p(i)+p(j),k=k+1,转S18，否则转S22S22:Density(Uij)=Density(Uij)/(p(i)+p(j))S23:若j<c,j=j+1,转S17，否则转S24S24:若i<c,i=i+1,转S15,否则转S25S25:i=1S26:j=1S27:若j!=i转S28,否则转29S28:聚类间密度Inter_dens=Inter_dens+Lij*Density(Uij)/(Stdev(Vi)+Stdev(Vj))S29:若j<c,j=j+1,转S27S30:若i<c,i=i+1,转S26，否则转S31S31:i=1S32:j=1S33:若j!=i转S34否则转35S34:聚类间分离性Sep=Sep+Lij/(1+Inter_dens)S35:若j<c,j=j+1,转S33S36:若i<c,i=i+1,转S32，否则转S37S37:有效性指数CDbw=Intra_dens*SepS38:输出CDbwS39:结束4.6.3算法流程图图4-6CDbw算法流程图第五章算法测试及结果5.1测试数据集本文测试所涉及到的有iris数据集（有150个数据，分为3个类别，每个数据有4种属性）、glass数据集（有214个数据，分为7个类别，每个数据有9种属性）、wine数据集（有178个数据，分为3个类别，每个数据有13个属性）、zoo数据集(有125个数据，分为7个类别，每个数据有16个属性)，具体情况如表5-1所示:表5-1数据集概况领域irisglasszoowine数据大小150214125178分类数3673属性数4916135.2F-measure评价法测试5.2.1程序运行情况下图为用s语言编写的F-measure算法在S-PLUS下运行情况:图5-1F-measure程序运行结果5.2.2测试结果根据F-measure算法的思想，在每次通过k-means进行聚类，聚类的所设定的个数C不同时，质量评价的结果F-measure值也不同，这些不同的F-measure值中的最大值所对应的C就是我们所要寻找的最佳聚类个数。图5-2以iris数据集为例，反映出F-measure值随聚类个数C的变化情况:图5-2iris数据集F-measure算法测试结果从图中我们可以看出对iris数据集聚类后的结果在C=3时取得最大值，而从表5-1中我们看到iris数据集的分类数为3，这说明我们通过评价算法所得到的最优划分数与原来的数据集的划分数目是一致的。同时我们也对其他数据集进行了和iris数据集一样的测试，其结果如表5-2所示:表5-2不同数据集的F-measure评价结果数据集Iriswineglasszoo数据集划分数3367F-measure最大值0.8330.9520.4910.821对应聚类个数c3367从表中我们可以看出其他数据集的评价结果与iris数据集的评价结果是一致的，而且我们可以看出F-measure的值都在[0,1]之间，如果我们横向比较，发现wine数据集的F-measure评价值最高为0.952，这也说明一个问题，那就是通过该评价算法得出的结果对于wine数据集而言是最佳的，也就是说wine数据集的事先划分达到了最优的效果，而对于glass而言，它的评价值仅有0.491,相对于其他数据集在k-means下的聚类结果而言并不是很好。这也从侧面反映出一个问题，我们的评价算法是针对聚类评价结果而进行的，但在本文中我们所采用的聚类算法均为k-means，它有可能并不适合于所有的数据集，因此对聚类的结果而言是有影响，从而我们对聚类结果的评价也存在一定的缺陷。但就算法本身而言，我们达到了预期的效果。5.2.3小结F-meaure评价算法是与原始数据集预先的划分个数c相关的，F-measure评价结果的最大值是与c一致的，但是F-mesure算法的评价结果受到聚类算法的影响，本文所采用的k-means算法并不可能全部适用于所有数据集，因此聚类的效果并不会是最好，这样导致我们的聚类评价结果在达到最大值时所对应的划分数有可能并不是数据集的最优聚类个数m，这个m的值并不一定针对k-means算法。此外，F-measure的值是在[0.1]之间，越接近1说明数据集在k-means下的聚类效果越好，我们所得到的最优划分数目的可信度也越高。当然，F-measure算法的思想导致了我们测试结果的局限性，当这并不影响我们从该评价算法中所得出的结论:F-measure的值越大，聚类的效果越好；F-measure最大值所对应的划分个数与数据集事先的划分个数一致。5.3Rand与Jaccard算法测试5.3.1程序运行情况下图为Rand与Jaccard算法程序运行情况，运行环境为S-PLUS图5-3Rand与Jaccard算法程序运行结果5.3.2测试结果Rand指数和Jaccard系数所反映的均为聚类后数据集和聚类前数据集的相似程度。对于Rand算法，R的值为，这里M是一定的，a是同簇同组的数据点对的总数，d是不同簇不同组的数据点对的总数，我们知道，在聚类划分最优时，a应该最大，d应该最小，而在小于最优划分或者大于最优划分时,a和d的值也都是此消彼长的。对于而言，并不一定在取得最优划分时获得了最大值，因此，R的值也就未必是最大的，对于Jaccard算法，,同理，a虽然在取得最优划分是最大，但是d同时也应该是最小的，这样的话J的值也取决于a的增加的幅度与d减少的幅度那个大，若前者大则J的值就相对大，反之亦然。这就说明我们并不能够从得到的R和J的值来判定最优的划分数目，它们仅仅反映了聚类前后数据点分布的变化情况。下图为我们通过同样以iriss数据集为例，通过多次k-means聚类后，用该算法进行评价的R值和J系数值随聚类个数clusternumber变化情况:图5-4iris数据集Rand算法测试结果图5-5iris数据集Jaccard算法测试结果从图中我们可以看出R的最大值在聚类个数c=5时出现，而J的最大值出现在c=2,,这与iris数据集的划分个数并不一致，我们也无法从图中找到一个合适的划分个数。但是，从图的走向情况，我们可以看出Rand指数值和Jaccard值在c=3后大幅度下降,在c=4后又出现大幅度的上升，这说明在这前后的聚类效果有很大的变化。下表我们对其他数据集的Rand算法和Jaccard算法测试结果作了一个统计，希望可以从中发现某些规律:表5-2不同数据集的Rand算法与Jaccard算法评价结果数据集iriswineglasszoo原始划分个数3367Rand最大值0.8370.9340.6940.918对应聚类个数5375Jaccard最大值0.5920.8240.3050.705对应聚类个数2345Rand临界下降聚类数3375Rand临界上升聚类数4246Jaccard临界下降聚类数3345Jaccard临界上升聚类数4276从表中我们看不出划分个数和评价指数最大值所对应的聚类个数之间有任何的联系，但是，我们发现在Rand和Jaccard值发生大幅度变化时所对应的聚类个数总是在划分个数的附近，以zoo数据集为例，它在c=5后突然下降，而在c=6后突然上升，这种变化情况至少说明在聚类个数为[5,6]前后的聚类质量发生了明显的变化，变化的区间也在划分个数7的附近，这正是由算法的原理所决定，因为R的值和J的值都受到划分个数的影响。再以glass数据集为例，它在c=7后突然下降，然后一直到c=4后又突然上升，在[4,7]这个区间前后聚类的质量有明显变化。这种变化并不会直接告诉我们最优的划分个数是多少，但至少我们可以根据这种区间的变化来决定我们在进行聚类的时候聚类个数的选择应该以变化区间前后为准，这样，我们的聚类效果就应该是比较好的。5.3.3小结Rand算法和Jaccard算法都是通过比较聚类前后数据集中代表点的分布情况来获取一定的评判值，评判值的范围在[0,1]区间，它的大小受到数据集划分个数的影响，但与F-measure算法的不同之处在于，根据该算法并不能直接得到最优划分个数。不过，通过两个评价值的变化区间，我们可以得到一个最佳聚类划分可能的存在范围，即最好的聚类质量结果所对应的划分个数应该在评价值的变化区间前后。因此，Rand算法和Jaccard算法能够提供给我们最佳聚类数目的存在区间，这对于我们在进行k-means聚类时同样具有一定的指导价值。总体来说，根据Rand算法与Jaccard算法得到的最大值所对应的划分数目并不是我们寻找的最优划分数目，通过该算法也得不到最优划分数目，但它可以给我们提供这个最优划分数目的存在区间，这对于如何聚类同样具有一定的指导意义。5.4SD算法测试5.4.1程序运行情况下图为SD算法程序在S-PLUS下的运行情况:图5-6SD算法程序运行结果5.4.2测试结果SD算法是基于聚类平均散布性Scat和聚类总体分离性Dis的一种相对度量法，对于每一次k-means聚类，都会得到一个Scat和一个Dis,假定我们对k-means从[3,10]进行了聚类，那就对应8组Scat和Dis，之后，我们需要指定Cmax即最大输入聚类个数，Cmax的值应该在[3,10]这个范围内，然后对应于每一个Cmax，我们都要计算从[3,Cmax]的SD指数，因此，假如我们指定了Cmax的值为4,5,6,那么我们就要计算3次从[3,Cmax]的SD指数。最后我们通过比较SD的大小，SD最小时所对应的聚类个数就是我们要寻找的。下图以iris数据集为例，描述了iris数据集在聚类后Cmax不同情况下SD算法评价结果，每一条线对应于一定的Cmax下的结果:图5-7iris数据集SD算法测试结果从图所反映的情况来看，在c=3时，SD的值最小，即在此时聚类的平均散布性和总体分离性出在最佳的平衡位置。它与数据集的划分数是一致的，但是仅仅通过这一个数据集是不能够说明问题的，我们还需要对其他的数据集进行测试，下表为其他数据集的SD算法测试情况:表5-3不同数据集SD算法测试结果数据集iriswineglasszoo原始划分个数3367SD最小值2.870.00019.951.724对应划分数目3863从表5-3反映的情况来看，除了iris数据集的评判结果所得到的最优划分数与原始划分数目一致外，其余数据集都没有达到一致。其实，这个结果应该是可以预料的，因为SD算法并没有涉及事先划分的相关概念，它是针对聚类后结果的自然属性来评判的，应此我们得到的最优划分数目也不一定与原有划分数目一直。同时，也从侧面说明一个问题，也就是说如果基于此种评判方法而言我们原有的划分方法并不好。5.4.3小结通过SD算法，我们从聚类后结果的自然属性出发，以聚类平均散布性Scat和聚类总体分离性Dis作为综合评判标准，SD最小值时所对应的划分个数就是我们所要寻找的最佳划分数目，我们可以发现SD的值是一个大于0的数，并没有像前面的算法那样被限定在[0,1]区间。实际上，SD的评价结果也是受聚类结果即我们所采用的聚类算法的影响，这种影响就敲好体现在不同数据集的SD值得差异性上，或许某些数据集我们并不适合用k-means进行聚类，这样的聚类结果对SD算法本身而言就有一定的缺陷。当然，尽管如此，但是，我们所关心的是通过该算法找出一个合适的划分数，而这个划分数就恰好是SD最小时所对应的聚类个数。5.5Ocq算法测试5.5.1程序运行情况图5-8为S语言编写的Ocq算法程序在S-PLUS下的运行情况:图5-8Ocq算法程序运行结果5.5.2算法测试结果Ocq算法是用聚类结果的自然属性来评价聚类内的同一性和聚类间的分离性，它与SD同属相对评价法范畴，因此其算法思想也有相似之处，Ocq的值所反映的是聚类密集性Cmp和聚类临近性Prox的平衡程度，它的值受到平衡因子ξ的影响，值越大，说明两者的整体平衡效果也就越好，即聚类内的密度和聚类间的临近性出在一个最合适的位置。下图以iris数据集为例,它是在ξ=0.5，即我们认为聚类密集性和聚类临近性这两种评价具有相等的权值时所得到的Ocq值。图5-9iris数据集Ocq算法测试结果从图5-9中所反映出的数据，我们发现综合质量最大时所对应的划分数目与原始划分数目也是毫无关联，而Ocq的值的范围是处在[0,1]之间的，这一点从它的定义也是可以预知的。实际上，从该表所得到划分数目并不能说是最优划分数目，因为Ocq的值受到ξ的影响。因此，我们还需要对其他ξ值对应的Ocq值做对比统计，以及对其他数据集进行测试然后看是否能从中找出我们需要的最优划分数目。下图就从其他数据集在ξ的不同值下的Ocq值做出了统计从中我们不难发现对数据集的评价结果的值Ocq确实是受到了ξ的影响，ξ不同我们所得到的对于划分数目也会有所不同，因此，Ocq算法是一个建立在人为指定平衡因子基础上的评价算法，我们所要寻找的最优划分数目与我们所设定的ξ的值有关，当我们认为聚类密集性和聚类临近性具有相等的权值时，我们得到的Ocq最大值所对应的划分个数c仅仅是在该情况下的最优值，不同的ξ会导致不同的最好划分数目。当然，如果我们综合所有ξ的值来考虑Ocq最大时所对应的划分数目，那么iris数据集、wine数据集、glass数据集、zoo数据集所对应的划分数就应该是3，9，10，6。从该表中我们也可以发现Ocq的值确实是在[0,1]区间，而且Ocq算法与数据集的预先划分结构也是毫无关系的。5.5.3小结Ocq算法是基于对聚类内和聚类间的数据点分布来评判的，它与数据点的预先制定结构没有关系，Ocq的值是平衡了聚类密集性Cmp和聚类临近性Prox而得到的。同时它受到权衡Cmp与Prox的因子ξ大小的影响，对某一特定ξ下的Ocq而言，Ocq最大值所对应的划分个数就是对我们有用的聚类适合划分数目。但是，这个结果并能说明它就是最佳聚类划分数目，不同ξ会产生不同的最大Ocq值所对应的划分数。Ocq评判算法是建立在人为指定基础上的，因此如何找到一个合适的ξ