数据仓库与数据挖掘课件_第十章_模型选择与模型评估

第10章 模型选择与 模型评估 数据挖掘与知识发现(第2版) 吉林大学计算机科学与技术学院 李雄飞 1 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型选择与模型评估 生成若干数据模型后，需要依据模型对数据的解释能力 或预测能力，确定一个最优的模型。本章介绍模型选择和 模型评估方法。主要讨论启发式方法，数据重用技术，以 及模型选择和验证的解析方法，具体包括： 模型的过拟合 没有天生优越的分类器 模型、模型选择和模型评估 自助法 Occam剃刀 最小描述长度准则 信息准则 比较分类器的方法 聚类评估 2 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型的过拟合 分类模型的误差有两类： 训练误差（training error）：也称为再代入误差（resubstitution error），是训练样本上的误分类比例。 泛化误差（generalization error）：是模型在未知样本上的期望误差 。 一个好的分类模型应该同时具有低训练误差和低泛化误差。 如果分类模型A拟合训练数据较好，但与另一个拟合训练数据相对较 差的分类模型B相比，模型A具有更高的泛化误差，则称模型A过拟合 。 例，以二维数据为例解释过拟合。 在图10.1二维数据集合中，数据点属于两类： 标记为“o”的数据由三个独立的正态分布产生，1200个。 标记为“+”的数据由均匀分布产生。1800个。 随机选取30%用于训练决策树，其余70%用于测试。为说明过拟合 现象，对完全生长的决策树进行不同程度的剪枝。图10.2显示了不同 节点数的决策树的训练误差和测试误差。 3 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型的过拟合 模型拟合不足(model underfitting):训练误差和测试误差都较大。 决策树生长不充分 模型过拟合(model overfitting):训练误差继续降低，测试误差增大。 决策树的规模过于复杂 4 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型的过拟合 图10.3给出了两颗具有不同规模的决策树，节点少的决策树具有较 高训练误差，但具有较低的测试误差，而节点多的决策树出现过拟合 。 导致过拟合的因素： 存在噪声数据 缺少典型样本 5 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 没有天生优越的分类器 考虑两类问题： 设训练集D由模式xi以及与之相应的类别标签yi=，i=1，n， yi由待学习的未知目标函数F(x)给出，即yi =F(xi)。 多数情况下，F(x)都含有随机成分，相同的输入被分到不同的类别 中，导致非零贝叶斯错误率。 令H表示假设集或待学习的可能参数集合。 h(x)H是特定的假设，如，神经网络中的量化权值、泛函模型中的 参数或者树中的决策集合等等。 设P(h)表示算法训练后产生假设h的先验概率。 P(hD)表示在数据集D上训练后产生假设h的概率。 对于确定性学习算法，P(hD)在单一假设h外，处处为零。 最近邻和决策树 对于随机算法，P(hD)可能是一个分布。 神经网络 令E表示0-1损失函数或其他损失函数的误差。 6 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 没有天生优越的分类器 评判学习算法的泛化性能：关于所有可能目标求和的误差期望值。 显然，固定训练集D上期望误差率，与以输入的概率P(x)为权、学习算 法P(hD)与真实后验P(FD)“匹配”的情况的加权和有关。 如果没有关于P(FD)的先验知识，不能检验任何特定的学习算法 P(hD)，包括其泛化性能。 当真实函数是F(x)，第k个候选学习算法的概率是Pk(h(x)D)时，非训 练集的期望误差率是： 7 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 没有天生优越的分类器 定理10.1：（没有免费的午餐，No free lunch，NFL）任给两个学习 算法P1(hD)和P2(hD)，下列命题正确，且与样本分布P(x)及训练点个 数n无关： (1) 对所有目标函数F求平均，有1EF,n-2EF,n=0； (2) 任意固定的训练集D，对所有F求平均，有1EF,D-2EF,D=0； (3) 对所有先验P(F)求平均，有1En-2En=0； (4) 任意固定的训练集D，对所有先验P(F)求平均，有1ED-2ED=0. NFL定理表明： 使用哪种算法完成分类任务，取决于问题本质特征，而不是数据挖掘者 对哪个算法更熟悉。 研究和试图说明某种算法具有天生的优越性是没有意义的。 当面对一个新的分类问题时： (1)应该关注事务的本质 先验信息、数据分布、训练样本数量、代价或奖励函数等。 (2)根据以上关于问题的“信息”，选择适当的分类算法。 8 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 没有天生优越的分类器 例10.1：二值数据的NFL 假设输入矢量由三个二值特征构成，给定目标函数F(x)，如表10.1 。 假设学习算法1认为每个模式除非被训练过，否则就属于类1； 学习算法2认为每个模式除非被训练过，否则就属于类2。 当训练数据集D含有三个样本时，两个算法分别给出假设h1和h2。 计算非训练误差率为1EF,D=0.4和2EF,D=0.6. 9 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 没有天生优越的分类器 假定没有关于F(x)的先验信息。所有目标函数平等。要全面地比较算 法，必须对所有与训练数据一致的目标函数求平均。 与训练数据集D中三个模式一致的不同目标函数一共有25个，确实存 在另一个目标函数G，其关于非训练数据的输出是表中F(x)的取反，也 即G(x)=(1,-1,1,1,-1,1,-1,-1), 而1EG,D=0.6和2EG,D=0.4， 也即F和G使得算法1和算法2 的性能相反，从而对定理10.1的(2)中公 式的贡献相抵消。 任何一个二值分类学习算法 如果不在某些问题上付出相等的负的性能代价，则不可能在所关心的 问题上得到等量的正的性能。 如果没有限定一定要使用某种特定的算法解决问题，那么，我们所能 做的就是在期望遇到的问题和不期望遇到的问题之间做一些性能折中 。 学习算法必须做一些与问题相关的“假设”，也就是偏置（bias）。 即使是非常流行而且理论坚实的算法，也会在学习算法与问题后验不“ 匹配”的情况下表现不佳。 仅仅熟悉有限的几种分类算法，并不能解决所有分类问题。 10 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型、模型选择和模型评估 模型可以定义为对输入输出之间联系的一种描述。这种描述可以用不 同方式形式化。 例如分类器、神经网络、决策树、产生式规则、数学方程等。 模型、分类器和估计子基本上含义相同。 分类器是用于分类目的的数据模型：给定新的输入，分类器依据训练 结果将其划分到某一个类中。 估计子来自于统计学，定义为样本值的函数，是计算参数的一种方法 。 估计模型时所必需的独立的信息项的数目称为模型的自由度。 选择简洁模型，在若干表现良好的模型中，选择参数数目少的模型。 模型误差指真实值和模型输出值之间的绝对误差或平方误差。 当由数据生成一个模型时，称之为模型拟合数据。 不仅需要检验模型的拟合优度（拟合误差），而且需要检验模型的预 测优度（预测误差）。 在生成的若干模型中择优的过程称为模型选择(model selection)。 11 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型、模型选择和模型评估 构建数据模型的方法有三类： 无监督学习 监督学习 半监督学习 模型评估方法： (1)根据可用数据的种类以及能否计算误差，对模型评估技术进行分类。根据方 法内在本质划分模型评估技术： 数据重用技术，或称为重采样技术。广泛应用于评估监督学习模型。 简单划分 交叉验证 自助法 启发式方法方法：不是形式化的，是最简单、常使用的方法。 简洁模型 奥坎姆剃刀 解析方法：是形式化的，但不够实用。 最小描述长度 Aikake信息准则 贝叶斯信息准则 兴趣度度量方法：模拟数据用户所使用的模型评估过程，这类方法较新且较流行。 (2)按照模型选择的方法。 评估拟合优度的方法 评估预测优度的方法。 12 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型、模型选择和模型评估 偏倚与方差 偏倚度量模型与问题“匹配”的准确度，高偏倚意味着更差的匹配 ； 方差度量“匹配”的精确度，高方差意味着更弱匹配。 对于给定的均方误差，偏倚和方差之间存在“守恒律”的形式。假如有 先验信息，可以创建出具有不同均方误差的分类器。 评估模型的拟合优度和预测优度，必须首先计算误差。 误差分为两部分：偏倚和方差。 (1)偏倚(Bias)是通过增加样本容量也无法降低的误差。偏倚也称系统误 差，包括： 测量误差：无法消除的试验误差 样本误差：样本可能没有正确地产生于分布，从而没有正确地描述数据 。 通过计算某些参数的估计值的数学期望和真实值之差得出偏倚： 13 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型、模型选择和模型评估 均方误差（mean square error，MSE） 其中方差为总体方差的无偏估计 或总体方差的有偏估计 (2)方差：由给定有限样本导致的附加误差。 有偏估计量具有非零偏倚 无偏估计具有零偏倚。 最小化MSE可以得到具有恰当偏倚和方差的模型。 图10.5中y轴表示偏倚/方差/MSE的值，x轴表示估计子/模型的复杂度/ 数据规模。 14 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 模型、模型选择和模型评估 拟合优度和预测优度，也即训练误差和测试误差。 过度训练通常意味着数据过拟合。 当将过度训练的神经网络应用于测试数据时，其预测/泛化误差通常较 大。 15 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 简单划分和交叉验证 简单划分： 为评估模型，将可用数据简单地划分为两部分：训练数据和测试数 据，训练数据用于拟合模型，测试数据用于评估模型的预测优度。 随机地通过一个经验公式，抽取约1/2或2/3数据用于训练。 特点：高偏倚、低方差。 交叉验证： 令n表示训练数据集中数据点的数目，将全部数据分为k个等规模 的子集，使用k-1个部分进行训练，余下的那一部分用于测试，并计算 预测误差(预测优度)。重复这一过程k次，得到k次结果的平均值。 常用的是10折交叉验证，数据集被分为10个子集，最终预测误差 为10次预测误差的平均值。 特点:低偏倚和高方差。 简单划分用于数据集规模较大的情况。 交叉验证用于数据集较小且难于处理的情况 。 16 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 自助法(Bootstrap ) 自助法：用于给出模型误差的非参数估计。 为计算估计子的置信区间，从总体中按等规模抽取B次采样，每次采 样包含n个样本。 (1)由总体有放回地抽取容量为n的B个采样，称得到的每一个采样为自 助法采样。 (2)对每一个自助法采样调整现有模型，评估各自助法采样的拟合优度( 误差)，通过平均B个自助法采样上的相应统计量的估计值，可以计算 出偏倚和方差的自助法估计： 为利用自助法计算预测优度，将自助法抽样作为训练集，原始数据 集作为测试集。用模型拟合所有自助法抽样，计算在原始数据上的预 测误差。 17 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 Occam剃刀 在给定论域，观测现象的最简单解释（模型）是最可能正确的。 给定若干模型，应该选择更“紧凑”的模型。 由更小数目规则构成 规则的平均长度比其他模型中的规则平均长度更短 许多机器学习算法使用了Occam剃刀启发式方法。 问题： 已经用其生成模型，但还要用其进行模型选择。 在某些情况下，Occam剃刀可能是完全错误的。 无论是“避免过拟合”技术，还是最小描述长度原理，都没有固有的优 越性，这类技术对分类器的形式或参数施加一种“偏爱”或“偏置”（ bias）。 这些技术仅在其恰好与问题“匹配”时才是有益的。 决定因素是学习算法与问题的“匹配”，而不是“避免过拟合”本身。 18 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 最小描述长度准则 Rissanen给出最小描述长度原理（Minimum Description Length Principle，MDL） 。 MDL：如果系统能够用输入和与之相应的输出数据定义，则最差情形( 最长）下，可以使用全部数据描述这一系统（数据的最长/最小的压缩 模型)。 MDL原理表明，理论（模型/假设）的复杂度可以通过理论本身的编码 位数与使用该理论表达数据的编码位数之和度量。 给定一组模型，选择最小化和： L(h,D)=L(M)+L(D|M) 的模型。即， 其中L(M)为描述模型的长度（位数），L(D|M)为使用模型M编码描述数 据的长度。 用贝叶斯的观点解释最小描述长度原理： 最优假设h*是使得 后验概率最大的那个假设。 19 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 最小描述长度准则 香农最优编码理论： 串x可以-log2P(x)为代价下界进行传输或表示。 关于过拟合问题： 具有较大L(M)值的复杂模型很容易构建，该模型具有较小的 L(D|M)值，过拟合数据。 具有较小L(M)值的简单模型也很容易构建，该模型具有较大的 L(D|M)值，拟合数据不足。 假定生成了两个解释/拟合数据一样好的两个不同模型， MDL原理提示应选择较简单的模型。 相互联系： MDL原理和贝叶斯方法之间的联系。 MDL原理可以看成Occam剃刀的形式化。 20 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 Akaike信息准则 Akaike信息准则（Akaike Information Criterion，AIC）和 Bayesian信息准则（Bayesian Information Criterion，BIC）是两 种统计学度量，用于在使用不同参数个数的模型间进行模型选择，这 些模型彼此相关。 要估计预测误差E，训练误差TrE易于计算，但是，由于测试向量不一 定与训练向量一致，TrE通常过于乐观，作为修正，需要估计乐观的 误差Eop，并计算样本内误差（in-sample error）如下： E=TrE+Eop AIC定义如下： (10.14) 其中logL是极大对数似然，即 (10.15) P(Y)是包含真实密度的密度族， 是的极大似然估计，d是模型 参数个数。 21 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 Akaike信息准则 如果生成了一族可以调整参数的模型，则AIC重写为 (10.16) 方差var2定义为 (10.17) AIC()是测试误差曲线的估计，选择最小化该函数的模型 为最佳模型。 22 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 Bayesian信息准则 BIC定义： (10.18) 对于方差为var2的高斯分布，BIC可以写为： (10.19) 选择最小化BIC的模型为最优模型。 因为对更复杂模型加重惩罚，所以BIC偏好于简单模型。 当样本规模N趋于无穷时，BIC将选择正确的那个模型，而 AIC将选择一个过于复杂的模型。 对于有限样本，BIC将倾向于选择过于简单的模型。此时 ，使用AIC是明智的策略。 23 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 比较分类器的方法 考虑一对分类模型MA和MB。假设MA在包含30个记录的检验集上的准 确率达到85%，而MB在包含5000个记录的不同检验集上达到75%的准 确率。根据这些信息，是否可以断定MA比MB更好呢？ (1)估计准确率的置信区间 为确定置信区间，需要建立支配准确率度量的概率分布。 通过将分类任务用伯努利实验建模来推导置信区间。 预测检验记录类标号的任务可看作是二项式实验。 给定包含N个记录的检验集，令X是被模型正确预测的记录数，p是 模型真正准确率。通过把预测任务用二项式实验建模，X服从均值为 Np、方差为Np(1-p)的二项分布。 可以证明经验准确率 也是均值为p、方差为Np(1-p)的二 项分布。尽管可以用二项分布来估计acc的置信区间，但是当N充分大 时，通常用正态分布来近似。根据推导出acc的置信区间为： 24 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 比较分类器的方法 其中Z/2和Z1-/2分别是在置信水平1-下由标准正态分布得到的上界和 下界。 因为标准正态分布关于Z=0对称，于是有Z/2=Z1-/2。重新整理不等式 ，得到p的置信区间如下： 下表给出了在不同置信水平下Z/2的值： 25 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 比较分类器的方法 例：考虑一个模型，它在100个检验记录上具有80%的准确率。在 95%的置信水平下，模型的真实准确率的置信区间是什么？ 根据上面的表格，95%的置信水平对应于Z/2=1.96。将其带入公式得 到置信区间为（71.1%，86.7%）。下表给出了随着记录数N的增大所 产生的置信区间。 注意，随着N的增大，置信区间变得更加紧凑。 26 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 比较分类器的方法 (2)比较两个模型的性能 考虑模型M1和M2，在两个独立的检验集D1和D2上进行评估，令n1、 n2分别表示D1和D2中的记录数。另外，假设M1在D1上的错误率为e1， M2在D2上错误率为e2。目标是检验e1与e2 的观察差是否是统计显著的 。 假设n1和n2都充分大，e1和e2可以使用正态分布来近似。 如果用d= e1-e2表示错误率的观测差，则d服从均值为dt、方差 为的正 态分布。d的方差为： 其中 和 是错误率的方差。最后，在置信水平1-下，可以 证明实际差dt的置信区间由下式给出： 27 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 比较分类器的方法 例：模型MA在N1=30个检验记录上的错误率e1=0.15，而 MB在N2=5000个检验记录上的错误率e1=0.25。错误率的 观察差d=|0.15-0.25|=0.1。在此例中，使用双侧检验来检 查dt=0还是dt0。错误率观察差的估计方差计算如下： 或 。把该值代入 ，得到在95%的置信 水平下，dt的置信区间如下： 由于该区间包含0，可以断言在95%的置信水平下，该观 察差不是统计显著的。 28 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 比较两种分类法的性能 假设用k折交叉验证比较两类分类算法的性能。 把数据集D划分为k个大小相等的部分。使用每类分类算法，在k-1 份数据上构建模型，并在剩余的划分块上进行检验，重复这个步骤k次 ，每次使用不同的划分进行检验。 令Mij表示分类技术Li在第j次迭代产生的模型，每对模型M1j和M2j在相 同的划分j上进行检验。分别用e1j和e2j表示错误率，在第j折上的错误 率之差可以记作dj=e1j-e2j。如果k充分大，则dj服从于均值为 (错误 率的真实差)、方差为 的正态分布。 观察差的总方差用下式估计： 其中， 是平均差。用t分布计算 的置信区间： 系数t(1-),k-1可以通过两个参数（置信水平1-和自由度k-1）查概率 表得到。 29 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 比较两种分类法的性能 例：假设两个分类算法产生的模型的准确率估计差的均值等于0.05， 标准差等于0.002。如果使用30折交叉验证估计准确率，则在95%置信 水平下，真实准确率差为： 因为置信区间不包括0，两个分类算法的观察差是统计显著的。 30 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 由于数据集特征和输入参数值不同，不同聚类算法的表现也不同。 若聚类算法参数设置得不合适，可能会得出对原始数据集拟合得不好 的划分模式，从而导致错误的决策。 图10.7 (a)由3个簇组成的数据集 (b)给定簇个数为4时K-均值算法的结果 聚类评估：令C为X上应用聚类算法所导致的聚类结构。 外部准则：按照独立抽取结构来评价C，它在X上引入一个预测，来影 响对X的聚类结构的认识。可以用来测量可用数据符合指定结构的程 度。 内部准则：按包含X向量本身的数据来评价C，例如相似矩阵。 相对准则：通过与其它聚类结构比较来评价C，这种聚类结构应用同 样的聚类算法，但不同的参数值，或X的其它聚类算法。 31 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 假设检验 令H0和H1分别是原假设和备选假设，H1:0，H0:=0。令 为对应 检验统计量q的显著性水平为的置信区间，1为在假设H1下的所有 可能取值。该检验的能量函数定义为： 对于指定的1，W()是可选下的检验能量。 W()是参数向量值为时q处于临界区域的可能性。这是H0被拒绝时做 出正确决定的可能性。 能量函数可用于比较两个不同的统计检验。在可选假设下能量大的检 验总是首选的。 两类与统计检验相关的错误： 假设H0为真。如果 ，H0将被拒绝。出现错误的概率是。当它 为真并接受H0的可能性是1-。 假设H0为假。如果 ，H0将被接受。出现错误的概率是1-W() ，它依赖于的值。 最终决定拒绝还是接受H0，部分依赖于前述问题，也依赖于其它 因素，比如错误决定的代价。 32 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 假设H0下统计量q的概率密度函数(probability density function, pdf) 有一个唯一的最大值，区域是一条半直线，或者是两条半直线。见图 10.8。 图10.8 (a)双尾指数的置信区间, (b)右尾指数的置信区间, (c)左尾指数的置信区 间 其中是零假设H0下q的临界值 33 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 在实践中，很难获得给定假设下统计量q的pdf的准确形状。 用仿真技术评价pdf的方法： (1) Monte Carlo技术 使用计算机生成足够数量的人造数据来仿真这个过程。对于每一 个人造数据集Xi（即r），计算已定义的指数qi（即q）。基于每个数 据集Xi的qi值，都可以创建一个散点图。这个散点图是该指数的概率 密度函数的近似。 假设已经使用指数q的r个值生成了散点图。 右尾检验：如果数据集的q值大于(小于)人造数据集Xi中(1-)r个qi值 ，则拒绝（接受）H0。 左尾检验：如果数据集的q值小于(大于)人造数据集Xi中r个qi值，则 拒绝（接受）H0。 双尾检验：如果数据集的q值大于人造数据集Xi中(/2)r个qi值，且小 于(1-/2)r个qi值，则拒绝（接受）H0。 34 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 在实践中，很难获得pdf的准确形状。一般采用仿真技术评价pdf： (1) Monte Carlo技术 使用计算机生成足够数量的人造数据来仿真这个过程。对于每一 个人造数据集Xi（即r），计算已定义的指数qi（即q）。基于每个数 据集Xi的qi值，都可以创建一个散点图。这个散点图是该指数的概率 密度函数的近似。 假设已经使用指数q的r个值生成了散点图。 右尾检验：如果数据集的q值大于(小于)人造数据集Xi中(1-)r个qi值 ，则拒绝（接受）H0。 左尾检验：如果数据集的q值小于(大于)人造数据集Xi中r个qi值，则 拒绝（接受）H0。 双尾检验：如果数据集的q值大于人造数据集Xi中(/2)r个qi值，且小 于(1-/2)r个qi值，则拒绝（接受）H0。 (2) 自助法（Bootstrap） 自助法建立一种可选方法来应对数据量有限的问题。 思想：根据一个未知参数来确定未知pdf的参数。 通过对X取样，创建几个伪造的数据集X1, . , Xr。用替代的方法应对 数据量有限的问题，以提高对pdf参数估计的精确度。 35 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 （一）外部准则 与依据直觉创建的数据独立划分P进行比较。 比较相似矩阵Pm与划分P。 1、聚类结构C与划分P的比较 考虑C=C1 . Cm是数据集X的一个聚类结构，PP1 . Ps是数 据的一个给定划分。数据集合的点对（Xv，Xu）： SS：属于C的同一个簇，且属于划分P的同一个组。 SD：属于C的同一个簇，且属于P不同组。 DS：属于C的不同簇，且属于划分P的同一个组。 DD：属于C的不同簇，且属于划分P的不同组。 现假设a、b、c、d分别是SS、SD、DS、DD点对的数目，那么 a+b+c+d=M是数据集中所有点对的最大数目，即MN（N-1）/2，其 中N是数据集中点的总数。 一组测量C和P的相似度的指数： Rand统计量：R=(a+d)/M Jaccard系数：J=a/(a+b+c) 以上两个指数得到0到1之间的值，当m=s时取到最大值。 36 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 Folkes and Mallows指数： (10.32) 其中m1=(a+b)，m2=(a+c)。 上述三个指数，取值越大，则C和P的相似度越大。 Huberts 统计量： (10.33) 该指数值越大，X和Y的相似度越大。 正态统计量： (10.34) 其中X(i,j)和Y(i,j)分别是要比较的矩阵X和Y的i行j列元素，而x, y, x, y分别是X和Y的均值和方差。该指数的取值介于-1到1之间。 37 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 计算这些指数的概率密度函数的蒙特卡罗技术： For i=1 to r 生成：在X的域上生成具有N个向量（点）的数据集Xi， 从而生成的向量与数据集X具有相同维数。 分配：把Xi的每个向量yj,i按照划分P，分配给数据集的第j个组 xj。 运行：对每个Xi，使用相同的聚类算法，生成结构C。 令Ci为所生成的聚类结构。 计算：为P和Ci计算给定指数q的q(Ci)值 End For 创建r个有效性指数值q(Ci)的散点图(在for循环中计算)。 在绘出给定统计指数的概率密度函数的近似图形之后，比较统计指 数值q和q(Ci)的值qi。 这里的q指数可以使用指数R、J、FM、。 38 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 2、比较相似矩阵P 与划分P 可以把划分P看成一个映射： g : X 1，.，n. 假设矩阵 (10.35) 可以使用相似矩阵P和矩阵Y计算(或正态)统计量。指数值可以 指示两个矩阵的相似度。 评估过程仍然使用蒙特卡罗技术。在“生成”阶段，为每个数据集Xi生 成相应的映射gi。在“计算”阶段，为了找到i相关的统计量指数，为每 个Xi计算矩阵Yi。 39 数据挖掘与知识发现(第2版) 李雄飞等2003,2010 聚类评估 （二）内部准则 内部准则仅使用数据的固有信息，证实由一个聚类算法产生的簇结 构是否适合数据。若数据用相似矩阵表示，考虑两种情况：(a)聚类结 构是聚类的一个层次；(b)聚类结构中包含单个簇。 1、聚类层次的验证 由层次聚类算法产生的系统树图可以由各自的cophenetic矩阵Pc 来表示。定义统计指数，来测量由特定层次聚类算法产生的 cophenetic矩阵Pc与X的相似矩阵P的一致程度。因为矩阵是对称的 且斜对角元素和为0，所以仅考虑Pc与P的斜对角上部分的 个元素。令dij和cij分别为P与Pc上的（i, j）元素。 第一个指数是CPCC（cophenetic correlation coefficient），用于 当矩阵是所测距离或比率时，测量Pc与P之间的相关性。 另一个统计指数是 统计量，适合于