基于数据场的量化关联规则挖掘方法设计

孟海东，李丹丹，吴鹏飞

(1.内蒙古科技大学矿业工程学院，内蒙古 包头 014010;2.内蒙古科技大学信息工程学院，内蒙古 包头 014010)

0 引言

数据挖掘是从大量的、不完全的、有噪声的、随机的数据中找出那些隐含的、事先未知的、但又潜在有用的知识的过程[1]。近年来，随着数据采集、存储等技术设备的飞速发展，导致了“数据爆炸但知识贫乏”现象的出现。然而，这些数据的背后隐藏着很多有意义的信息，传统的检索和统计分析工具已无法满足需求，数据挖掘应运而生并已成为数据库和信息决策领域的研究热点。

关联规则挖掘是数据挖掘的一个重要分支，主要用来发现存在于数据库中的属性集之间有趣的关系。关联规则最初是 R.Agrawal等人于1993年提出的[2]，关联规则的一般形式为:X和Y分别表示属性集，规则形如X⇒Y[s%c%]，表示由X可以预测Y，其中，支持度为s%，置信度为c%。一个典型的关联规则的例子是:“顾客买尿布⇒买啤酒(20%，80%)”，该规则表示在所有的交易记录中，有20%的顾客同时购买了尿布和啤酒，而在购买了尿布的顾客中又有80%的顾客购买了啤酒。这个例子是典型的布尔型关联规则挖掘，现有的关联规则挖掘方法多是针对布尔型属性或分类属性提出的，并且研究工作已经较成熟，如经典Apriori算法及其各种变形和改进，但实际应用中的关系型数据库中包含有大量的量化属性，而这些算法都不能直接用于量化关联规则的挖掘，相比布尔型关联规则挖掘的研究而言，对量化关联规则的挖掘算法的研究较少，因此迫切需要对量化关联规则挖掘算法进行更深入的分析与研究。

1 研究现状

量化关联规则研究处理的是量化属性，由于量化属性的取值是数值型的，取值范围大，其定义域是连续的，不再是0、1两种取值，存在隐含的序，通常是将这些量化属性划分成多个不同的区间，从而将量化关联规则的挖掘研究问题转化为布尔型关联规则问题进行研究。分析现有的量化关联规则挖掘的研究现状，主要存在下面一些问题。

1.1 基于区间划分的方法

该类处理方法是将属性的定义域划分成不同的区间，使每个区间成为新的布尔属性，进而转化为布尔型关联规则挖掘问题[3-5]。这类方法又可以分为两种:一种方法是将属性的定义域划分成离散的、互不重叠的区间，区间划分的较明显，这样会将某些区间附近的一些潜在元素排除在外，从而导致一些有意义的区间的支持度小于最小支持度，可能被忽略掉。另一种方法是将属性的定义域划分成重叠的区域，这时处于边界附近的元素就很可能同时处于两个区间，造成过分强调这些交叉元素的作用，导致过分强调某些区间的意义。

为了避免上面的区间划分过硬问题，后来在对属性离散化处理时引入模糊概念[6-7]，将属性的定义域模糊化，即将属性的定义域划分成多个模糊集，达到软化边界的目的。模糊概念虽在一定程度上解决了区间划分过硬问题，也得到了广泛应用，但是其隶属函数的具体确定方法仍没有得到根本解决。

1.2 基于距离的方法

该类方法是考虑属性取值的分布，使用聚类方法将属性定义域划分成很多聚类子区间[8-9]，进而形成数据项，然后将其转化为布尔型关联规则挖掘研究。该方法虽然充分考虑了属性取值之间的距离，更好地体现了数据间的关系，不会出现属性区间划分过硬的问题。但该类方法没有考虑有限的数据点对数据挖掘任务的不同作用。

1.3 基于云模型的方法

该方法在对量化关联规则进行的挖掘的过程中，使用了云模型的概念，并给出了云模型下规则支持度、置信度、相关性的计算方法，很好地解决了区间划分过硬问题以及隶属函数不好确定的问题[10]。该方法仍然没有考虑有限的数据点对数据挖掘任务所发挥的不同作用。

针对上述问题，本文设计了基于数据场的量化关联规则挖掘方法，在挖掘量化关联规则的过程中运用数据场的概念，该方法不仅能解决区间划分过硬问题，又能充分考虑数据之间的距离和有限的数据点对数据挖掘任务的不同作用，从而使得发现得到的关联规则更准确、更具现实意义。

2 数据场

场概念的提出最早是用于描述物质粒子间的非接触性相互作用，随着场论的发展，人们尝试着将物质粒子间的相互作用及其场描述方法引入到抽象的数域空间中。在进行数据分析处理时，收集到的数据集往往是观测数据，这些数据相对于母体常常是非完备的，即母体的非完备样本。而且对同样的一堆数据，不同的人看，有不同的结果;同一个人从不同的角度看，也可能有不同的结果。但是，样本数据集中的每个数据点都不是独立的，都对数域空间中的每个数据点有影响。李德毅院士曾提出:每个数据对象都相当于具有一定质量的质点，其周围存在着一个作用场，位于场内的任何其它数据点都受到一个场力的作用，如同发光体、发热体向周围发散能量一样，将这种可以辐射的作用称之为数据能量，这种作用使得每个观测数据都充当“周围”未出现的观测数据的代表，由此，所有数据点的联合作用就在空间中确定了一个数据场。此时，为了利用有限的样本数据更好地认识母体，数据通过数据辐射将其数据能量从样本空间辐射到整个母体空间，以显示自己在数据挖掘任务中的不同作用，接受数据能量并被数据辐射所覆盖的空间就叫做数据场[11]。

2.1 数据场的性质

数据场的存在，必须满足独立性、就近性、遍历性、叠加性、衰减性和各自同向性等条件。

(1)独立性:每一个数据点在向外辐射数据能量的过程中，都是以自己为中心，独立地辐射能量，其特性不会因为其它数据的存在而发生改变，不同数据辐射的数据能量可以同时存在于同一个空间中。

(2)就近性:每个观测数据既向外辐射能量，又接受来自其它数据的辐射能量通常称之为数据辐射主动点;而非观测数据所处的点，只是接受其他数据点所辐射的数据能量，通常称之为数据辐射被动点。就近性指的是，所有的数据辐射主动点的数据能量均大于全部的数据辐射被动点的数据能量。

(3)遍历性:数据点通过数据辐射将其数据能量从样本空间辐射到整个的母体空间，实现全域覆盖。

(4)叠加性:数据辐射的遍历性导致数据能量的叠加，数据能量的叠加又依赖数据辐射的遍历性。在数据辐射过程中，当几个数据点同时向某个未观测数据点辐射数据能量时，这个未观测数据点的数据能量就等于各个数据点独立辐射数据能量时在该点的数据能量的合成量。

(5)衰减性:数据场是一个短程场作用，数据辐射的强度随距离的增加而衰减，即给定空间某一数据点，在距离该数据点的距离为0时，此处数据点的数据能量最大，而当距离该数据点超出一定的距离时，该数据点所辐射的数据能量就可以忽略不计。

(6)各自同向性:目标数据集中的观测数据只是“周围”未出现数据对象的代表，观测数据向外辐射数据能量，并为“周围”所分享。各自同向性表示的是每个观测数据点在其周围的各个方向上是均匀辐射的。

2.2 场强函数和势函数

场强函数是定义在数据集上的连续光滑函数，是场点到场源距离的单值单调下降函数。场强函数描述数据辐射能量的分布规律，度量在数据场中不同位置的场强。数据发射能量的形式和特征不同，描述数据场的场强函数也会不同。实际应用时，应选择合适的适于数据挖掘的场强函数。

常用场强函数为:

其中，r一般为欧式距离;σ叫作辐射因子，与数据量和数据的分布有密切关系，对场强和势起调节作用;CT(x)表示辐射亮度，在很大程度上决定了数据辐射的能量强弱，在无法给定数据的辐射亮度时，可以统一设为1。

当各个数据点都独立地向周围辐射能量时，在数据集中的一点所引起的数据能量之和，称为在此处数据场的势，势值的大小在一定程度上表示了该数据点对数据挖掘任务的作用大小。根据数据集上的场强函数，不难得到对于有n个数据点的样本数据集中的任一点x，其余数据对象在x处产生的势函数为:

其中，在同一数据集中，P为数据场的势(即某点所接受的全部数据辐射过来的数据场的场强之和);n为数据的数量;ri为该点和数据xi的距离;CT(xi)是数据xi的辐射亮度;σ仍为辐射因子。

由式(2)可以看出，数据场的势函数是关于场中数据点位置的标量函数，在数据场的不同位置的数据点，就有不同的势函数值。

把数据场中势相等的点，用曲线连起来形成嵌套的等值线，称为等势线。σ的变换将直接影响等势线的间距，σ越小单个数据点的影响范围就越小，等势线越密集;σ越大单个数据点的影响范围就越大，等势线就越稀疏。全部等势线对数据空间的覆盖构成了势场，在势场中，等势线所围绕的不同中心点叫势心。一个数据形成的势场中，其势心就是该数据本身所在的位置;多个数据叠加而形成的势场中，其势心会靠近于权值较大的数据点或是数据很密集的位置。数据集的势心是该类数据对数域空间中的某个概念的隶属中心，也就是数据在该概念特征聚类的中心点。势场是数据场的外在表现方式之一，根据势场中等势线的分布特性，可以看出某些数据所呈现出的抱团特性，形成自然拓扑聚类和类谱图。

数据场的影响因素主要有数据辐射半径r、数据辐射因子σ、数据辐射亮度CT(x)和数据数量n，以及这些因素的综合作用。

3 基于数据场的量化关联规则

3.1 问题定义

设 T={t1，t2，…，tn}是一个交易数据库，tj表示 T的第 j个元组或第 j个记录;I={i1，i2，…，im}表示属性集，tj[ik]表示属性ik在第j个记录上的值。R是实数的集合，IR=I× R × R，即 IR={(x，l，u)|x∈I，l∈R，u∈R，l≤x ≤u}。三元组(x，l，u)∈IR 表示一个数值型属性x取值的区间是(l，u)，或者是一个类别属性的值l(l=u)。量化关联规则r形如X⇒Y，X⊂IR，Y⊂IR，attr(X)∩attr(Y)=φ。如果交易数据库D中有s%的交易记录支持X∪Y，并且支持X的记录中有c%的交易记录支持Y，那么称量化关联规则X⇒Y的支持度为s%、置信度为c%。量化关联规则挖掘问题就是在含有量化属性的交易数据库中找出满足最小支持度和最小置信度的关联规则的问题。

聚类在数据挖掘中是一种很重要的无监督学习技术，它在无监督的学习下发现数据的结构信息，即将数据集中的数据点或记录划分为不同的类簇，使得同一类簇中的数据具有较高的相似性，不同类簇中的数据具有较小的相似性[12-13]。

3.2 提出的算法

基于数据场的量化关联规则的挖掘可以分为以下几个步骤:

(1)将给定的交易数据库的属性投影到IR=I×R×R。对于非数值型的数据，将其转化为对应的数值型的数据。对于数值型数据或保留原有的值或是进一步转换为标准化的形式。

(2)在第(1)步完成的基础上，把所有的属性都考虑进来，将一个数据点或记录看成是具有m维的向量，计算数据库中任意两个数据点或记录之间的距离，以及每个数据点或记录的势函数值大小，并将记录按势函数值的大小降序排序。

(3)应用聚类算法对数据集进行聚类。选取势值最大值点作为初始聚类中心，这里采用基于密度和自适应密度可达的聚类算法CADD[14]进行聚类，使得聚类得到的结果可以是任意形状的。

(4)计算每个类簇的支持度大小，并判断是否满足给定的最小支持度。

(5)将满足最小支持度的类簇分别投影到数值型属性所在的域。

(6)生成满足给定最小置信度的规则。

3.3 定义规则的支持度计算方法

通过定义数据之间的势函数，将数域空间映射到数据场空间。数据场中各个数据点的势值体现了数据点在数据集中发挥的不同作用，也就是说，势值在一定程度上体现了该数据点的重要性，是该数据点对数域空间中的某个概念的隶属程度。所以，将基于数据场的量化关联规则的支持度s定义为:

3.4 定义规则的置信度计算方法

同支持度的计算公式一样，置信度的计算在传统的计算公式的基础上，也考虑到数据点对挖掘任务的不同作用，将规则的支持度定义为c:

4 结束语

本文设计了一种基于数据场的量化关联规则挖掘方法。引入数据场的概念进行量化关联规则挖掘的关键:充分考虑了数据集中数据的非完备性以及各个数据对数据挖掘任务所发挥的不同作用，把一个交易作为一个m维向量，并计算每个数据点或记录的势值，根据势值的大小选择合理的聚类中心点对给定数据集进行聚类，算出一个较传统聚类更好的聚类结果，然后将满足最小支持度的类簇投影到数值型属性所在的域，克服了传统方法中区间划分过硬的问题，并给出衡量关联规则的支持度和置信度的新的计算方法。

[1]毛国君.数据挖掘技术与关联规则挖掘算法研究[D].北京:北京工业大学，2003.

[2]Miller R J，Yang Y.Association rules over interval data[C]//Proceedings of ACM-SIGMOD Int.Conf.Management of Data，1997:452-461.

[3]刘亚波.关联规则挖掘方法的研究及应用[D].长春:吉林大学，2005.

[4]董引娣.数据挖掘中关联规则在零售业中的应用[J].重庆科技学院学报，2010，12(1):121-123.

[5]王玮，陈恩红.连续数据的分割及关联规则发现[J].计算机工程，2000，26(9):17-19.

[6]李乃乾，沈钧毅.基于模糊概念的量化关联规则挖掘[J].计算机工程，2002，28(11):13-14.

[7]孙建勋，陈绵云，张曙红.用模糊方法挖掘量化关联规则[J].计算机工程与应用，2003，39(18):190-192.

[8]张德丰，马子龙，梁忠宏.基于聚类和关联规则的挖掘算法[J].计算机工程与科学，2004，26(9):64-66.

[9]邢东旭，申海涛，孟海东.基于距离的关联规则挖掘算法研究[J].内蒙古大学学报:自然科学版，2010，41(6):703-706.

[10]杜鹢，宋自林，李德毅.基于云模型的关联规则挖掘方法[J].解放军理工大学学报，2002，1(1):30-34.

[11]李德仁，王树良，李德毅.空间数据挖掘理论与应用[M].北京:科学出版社，2006:364-508.

[12]郭峰.基于数据场的聚类方法研究[D].哈尔滨:哈尔滨工程大学，2009.

[13]王海军，邓丽，王丽，等.基于数据场的C均值聚类方法研究[J].武汉大学学报:信息科学版，2009，34(5):626-628.

[14]宋宇辰，宋飞燕，孟海东.基于密度复杂簇聚类算法研究与实现[J].计算机工程与应用，2007，43(35):162-165.