对单数据库和多数据库中挖掘模式的评价
开篇：润墨网以专业的文秘视角，为您筛选了一篇对单数据库和多数据库中挖掘模式的评价范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：文章从客观和主观两方面分别分析了现有的一些对数据挖掘模式的评价方法，并提出对多数据库中模式评价的两种客观性度量。
关键词：数据挖掘；数据库；多数据库；模式评价
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)19-30021-02
Data Mining Pattern Valuation in Multi-database and Single-database
MI Jie, LI Ke
(Henan Institute of Engineering, Zhengzhou 450007, China)
Abstract: Some measures of pattern evaluation are analyzed from both the objective and subjective point of view respectively. Also two objective measures to evaluate patterns in multi-database are proposed.
Key words: data mining; database; multi-database; pattern evaluation
1 引言
数据挖掘(DM)，又称为数据库中的知识发现(KDD)。根据目前比较公认、完整、深刻和全面的数据挖掘定义――德国Fayyadz等人在1996年发表的论文《From Data Mining to Knowledge Discovery》中提出：数据挖掘是从大量的数据中提取出有效的、新颖的、有潜在价值的、可信的、并能最终被人理解的模式的非平凡的处理过程。从该定义可以看出，数据挖掘得到的模式，评价其度量标准主要包括有效性、新颖性、潜在有用性和最终可理解性[1]。对它们进行综合度量的标准称为模式或规则的感兴趣度，它分为客观感兴趣度和主观感兴趣度。前者的主要根据是模式或规则的形式和数据库中的数据，属于数据驱动；而后者还要考虑用户的参与等人为因素的影响，属于用户驱动。在评价过程中应该综合使用这两种度量标准，比较合理的方法是首先用客观感兴趣度作为第一级过滤器，选出潜在感兴趣的模式，然后再用主观感兴趣度来对它们进行第二级筛选，得到用户真正感兴趣的知识。
2.1 客观评价
目前，感兴趣度的研究主要针对规则的客观感兴趣度[2]，客观度量是对用户兴趣的估计。有趣性的客观评价是指规则的有趣性是由规则的具体结构和在数据挖掘过程中所依赖的数据决定的，这种方法主要是在这些规则上应用统计学方法，用定量的数值来判定规则的有趣性，从而避免了人为的主观意见，因此从这个意义上讲，规则有趣性的客观评价是可靠的、有说服力的。
一般的，影响规则感兴趣度的数据方面的因素共有三个（假设规则为A=>B）：
(1)覆盖度(Coverage)：指前件A出现的概率P(A)；
(2)完全性（Completeness）：指两者（A与B）同时出现的概率与B出现的概率之比，即P P(A∧B)/P(B)；
(3)可信度（Confidence Factor）：指两者（A与B）同时出现的概率与A出现的概率之比，即P(A∧B)/P(A)。
Piatetsky-Shapiro提出的规则感兴趣性RI(Rule Interestingness)度量的三个准则为：
(1)如果P(A∧B)=P(A)P(B)，那么RI=0；
(2)当其它参数固定时，RI随着P(A∧B)的增加单调递增；
(3)当其它参数固定时，RI随着P(A)或P(B)的增加单调递减。
Magor和Mangano提出了第四个准则：
(4)当给定的可信度大于允许的可信度时，RI随着P(A)的增加单调递增。
另一个通用的评价规则质量的是规则简洁度。它是用来衡量规则的最终可理解程度的指标。它表现在两个方面：一方面是在规则项的个数上，如果规则项数很多将不利于对这条规则的理解。因此，规则的项数是一个衡量规则简洁性的逆向指标，即规则的项数越多，规则的简洁性越差；另一方面是在规则所包含的抽象层次上，层次越高，它对数据的解释能力越强，也越容易理解；相反则它对数据的解释能力越差，因此也越不容易理解。
Symth利用如下函数对规则A=>B的简洁性和包含的信息量进行综合度量，考虑了规则的前件A和后件B的概率分布的相似程度，以及用A的出现概率作为前件的简洁性的度量，但是，忽略了P(B)的作用。
■
以关联规则为例，支持度和可信度度量是评价关联规则的两个常用客观性指标，支持度度量反映了规则的实用性，而可信度度量反映了规则的有效性。很多传统的关联规则挖掘算法就是基于这种模型来进行关联规则挖掘的，也就是找出所有的强关联规则。但是强关联规则并不一定是有趣的，有时甚至是有错误的。
因此，有人提出了各种新的规则评价标准，并将其加入到挖掘算法中，对关联规则的产生加以限制和约束，以得到更加新颖、更加有效的关联规则。有人提出了兴趣度（lift）度量方法。对于一条规则A=>B，兴趣度定义为：
■
兴趣度反映了交易A和交易B之间的关系，当兴趣度等于1时，表明两项交易同时出现属于概率事件，不具有特别意义，即A和B是独立的，称该规则为不相关规则；兴趣度小于1时表明其中一个项集的出现降低了另一个项集出现的可能性，称为负相关规则；兴趣度大于1时表明一个项集的出现会增加另一个项集出现的可能性，称为正相关规则。一般情况下，挖掘出正相关的关联规则更具现实意义，但有时负相关规则的出现也会为用户带来新的知识。
我们可以将兴趣度同支持度和可信度一起作为规则的客观度量标准，以提高所挖掘规则的有效性。
2.2 主观评价
规则有趣性的客观评价只是基于数据本身的结构来展开的[3]，规则的产生完全基于事实数据，并没有考虑规则之间的联系和用户对规则的认同程度。但是一个规则是否有趣最终要取决于用户的感觉。只有用户可以决定规则的有效性和可行性。我们应该将用户的需求和挖掘系统结合起来才能挖掘出更加有效的规则。因此，判断规则的有趣性必须考虑到主观层面上的意义。仅根据客观感兴趣度选取用户所关注的模式，难以获得用户真正感兴趣的模式，还需要人为的参与。从主观的角度讲，能使用户对发现的模式产生兴趣的原因主要有两个：意外性和实用性。
这两者是紧密相关的。以关联规则为例，有趣性的主观评价是指关联规则的有趣性不仅由规则的具体结构和在数据挖掘过程所依赖的数据决定，而还应与使用规则的用户感觉有关。而高支持度和高可信度的规则对用户来讲并不一定有意义，从用户的主观角度看，规则的非预期性(指所挖掘的规则对用户来讲是超乎想象的、没曾见过的)和可行性（指依据所挖掘出来的规则进行决策）应该是用户更感兴趣的。
与主观评价有关的指标有新颖度、用户感兴趣度等，本文认为，规则的新颖度是其中一个很重要的评价指标。
模式的新颖性主要表现在发现模式与知识库中模式的差异程度上。对模式的新颖性评价是针对于原有的模式而言的，这可能会包括两个部分的内容：
首先，所挖掘出来的模式与已有的模式有差异，产生这种情况的原因可能是：
(1)所挖掘的数据对象有问题，则该模式是错误的；
(2)新挖掘出来的模式是对原有模式的一个补充或具有更高的抽象层次；
(3)新挖掘出来的模式了原有的模式。这说明原有的模式可能失效，应删除原有的模式。
其次，所挖掘出来的模式与用户的期望模式有差异，用户在进行模式挖掘的过程中，往往期望得到一些自己感兴趣的模式。然而，实际的挖掘过程中可能会出现用户意想不到的新模式。这些可能有助于用户修正原有的期望模式，同时可以通过对新模式的进一步分析，从而得到更具新颖性的。
用户对规则是否感兴趣的重要指标是新颖性，它是针对于原有知识而言的，这些知识包括两个部分：一是以往得到的准确性很高的规则，与当前所得到的规则相悖；二是与用户所期望的知识相悖。因此，衡量新颖性主要是从形式上进行的，即分别用与规则的前件和后件的相悖程度来衡量，也可以用与原有知识的相悖的项数来衡量。我们可以通过模板匹配的方法来评价模式的新颖度，首先由用户给出他所期望的模式作为模板，然后我们将挖掘得到的模式与模板对前件和后件分别进行匹配。匹配的结果可以将挖掘得到的模式分成四类：前件后件都匹配、前件匹配后件不匹配、后件匹配前件不匹配及前件后件都不匹配。前件后件都匹配的模式与用户的期望一致，达到了用户预想的目的，但是它对用户的期望不具有新颖性。其他三类模式均与用户的期望有差异，也即具有新颖性，这时用户便可以对这些模式进行更深层次的分析，从而发现问题或作出更加有利的决策。
目前，专门针对多数据库中的模式的评价尚不多见。本文认为从主观方面，对多数据库中的模式的评价与单数据库中的模式评价方法类似，但从客观方面应有不同，因为多数据库在数据方面与单数据库有着很大差别，需要考虑许多单数据库不需要考虑的因素，比如说应考虑多数据库中每个数据库的权重等。对于多数据库中模式的客观度量主要考虑以下两方面：
3.1 模式的支持度
假设模式为A，我们定义模式A的支持度为多数据库中模式A的支持程度，记为support(A)，计算方法如下：
■
其中，num(A)表示多数据库中支持模式A的数据库个数，n为总的数据库个数。
模式的支持度反映了模式在多数据库中的实用性或普遍性。支持模式的数据库个数越多，则模式的支持度也越高，该模式在多数据库中就越普遍，也即实用性也越高。
3.2 模式的重要度
我们定义多数据库中模式的重要度为模式对整个多数据库系统的重要程度，记为importance(A)。 计算方法如下：
其中，k为支持模式A的数据库个数，即num(A)；Wi为支持模式A的第i个数据库的权重，这里我们对如何为数据库赋权值不作讨论，只在我们假设多数据库中各个数据库具有相同地位时将其权重默认为1；sup(Ai)为模式A在支持它的第i个数据库中的支持度；min supi为支持模式A的第i个数据库中用户给定的最小支持度阈值；max supi为支持模式A的第i个数据库中所有模式的最大支持度。
重要度的计算中我们主要考虑到三个因素：模式的支持度、支持模式的数据库的权重及模式在支持它的数据库中的相对支持度。模式的支持度反映了模式的实用性或普遍性；每个数据库所在的分支对总公司的贡献是不同的，因此对不同的数据库应赋予不同的权重；每个数据库有不同的数据信息，模式在支持它的不同数据库中的支持度有着不同的标准，因此要计算模式在支持它的各个数据库中的相对支持度，即公式中的■。
模式的重要度越大，我们认为模式对整个多数据库系统越重要。
4 小结
在知识发现过程中，通过挖掘算法产生大量的模式，但是大多数用户对此并不感兴趣。如何对它们进行评价，选取出用户感兴趣的和有用的知识是至关重要的，故对知识评价的研究具有重要的意义。
现有的各种评价方法都存在一定的缺陷，目前还没有一种非常有效的评价方法能适应所有的数据或不同的用户需求。这方面的研究工作还有待我们继续进行。
参考文献：
[1] 綦艳霞,杨炳儒.KDD中知识评价的研究综述[J].计算机应用研究,2001(12):1-4.
[2] 娄兰芳,蒋志芳,田世壮.影响关联规则挖掘的有趣性因素[J].计算机工程与应用,2003(6):190-191.
[3] 苏占东,游福成,杨炳儒.关联规则的综合评价方法研究与实例验证[J].计算机应用,2004,24(10):17-20.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文