数据挖掘规则更新计算机

一、数据库中数据挖掘的基本定义及定理

在计算机数据库的数学墨镜建立过程中，可以将数据分为项目数据与事务数据，其中项目数据代表的是某种物品，而事务数据代表的是动作。假设项目集合为I={i1，i2，i3，……，im}，事务集合为D，T是集合D中的非空子集，代表某一组物品，此时必然满足条件T∈I。下面将根据上述的数学因子来解释数据库中关联规则如何被挖掘。

（一）关联规则的内涵

以超市的销售情况为例，我们假设数据库内为超市门店的详细交易数据，任意一次交易的事务t是商品集合I的子集，而关联规则在事务集合D的支持度代表的是在子事务中同时包含了事务元素X与Y的概率；而置信度则是表示含有事务元素X的子事务中同时包含了事务元素Y的条件概率。根据超市门店销售人员对消费者购买商品的市场了解需求，可以制定出相应的支持度与置信度的最小阈值，此时，利用数据库即可找出符合销售人员需要了解的商品之间的关联规则。

（二）相关定义

定义1：若项目集X包含于T，那么我们可以认为事务T支持X；定义2：若事务集D中存在s%的事务支持项目集X，则称项目集X的支持度为s%，并记为sup（X）；定义3：当支持度不小于数据库用户所定义的最小支持度阈值min_sup时，称该项目集为繁荣项目集；当支持度小于数据库用户定义的最小支持度阈值min_sup时，称该项目集为非繁荣项目集，其中项目集中的项目数量成为项目集的长度或维度；定义4：关联规则可以用如下的蕴含形式表示：X→Y，X、Y∈I，并且X∩Y=Ф；定义5：若X→Y的关联规则在事务集合D内支持度为s%，如果项目集（X∪Y）具有大小为s%的支持度，则存在support（X→Y）=P（X∪Y）。定义6：若X→Y的关联规则在事务集合D内支持度为c%，如果事务集D内有c%的事务支持项目集（X∪Y），则存在confidence（X→Y）=P（X∪Y）/P（X）；定义7：设集合S全部由繁荣集构成，那么将S的否定边界记做Bd-（S），符合如下等式：Bd（S）={X|XS，|x|=1}Y{X|任意Y属于X，Y∈S，且XS}，也就是说集合S的否定边界包含了所有本身不是繁荣集但子集全是繁荣集的事务集合，以及所有不是繁荣集的单个因子。

（三）相关定理

针对繁荣集与非繁荣集的关系，也存在以下定理：定理1：繁荣集一定是由繁荣集组成（子集概念）；定理2：非繁荣集的子集一定是非繁荣集。

二、挖掘关联规则过程中的问题分析

关联规则初次生成中的问题数据库关联规则的挖掘过程可分为两部分，首先，需要找出一个繁荣项目集，该集合内所有因子的支持度均大于给定的支持度最低阈值；接下来一步，就是从此繁荣项目集中挖掘出关联规则，当该规则满足可信度条件conf≥min_conf时，该规则即为用户所需规则。算法的挖掘效能高低主要由发掘符合支持度的繁荣项目集决定，第二步的算法主要为判别过程，耗费时间短，因此数据发掘关联规则算法的研究焦点对准了繁荣项目集的发现。已有的算法主要是以重复多次扫描为主，不仅做法复杂，而且效率较低。在事务D数据库中，参数可信度c和参数支持度s对关联规则影响较大，一旦用户定义的支持度s发生改变，繁荣集和信任度也会发生改变，最终引起关联规则的变化。

三、更新关联规则的算法

（一）关联规则更新的数学建模

假设用户原定义的支持度最小阈值为s，用户新定义的支持度最小阈值为s’，那么更新关联规则可以分为以下两种情况：（1）当s’＞s时，由于前一次产生的繁荣集合为Apriori算法求得，那么根据该算法的定义可知，任意一个的繁荣集均存在一个标记属性count记录符合条件的事务元素个数，当新的支持度大于原有支持度时，可以使用原繁荣集的count值排除不符合新要求的繁荣集；（2）当s’＜s时，那么前一次产生的繁荣集是否能够满足新定义支持度阈值而成为繁荣集则需要因情况而定，甚至衍生新的繁荣集。根据上述的定理2不难发现，当用户新给出的支持度阈值s’小于原有的s时，原来繁荣集中的所有元素组成的几何仍旧为繁荣集，但是此时的S否定边界Bd（S）中的部分元素则可能满足条件而成为满足新支持度的繁荣集元素。根据这个原理，在前一次已生成的关联规则上，适当更新算法，即可避免重复的扫描过程，明显降低重新计算时的工作量。当支持度最小阈值降低时，非繁荣集的否定边界集合中部分元素可能转换为繁荣集元素，当且仅当所有子集均为繁荣集时，父集才是繁荣集。所以在进行数据挖掘过程中，只有当否定边界集元素满足新输入的支持度s’时，该元素才有可能从非繁荣集转入繁荣集。接下来，需要使用可信度做进一步的验证，而非繁荣集中的元素由于不满足新支持度s’，因此不需要进行再次验证。重新定义条件与求解内容：条件：数据库DB中已存在某种关联规则r，在该关联规则存在时，S为满足员支持度s的繁荣集，用户改变可信度阈值为c''''，支持度阈值s’满足s’＜s。求解：满足c''''以及s''''的关联规则r''''。

（二）算法程序

根据上述条件与求解内容，可知更新计算分析的重点在于怎样在更短时间内求得新增如繁荣集的元素，也就是上文所提的关联规则挖掘步骤的第一部分，繁荣集的求解。编辑更新算法如下：S={x|support(x)≥s，X是项目集合}Candidate=ΦL.Gets’(s’＜s)fromuser//用户输入s’ComputeTemp：={X∈Bd-(S)|Support(X，A.r)≥s’}//Temp表示从Bd-(s)中找到的满足新支持度s’的元素集合B.S1=S，S=STempC.RepeatD.S2=S1TempE.Temp=Bd(S2)-[Bd-(S1)-temp]//Temp表示新衍生出的候选集F.S1=S2G.Candidate=CandidateTemp//candidate表示当前的新候选集全集H.UntilTemp=ΦputeNew：=(X∈Candidate{support(X，r)≥s’})//求出新增繁荣集J.Result=SNew//将新增繁荣集和原有繁荣集合并，得出符合新支持度s’的所有繁荣集K.Find_Rule（Result，c）更新后的算法首先也需要经过一次数据库扫描来获取部分的新产生繁荣集，并据已得的繁荣集求出推演所得的候选集。对候选集并不急于做验证步骤，而是从衍生候选集中循环计算以求得更多的候选集，直到无法再产生候选集为止，退出循环。在挖掘新繁荣子集的过程中，需要两次扫描数据库，一次目的是搜索Bd(S)否定边界集合中是否存在满足用户新输入支持度s’的可疑元素，并利用这些可疑元素生成下一步的候选集；另一次扫描的目的是验证既得的候选集中是否所有元素均满足用户新输入支持度s’。

（三）改进算法的证明与更新

[Bd(S1)-Temp]集合包含了所有BD(S1)中非繁荣集合，该集合肯定为Bd(S1temp)的子集，因此不满足用户新的定义，可删除。若要得出[Bd(S1)-Temp]真包含于Bd(S1YTemp)，则必有任意Z∈[Bd(S1)-Temp]，同时Z∈Bd(S1YTemp)。根据对否定边界Bd（S）的定义可知，当五、|Z|=1，并Z∈Bd(S1)时，ZTemp又Z(S1)，ZTemp→ZBd(S1YTemp)→Z∈Bd(S1)六、|Z|＞1，并Z∈Bd(S1)时，ZTemp又任意Y属于Z，Y∈S1，并Z(S1)∵Z(S1)并ZTemp→ZBd(S1YTemp)∴综上所述，上述命题成立。

四、更新算法的测试及结果

（一）更新算法的环境要求

在P4-2.4c/512M内存/120G硬盘计算机环境下，运行delphi7.0编辑器实现Aproiri算法的模拟测试，以某售票点的销售额与日期之间的关系为目标关联规则，在经过两种算法的多次运行和数据采集后，取各量化平均值，得出如下数据图表：

（二）更新算法的效果分析

由图可知，在使用本文所提出的更新算法后，原算法的效率得到大大的提高。提高原因主要是从原算法的反复扫描升级至现算法的两次扫描，就可得出所需挖掘关联规则，尤其是在大规模的数据库环境下，本算法的优越性表现越明显。