|
内容来自www.paper51.com 图1 知识发现过程 内容来自论文无忧网 www.paper51.com
虽然数据挖掘是知识发现过程的一个步骤，然而，在产业界、媒体和数据库研究界，“数据挖掘”比较长的术语“数据库中知识发现”更流行。目前比较公认的定义是Fayyad等给出的：KDD是从数据集中识别出有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。这里的高级处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式的上升过程。而数据挖掘则指的是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。数据挖掘其实是知识发现的核心部分，而知识发现是在积累了大量数据后，从中识别出有效的、新颖的、潜在的、有用的及最终可以理解的知识，人们利用这些知识改进工作，提高效率和效益。 内容来自www.paper51.com
KDD是一门交叉学科，涉及到人工智能、机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、专家系统等多个领域。数据挖掘算法的好坏将直接影响到所发现知识的好坏。数据挖掘的任务是从数据中发现模式。 copyright paper51.com 虽然数据挖掘是知识发现过程的一个步骤，然而，在产业界、媒体和数据库研究界，“数据挖掘”比较长的术语“数据库中知识发现”更流行。目前比较公认的定义是Fayyad等给出的：KDD是从数据集中识别出有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。这里的高级处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式的上升过程。而数据挖掘则指的是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。其实数据挖掘是知识发现的核心部分，而知识发现是在积累了大量数据后，从中识别出有效的、新颖的、潜在的、有用的及最终可以理解的知识，人们利用这些知识改进工作，提高效率和效益。 paper51.com
KDD是一门交叉学科，涉及到人工智能、机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、专家系统等多个领域。数据挖掘算法的好坏将直接影响到所发现知识的好坏。数据挖掘的任务是从数据中发现模式。 paper51.com 2.3 数据挖掘的应用 内容来自论文无忧网 www.paper51.com 数据挖掘可以应用在各个不同的领域。电讯公司和信用卡公司是用数据挖掘检测欺诈行为的先行者。保险公司和证券公司也开始采用数据挖掘来减少欺诈。医疗应用是另一个前景广阔的产业:数据挖掘可以用来预测外科手术、医疗试验和药物治疗的效果。零销商更多的使用数据挖掘来决定每种商品在不同地点的库存，通过数据挖掘更灵活的使用促销和优惠券手段。制药公司通过挖掘巨大的化学物质和基因对疾病的影响的数据库来判断哪些物质可能对治疗某种疾病产生效果。 内容来自论文无忧网 www.paper51.com 以下为数据挖掘的一些成功案例:(1)加拿大BC省电话公司要求加拿大Simon Fraser大学KDD研究组根据其拥有的十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。(2)美国著名的国家篮球队NBA的教练，利用IBM公司提供的数据挖掘工具临场决定替换队员。大约20个NBA球队使用了IBM公司开发的数据挖掘应用软件Advanced Scout系统来优化他们的战术组合。例如Scout就因为研究了魔术队队员不同的布阵安排，在与迈阿密热队的比赛中找到了获胜的机会。（3）国外使用数据挖掘技术，对西药的新药开发研究也早已利用数据挖掘技术。我国在中药的数据挖掘技术上已步入起步阶段。 copyright paper51.com 3关联规则挖掘 内容来自论文无忧网 www.paper51.com 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析。 内容来自www.paper51.com 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，如果顾客购买牛奶的同时也购买面包（和什么类型的面包）的可能性有多大？通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。 http://www.paper51.com
3.1基本概念 http://www.paper51.com 设I={i1,i2,…,im}是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得TÍI。每个事务有一个标示符，称作TID。设A是一个项集，事务T包含A当且仅当 AÍT。关联规则是形如AÞB的蕴涵式，其中AI，BI，并且A∩B=Æ。如果D中有s%的事务包含A∪B，则称关联规则AÞB在事务数据库D中具有大小为s%的支持度，它是概率P(A∪B)。如果D中包含项目集A的事务中有c%的事务同时也包含项目集B，则称规则AÞB在事务数据库D中具有大小为c%的置信度，它是条件概率P(B|A)。即： 内容来自论文无忧网 www.paper51.com
support(AÞB)= P(A∪B) http://www.paper51.com confidence(AÞB)=P(B|A) 内容来自www.paper51.com 如果不考虑关联规则的支持度和置信度，在事务数据库中可以发现无穷多的规则。事实上，满足一定的支持度和置信度的关联规则才是有意义的。因此，需要给定两个阈值：最小支持度（min_sup）和最小置信度（min_conf）。同时满足最小支持度阈值和最小置信度阈值的规则称作强规则。为方便计，我们用0%和100%之间的值而不是用0到1之间的值表示支持度和置信度。 内容来自论文无忧网 www.paper51.com 项的集合称为项集(itemset)。包含k个项的项集称为k-项集。项集的出现频率是包含项集的事务数，简称为项集的支持计数。如果项集满足最小支持度，则称它为频繁项集(frequent itemset)。频繁k-项集的集合通常记作Lk。 copyright paper51.com 3.2购物篮分析 paper51.com 先看看购物篮分析，这是一个引发关联规则挖掘的典型例子。 内容来自www.paper51.com 例1 超市的经理想了解顾客的购物习惯。例如，想知道“哪些商品组合常常被顾客同时购买？”为回答这一问题，可以在超市的事务数据库上运行购物篮分析。分析结果可以帮助超市经理设计不同的商品布局。一种策略是：将经常一块购买的商品放近一些，以便进一步刺激这些商品一起销售。例如，如果顾客购买牛奶也倾向于同时购买面包，那么将牛奶和面包摆放得近一点，可能有助于增加二者的销售。另一种策略是：将牛奶和面包分别放在超市的进、出口，可能诱发买这些商品的顾客一路挑选其他商品。例如，顾客在买了牛奶之后，去找面包，路上看到水果，可能会决定也买一些水果。购物篮分析也可以帮助超市规划什么商品降价出售。如果顾客趋向于同时购买数字彩电和DVD机，数字彩电降价出售可能既促使购买数字彩电，又促使购买DVD机。 http://www.paper51.com
想象全域是超市中可利用的商品的集合，则每种商品有一个布尔变量，表示该商品的有无。每个篮子则可用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如，购买牛奶也趋向于同时购买面包可以用以下关联规则表示： http://www.paper51.com 牛奶Þ面包 [support=2% ,confidence= 60% ] paper51.com 规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。上一条关联规则的支持度2%意味分析中的全部事务的2%同时购买牛奶和面包。置信度60%意味购买牛奶的顾客60%也购买面包。如果关联规则满足最小支持度阈值和最小置信度阈值，则被认为是有趣的。这些阈值可以由用户或领域专家设定。 copyright paper51.com 3.3Apriori经典算法 内容来自论文无忧网 www.paper51.com 下面介绍形式最简单的关联规则挖掘方法。这种关联规则是单维、单层、布尔关联规则，如前面讨论的购物篮分析。 内容来自www.paper51.com 关联规则的挖掘分两步： http://www.paper51.com
1) 找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。 内容来自www.paper51.com
2) 由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。 paper51.com 也可以使用附加的兴趣度度量。这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。 http://www.paper51.com Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于频繁项集性质的先验知识，正如我们将看到的。Apriori使用逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。 http://www.paper51.com 为提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。我们先介绍该性质，然后用一个例子解释它的使用。 http://www.paper51.com Apriori性质：频繁项集的所有非空子集都必须也是频繁的。Apriori性质基于如下观察：根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P(I)<min_sup。如果项A添加到I，则结果项集（即I∪A）不可能比I更频繁出现。因此，I∪A也不是频繁的，即P(I∪A)<min_sup。 copyright paper51.com
该性质属于一种特殊的分类，称作反单调(anti-monotone)，意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。称它为反单调，是因为在通不过测试的意义下，该性质是单调的。 内容来自www.paper51.com “如何将Apriori性质用于算法？”为理解这一点，我们必须看看如何用Lk找Lk-1。下面的两步过程由连接和剪枝组成。 paper51.com
(1) 连接步：为找Lk ，通过Lk-1 与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集。记号li[j]表示li的第j项（例如，l1[k-2 ]表示l1的倒数第3项）。为方便计，假定事务或项集中的项按字典次序排序。执行连接Lk－1∞Lk－1 ，其中Lk－1的元素是可连接的，如果它们前(k- 2 )个项相同。即是，L k－1的元素l1和l2是可连接的，如果(l1[1] = l2[1])∧(l1[2] =l2[2])∧ . . . ∧(l1[k-2]=l2[k-2])∧(l1[k-1]< l2[k-1] )。条件(l1[k-1]< l2[k-1] )是简单地保证不产生重复。连接l1和l2产生的结果项集是l1[1] l2[2]... l1[k- 1] l2[k- 1 ]。 copyright paper51.com
(2) 剪枝步：Ck是Lk的超集；即是，它的成员可以是也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk（即根据定义，计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用 Apriori性质：任何非频繁的(k-1)-项集都不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。 copyright paper51.com 下面的Apriori算法是Agrawal R提出来的： http://www.paper51.com 算法1：Apriori使用根据候选生成的逐层迭代找出频繁项集。 paper51.com 输入：事务数据库D；最小支持度阈值min_sup。 paper51.com 输出：D中的频繁项集L。 http://www.paper51.com
方法： 内容来自论文无忧网 www.paper51.com
1) L1= find_frequent_1-itemsets(D) ; 内容来自论文无忧网 www.paper51.com
2) for (k = 2; Lk-1≠Φ ; k++) { 内容来自论文无忧网 www.paper51.com 3) Ck= aproiri_gen(Lk-1,min_sup) ; paper51.com
4) for each transaction t∈D{ //scan D for counts paper51.com
5) Ct = subset(Ck , t); //get the subsets of t http://www.paper51.com 6) for each candidate c∈Ct 内容来自www.paper51.com 7) c.count++; http://www.paper51.com 8) } copyright paper51.com
9) Lk= {c∈C | c.count ≥ min_sup} http://www.paper51.com 10) } copyright paper51.com 11) return L = ∪kLk; copyright paper51.com procedure apriori_gen(Lk-1:frequent(k-1)-itemsets; 内容来自论文无忧网 www.paper51.com min_sup:minimum support threshold) 内容来自论文无忧网 www.paper51.com 1) for each itemset l1∈Lk-1 http://www.paper51.com 2) foreach itemset l2 ∈Lk-1 内容来自www.paper51.com
3) if (l1[1]=l2[1])∧(l1[2]=l2[2])∧. . .∧(l1[k-2] =l2[k-2])∧ copyright paper51.com (l1 [k-1]<l2[k-1]) then { 内容来自论文无忧网 www.paper51.com 4) c = l1∞l2 ; //join step: generate candidates copyright paper51.com 5) if has_infrequent_subset(c,Lk-1) then http://www.paper51.com
6) delete c; // prune step: remove unfruitful cadidate 内容来自论文无忧网 www.paper51.com
7) else add c to Ck ; 内容来自论文无忧网 www.paper51.com 8) } paper51.com 9) return Ck; http://www.paper51.com procedurehas_infrequent_subset(c:candidate k-itemset; copyright paper51.com L :frequent (k-1 )- itemset )// use prior knowledge 内容来自论文无忧网 www.paper51.com
1) foreach (k-1)-subset s of c 内容来自www.paper51.com
2) if sLk-1 then 内容来自www.paper51.com 3) return TRUE ; 内容来自www.paper51.com 4) returnFALSE; 内容来自论文无忧网 www.paper51.com 如上所述，Apriori_gen做两个动作：连接和剪枝。在连接部分，Lk与Lk-1连接产生可能的候选（第1-4步）。剪枝部分（第5-7步）使用Apriori性质删除具有非频繁子集的候选。非频繁子集的测试在过程has_infrequent_subset中。 http://www.paper51.com
一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满最小支持度和最小置信度）。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。 内容来自www.paper51.com
copyright paper51.com 其中，support_count(AB)是包含项集AB的事务数，support_count(A)是包含项集A的事务数。 内容来自www.paper51.com
4需求分析和设计方案 内容来自www.paper51.com 4.1需求分析 copyright paper51.com
由于事务数据库一般只具有对大量数据的存取、检索功能，对于用户的一般性的使用可以满足，然而，正是由于数据库中存放了大量的数据，不同的数据项，以及多个数据项之间还存在有大量的隐含的、未知的、有意义的数据关系，这些关系对于用户有着及其重要的作用，所以数据挖掘便在此情况下产生了。而关联规则挖掘是数据挖掘中一个重要规则，Apriori算法又是关联挖掘的一个经典算法，它能发现大量数据中项集之间有趣的关联和相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析。 http://www.paper51.com
4.2设计方案 copyright paper51.com 图2 系统结构图 http://www.paper51.com 通常在寻找频繁项集时要反复扫描整个事务数据库，读出每一条记录，判断记录是否包含候选项集，这样对于较大型的事务数据库，花在扫描数据库、读记录上的开销很大。同时，本文提出的关联规则是建立在置信度上的挖掘技术，与频繁项集无关，更是需要反复扫描事物数据库。于是本文引入了位图矩阵。先给方剂库建立一个位图矩阵，然后只在位图矩阵上进行挖掘操作。使用位图矩阵有如下好处： http://www.paper51.com （1）对位图进行操作，简单快速。（2）只需要在建立位图矩阵时对整个方剂库扫描一次。 copyright paper51.com
（3）在做实验时需要反复调整支持度阈值和置信度阈值，以得到多组实验数据，但位图矩阵只在做第一组实验时建立一次，调整支持度阈值和置信度阈值再做实验时，不用再建。 copyright paper51.com 用Ik(k为自然数)表示事务数据库中的一项，I1、I2、…、Ik、…、In表示事务数据库中的所有项。用Tj(i1,i2,…,ik,…,in)表示事务数据库中的一个事务，ik对应Ik，占用1位(bit),当事务Tj含有Ik这项时，Tj的ik位为1,否则为0，所以事务Tj可以用位图i1i2…ik…in来表示。T1、T2、…、Tj、…、Tm表示事务数据库中所有的事务，T1、T2、…、Tj、…、Tm都可以用位图i1i2…ik…in来表示，这样所有这些位图就构成了事务数据库的位图矩阵。 内容来自论文无忧网 www.paper51.com 图2就是一个位图矩阵。该位图矩阵对应的事务数据库含I1、I2、I3、I4、I5共5个项，含T1、T2、T3、T4、T5、T6、T7共7个事务。事务T1的位图为11010，所以含I1、I2、I4三个项；事务T2的位图为01001，所以含I2、I5两个项；事务T3的位图为10110，所以含I1、I3、I4三个项；事务T4的位图为11101，所以含I1、I2、I3、I5四个项；事务T5的位图为10100，所以含I1、I3两个项；事务T6的位图为11001，所以含I1、I2、I5三个项；事务T7的位图为01010，所以含I2、I4两个项。 内容来自论文无忧网 www.paper51.com |