基于显露模式的对比挖掘研究及应用进展

摘 要:

对比挖掘是近年来数据挖掘领域的新热点之一。对比挖掘关注并描述不同类别和条件下，或随时间变化的知识，旨在设计能够发现刻画数据集中不同类别或条件的样本间差异的模式或模型的方法。由于对比挖掘技术能化繁为简、准确分类，在实践中得到广泛应用。显露模式的挖掘和应用是对比挖掘的重要分支。综述了显露模式的背景、基本概念和原理，分析了显露模式的挖掘方法，讨论了显露模式的扩展定义和挖掘，介绍了基于显露模式的分类器构造方法，展示了显露模式的若干实际应用，展望了基于显露模式的对比挖掘的未来研究。

关键词:

数据挖掘; 显露模式; 模式发现; 频繁项集; 分类

中图分类号:

TP311.13

文献标志码:A



Survey on emerging pattern based contrast mining and applications



DUAN Lei1, TANG Changjie1*, Guozhu DONG2, YANG Ning1, GOU Chi1



1.College of Computer Science, Sichuan University, Chengdu Sichuan 610065, China

;

2.Department of Computer Science and Engineering, Wright State University, Dayton 45435, USA

Abstract:

Contrast mining is one of fairly new hot data mining topics. Contrast mining focuses on knowledge that describes differences between classes and conditions, or describes changes over time. Contrast mining aims at developing techniques to discover patterns or models that contrast, and characterize multiple datasets associated with different classes or conditions. Contrast mining has wide applications in reality, due to its ability of simplifying problems and classifying accurately. Research on the mining and application of emerging patterns represents a major direction of contrast mining. This paper provided a survey of such issue. More specifically, after introducing the background, basic concepts and principles of emerging patterns, the paper analyzed the mining methods of emerging patterns, discussed extended definitions of emerging patterns and their mining, stated methods for constructing emerging pattern based classifiers, and illustrated applications of emerging pattern in several realworld fields. Finally, this paper gave out some topics for future research on emerging pattern based contrast mining.

Key words:

data mining; emerging pattern; pattern discovery; frequent itemset; classification



0 引言

数据项在事务数据库中出现的次数是数据统计分析和知识发现的重要技术指标。在数据挖掘中，关联规则［1］以发现频繁项集为目标，揭示在数据库大量事务中同时出现的项集——频繁模式。出现次数与事务数目的比值称为支持度。频繁模式挖掘不需要太多领域知识和专业背景,它借助计算机完成人力非常困难、甚至无法完成的统计工作，在实践中被广泛应用，为发现数据中的隐藏知识提供了有效途径。例如：商家了解商品销售的频繁模式，可预测顾客购买了某样商品后，还可能购买哪些其他商品。

项集的支持度是对该项集在当前数据库中出现频繁程度的静态的定量描述。

如果计算上再前进一小步——计算项集在两个或多个数据库中的支持度，则在概念上前进了一大步：获得了项集支持度在不同数据库中的变化和对比。有比较才有结论，有比较才有发展；由此而揭示了更多的内在规律。

如果进一步计算项集在两个或多个数据库中的支持度，则能够获得项集支持度在不同数据库中的变化和对比，从而揭示更多的内在规律。

例如：商家了解到不同季度下商品销售频繁模式的变化，即可选择在最佳时机进行促销活动，调整销售重点，保持利润的获取。

考虑项集支持度变化非常大的情况：项集在一个数据库中频繁，而在其他数据库中非频繁。例如：具有地方特色的产品总是在当地有较高的销售量。若每一个数据库包含相同类别样本的集合，那么项集支持度的变化体现了该项集在不同类别样本中出现频率的差异。当支持度的变化差异大到一定程度时，项集可作为样本类别判断的特征。例如：腹泻、呕吐、恶心既是胃肠型流感的主要症状，也是临床确诊的主要依据。

通过“对比”项集在不同数据库(集)上的支持度，可以发现其支持度变化的规律和特点，揭示更多未知知识。在日常生活中，人们常无意识地使用“对比”方法进行决策支持。例如：投资者通过对比股票指数的变化来确定投资行为；顾客通过对比产品质量，选购心仪的产品；企业人力资源部门通过对比应聘者能力，优选聘用人员。

对比挖掘(contrast mining)泛指发现在不同类别或条件下，数据集中具有“对比”特性的模式(模型)的方法。对比挖掘关注分析对象在不同类别(条件)下的变化，并利用变化信息揭示未知知识。能够产生对比的类别或条件是对比挖掘的基础，有较广的选择范围，例如：时间、空间、类别等。

理想的对比挖掘结果是具有代表性、可解释、易于计算、满足统计意义的对比模式或模型。研究表明：对比挖掘有助于对研究领域的理解，构建分类器，进行预警分析等。对比挖掘研究关注数据中的变化，它同频繁模式挖掘［1］、变化检测［2］、概念漂移［3］、梯度挖掘、基于关联规则的分类等数据挖掘研究分支有着密切的关系。

以显露模式(Emerging Pattern, EP) ［2］为主体的对比挖掘研究正逐渐成为数据挖掘研究的一个重要分支。截至目前，在此方向已有100余篇高水平论文发表。2007年，在IEEE数据挖掘国际会议ICDM上，EP概念的提出者之一Guozhu Dong作了相关专题讲座。2011年，ICDM举办了对比挖掘研究专题研讨会：ContrastDM Workshop。越来越多的研究者开始关注对比挖掘，并进行相关研究。

本文余下部分首先概述了显露模式的基本概念；然后介绍了显露模式的发现方法；其次讲述了在显露模式定义基础上对显露模式进行的扩展和基于显露模式的分类器构造方法；接着，讲述了显露模式在若干实际领域中的应用；最后总结全文，并讨论了未来的工作。

1 显露模式基本概念

例1 直观地，在判定糖尿病时:1)用以身高为自变量的函数作模式，几乎不起判定作用；2)用以年龄或体重为自变量的函数作模式，有一定判定参考作用；3)空腹血糖的度量的判定作用有限；4)餐后血糖的度量是重要判据。我们说，条件1)和3)是不显露的，而条件2)和4)是显露的。

把例1的直观感觉形式化，有下面的描述：给定数据集D和模式X，数据集D中包含模式X的样本数记为freq(X, D)。模式X在数据集D中的支持度记为Sup(X, D)，Sup(X, D)=freq(X, D) / |D|(|D|为D包含的样本数量)。

对于一个项集，当它在不同数据集中的支持度差异大于指定阈值时，称该项集为显露模式［3］。给定数据库(集) Dp和Dn，Dp∩Dn=，形式化定义显露模式有两种形式：1)给定阈值ρ，若Sup(X, Dp) /Sup(X, Dn)≥ρ(ρ > 1)，则X为显露模式；2)给定支持度阈值α、β，且α > β，若Sup(X, Dp) ≤ α，Sup(X, Dn) ≤ β，称X为显露模式。

从显露模式的定义可以看出，显露模式发现的目标是通过对比的方法，找出支持度变化大的项集。区别于关联分析仅在单个数据集中挖掘支持度大的频繁模式，显露模式是多个数据集中仅在某个数据集中具有高支持度，或多类样本集中仅在特定类别样本集中具有高支持度的项集。

特别地，当项集仅在一个数据集，或特定类别样本集中出现，而在其他数据集或样本集中支持度为0时，这样的项集称为跳跃显露模式(Jumping EP, JEP)［4］。例如：若Sup(X, Dp)>0，Sup(X, Dn)=0，Sup(X, Dp) /Sup(X, Dn)=+∞，那么称X为JEP。

2 显露模式挖掘

自从显露模式的概念提出以后，诸多显露模式挖掘算法被陆续提出［4-8, 10］。根据算法采用的数据结构，可将算法可分为：基于边界、基于树、基于

零压缩决策图(ZeroSuppressed Binary Decision Diagrams，ZBDD)等类别。

2.1 基于边界的显露模式发现

Dong等在文献［4］中分析了EP挖掘的挑战：

1)关联分析中的Apriori性质不适用于显露模式分析。例如，在EP挖掘过程中，已知项集{a, b}不是EP，不能推断{a, b, c}也不是EP。

2)当数据维度高，或支持度较低时，EP挖掘候选项集的规模将会非常大，直接根据其定义挖掘显露模式的计算代价非常大。

根据EP挖掘目标将数据集D划分为Dp和Dn，根据指定的支持度θ，找出在Dp中支持度≥θ，以及在Dn中支持度 ≤ θ/ρ的项集，理论上可找出满足支持度变化条件的EP，但在实际中会由于候选项集规模庞大而导致算法效率执行过低，难以实用。

文献［4］设计了基于边界的EP挖掘算法，要点在于利用边界来表述项集，从而提高EP挖掘效率。所谓边界〈L, R〉是一个由项集集合L和R组成的二元组，边界〈L, R〉描述的项集集合(记为［L, R］)满足：以L的子集为子集并且以R的子集为超集，即［L, R］={Y |X∈L, Z∈R, XYZ}。

例2 若有边界〈{{a},{b,c}},{{a,b,c},{b,c,d}}〉，其描述的全体项集为：{{a},{a,b},{a,c},{a,b,c},{b,c},{b,c,d}}。

容易看出，利用边界可以准确且简洁地描述大量项集。这样，通过对两个边界进行比较，可以发现同样用边界描述的满足支持度条件的项集集合。

2.2 基于树的显露模式发现

Bailey等在文献［5］中采用称为成分树(component tree)的树型结构存储原始数据集，并在成分树中挖掘JEP。成分树的结构类似于频繁模式树，包含相同项的项集可以在树中共享存储单元，从而对原始数据集进行压缩。压缩后的数据有利于保持在内存中运行，提高算法执行效率。

成分树中若干项集共享的第1个节点称为Root节点，每个节点记录了从Root节点到其自身这条路径上所有项同时在两类数据集中出现的次数。文献［5］将成分树中在某类数据集中出现次数为0的节点称为Base节点,并利用Root节点和Base节点寻找所有JEP。

文献［5］指出在构建成分树时，项集中项的顺序不仅要利于减少成分树的节点，还要利于算法执行遍历操作，从而达到高效挖掘JEP的目的。此外，文献［6］提出了一种基于树型结构挖掘基本显露模式(essential EP)的方法。

相对于其他EP挖掘方法，文献［7］提出DPMiner算法，在频繁模式树的基础上，采用深度优先的搜索策略同时挖掘数据集的闭模式(closed pattern)和构造因子(generator)。DPMiner不仅能快速地挖掘闭模式，也能有效地挖掘EP，而且DPMiner可一次挖掘出针对数据集中所有类的EP，是目前已有研究成果中挖掘效率最高的算法［7］。

2.3 基于超图的显露模式发现

最小超图遍历(minimal transversals of hypergraph)旨在找出包含超图的每条边中至少一个元素的顶点的所有最小集合。最小超图遍历是离散数学的一个重要问题，文献［8］研究了最小超图遍历同挖掘显露模式之间的关系，并设计了基于超图遍历挖掘显露模式的算法。

下面用例子说明如何将EP挖掘转化为最小超图遍历。

例3 给定事务集Dp和Dn，设Dp={{a, c, e, h},{a, d, f, h}}，Dn={{e, h, i, j},{b, e, g, i},{a, d, f, g},{c, e, h, i}}，考察Dp中的每条事务，如：{a, d, f, h}，对比Dn中的每条边，将不在Dn中的顶点集构造成超图：{{a, d, f},{a, d, f, h},{h},{a, d, f}}。对此超图求最小遍历：{ah, dh, fh}，即为Dp的EP。

2.4 基于ZBDD的显露模式发现

ZBDD是一种有效表示和处理稀疏向量集合的数据结构，由于ZBDD中冗余节点较少，同时能够自动存储和提取已完成的计算结果，并在内存消耗和计算速度间做到很好的平衡。在ZBDD中，利用n元向量来描述项集，向量中取1的位，表明项集包含该位所对应的项。此外，利用ZBDD可方便地进行集合运算。限于篇幅，本文略去ZBDD的构造方法和操作执行，细节可参阅文献［9］。

推荐访问:显露 挖掘 进展 模式 研究

---