关联规则技术（共10篇）
关联规则技术 篇1
0 引 言
关联规则挖掘是数据挖掘中最活跃的研究方向之一,反映了大量数据中项目之间有趣的关联或相关联系。关联分析的目的就是为了挖掘出隐藏在数据间的相互关系。通过关联规则技术,可以发现这样一条规则:如果客户购买了某一种商品,那么他也可能会购买另一种商品。随着大量数据不停地被收集和存储,许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。
本文首先介绍了Web挖掘的一些基本概念及其当前发展的几个方向,然后将关联规则挖掘应用到Web的海量数据上,并给出了挖掘的基本算法,在此基础上挖掘出新的关联规则及其模式,最后将结果在一些较简单的网页上进行了验证,取得了较好的应用效果。
1 Web挖掘
1.1 Web挖掘概述
Web挖掘是利用数据挖掘技术从Web文档和Web服务器中发现并提取人们感兴趣的信息或知识的过程,涉及到Internet技术、人工智能、计算机语言学、信息学、统计学等多个领域。
Web包含了丰富和动态的超链接信息,以及Web页面的访问和使用信息,这为数据挖掘提供了丰富的资源。然而,从以下的分析中可以看到,对Web进行有效的知识发现具有极大的挑战性:Web挖掘对象为数据的海量性;Web页面的复杂性;Web是一个动态性极强的信息源;Web面对的是一个形形色色的用户群体;Web上的信息只是很小一部分是相关或是有用的。这些挑战已经推动了如何有效地发现和利用因特网资源的研究工作,Web挖掘是一个极有挑战性的研究课题。
1.2 Web挖掘基本流程
Web上的信息是非结构化、半结构化的或动态的,并且是容易造成混淆,所以很难直接对Web网页上的数据进行挖掘,而必须经过必要的数据处理。典型Web挖掘的处理流程如下:
1.3 Web挖掘的分类
根据对Web数据的感兴趣程度不同,一般可以分为三类:Web内容挖掘、Web结构挖掘和Web用法挖掘。下面就这3个方面进行讨论:
Web内容挖掘即从网络的内容、数据、文档中发现有用信息的过程,Web内容挖掘的对象包括文本、图像、音频、视频和其他各种类型的数据。Web结构挖掘是从WWW的组织结构以及引用和被引用间的连接关系中推理得到知识,利用这些知识,可以对页面进行排序,发现重要的、权威的页面等。Web用法挖掘是指对互联网用户访问网络的行为进行分析挖掘,以获取描述其内在规律的模式。常用技术有:频繁项目集和关联规则。
1.4 Web挖掘的应用前景
Web挖掘的应用非常广泛,它已经广泛应用于金融业、远程通信业、制造业、医疗服务以及体育事业中,对它的应用研究正在成为一个热点。Web挖掘的应用前景主要表现在以下3个方面:电子商务,网站设计以及搜索引擎。
2 关联规则挖掘
2.1 基本概念
设I={i1,i2,…,im}是由m个不同项目组成的集合,D是交易数据库(亦称事务数据库)。其中,每一个交易或事务T是I中一组项目的集合,即X⊆I。关联规则是指形式如下的一种数据隐含关系:X→Y,其中X⊆I,Y⊆I,且X∩Y≠∅。
定义1 项目集X的支持数(支持度)。事务数据库D中支持项目集X的事务数称为项目集X的支持数,记为Count(X)。设事务数据库D中总的事务数为|D|,则项目集X的支持度为Count(X)/|D|,记为Sup(X)。
定义2 关联规则X→Y的支持数(度)。事务数据库D中支持项目集X∪Y的事务数称为关联规则X→Y的支持数,记为Count(X→Y)。关联规则X→Y的支持度为Count(X→Y)/|D|,记为Sup(X→Y)。
定义3 关联规则X→Y的置信度。关联规则X→Y的置信度定义为Count(X→Y)/Count(X),记为Conf(X→Y)。
为了挖掘出有意义的关联规则,需要给定两个阈值:最小支持度(Minsup)和最小置信度(Minconf)。关联规则挖掘的任务是在给定的交易或是事务数据库D中,发现D中所有的频繁关联规则。所谓频繁关联规则是指这些规则的支持度、置信度分别不低于用户给定的最小支持度和最小置信度。
2.2 关联规则的Apriori算法
Rakesh Agrawal等提出的Apriori算法最为著名,其基本思路将Apriori算法分成两步:
Step1:从事务数据库D中找到所有支持度不少于用户指定的最小支持度阈值的频繁项目集。在数据挖掘中,支持度不少于用户给定的最小支持度阈值的项目集简称为频繁项目集。
Step2:使用频繁项目集产生关联规则,产生关联规则的基本原则是其置信度不小于用户指定的最小置信度阈值。
Apriori算法的具体步骤:它是一种使用逐层搜索的迭代方法,首先找出所有频繁1-项目集L1;L1用于找频繁2-项目集L2;L2用于找频繁3-项目集L3,如此下去,直到不能找到频繁项目集为止。具体操作:Apriori算法的第一步是简单统计所有含1个元素的项目集出现的频率,以此决定频繁1-项目集;在第k步,分两个阶段,首先调用函数Apriori-Gen,通过第(k-1)步中生成的频繁(k-1)-项目集Lk-1来生成候选频繁k-项目集Ck,其次扫描事务数据库D计算选频繁k-项目集Ck中各元素在D中的支持数或支持度。其中,所谓候选是指候选中的项目集有可能成为频繁项目集,而不属于候选的项目集均不可能成为频繁项目集。此外,为了挖掘出事务数据库D中所有的频繁项目集,Agrawal等人还建立了项目集格理论。此理论的核心原理即为频繁项目集的所有非空子集也是频繁项目集;非频繁项目集的任何超集亦是非频繁项目集。
2.3 Apriori算法的改进
随着研究的不断深入,发现Apriori算法存在2个缺点:
(1) 必须耗费大量的时间处理规模巨大的候选项目集;
(2) 必须多次重复扫描事务数据库,对候选项目集进行模式匹配。
Agrawal等人提出了几种改进方法:
(1) 基于散列的方法。Park等人引入散列技术来改进产生频繁2-项目集的方法,当扫描事务数据库D中的每个事务时,可以产生每个事务的所有2-项目集,并将它们散列到相应的桶中,在哈希表中对应的桶计数低于min×|D|的2-项目集不可能是频繁2-项目集。
(2) 基于数据分割的方法。
(3) 基于采样的方法。
3 实际应用
由于编程的难度和硬件设施的限制,从一个介绍计算机应用基础的网站中抽取5个网页,并给定初始的实体对lnternet和娱乐,出现模式为“应用”,即娱乐是Internet的一种应用。接着产生初始2-项集,如表1所示,这里只给出其中比较重要的几个。利用这个2-项集来进行关联分析,得出的结果如表2所示。对于这个例子只需要运行2步即可,因为没有4-项集产生。对表2结果(Internet,娱乐)和(因特网,娱乐)这两项则可以进行同义词合行为一项,支持度就变为0.69。所以经过这样3个步骤,从中发现与Internet,Windows相关性较大的这些实体,也就是得出了一些新的关联规则及其应用的模式。所以利用改进的关联规则算法可以在网页中发现大量的未知信息,进而总结出一些新的知识,然后对这些新的知识进行关联分析,使其能得到一些有价值的信息。这样就能够帮助用户从大量的信息中找出隐含的内容,特别是在用户的资源搜索过程中给出用户感兴趣的信息。
同时在实践过程中发现了下一步需要进行研究的方向,即在从2-项集产生多项集的过程中,可以引入散列技术,与其结合来改进算法。值得注意的是由于Web页面是一个不断更新的信息源,所以挖掘的过程是一个长期执行的任务。
4 结 语
Web挖掘是数据挖掘技术的新方向,而作为数据挖掘的重要方法——关联规则挖掘方法一直是研究的重点。本文在介绍了Web挖掘和关联规则挖掘的基础上,试图在这方面做了一些探讨,从而促使Web数据挖掘技术的发展。
参考文献
[1]毕永成.Web日志挖掘中预处理过程的具体研究[J].现代电子技术,2010,33(18):97-100.
[2]朱玉全,杨鹤标,孙蕾.数据挖掘技术[M].南京:东南大学出版社,2006.
[3]周贺来.Web挖掘中关联规则的研究与应用[D].郑州:郑州大学,2006.
[4]刘云,刘东苏.基于Web的数据仓库与数据挖掘[J].情报理论与实践,2001,24(4):289-290,320.
[5]韩家炜.数据挖掘概念与技术[M].北京:机械工业出版社,2006.
[6]王中海.基于Web挖掘研究:网络挖掘[J].图书馆学刊,2006,25(3):35-36.
[7]郭岩,白硕.Web使用信息挖掘综述[J].计算机科学,2005,32(1):1-7.
[8]方元康,胡学刚.一种改进的Web日志会话识别方法[J].计算机技术与发展,2008,18(11):214-216.
[9]潘有能.基于XML的Web日志挖掘研究[J].现代图书情报技术,2006(5):62-64.
[10]周大镯,马文秀.一种有效的Web关联规则挖掘方法[J].数字技术与应用,2007(9):109-110.
数据挖掘关联规则的研究 篇2
【关键词】数据挖掘；关联规则
1.数据挖掘
从信息处理的角度，人们更希望计算机帮助我们分析数据、理解数据，帮助我们基于丰富的数据作出决策，做人力所不能及的事情。于是，数据挖掘——从大量数据中用非平凡的方法发现有用的知识——就成了一种自然的需求，它的主要目的便是从庞大的数据库中寻找出有价值的隐藏事件，找出其中的知识，并根据不同的问题建立不同的模型，以提供决策时的依据，数据挖掘对组织及决策行为将有相当大的帮助。
数据挖掘又称数据库中的知识发现（Knowledge Discovery in Databases），知识发现的一般步骤为：数据抽取，数据清理，数据设计，算法设计，算法运行，结果分析。
数据挖掘的核心步骤是算法的设计阶段，一个好的算法（速度快、伸缩性好、结果容易使用且符合用户的特定需求）是影响数据挖掘效率的最重要因素。数据挖掘是一个循环过程，如果用户对结果不满意，可对数据库进行重新挖掘。
从数据库中发掘的规则可以有以下几种：特征规则、区分规则、聚类规则、关联规则和进化规则等。关联规则是比较新的一种，它的形式简洁，易于解释和理解并可有效捕捉数据间的重要关系。
2.关联规则
关联规则挖掘最相关的三个重要的研究领域是：统计学（Statistics），机器学习(Machine Learning)（或称人工智能，Artificial Intelligent）及数据库（Database）。关联规则挖掘与统计学和机器学习的共同特点是：都是从数据集中发现知识。
2.1 基本概念
Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，是数据挖掘的一个重要研究领域。它反映出一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其它事物预测到。具体描述为：
设I={i1，i2，…，im}是二进制文字的集合，其中的元素称为项(item)。记任务相关的数据D为交易T(transaction)的集合，这里交易T是项的集合，并且T⊆I。每个交易都有一个唯一的标识，如交易号，记作TID。设X是一个I中项的集合，如果X⊆T，那么称交易T包含X。
2.2 关联规则挖掘的算法
Agrawal等人在1993年设计了一个基本算法，提出了挖掘关联规则的一个重要方法—这是一个基于两阶段频繁项集思想的方法，将关联规则挖掘算法的设计可以分解为两个子问题：
1)找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁项集（Frequent Itemset)。
2)使用第1步找到的频繁项集产生期望的规则。
第一个问题是算法设计的核心问题，它的效率高低是影响算法的关键，从庞大的数据库中找出所有符合大于或等于最小支持度的频繁项集，往往是相当艰巨且耗时的过程，但频繁项集被确定以后，要产生相对应的关联规则就容易且直接了，第2步只在生成的频繁项集中创建相应规则的枚举过程，无需复杂的计算，目前所谓的算法设计问题主要是围绕如何生成频繁集展开的。
2.2.1 经典频集方法
为了生成所有频繁项集，Agrawal等人在1993年设计了Apriori算法，使用了递推的方法。
首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频繁项集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频繁项集的候选集，最后的频繁项集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频繁项集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。
2.2.2 FP－tree算法
Han等人提出FP－tree算法[32]，此算法是不产生候选项集作法的代表，因为不用产生候选项集，只需扫描数据库两次，因此节省了大量I／O的时间，整体的效能大幅提升，而且已运用在实际的产品中。
FP－tree算法和上述算法最主要的差别在于：FP－tree算法不用产生候选项集，且将数据库压缩在FP－tree的结构中，改进了扫描多次数据库的高成本。我们利用表2-1中的例子来说明FP－tree算法。它的最小支持度设为2，其作法可分为两个阶段。
第一个阶段为构建FP－tree结构，需扫描数据库两次，第一次扫描数据库将每个支持度大于或等于最小支持度的项目（频繁1-项集）找出，并根据其支持度值大小和在数据库出现的先后次序作排序。并使得每一项通过一个节点链指向它在树中的出现。第二次扫描过滤掉数据库中不足最小支持度的项目并依据排序表的频繁1-项集的次序得到每笔记录中包含频繁项的模式，同时构建FP－tree结构。
FP－tree构造如下：首先，创建树的根节点，用“root”标记，读入经过排序处理的每笔记录的第一个项时，检查root下的子树是否存在此项目节点，若此项目不存在，则在root下新增此项目节点（Ni）；如果此项目存在，则将此节Nj支持度加l。之后的项目读入时，检查Nk（Nk为Ni或Nj）下的子树是否存在此项目节点，如果不存在，就在Nk下新增一个项目节点，如果存在，则将此节点支持度加1，以此类推做完每笔频繁项集中的所有项目。
2.2.3 FPL算法
E C.Tseng及Hsu Tseng提出FPL（Frequent Pattern List）算法以改进FP-tree算法，FPL主要是将数据库中的交易数据做适当的处理后储存在一线性串行数据结构中，并在此线性串行结构上执行简单的运算，即可有效找出所有频繁项集模式，因为FPL算法利用简单的线性串行数据结构，不需产生候选项集，只需扫描数据库两次，且不管是稀疏数据库或是密集数据库均能有效找出所有的频繁项集模式，因此克服了FP-tree的缺点。
FPL算法扫描数据库两次，第一次扫描数据库将每个支持度值大于或等于最小支持度的频繁1-项集找出，并依照支持度大小和在数据库出现的先后次序作排序，第二次扫描以过滤掉记录中不足最小支持度的项目并根据己排序好的项目次序得到每笔记录的包含频繁项的模式，这一步与FP-tree算法一致。
此后FPL执行以下两个阶段。第一个阶段是构建频繁项目线性串行。根据表2-5将频繁项依支持大小建立成FPL串行，并将表2-3中的每笔记录建构成0、1二元数据表（DB-BIT），作法是根据FPL串行节点顺序与表2-3的数据做比较即可得到每笔记录，记录Ti之某位数据若为0（1）表示相对的频繁数据项目未出现（出现）在此记录中，最后将DB-BIT中的所有记录挂至适当的FPL串行节点上。
第二个阶段是从此串行结构中挖掘所有的频繁项集模式。首先检查串行最右边节点（Ni），这也与FP-tree算法相似，从支持度最小的项开始挖掘。在此要找出所有包含Ni项目的频繁项集模式，计算出现在Ni节点上的其它各项出现次数(Bit count)，接着忽略Ni以及所有Bit count小于最小支持度的项产生Ni项目的频繁1-项集模式：I5：2（代表项目I5在数据库中出现二次），接下来处理Bit count值大于或等于最小支持度的节点(Nb(b=l，2，…n))，产生频繁模式为Nb和Ni组合，其出现次数皆为Nb支持度值（I2，I5：2），（I1，I5：2），再将Nb重新建立一子串行，并且将Ni所属的所有记录挂至适当的节点上，依据上面的方法，再挖掘新的频繁模式：（I2，I1，I5：2），直到串行中只剩下一个节点I2。接着考虑移走Ni所属的记录及DB-BIT最后一位，找出下一个Ni=1的所有记录并挂至此串行下。重复上述方法寻找频繁项集模式，直至串形结构上只有一个最大节点存在为止。
3.总结
总之，Apriori、FP-tree等现有关联规则挖掘算法都是在单维、单层、布尔关联规则下讨论的，是最简单形式的关联规则，它是解决其它问题的基础。
参考文献：
[1]朱扬勇,周欣,施伯乐.规则型数据采掘工具集AMINER[J].高技术通讯,2000,10.
[2]胡侃,夏绍伟.基于大型数据库的数据采掘:研究综述[J].软件学报,1998,3.
[3]王曙光,施英.一种改进的相联规则提取算法.计算机工程与应用[J].2002,15.
[4]颜雪松,蔡之华.一种基于Apriori的高效关联规则的挖掘[J].计算机工程与应用,2002,10.
作者简介：赵超（1983—），陕西西安人，硕士研究生，渭南师范学院教师，研究方向：计算机技术与应用。
关联规则技术 篇3
关键词：关联规则,多故障定位,提高定位效率,聚类方法
0 引言
随着软件产品的发展，软件规模以及软件复杂度的不断增大使得软件调试过程越发困难。软件故障定位是调试过程中成本最高同时耗时最长的一项[1]。在软件自动化调试领域，出现了许多相应的方法，Jones和Har rold提出了Tarantula[2]方法，该方法通过对比程序实体在失败测试用例和成功测试用例之间的差别，计算程序实体的怀疑度实现故障定位。C.Liu提出了SOBER[3]方法，该方法使用谓词在测试用例中取值为真对程序故障出现的影响实现故障定位。其他还有一些定位方法[4-6比如CBI、NNQ、SBI等。这些方法大多使用程序实体的覆盖信息来计算每一个程序实体的可疑度，然后通过可疑度排名列表去发现软件故障。这些方法虽然在单故障的情况下取得了很好的效果，但是在多故障的情况下，效果都不是很理想。他们大多都采用one-bug-at-a time的方式实现多故障的定位，但是这种方式弊端明显：时间效率低，同时需要重复测试。
Jones和Harrold提出了一种并行调试技术[7]，通过对可能导致同一个故障的测试用例进行分类，然后结合成功执行的测试用例构造用以测试每个故障的测试用例子集，来同时定位不同的软件故障。但现有的基于覆盖率的错误定位（Coverage Based Fault Localization,CBFL）方法只是统计代码语句或代码基本块的覆盖率，并没有考虑程序执行的数据依赖和控制依赖，因此会出现定位不准确的情况。结合以上两点，本文将在并行的基础上使用关联规则挖掘软件故障。
1 相关工作
许多该领域的学者提出了不同的软件故障定位技术。这些技术大多通过收集语句或者谓词等程序实体的覆盖信息，然后对收集到的信息利用相应的怀疑度公式计算每条语句的怀疑度，据此找出软件中的故障。本文也使用这种方式，同时，结合关联规则的思想来提高软件的多故障定位效率。
1.1 基于交叉表的故障定位技术
W.Eric提出了一种基于交叉表的技术进行软件故障定位的方法[4,8]。该方法的主要思路是：针对每个测试用例的每一条语句构造一个交叉表，通过该交叉表收集语句的覆盖信息和执行结果。然后，利用每条语句的统计信息计算该语句的怀疑度（Suspiciousness）。通过这种方式，所有的语句都可以根据计算出的怀疑度来降序排名。语句的怀疑度越高，该语句越会被优先检查，可以通过排名依次检查语句，直至发现软件的故障。
该技术通过引用一个名为Chi-square test的假设测试来检查测试用例执行结果和语句覆盖信息之间的依赖关系。Chi-square的数据通过交叉表中的数据计算而来，同时与Chi-square中的关键值进行对比，决定这个假设（即执行结果独立于与语句的覆盖信息）被接受还是被抛弃，然后，通过计算语句的怀疑度数值ζ进行故障定位。ζ的数值越大表示语句的怀疑度越高，怀疑度越高则会被优先检查。基于交叉表的软件故障定位技术通过计算语句的怀疑度来预测语句包含故障的可能性。其实验结果表明基于交叉表的软件故障定位技术相比于绝大多数的软件故障定位技术，如Tarantula、Liblit05、SOBER等方法，效果更好。
1.2 并行调试
通常状况下，一个软件出现失效状况下，软件中会包含多个故障，同时软件调试的人员也会不止一个，因此可以通过并行的方式实现软件故障的定位工作，相比于one-bug-at-a-time的方式，并行故障定位会更加高效，通过构造并行工作流，不同的工作人员可以专注于不同的软件故障。要实现并行的软件故障定位，最重要的问题是如何对任务进行划分和分派，这就需要一种可以把错误的测试用例集从新分配成多个小的与特定故障相关的错误测试用例子集的技术。Jones和Harrold提出了一种并行调试的技术[7]用以实现解决这个问题。这种技术会自动把失败的测试用例集分割为针对不同软件故障的测试用例子集。通过使用测试用例动态运行获取执行结果的行为模型和信息，该技术可以生成一个针对不同错误的失败测试用例子集。通过把失败测试用例子集和成功的测试用例结合，就得到了一个专注于特定单错误的测试用例集。这些单错误测试用例集的个数就是对程序中故障个数的预测。
2 关联规则在软件故障定位中的应用
在基于覆盖的软件故障定位技术中，现有技术通过收集测试用例执行的覆盖信息计算语句可疑度，进而定位软件故障。在现有的技术中，往往没有考虑语句间的数据依赖和控制依赖关系，不同语句的覆盖统计是相互独立的，这导致定位的不准确，CBFL方法经常能定位到程序失效时的执行代码，而这些失效时的执行代码多数情况下并不是错误代码[9]，文献[9]表明，基于覆盖的软件故障定位计算可疑度得出的高可疑度语句主要分一下几种情况：
(1）该语句基本块本身就是故障语句，并且该基本块出现在错误测试用例的概率高于出现在成功测试用例的概率。
(2）该语句基本块本身不是故障语句，但是该基本块的执行会导致故障语句的执行，进而发生故障。这表明高可疑语句块或者是故障或者会导致故障，因此考虑通过关联规则挖掘高可疑代码与软件故障的关系，提高故障定位的效率。
测试用例的执行路径能够反映出故障代码与高可疑代码之间的关联，即高可疑代码的执行导致故障语句的执行，进而出现故障。故障语句与高可疑语句表现出了在执行路径上覆盖信息的一致性，然而执行轨迹的路径表示十分复杂和耗时[10]，因此采用相对轻量级的覆盖向量来近似表示路径的覆盖信息。
2.1 路径覆盖向量的表示
定义1：中间不存在控制跳转的连续代码语句构成一个代码基本块，简称为基本块。
定义2：覆盖向量值指代码基本快在每次执行中的覆盖信息构成的向量pathi=(b1,b2,⋯,bn)。其中：path表示覆盖向量；bi表示程序中代码基本块，bi=0表示该代码基本块没有被覆盖，bi=1表示该代码基本块被覆盖。
定义3：一个函数在测试用例集下的执行轨迹符号化表示为EXEM(fi)={B,T,PATH}。其中：B表示函数的基本块集合；T表示测试用例集的所有测试用例集合，PATH={path0,path1,⋯,pathm}表示针对每个测试用例的覆盖向量集合。根据程序执行的结果可以将执行轨迹分为成功执行和失败执行，即EXEMp和EXEMf。
2.2 求解频繁集
根据故障语句与高可疑代码之间表现出的覆盖一致性，可以求解故障语句的“频繁集”来表现这种关联[11,12]，软件故障或者存在于高可疑代码中，或者存在于高可疑代码的频繁集中，因此通过频繁集来提高软件故障定位的效率。只需求出与高可疑代码保持覆盖一致的分量对应的基本块，即可通过频繁集提高故障定位的效率。
求解频繁集的算法如下：
算法中：bk代表目标代码；fg(bk)表示与bk保持频繁一致性的分量集，即求解出的以bk为目标的频繁集。算法过程为：遍历bk不等于0的分量进行与操作，即得到所有的bk的频繁集。通过计算每一条语句块的可疑度，按照可疑度降序检查发现错误，若语句块中不存在错误则检查语句块的频繁集（依据可疑度排序）查找错误，这种方式可提高定位效率。
3 基于交叉表的软件多故障定位技术
下面对基于交叉表的软件多故障定位技术进行具体介绍。
图1为程序实例展示，该程序用于求取输入的是三参数中间值。
图1的程序中包含两个错误，分别是语句行6和语句行9，使用在测试用例集中10组参数组合分别为T1～T10。图中“√”代表了每条测试用例的语句覆盖信息；在最后一行给出了每个测试用例的执行结果：P代表成功，F代表失败。
由图1可知，导致失败的测试用例往往具有相同或者相似的语句覆盖信息。因此可以通过聚类方法将测试用例进行分类，将错误测试用例中语句覆盖路径相同或者相似的路径分为一类，这些被分为不同类的失败测试用例子集就是专注于不同错误的测试用例集。在mid函数中，测试用例7～10失败了。而且，测试用例7,8有相同的覆盖信息，这意味着测试用例7,8可能会导致同样的软件故障。同时，测试用例9,10也具有相同的覆盖信息，同理，它们也可能导致同样的软件故障。通过上述分类原理和观察到的现象，下面把失败的测试用例分为两组针对不同错误的失败测试用例子集。然后通过使用Jones和Harrold的并行调试的方法，将失败的测试用例子集分别与成功测试用例结合，形成两组不同的测试用例子集。两组测试用例子集如图2和图3所示。
针对不同语句构造一个用于计算语句怀疑度的交叉表，语句交叉表模板如图4所示。
图4所示交叉表是一个表示测试用例执行情况和测试用例是否被覆盖的二维表。表中各个变量的含义分别是：w代表程序中的一条语句；NCS(w)代表覆盖w的成功的测试用例数；NUS(w)代表没有覆盖w的成功测试用例数；NS代表成功的测试用例数；NCF(w)代表覆盖了语句w的失败测试用例数；NUF(w)代表没有覆盖语句w的失败测试用例数；NF代表失败的测试用例数；NC(w)代表覆盖了的测试w用例总数；NU(w)代表没有覆盖w的测试用例数；N代表总的测试用例数。
使用图4提供的模板和文献[4]中提供的公式计算每条语句的怀疑度。针对图2和图3两个测试用例集分别计算怀疑度，给出怀疑度列表降序排名如表1所示。
表1中，语句9的怀疑度最高，会最先被检测。在表2中语句6的怀疑度最高，会最先被检测。这表明通过构造针对不同错误的测试用例子集并行的进行故障定位是可以实现的，这将有利于提高软件故障定位的效率。在此计算验证了通过并行的方式进行软件故障定位的有效性。进行并行的故障定位有一个前提就是构造针对不同错误的测试用例。通过使用二分法构造针对不同的测试用例，针对不同的待测函数，可以根据函数的输入集合和函数的功能创造出不同的二分法条件。在上面例子中，mid函数是用作求取输入的3个数的中间值的函数，因此中间的参数最有可能导致软件故障。所以中间的参数作为分类条件，在mid函数中使用“中间的参数是不是在第一个出现”作为分类的条件，如果一个失败测试用例满足这个条件则把它放在一个类别中，不满足则放在另一个类别，同样以图1的测试用例为例，发现T9和T10满足这个条件，所以把他们分为一类，T7和T8分为另一类，这样即可进行并行软件故障定位。
同时，给出一个终止条件，用于判断分类是否完成，即针对不同错误的测试用例是否已经被分配到了各自相应的类别下。聚类的相似性系数可以提供判断不同对象之间相似程度的度量，因此可以使用相似系数来判断每个类别中的对象是否足够相似，不同类别间的对象是否足够相异来判断分类是否完成。相关系数公式如下：
式中：Xi为第i条语句在失败测试用例X中的覆盖情况，Xi为1代表覆盖，0代表未覆盖；Xˉ表示失败测试用例Xi的覆盖比例；相应的Y的含义和X相同。利用图1中的例子可以将失败的测试用例集分类。给定一个相关性系数的值，比如0.8，当两个失败测试用例的关联系数小于0.8时说明它们关联性不大，即它们针对不同的错误。计算r78=1，这表明T7和T8关联性非常大，针对相同的错误，对T9和T10计算结果也是1，说明它们应该分为一组。通过循环计算每两个测试用例之间的相关系数，直到类别内任意两个测试用例的相关系数大于0.8时，就说明分类完成。本文给出的上述方法虽然能够对针对不同错误的测试用例进行分类，但需要对每两个错误测试用例进行计算，所以这个过程相当耗时，开销也是很大。
4 实验及结果分析
下面使用本文给出的基于关联规则的软件多故障定位技术和Tarantula方法进行对比来验证本文方法的定位效果。在此使用Siemens程序集来进行试验的对比工作。程序集中tacas程序包含的故障版本数最多，同时可执行的语句数最少，这意味着tacas程序有可能包含多故障，因此选用该程序验证本文的方法。对文献[4]中的EXAM度量进行扩展，将针对每个故障的EXAM相加，形成EXAMtotal作为度量的标准。
基于关联规则的软件多故障定位方法与Tarantula方法的对比如图5所示。
图5分别给出了在不同的故障版本比例下两种方法的EXAMtotal得分。其中“1”代表20%的故障，“2”代表40%的故障，“3”代表60%的故障，“4”代表80%的故障。可以看到在故障比例较低的环境下，本文的方法效率明显优于Tarantula方法。
5 结语
本文提出了基于关联规则的软件多故障定位方法，并且与Tarantula方法进行了对比，结果表明本文的方法效率较高。不过本文提出的方法也存在一些不足，并没有考虑把测试用例划分为针对不同故障的测试用例的效率，同时也没有考虑失败测试用例分类的效果进行验证。在Siemens测试集上通过实验验证了基于关联规则的软件多故障定位的效率，结果证明本文的方法能有效地发现软件的故障。
参考文献
[1]JONES J A.Semi-automatic fault localization[D].USA:Geor-gia Institute of Technology,2008.
[2]JONES J A.HARROLD M J.Empirical evaluation of the Ta-rantula automatic fault-localization technique[C]//Proceedingsof the 20thIEEE/ACM international Conference on AutomatedSoftware Engineering.Long Beach,CA,USA:IEEE,2005:273-282.
[3]LIU C,FEI L,YAN X,et al.Statistical debugging:A hypothe-sis testing-based approach[J].IEEE Transactions on SoftwareEngineering,2006,32(10):831-848.
[4]RENIERES M,REISS S P.Fault localization with nearestneighbor queries[C]//Proceedings of the 18thIEEE/ACM Inter-national Conference on Automated Software Engineering.Mon-treal,Canada:IEEE,2003:30-39.
[5]LIBLIT B,NAIK M,ZHENG A X.Scalable statistical bug iso-lation[C]//Proceedings of the 2005 ACM SIGPLAN Conferenceon Programming Language Design and Implementation.2005:15-16.
[6]HAO D,ZHANG L,PAN Y,et al.On similarity-awarenessin testing-based fault localization[J].Automated SoftwareEngineering,2008,15(2):207-249.
[7]JONES J A,BOWRING J F,HARROLD M J.Debugging inParallel[D].London,UK:Georgia Institute of Technology,2007.
[8]WONG E,WEI T,QI Y,et al.Crosstab-based statisticalmethod for effective fault localization[C]//Proceedings of the2008 International Conference on Software Testing,Verifica-tion,and Validation.Lillehammer,Norway,2008:42-51.
[9]ZHANG Z,CHAN W K,TSE T H.Capturing propagation ofinfected program states[C]//Proceedings of the 17thInterna-tional Conference on Foundation of Software Engineering.Am-sterdam,Netherl:[s.n.],2009:43-52.
[10]BALL T,LARUS J R.Efficient path profiling[C]//Proceedingsof the International Symposium on Microarchitecture.Paris,France:[s.n.],1996:46-57.
[11]WONG E,QI Y.Effiective program debugging based onexecution slices and inter-block data dependency[J].Jour-nal of Systems and Software,2006,79(2):891-903.
基于关联规则的术语自动抽取研究 篇4
关键词：大数据 术语自动抽取 关联规则
中图分类号： G250.2 文献标识码： A 文章编号： 1003-6938（2014）05-0020-06
Research of Automatic Term Extraction based on Association Rules
Abstract On the basis of sufficient literature review， the rationality and availability of automatic term extraction based on association rules are discussed by the theoretical and experimental methods. Theoretically， the basic principle of association rule， under the condition of full solution of the "sequence"， can solve the problem of identification and extraction of the term. Practically， association rules method can extract correct terminology， and by comparing with the existing algorithm， association rules algorithm has more obvious advantages in difficulty of realization and occupied resources.
Key words big data; automatic term extraction; association rules
术语自动抽取是自然语言信息处理中的一项重要课题，在机器翻译、信息检索、词典编纂、文本分类和自动文摘等领域中有重要的作用。目前，人们已经从多个方面提出了各种方法，并且不断有新的方法出现。本文的目的是研究关联规则算法抽取术语的可行性及优势。
1 相关研究
国内外研究人员已经通过大量的研究工作取得了一系列的成果。归纳起来，术语自动提取的方法可以分为基于语言学知识的方法、基于统计学原理的方法以及基于语言学知识和统计学原理结合的方法。
1.1 基于语言学知识的自动抽取方法
基于语言学知识的方法，又称为基于规则的方法。所谓的“规则”指的是术语的词法模式、词形特征、语义信息等，利用这些知识可以从语料中抽取出术语或者识别术语在语料中的位置。基于语言学知识的术语自动抽取研究主要集中在上个世纪90年代，以Justeson & Katz 算法[1]为代表，该算法首先确定一系列语言性质的规则，然后用这些规则来识别文本中的术语。较为成熟的自动术语抽取系统有FASTR系统[2]、Termight系统[3]、Termino系统[4]、Nodalida系统[5]、Clarit系统[6]、Heid -96系统[7]、Lexter系统[8]和Naulleau-98系统[9]等。
1.2 统计学原理的抽取方法
基于统计学原理的抽取方法，主要利用统计学的原理计算出文本的各种统计信息，并利用统计结果选取术语。在线系统Term Extraction[10]通过简单统计基本词频来实现术语识别。Termextractor系统[11]也是如此，通过统计选取高频词为术语。RIDF算法[12]则不同，该算法关注低频词，在逆文档频率（IDF）的基础上，利用Poisson检验来确定术语;互信息方法[13]也是一种比较常用的术语抽取算法，它利用两个或两个以上的词之间的互信息度，来决定这些词汇是否组成一个复合词，即它们是否组成了一个术语。
1.3 基于语言学知识与统计学原理结合的抽取方法
目前，单纯运用语言学知识或者统计学原理的抽取方法并不多见，因为，基于语言学知识的方法和基于统计学的方法虽各有优势，但也有明显缺点。因此，有很多研究将基于语言学知识的方法与统计学原理的方法结合起来，力争扬长避短。例如，将统计学的策略融入到基于语言知识的抽取方法中去，将二者有效地结合，可以显著改善术语抽取系统的性能。这方面的代表方法是C-value/NC-value方法[14]，该方法综合运用结合语言知识和统计信息来提取由多个词汇组成的术语。C-value/NC-value方法包括了两个步骤，首先，用C-value方法计算词汇的出现频率测量，找出多词候选术语，然后利用NC-value方法根据词的上下文信息，最终确定要抽取的术语。近年来，机器学习的方法[15]是这类基于语言学知识与统计学原理结合的抽取方法的一个重要发展方向，并取得了较好的抽取效果，它主要通过利用计算机对先前知识进行学习（训练），利用这些训练的经验来对后续的文本进行相应的抽取，得出准确术语。
2 关联规则方法及其抽取术语的可行性分析
2.1 关联规则的基本原理
韩家炜在《数据挖掘概念与技术》一书中给出了关联规则的确切定义[16]：
项的集合I={I1，I2，I3，…，Im }，数据库中事务的集合T={t1，t2，t3，…，tn }，每个事务ti则是项的集合，即 ti？哿I。若X→Y，满足X？奂I，Y？奂I，且X∩Y=？准，则X→Y为T中的关联规则。
关联规则中，支持度（Support）是指T中的事务同时包含X、Y的百分比：
Support（X→Y）=P（XY）
置信度（Confidence）是指T中事务已经包含X的情况下，包含Y的百分比：
Confidence（X→Y）=P（Y│X）=P（XY）/P（X）
若关联规则X→Y，同时满足支持度大于最小支持度Support（X→Y）>minSupport和置信度大于最小置信度Confidence（X→Y）>minConfidence，则认为关联规则X→Y是有趣的，即为强关联规则，其中，最小支持度和最小置信度的阈值均人为设定。关联规则挖掘就是在事务集合中挖掘强关联规则。
关联规则关注两个事项的共同出现，或者说在前驱出现的条件下，后继也出现，其经典应用是发现顾客的购买规律（如沃尔玛超市发现的“啤酒和纸尿裤”的购买规律），在图书馆中进行书目推荐[17]以及火灾分析[18]、交通事故处理[19]、森林病害虫预测[20]和肺肠合病医案用药规律研究[21]等。
2.2 术语构成基本原理
术语是特定领域中概念的语言表示，它可以是字、词语或者字母与数码符号。按照术语的构成，可将术语分为简单术语和复杂术语。简单术语，就是指仅由一个单词构成的术语。例如：“信息（information）”、“天（sky）”、“雨（rain）”等。这样的简单术语不能再分解为更小的具有独立含义的单元。复杂术语，则是指由两个或更多单词或语素按照一定的语法或语义结构组成的术语。例如：“信息检索（information retrieval）”、“复杂系统（complex system）”、“计算机系统理论（computer system theory）”等，其中“信息检索（information retrieval）”是由“信息（information）”和“检索（retrieval）”构成，“复杂系统（complex system）”是由“复杂（complex）”和“系统（system）”构成。
2.3 关联规则抽取术语的适用性
从以上关联规则的定义可以看出，事务组合（X→Y）满足最小的支持度和置信度，就可以称之为“规则”，这就说明关联规则中强调的是事项（即上述定义中的“项”In）的共同出现，或者说在前驱出现的条件下后继出现。
术语的基本构成方式与关联规则方法关注的内容具有一定的契合点，例如，如果我们把构成复杂术语的每个单词或语素（以下简称词汇）看作是“项”，那么，能共同构成一个复杂术语的若干个词汇（项）必定会同时出现，因而可以根据词汇之间的关联程度来达到提取复杂术语的目的。不过，与一般的关联规则发现中仅强调“共现”有所不同，构成复杂术语的词汇之间必须具备位置相邻性，而不是单纯的“共现”，也就是说，在经典的关联规则方法中引入项之间的邻接性限定，是关联规则应用于术语抽取的关键。
由此，术语抽取中的关联规则可以表述为：若词汇X与词汇Y依次邻接出现，且满足最小的支持度和最小的置信度，则可以认为词汇X和词汇Y按照XY的次序，组成复杂术语。其中，关键的两个参数即支持度和置信度可以这样理解，支持度体现了词汇邻接出现的频率，支持度高，说明词汇邻接组合出现的次数多，这样邻接出现的词汇往往就会组成一个术语。置信度是指在词汇X出现的条件下，词汇Y紧跟其后出现的概率，或者在词汇Y出现的条件下，词汇X恰好出现它前面的概率，置信度越高，说明词汇X和词汇Y的组成一个复杂术语的可能性越大。所以，可以这样给支持度和置信度下定义：
支持度为词汇X和词汇Y依次邻接出现的概率，即：
support=P（XY）=count（XY）/N
其中，N为用于术语抽取的文本的句数。
置信度为在词汇X出现的条件下，词汇Y紧跟X后出现的概率或词汇Y出现的条件下，词汇X和词汇Y依次邻接出现的概率，即
confidence1=P（Y│X）=P（XY）/P（X）
或
confidence2=P（X│Y）=P（XY）/P（Y）
如此，一个复杂术语的抽取将涉及到一个置信度的集合C，如果抽取者更重视召回率（Recall），置信度可取集合中的最大值（confidence=max（C）），并将它与预定的最小置信度比较，这样的取值强调在置信度集合C中“存在”比最小置信度大的值，能够保证召回率。
如果抽取者更重视准确率（Precision），置信度可取集合中的最小值（confidence=min（C）），并将它与预定的最小置信度比较，这样的取值强调在置信度集合C中的“所有”值均比最小置信度大，能够保证准确率。
如果抽取者的要求比较苛刻，需要召回率和准确率均较高，但由于召回率和准确率呈反比例关系，取最大值和最小值的方法均不可取，必须选取最大值和最小值之间的合理的数值，这个值可以为置信度集合的算数平均数、几何平均数以及中位数等。
这里给出的置信度的定义，与经典的关联规则不同，它不涉及“前驱”和“后继”的概念，在术语抽取中区分词汇的“前驱”和“后继”的意义不大。这里的置信度是指多个词汇组成新的复杂术语的可能性的大小。
3 实验结果及分析
3.1 实验基本条件与内容
实验的基本条件如表1所示。
3.2 用关联规则方法进行术语抽取的实验过程及结果
（1）基本结果展示
表2是利用关联规则FT-tree算法，对图书馆学情报学领域中英文文摘进行术语抽取所得到的部分术语。
（2）中英文对照实验
从理论上讲，中英文在利用关联规则进行抽取时仅有预处理部分有所不同。中文不像英文那样词与词之间存在着空格，因此在预处理时需要对中文进行分词。在中英文对照实验中，对图书馆与情报学领域的全部中英文数据进行了抽取，实验使用了49种最小支持度和最小置信度组合，得到了49种抽取结果，表3列出了这49种抽取结果中最高的F-measure值、召回率值或准确率值（最高项用阴影标识）及它们对应的支持度与置信度取值。
从表3中可以看出，在应用关联规则进行术语抽取时，可以通过合理配置参数（最小支持度和最小置信度）而得到满意的效果，而且，无论是对于中文文本，还是英文文本，都可以通过配置不同的最小支持度和最小置信度来获得较好的抽取效果。这说明，用关联规则方法进行术语抽取不存在语言依赖，如果不考虑不同语言在预处理阶段有较大的差别，关联规则方法可以用于抽取任何一种语言中的术语。
（3）数据量大小对照实验
分别以10条、100条、1000条图书馆学与情报学的英文数据作为抽取对象，每一种数据量都可以得到49种抽取结果，表4列出了这些结果中最高F-measure值、召回率值或准确率值（最高项用阴影标识）及它们对应的支持度与置信度取值。
从表4中可以看出，关联规则方法不适用对数据量过小的数据集进行抽取，相反，数据量越大，抽取效果越好，而且，对于不同数量的数据集，同样可以通过配置不同的参数来达到用户最满意的效果。
（4）不同学科数据对照实验
实验过程中，除图书馆与情报学数据之外，还增加了数学和地球科学的数据，分别对这三种学科的数据进行术语抽取，对每一个学科的抽取结果，做与表3或表4相同的统计分析，得到表5的结果。
从表5可以看出，用关联规则方法对各个学科的文本进行抽取，均能得到较好的结果，这说明，关联规则应用于术语抽取不存在学科依赖，即使用关联规则进行术语抽取不存在学科限制。在本实验中，由于不同的学科具有不同的数据量，同时，各个学科的术语结构、已知术语等有所区别，因而达到最佳抽取结果的参数配置（最小支持度和最小置信度）也有所不同，这再次证明，合理的参数配置是将关联规则应用于术语抽取的关键问题之一。
3.3 关联规则方法与其他方法的对比实验及结果
以图书馆学与情报学领域1000条英文文摘数据为处理对象，分别用互信息（基于统计学原理方法）、Justeson & Katz 算法（基于语言学知识方法）、C-value算法（基于语言学和统计学结合方法）以及关联规则的FT-tree算法进行术语抽取，以下是实验过程中算法的实现难度、算法所需资源以及算法抽取效果等三方面比较结果。
（1）算法实现难度比较
算法实现难度是算法实用性的标志之一。表6列出了实验中使用的四种算法的核心代码量、核心内容和人为参与情况。
从表6可以看出，关联规则有着较小的代码量，但各个算法的核心代码量不存在数量级上的明显差别。在需要加载的内容方面，C-value/NC-value和Justeson & Katz算法需要加载规则，这类算法需要很强的先验知识，关联规则和互信息方法则不需要过多的规则，仅在在预处理部分做停用词拆分和已知术语切分即可。值得一提的是，四种算法均必须人为控制参数，而且这些参数都是至关重要的。从总体上看，关联规则方法拥有较小的代码量，较简单的抽取步骤和少量必须的人为参与，因此，关联规则应用于术语抽取有着易于实现的优势。
（2）算法所需资源比较
运行算法时所需计算机资源的多少，是算法可用性的重要表现。计算机资源最重要的是时间和空间资源。以1000条图书馆学与情报学英文数据（大小为1028kb）为处理对象，统计各算法在术语抽取时的时间消耗以及最大内存占用量，结果如表7所示。
从表7中可以看出，FT-tree（关联规则）和互信息算法具有明显的运行时间优势，C-value/NC-value和Justeson & Katz算法除进行基本词频统计和参数控制外还需要进行规则的加载和筛选，因而时间消耗较大。在占用内存方面，FT-tree（关联规则）和互信息算法同样有明显优势，C-value/NC-value和Justeson & Katz算法所使用的规则库必需常驻内存，同时，为了满足规则匹配的需要，这两种算法还要求对每个词进行词性的标注等，所以其所需内存较大。这一结果表明，关联规则算法在算法的可用性即占用计算机资源方面具有一定优势。
（3）算法抽取效果比较
算法的抽取效果是评价算法优劣的重要方面。此部分实验，是中英文对照实验中的运行结果。算法的参数配置，关联规则选取本节数据量大小对照实验运行结果F-measure值最高的一组支持度和置信度，其他算法的参数配置来源于相应的参考文献[1，13，14]。算法的抽取效果从准确率、召回率和F-measure三个指标进行评价，结果如表8所示。
从表8中可以看出， Justeson & Katz算法的准确率要高于其他算法，C-value/NC-value算法和关联规则算法的准确率次之，互信息方法的准确率最低。而实验结果的召回率与准确率结果相反，Justeson & Katz算法的召回率最低，互信息方法的召回率达到了1。F-measure是综合评价准确率和召回率的指标，C-value/NC-value算法的F-measure值最高，其次为关联规则算法以及Justeson & Katz算法，互信息算法的F-measure值最低。综合来看，就1000条的数据量来讲，关联规则算法取得了不错的抽取效果，但还有一定的进步空间。
4 结语
本文讨论了基于关联规则的复杂术语抽取方法，从理论上看，关联规则的基本原理决定了它在充分解决“序”的条件下，可以很好的完成术语的识别和抽取问题。从实践上看，关联规则的方法的确可以正确抽取出术语，而且，通过与现有算法的比较，可以发现，关联规则在算法实现难度和占用资源方面具有非常明显的优势。而且，关联规则在术语抽取时没有学科和语言的依赖性，这一点，是基于规则的方法所不能比拟的。我们的下一步工作将进一步分析如何合理配置参数以及各种关联规则算法用于术语抽取时的特点，包括效率、效果和限制条件。
参考文献：
[1]Justeson J， Katz S. Technical Terminology： some Linguistic Properties and an Algorithm for Identification in Text [J].Natural Language Engineering，1995，1（1）：9-27.
[2]Jacquemin C. Recycling Terms into a Partial Parser[C].Proceedings of NALP’94，1994：113-118.
[3]Dagan I， Church K. Termight： Identifying and Translating Technical Terminology[C]. 4th Conference on Applied Natural Language Processing，1994：34-40.
[4]Andy L. Automatic Recognition of Complex Terms： Problems and the TERMINO Solution [J]. In Terminology： Applications in Interdisciplinary Communication， 1994，1（1）：147-170.
[5]Arppe A.Term Extraction from Unrestricted Text [C].10th Nordic Conference of Computational Linguistics，1995.
[6]Chengxiang Z， Xiang T， Frayling MN. Evaluation of Syntactic Phrase Index CLARIT[C].Proceedings of TREC
-5，1996.
[7]Ulrich H， Jauss S， Katja K. Term Extration with Standard Tools for Corpus Exploration： Experience from German[C].4th International Congress on Terminology and Knowledge Engieering，1996：139-150.
[8]Bourigault D， Mullier GI， Gros C. Lexter， A Natural Language Processing Tool for Terminology Extraction[C].7th EUEALEX International Congress on Lexicography，1996：771-779.
[9]Naulleau E. Profile-guided Terminology Extraction[C].the TKE’99： Terminology and Knowledge Engineering，1999：222-240.
[10]Herman E， Chomsky N. Term Extraction[EB/OL].[2014-07-02]. http：//fivefilters.org/term-extraction/.
[11]Sclano F， Velardi P. Termextractor： a web application to learnthe shared terminology of emergentweb communities[C].the 3rd International Coference on Interoperability for Enterprise Software and Applications，2007.
[12]Church K，Gale W.Inverse Document Frequency （IDF）： A Measure of Deviations from Poisson[C].the 3rd Workshop on Very Large Corpora. Cambridge， Massachusetts， USA，1995：121-130.
[13]Frantzi K， Ananiadou S. Extracting Nested Collocations[C]. Proceedings of the 16thinternational conference on computational linguistics，Coling 96，1996：41-46.
[14]Frantzi K， Ananiadou S， Mima H.Automatic recognition of multi-word terms： the C-value/NC-value method [J].Internation Journal on Digital Libraries，2000，
3（2）：115-130.
[15]辛欣，李涓子. 文本信息抽取平台的设计与实现——基于机器学习[A].第七届中文信息处理国际会议论文集[C].中国中文信息学会，2007：7.
[16]韩家炜.数据挖掘概念与技术[M].北京：机械工业出版社，2013.
[17]陈定权，朱维凤. 关联规则与图书馆书目推荐[J]. 情报理论与实践，2009，（6）：81-84.
[18]徐晓楠，张晓珺，张伟等. 北京市火灾关联规则分析[J]. 安全与环境学报，2010，（3）：151-156.
[19]罗五明，韩平阳. 车辆事故关联规则的提取[J]. 交通与计算机，2003，（2）：17-19.
[20]任长伟，尚艳英，曹彦荣. 基于GIS与空间关联规则数据挖掘在森林病虫害预测中的应用初探[A].中国地理信息系统协会.第四届海峡两岸GIS发展研讨会暨中国GIS协会第十届年会论文集[C]，2006：6.
[21]林炜烁，纪立金， 高思华. 基于关联规则的肺肠合病医案用药规律探索[J]. 世界中医药，2014，（4）：401-404.
[22]Zhang Z， Iria J， Brewster C， Ciravegna F.Java Automatic Term Extraction toolkit[EB/OL]. [2017-07-02].https：//jatetoolkit.googlecode.com/svn/trunk/2.0Alpha.
关联规则挖掘技术在商场中的应用 篇5
随着商场信息化的建设, 商场积累了大量的销售数据。面对海量销售数据和大量繁杂信息, 如何从数据海洋中提取有价值的知识, 为商场的管理提供决策支持, 提高商场的竞争力, 已经成为商场管理者关注的热点。要解决这一问题, 传统的数据库技术已经很难满足商场管理者的需求。在这一背景下, 数据挖掘技术应运而生。数据挖掘技术就是从大量的数据中挖掘出有效的、新颖的和潜在有用的知识, 目的是为企业的管理决策提供支持。
在数据挖掘的知识模式中, 关联规则挖掘是非常重要的一种, 也是非常活跃的一个分支。关联规则挖掘能发现大量数据中项集之间有趣的关联或相关关系。随着大量数据不断地收集和存储, 许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系, 可以帮助许多商务决策的制定, 如分类设计、交叉购物和促销分析。关联规则可以广泛应用到商场、金融、政府、通信等各个领域。
二、关联规则数据挖掘技术
1.关联规则的定义及问题的描述
假设是项的集合。设任务相关的数据D是数据库事务的集合, 其中每个事务T是项的集合, 使得。每一个事务有一个标识符, 称作TID。设A是一个项集, 若事务T包含A, 则一定有。这里用下面的表格来说明:
定义1 关联规则采掘的数据集记为D (D为事务数据库) , , 为一个事务;tk中的元素称为项目 (Item) 。
定义2 设是D中全体项目组成的集合, I的任何子集A称为D中的项目集 (itemset) , 称集合A为k项目集。设tk和A分别为D中的事务和项目集, 如果, 称事务tk包含项目集A。
定义3 数据集D中包含项目集A的事务数称为项目集A的支持数, 记作。D中事务总数记作|D|, 项目集A的支持度, 记作:
若support (A) 大于或等于用户指定的最小支持度minsupport, 则称A为频繁项目集, 否则称A为非频繁项目集。
定义4 关联规则是形如的蕴涵式, 其中, 并且。规则在事务集D中出现, 具有支持度s, 其中s是D中事务包含 (即A和B二者) 的百分比, 其是概率。规则在事务集D中具有置信度c, 如果D中包含A的事务的同时也包含B的百分比是c, 这是条件概率P (B|A) , 即:
支持度和置信度是描述关联规则的两个重要概念, 前者用于衡量关联规则在整个数据集中的统计重要性, 后者用于衡量关联规则的可信程度。一般来说, 只有支持度和置信度均较高的关联规则才可能是用户感兴趣的、有用的关联规则。
通常用户根据采掘需要指定最小支持度 (记为minsupport) 和最小置信度 (记为minconfidence) 。前者描述了关联规则的最低重要程度, 后者规定了关联规则必须满足的最低可靠性。
定义5 如果supportminsupport且confidenceminconfidence, 称关联规则为强规则, 否则称关联规则为弱规则。
关联规则的挖掘问题就是在D中求解所有支持度和置信度均分别超过minsupport和minconfidence的强关联规则。
2.关联规则问题的挖掘过程
关联规则挖掘在需要挖掘的源数据准备好的基础上, 需要以下过程完成挖掘任务:
(1) 找出所有频繁项集:
即所有支持度不低于用户给定的最小支持度的项目集。
(2) 由频繁项集产生强关联规则:
即从⑴得到的频繁项集中开采置信度不小于用户规定的最小置信度的规则。
(3) 结果评价和解释:
根据用户需求, 对挖掘的结果进行评价, 选择满足要求的模型, 结合实际问题, 做出评价和解释。
其中⑴是关联规则挖掘算法的核心, 挖掘关联规则的总体性能由第一步决定。要求解第一个子问题, 往往需要多次扫描数据库D, 这意味着大量的时间将花在数据库扫描和I/O操作上。现有的各种关联规则采掘算法大致可分为搜索算法、层次算法、数据集划分算法、抽样算法等。
三、关联规则挖掘在商场中的应用
由于商场行业的特殊性, 销售管理信息系统的成熟和普及, 商场积累了大量的销售数据。通过关联规则挖掘技术, 从销售数据中, 我们可以根据商场管理者关心的问题 (如每种商品的最佳订货量、商品的最佳组合摆放方式、顾客需求等) 挖掘出商品的关联性、顾客的购物行为规则、市场开拓和趋势分析、促销活动分析、销售人员业绩评价等知识。下面, 以商品关联规则分析和销售人员业绩评价分析为例说明关联规则挖掘在商场中的应用。
1. 商品关联规则挖掘分析
下面以一个例子说明, 设I={milk, bread, orange, banana}, 共四种商品属性, 在某个商场中, 存在表2所示的销售记录。其中的每条记录的含义是一次购买行为所购买的商品。
根据销售记录, 我们将所有属性项为1个, 2个和3个的属性集合以及相应的支持度列举在表3中。
假设minsupport=35%, minconfidence=50%, 则频繁项目集包括{{bread}, {milk}, {orange}, {banana}, {bread, milk}, {bread, orange}, {bread, banana}, {orange, banana}}, 可以得到表4所示的规则。
根据上述关联规则, 可以发现超市顾客的购买习惯和偏好, 销售管理人员可采取如下措施:如商场市中60%的客户在购买商品bread的同时, 有75%会购买milk, 这样可以将商品bread、milk放置在一起, 便于顾客购买, 或者说顾客买了bread后, 销售人员向顾客推荐milk, 尤其是新的产品促销;另外, 还可以根据bread和milk购买量和比例, 来确定进货的情况。这样商场可以扩大销售额, 提高了服务水平。
2. 关联规则挖掘在评价销售人员能力方面的应用
一个商场的销售增长率, 赢利能力, 除了与产品质量, 市场供求有直接联系外, 与公司销售人员的能力也有密切关系。如某公司对50名销售人员进行测试, 得到他们各方面的测试成绩, 有创造力成绩 (用X1表示) , 客观推理成绩 (用X2表示) , 想象力成绩 (用X3表示) , 以及每个销售人员的销售增长率 (用X4表示) , 数据格式如下: (只写出了部分数据)
根据X1、X2、X3、X4的关联分析, 我们得到以下规则:
(1) 的support=8%, confidence=89.6%
(2) 的support=4%, confidence=95.3%
规则 (1) 说明销售人员的创造力成绩为14至18, 客观推理成绩为18至20时, 其销售增长率大于等于105的可能性是89.6%, 支持度为8%;规则 (2) 说明销售人员的创造力成绩为14至18, 客观推理成绩为18至20, 抽象推理成绩为10至12时, 其销售增长率大于等于105的可能性是95.3%, 支持度为4%。
这样, 在选择销售人员时, 可以他们的这三种成绩作为依据, 从而科学地决定人选。销售人员的能力还要从多方面综合考虑, 我们仅就获得的这几种成绩来挖掘它们与销售增长率之间的关联规则, 随着多方面大量数据的获得, 数据挖掘工具必将带来更准确有价值的信息。
四、结束语
数据挖掘是一个飞速发展的领域, 不断有新的技术和系统出现。而如何将这一技术应用于实际工作中, 还需要做更深一步的开发与研究, 作为一个年轻的和很有希望的领域, 数据挖掘依然面临着很大挑战和许多亟待解决的问题, 本文仅对关联规则挖掘技术进行了讨论, 并研究了在商场中的应用。随着关联规则数据挖掘技的研, 其必将有更广阔的应用领域。
摘要：在关联规则数据挖掘概念的基础上, 分析了关联规则挖掘技术实施的步骤, 并从商品关联挖掘分析、销售营业员评价挖掘分析两个方面提出了关联规则数据挖掘技术在商场中的应用。
关键词：数据挖掘,关联规则,商场,应用
参考文献
[1]毛国君段立娟:数据挖掘原理与算法[M].北京:清华大学出版社, 2005
[2]高洪深:决策支持系统 (DSS) :理论·方法·案例[M], 北京:清华大学出版社, 2000
[3]王珊:数据仓库技术与联机分析处理[M].科学出版社, 1998
关联规则技术 篇6
一、关联规则的定义
关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品 (项) 之间的联系, 找出顾客购买行为模式, 如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。
二、关联规则挖掘的过程
关联规则挖掘过程主要包含两个阶段:关联规则挖掘的第一阶段必须从原始资料集合中, 找出所有高频项目组 (Large Itemsets) 。高频的意思是指某一项目组出现的频率相对于所有记录而言, 必须达到某一水平。关联规则挖掘的第二阶段是要产生关联规则 (Association Rules) 。根据定义, 这些规则必须满足最小支持度和最小可信度。
三、关联规则分类
1. 基于规则中处理的变量的类别, 关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的, 它显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来, 对数值型字段进行处理, 将其进行动态的分割, 或者直接对原始的数据进行处理。
2. 基于规则中数据的抽象层次, 可以分为单层关联规则和多层关联规则。在单层的关联规则中, 所有的变量都没有考虑到现实的数据是具有多个不同的层次的;而在多层的关联规则中, 对数据的多层性已经进行了充分的考虑。
3. 基于规则中涉及到的数据的维数, 关联规则可以分为单维的和多维的。在单维的关联规则中, 我们只涉及到数据的一个维;而在多维的关联规则中, 要处理的数据将会涉及多个维。
四、关联规则挖掘相关算法
1. Apriori算法:
使用候选项集找频繁项集。Aprior算法是关联规则挖掘的基本算法, 是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。首先找出所有的频集, 这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则, 这些规则必须满足最小支持度和最小可信度。
2. 基于划分的算法。
Savasere等设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块, 每次单独考虑一个分块并对它生成所有的频集, 然后把产生的频集合并, 用来生成所有可能的频集, 最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存, 每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的, 可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后, 处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈;而另一方面, 每个独立的处理器生成频集的时间也是一个瓶颈。
3. FP-树频集算法。
针对Apriori算法的固有缺陷, J Han等提出了不产生候选挖掘频繁项集的方法:FP-树频集算法。采用分而治之的策略, 在经过第一遍扫描之后, 把数据库中的频集压缩进一棵频繁模式树 (FP-tree) , 同时依然保留其中的关联信息, 随后再将FP-tree分化成一些条件库, 每个库和一个长度为1的频集相关, 然后再对这些条件库分别进行挖掘。当原始数据量很大的时候, 也可以结合划分的方法, 使得一个FP-tree可以放入主存中。实验表明, FP-growth对不同长度的规则都有很好的适应性, 同时在效率上较之Apriori算法有巨大的提高。
五、关联规则应用领域
关联技术不但在商业分析中得到了广泛的应用, 在其它领域也得到了应用, 包括工程、医疗保健、金融证券分析、电信和保险业的错误校验等。它的主要挖掘对象是事务数据库。关联挖掘技术在西方主要应用于金融行业企业中, 可以成功预测银行客户需求。一旦获得了这些信息, 银行就可以改善自身营销。另外, 关联规则也可以服务于cross-sale (交叉销售) 。交叉销售是一种行销技巧, 它是指向顾客推销与其已有消费有关的产品与服务。通过分析老顾客的购买记录, 了解他们的产品消费偏好, 给他们提供其它产品的优惠及服务, 这样不但能留住他们还可以使他们逐渐熟悉另外的产品, 公司从而以尽快的速度获得利润。
摘要：数据挖掘技术是日前广泛研究的数据库技术, 关联规则是表示数据库中一组对象之间某种关联关系的规则。本文简要介绍了关联规则挖掘的相关理论和概念、Apriori算法, 最后介绍了关联规则数据挖掘的应用情况。
关键词：关联规则,数据挖掘,Apriori算法,应用
参考文献
[1]David Hand, Padhraic Smyth.张银奎, 廖丽, 宋俊等译.数据挖掘原理[M].北京:机械工业出版社.2003 (4) .
[2]秦亮曦, 史忠植.关联规则研究综述[J].广西大学学报:自然科学版.2005 (4) .
关联规则技术 篇7
在竞争日趋激烈的商品销售中, 促销活动正扮演着越来越重要的角色。促销活动一直贯穿于商品销售过程之中。合理的促销活动曾经帮助商家创下了辉煌的销售成绩, 但同时不合理的促销活动也屡见不鲜。一些花样百出的促销活动, 往往对于商品的宣传或销售业绩的提升并没有起到实质性的作用, 并且还造成了促销成本的极大浪费。而随着时代的不断发展和消费群体及消费习惯的变化, 促销活动也出现了新的特点:
(一) 消费人群精确化
现在的促销对象不再是针对整个大众化的人群, 而是把消费对象进行进一步的细化。根据不同的消费群体的消费特征和消费习惯, 设计特定促销方案, 做到了精确化促销;使促销活动的宣传费用、组织实施费用发挥得更加有效, 促销活动的效果也大大增强。
(二) 产品销售关联化
通过对消费者需求的不断分析和研究, 发现越来越多的商品之间呈现较强的关联性。同时, 随着互联网络的不断发展和通信平台的升级完善, 即使是不相关的商品之间都能够通过庞大的信息平台实现联盟。通过厂商之间以及品牌之间的联合促销代替原来的单独促销比较, 能够对市场产生更大的合力。联合促销可以对各个单独的商品资源进行重新整合, 打造多赢的市场格局。
(三) 促销活动战略化
随着市场经济的不断发展, 市场竞争日趋激烈, 商家必须思考如何更合理有效地运用促销:既要对抗竞争对手, 争夺市场分额, 又要保证利润空间;既要有效吸引消费者, 又要维护和提升品牌形象;既要保证短期局部利益, 又要考虑长期整体利益。从一开始就应该制定出促销活动的整体规划。
(四) 促销宣传多样化
在促销方法日趋多样的同时, 消费者对促销活动也会有更多的选择, 这就需要商家在进行促销活动前进行充分的宣传, 更需要多个部门配合进行。同时, 还要根据消费者的新变化, 对新的宣传媒体, 比如手机短信、电子邮箱、广播电视、现场广告等综合利用, 从而达到多渠道促销宣传。
面对促销活动的新特点, 我们需要对促销的各个方面进行详细的分析, 并从整体对促销活动进行规划。面对竞争激烈的市场和日趋理性的消费者, 商家应该更详细和精确化的处理促销活动的每一方面, 这就要求商家用更科学的方法来获取促销信息并制定促销策略。面对收集的海量客户信息, 数据挖掘技术给我们提供了发现促销关联和规则的方法, 从而帮助我们进行促销策略的分析和制定。
二、数据挖掘技术的功能
所谓数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的原始数据中提取隐含在其中的、事先未知的、但又是潜在有用的信息和知识的过程。通过数据挖掘技术, 能够找出已有数据之间的潜在联系, 从而促进信息的传递, 对将来的趋势和行为进行预测, 从而很好地支持人们的决策。随着数据处理工具、先进数据库技术及万维网技术的迅速发展, 不断涌现出大量的形式各异、类型复杂的数据, 要处理此类数据以使价值最大化, 引入了Web数据挖掘。
数据挖掘系统需要能够挖掘多种类型的模式, 以满足不同用户的需求和应用。其中的频繁模式在商业统计分析中起到了巨大的作用。频繁模式是在数据中频繁出现的模式, 包括项集、子序列和子结构三种类型。挖掘频繁模式能发现数据中的有趣的关联和相关, 其常用的分析方法有以下几种:
第一, 关联规则挖掘技术。Web数据挖掘中数据关联规则的发现是找到客户对网站上各种文件之间访问的相互联系。比如用户之间、页面之间以及用户浏览页面和网上行为之间的潜在关系, 通过关联挖掘可以从杂乱无规则的客户信息中挖掘出隐含的有用信息, 有利于企业更好地组织站点。
第二, 聚类分析技术。在电子商务中, 聚类多指客户群体聚类和Web网页聚类, Web网页聚类提供有针对性的网络服务应用, 它主要帮助是市场分析人员从客户数据仓库中发现不同购买模式的客户群, 通过聚类分析可以使电子商务组织者更好的了解客户。
第三, 分类分析技术。分类时建立模型的数据对象的类别是已知的, 可挖掘出某些共同的特性, 而这一特性可对新添加到数据库里的数据项进行分类。在Web数据挖掘中, 分类技术可以得到用户个人信息、共同的访问模式以及访问某一服务器文件的用户特征。
第四, 统计分析方法。通过对Session文件的分析, 可以对感兴趣的信息进行统计, 一般包括各种统计数据, 如最频繁访问的N个页面、每页平均浏览时间、网址路径平均访问长度等, 也可能涉及一些关于限制的错误分析, 如统计非法IP、无效URI和未授权访问等, 这些信息对于提高系统性能, 加强网站安全起到辅助决策作用。
三、使用数据挖掘技术进行促销决策
根据上面介绍的数据挖掘技术, 现提出一种基于关联分析挖掘频繁模式的促销策划方案。其具体步骤如下:
(一) 明确促销目的
常见的促销目的有:增加铺货量;扩大销量;新品上市;处理库存;对抗竞争。概括起来促销的目的就是增加销量和推荐产品。在明确了促销目的后, 待销售的商品也就随之确定。
(二) 锁定目标人群
由于每一类人群的购物喜好和消费习惯都不相同, 商家就必须针对不同的商品锁定相应的目标人群。当明确了待促销的商品后, 我们可以通过数据挖掘技术对以往的销售记录进行挖掘, 找出该类商品的销售规则, 从而锁定目标人群。
在挖掘目标人群时, 首先要根据该商品的特性设定需达到的参数, 如支持度support、置信度confidence等。再由销售记录中顾客的详细信息中选取感兴趣的若干属性进行挖掘, 找出与该商品相关的多维频繁项集。从得到的频繁项集中的顾客属性锁定消费人群。例如, 当确定要对商品A进行促销, 而感兴趣的顾客属性是顾客的年龄段age和收入income (也可根据需要选取或添加其他属性) , 则可把待挖掘模式设定为:
其中, X表示顾客的姓名或ID号;value表示该属性的值;buy属性指明的是所购买的商品, 这里都选定为A商品;Support为支持度, 表示满足该模式的事务在所有参与挖掘的事务中所占的百分比, 如上式support=10%表示100个事务中有10个满足上述条件;confi-dence为置信度, 表示该规则的强度, 如上式confidence=50%, 表示满足规则左端条件时有50%的可能会同时满足规则的右端条件。
根据挖掘模式中的属性项构造销售事务的数据立方体。由于选取了age和income两个属性, 所以要构造2-维立方体如图1所示 (如果选取属性较多要构造相应的多维立方体) 。
对每个由这两个属性划分的小立方体进行赋值, 该值达到预先设定的参数的小立方体将被进行标识, 根据标识的立方体的位置先进行合, 简化挖掘出的规则, 最终锁定对商品A满足要求的人群。锁定目标人群完成。
(三) 确定促销时间
促销时间可根据两种规则模式进行挖掘, 一种模式是针对待销商品A进行挖掘, 找出该商品的销售旺季, 如季度quarter、月份month等。其挖掘模式可设定为:
另一种模式是针对上面挖掘出的目标人群, 挖掘其习惯的消费发生时间, 如周中还是周末weekend (值yes/no) , 白天还是夜晚night (值yes/no) , 商场还是网络以及哪一个时间段time等。其挖掘模式可设定为:
根据模式中的属性构造数据立方体, 挖掘确定促销进行的时间。
(四) 选取促销策略
具体的促销策略可谓五花八门, 层出不穷, 常用的促销策略有:打折、赠品、积分、抽奖、联合销售。总之, 所有的促销策略都是变向的增加商品的附加价值。这里主要讨论赠品和联合销售。这两种促销策略都是靠除本商品外的附加商品来吸引消费者, 那么赠品和搭配商品的选取就显得尤为重要。我们可以通过数据挖掘的单维关联规则模式进行挖掘。
其挖掘模式可设为:
其挖掘结果可能为:buy (X, A) →buy (X, B) ∧buy (X, C) , 此规则说明购买商品A的顾客很可能同时购买商品B和C。那么如果促销目的是为了提高待销商品的销量, 则可以选取商品B或C作为商品A的赠品;或者对商品A、B、C进行联合销售。通过商品B、C提高商品A的销量。如果促销的目的是推荐新产品D与A属于同一类商品, 也可以根据该规则, 将其作为商品B或C的赠品等方法。
(五) 促销策略检验
对挖掘出来的关联规则进行相关分析, 通过计算各商品之间的提升度lift来判断设计出来的策略是否合理。如果购买商品A和购买商品B这两个事件是互不影响的, 则称商品A和B不依赖, 即P (AUB) =P (A) P (B) ;否则就称A和B是依赖的, 我们用提升度lift来度量其依赖关系:
若lift (A, B) =1时, 说明商品A和B的销售相互之间没有影响;若lift (A, B) >1, 说明商品A和B的销售是正相关, 可以相互促进;而当lift (A, B) <1, 说明商品A和B的销售是负相关, 一种商品的销售会引起另一种销量的降低。并且, 当一个商家针对多个商品进行促销时, 还可通过该检验分析各促销活动之间是否会发生冲突而引起销量的降低。
四、总结
数据挖掘技术能通过挖掘各种频繁模式找到各种销售事务之间的关联, 从而商家从海量数据中识别客户的购买行为特征, 发现客户购买模式和趋势。它基本可以满足新形势下促销活动精确化、数据化以及战略化的要求。数据挖掘丰富的挖掘模式以及多样的分析方法还可以从另外的角度对促销活动提供帮助, 甚至挖掘并延伸出更新颖的促销形式, 还有待于进一步的研究和发现。
摘要：促销活动在现今的商品销售中发挥着巨大的作用。随着时代的发展, 促销活动也展示出了新的趋势, 这就要求商家必须对促销活动进行科学和量化的分析, 制定出更精确和具有针对性的策略。文章通过对数据挖掘技术的研究, 提出一种基于关联规则发现频繁模式的方法, 进行促销决策。
关键词：促销,数据挖掘,关联规则
参考文献
[1].夏火松, 蔡淑琴.知识管理与市场营销专家知识的分形特征[J].武汉科技学院学报, 2001 (1) .
[2].陈京民.数据仓库与数据挖掘技术[M].电子工业出版社, 2002.
关联规则技术 篇8
关键词：数据挖掘,模糊关联规则,个性化推荐
1绪论
1. 1研究背景及意义
网站的个性化推荐系统是数据挖掘中很重要的一个领域。 随着个性化推荐系统的快速发展, 保存在数据库中的数据量也在快速增长, 数据库中自然保存了大量数据。分析这些数据的是为了可以探索出之前不知道的并且有价值的内容。这些有用的内容不仅能指导商家开发客户购买潜力, 同时提高客户群数量, 也能更好服务客户。最实际的一个例子就是在大型的购物网站中, 获取用户有用的信息。包括: 用户的爱好、页面访问情况、广告点击情况等, 优势在于帮助商家对客户进行分类, 发现和进一步吸引潜在的客户, 使市场销售策略更有效, 获得更大的利润[1]。
1. 2模糊关联规则的概念
模糊关联规则的定义是将模糊理念和数据挖掘技术相结合, 将Apriori算法和包含模糊属性的事务相结合, 制定事务的每个模糊属性分配的数目, 之后将每个属性的数值对应到相关模糊集合中, 目的是找出支持度大于最小支持度的频繁项目集, 通过研究出现的频繁项目集, 得到模糊关联规则, 从而找到用户感兴趣的规则形式。
1. 3模糊关联规则挖掘过程
挖掘过程表示如下: 先进行模糊化处理保存在数据库的数据, 也就是说先设定好每个数量型属性的隶属函数, 再利用模糊集合划分数据属性成为多个语义项, 同时获得每条事务的隶属度取值; 最后挖掘模糊化后的数据库, 找出有意义的规则, 最终展现给用户[2]。
与关联规则类似, 将挖掘过程划分为两个部分: 1利用用户事先设定好最小支持度阈值, 去找到最多的模糊频繁项目集合。2对于每个模糊频繁项目集来说, 都要尽可能找到最多的模糊关联规则, 然后从获得的规则里面筛选出所有支持度和置信度都大于给定值的关联规则, 给用户最大的价值, 呈现更多有用信息。
2推荐系统与模糊关联规则挖掘算法应用
在推荐系统中使用模糊关联规则的原因如下: 可以更直接地展示推荐结果, 而且会以比较容易的方式让用户接受, 另外, 可以轻松发现新的兴趣点, 而且不需知道过多的专业知识。
2. 1挖掘系统框架
本文模糊关联规则框架表示如下。
1) 用户提交挖掘请求。
2) 预处理模块根据提交的请求将数据进行转换。
3) 转换后的数据, 通过模糊关联规则, 建立频繁项目集。 根据设定的置信度, 最后得到关联的内容, 将挖掘结果反馈给用户。
2. 2模糊关联挖掘在推荐系统中的应用
模糊关联规则推荐系统的实现过程如下。
1) 个性化推荐系统将网站数据库中的某段时间内的历史订单数据库导出。
2) 转换导出的数据为模糊关联规则可以进行挖掘的格式。
3) 通过NFAR算法对已经处理好的数据进行挖掘, 生产相应的规则, 导入到网站数据库的关联规则表中。
4) 推荐系统模块按要求从关联规则表中得到相应的商品推荐结果, 从而使用户能看到自己需要的推荐商品。
实验数据是来自大型购物网站的订单表, 数据库中有15 480种库存商品, 数据库中包括100万条以上的记录, 删除事务数据库中一些不相关的数据, 统计了商品销售情况、商品浏览记录、推荐商品浏览和销售情况, 将与订单表相关联的书籍类型表中商品种类属性定义为A、B、C、D 4种, 通过实验分析出4种商品类型之间的关联。这里A为军事类, B为天文学类, C为数理化类, D为社会科学类。
根据以上的实现过程得到第一条模糊关联规则是: 天文学类 ( 大量) = > 军事类 ( 大量) 模糊规则, 全部事务中有33. 0% 的设置值是满足这个规则的, 并且有94. 0 % 的情况是可信的。 意味着天文学和军事类书籍同时出现的概率是33% , 并且用户在购买大量文学类书籍的情况下, 有94% 的情况下会购买大量军事类书籍。为了简化, 本文将这条模糊关联规则输入到推荐系统中, 测试会不会得到合适的推荐。当输入用户购买的天文学类书籍为4时, 提示给用户的信息是: “无推荐建议”; 当输入的天文学类书籍数量为8时, 提示的信息是: “推荐用户购买16本军事类书籍” ( 已经对数字做了四舍五入) 。
这里研究的算法获得了想要的结果, 而且完整性也比较好, 可以证明算法是合理有效的。将模糊关联规则应用于个性化推荐系统是可以使用户得到合适的推荐信息。但是仍然可以更优化关联规则的数量。
2. 3算法的推荐性能分析
本文用查全率 ( Recall) 和准确率 ( Precision) 公式分析推荐结果性能, 查全率定义是推荐信息在用户真正购买中的比重, 准确率定义是推荐产品中用户成交的比重。公式表示如下。
Recall = PReci / N ( PRec为推荐后购买的商品种数, N为商品种类数) 。
Precision = PReci / Reci ( Rec为推荐商品种类数) 。
结合网站数据库中的数据和以上的公式, 论文将数据转换为图表形式分析Fuzzy FP-tree算法和NFAR算法推荐性能比较。如图1性能分析图所示。
实验做了10组, 每组400用户, 从分析图中可以看出, 随着用户数量的增多, 改进后的算法的查全率和准确率均比之前的算法有了很大的增加, 说明了改进后的算法性能有明显提高, 主要是因为新的算法能得到更加合适的固定聚类数目, 推荐精度更高。
参考文献
[1]郑庆华, 刘均, 田锋, 等.Web知识挖掘:理论、方法与应用[M].北京:科学出版社.2010:20.
关联规则技术 篇9
关键词：电子商务；数据挖掘；模糊关联规则；信任评价系统
1引言
电子商务中的信息挖掘一直是人们研究的热点。很多研究数据挖掘的学者纷纷将其研究的成果应用到实际当中，并作为市场预测、市场细分与分类、客户关系管理以及其他商务应用的参考模型。电子商务信息挖掘一般采用的是WEB数据挖掘中的一部分。例如，文献[1]就是利用SVM来进行电子商务中的应用挖掘——网络日志的分析，以提取客户分类及评分。
在电子商务环境中，一个电子商务支撑环境能够产生一个信任值，通过衡量已交付的服务质量以及从顾客和信任管理机构中获得的服务评价。没有任何信任管理机制，许多消费者也许会因为欺骗性的广告而请求了欺骗性的服务。另一方面，一个简单但是不完整的信任管理系统也许让服务提供商有选择性地欺骗顾客（例如，通过给许多低价的交易提供好的服务，但是在高价的交易中欺骗顾客来谋取大量的好处），以及欺骗信任管理机构（例如，通过在信任评价中合谋欺骗）。一些如此的欺骗可能导致服务质量降级，并且给客户带来经济损失。因此，电子商务行业必须有有效的信任管理[2]。
2关联规则的分类
关联规则的一个要求是结果得有透明度和可用性，这些结果是以产品群组规则的形式表示的，它表述了现实的产品和服务是如何组合到一起的。关联规则容易理解，但它们并不总是有用的。
有用的规则包含高质量、可操作的信息。平凡的结果早已被熟悉商业的任何一个人所知晓。平凡规则确实有一个用处，尽管它不是直接的数据挖掘应用。当一个规则应当在该时间100%出现，然后它却没有出现，这种情形可以提供关于数据质量的许多信息。换句话说，不遵循平凡规则的例外情况指出了商业运作、数据收集和处理等可能需要进一步改进的方面。费解的规则似乎没法解释，并且不给出行动过程。
当应用购物篮分析时，许多结果常常是平凡的或费解的。平凡规则再现商业常识，浪费了利用高级分析技术的努力。费解的规则是数据中的偶然事件，是不可操作的。[3]
关联规则有三个度量。支持度反映在交易数据中发现该规则的频繁程度，置信度说明当“如果”部分为真时“那么”部分也为真的频繁程度，而提升度反映该规则预测“那么”部分额相对根本没有规则要好多少。
这样生成的规则可以分成三类：有用的规则阐明可能没有预料到的关系，平凡规则阐明已知（或应该知道）存在的关系，费解的规则没有意义。费解规则常常有很弱的支持度。
3基于模糊关联规则的电子商务评价系统设计
3.1电子商务信任评价系统
一些著名的电子商务网站采用的是集中式信任管理机制[8]。在淘宝，每完成一笔交易之后，买家能够给一个反馈给系统，这个反馈是有关卖家的服务质量的，也许是良、中评或差评。淘宝服务器将这个评分存储在中心管理系统中。它用公式S=P-N来计算出这个反馈的分，其中P表示好评个数，N表示差评个数。淘宝网将这个S值显示在卖家的网页上。另一值R=（P – N）/（P + N）（1 ≥ R ≥ 0）是好评率。如果仅用好评率来作为信任评价的标准是不对的。通过模糊关联规则中，防止一些欺骗。例如，通过给许多低价的交易提供好的服务，但是在高价的交易中欺骗顾客来谋取大量的好处。
规则集相似度可以量化地表示当前的交易状态是否与正常的状态的相似程度，由此可以推断出此次交易的风险程度。并且可以根据其风险程度来进行报警或者提醒。
基于模糊关联规则的电子商务信任评价系统的流程如下图所示。
3.2模糊集和模糊隶属函数的建立
模糊集的建立实际上就是把数据集中的所有属性用模糊属性表示[4]，每个模糊属性包含多个模糊值，每个模糊值有其对应的模糊集。模糊隶属函数用来描述一个确定属性值对于一个模糊属性集的隶属度。一个确定属性值可以隶属于多个模糊值，对应有多个隶属度。
如表1所示交易数据库T={t1，t2，t3，t4}，属性I={num，money}（i1=num，i2=money）。
将每个属性又分别划分为若干个模糊集，对表1所示的数据库，在计算其各数据项隶属度之后数据库被转换为如表2所示。
4结束语
本文从电子商务信任管理中所发现的一些问题，结合现在数据挖掘在电子商务的应用，找到了一种基于模糊集的关联规则算法应用到电子商务信任评价中。在基于信誉的电子商务评价问题中，电子商务的评价往往是通过反馈的信息来完成，但是反馈回来的信息以及交易过程中本身所产生的信息要尽量将其中所隐含的信息挖掘出来，进行一定的分析，就可以得到一些有用的规则。而对于一些平凡的规则，也可以利用其来寻找其中的问题。这个系统还可以在进一步的进行扩展。例如，对规则集进行修正，去掉一些费解的规则，还可以去掉一些冗余的关联规则。这些都可以对整个流程有更好的改进。本文主要是对交易管理中的一些数据属性进行提取和发现规则。
参考文献：
[1] 过蓓蓓，方兆本.基于SVM的Web日志挖掘及潜在客户发现[J].管理工程学报，2010（1）.
[2] Yan Wang and Kwei-Jay Lin.Reputation-Oriented Trustworthy Computing in E-Commerce Environments.
[3] Michael J.A.Berry，Gordon S.Linoff.别荣芳 尹静 邓六爱译.Data Mining Techniques：For Marketing，Sales，and Customer Relationship Management 数据挖掘技术：市场营销、销售与客户关系管理领域应用（原书第2版）[M].北京：机械工业出版社，2006.
[4] 王坤.模糊关联规则挖掘在入侵检测中的应用研究[D].西南交通大学，2006.
[5] 吴君辉，殷肖川，张薇.基于模糊关联规则挖掘改进算法的IDS研究[J].计算机测量与控制..2009.17（11）
[6] 邵峰晶，于忠清，著.数据挖掘原理与算法[M].北京：中国水利水电出版社，2003.
关联规则技术 篇10
随着数据库技术和数据收集技术的发展和广泛应用, 我们身边积累了大量的数据, 如何将这些数据转化成有用的信息和知识变得日益重要起来。
数据挖掘[1] (Data Mining) 就是从大量不完全的、有噪声的、模糊的或者随机的数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则, 这些知识和规则蕴含了数据库中一组对象之间的特定关系, 揭示出一些有用的信息。它融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。
二、关联规则挖掘概述
数据挖掘的方法有分类、聚类、关联分析、预测等, 其中关联分析[2]法是数据挖掘的一个重要方法, 也是目前应用得最为广泛的一个方向。
关联规则的主要目的是寻找数据项之间的有意义、有价值的内在联系。一个事务数据库中的关联规则可以描述如下:
设I={i1, i2, …, in}是项 (Item) 的集合, 包含K个项的项集称K项集 (Itemset) 。设D是数据库事务的集合, 其中每个事务T是项的集合, 使得每个事物有一个标识符, 称作TID。设X是一个项集, 事务T包含X当且仅当关联规则是形如在事务集D中成立, 其中且一般用两个参数描述关联规则的属性:
1、支持度 (Support) 。支持度描述了X和Y这两个项集在所有事务中同时出现的概率。
2、可信度 (Confidence) 。可信度表达的是在出现项集X的事务集D中, 项集Y也同时出现的概率。
事实上人们一般只对满足一定的支持度和置信度的关联规则感兴趣, 因此。为了发现有意义的关联规则, 需要给定两个阀值:最小支持度和最小可信度。这些阀值可以由用户或专家设定。
三、应用背景简析
本文探讨的应用平台是我校的“网络教学应用系统”, 网络教学作为一种新型的教学手段, 教员可以方便地利用平台进行备课和组织实施网络教学;学生可以不受时间、地点和学习形式的限制进行个性化的自主学习。但在网络教学的实施过程中, 由于学生的自我监督能力不足和教员对学员网络学习情况掌控的限制等因素, 导致教学内容与学习状况的脱节, 影响了教学效果。为了研究网络教学用质量的影响因素, 可以利用数据挖掘技术对收集到的教员建设情况和学生学习情况的相关历史数据进行分析, 从而为教员改进教学策略、提升网络教学效果和学校教务部门制定网络教学的相关政策提供强有力的决策支持。
四、关联规则挖掘在军队院校网络教学中的应用
(一) 教员课程建设分析。
网络课程的主讲教员在网络课程中起着专业资源建设、虚拟教室配置和与学生进行教学互动等作用, 教员对本专业课程的建设质量以及与在网上引导学生进行学习、交流的持续性对于学生网络学习的积极性以及对本门专业网络课程的忠诚度起着至关重要的作用。因为只有一门资源丰富、配置齐全、学生在网上学习交流的情况不断得到反馈的网络课程, 才能提升学生学习的兴趣, 保持学生对这门网络课程学习的忠诚度;反之, 我们通过学生对此门网络课程的学习情况也能反映出这门网络课程建设的质量好坏, 从而也能对负责建设这门网络建设的教员对他所承担的网络课程建设任务作出一个评价分析。
例如我们通过数据库里的记录教员教学活动情况的“教员日志” (包括教员姓名、课程名称、最近访问时间、累计在线时间、批阅作业次数、回答问题次数、组织考试次数、批阅试卷份数) 信息表和记录网络课程基本信息的“虚拟教室” (包括课程名、授课教员、课程访问量、章讲数量、习题数量、课程配置指数) 信息表, 以及记录学生学习活动情况的“学员情况” (包括学生姓名、最登录时间、累计在线时间、访问本课程的章讲数、提问发帖、作业考试) 的信息表进行数据准备、数据挖掘 (过程略) , 得出挖掘出来的关联规则例如下:
VisualClassroom (260, “配置指数高”) →Classroom (“访问量高”) [0.3, 0.7]。
我们对此结果进行评价分析:这是一个布尔型关联规则, 该规则的含义是虚拟教室配置丰富完善的, 使该虚拟教室的访问高的这种结果, 其支持度为0.3, 可信度为0.7。它包含的意思是“在260个虚拟教室中, 有30%的访问量高, 其中配置指数数高的虚拟教室访问量高的达到70%”。我们从中可以看出, 一门资源丰富、课程配置齐全的虚拟教室更能吸引学生前来进行网络学习, 而学生访问量高的课程同时也督促建设该网络课程的教员更加积极地维护、完善网络课程, 从而形成良性互动。
(二) 学员学习行为分析。
由于网络学习较课堂实时学习相比, 它给学习者带来学习的灵活性的同时也造成了学习者学习的随意性, 而学生网络学习的情况和结果也是千差万别。因此, 为了教师更好地掌握学生的网络学习情况, 可以借助于相应的数据挖掘工具, 发现数据中隐藏的课程相关规律或模式, 为引导学生积极参与网络学习、改进教师的网络教学策略提供必要的支持。
例如我们通过提取数据库里的记录学生学习在线时间、讨论交流、考试测试等学习信息进行数据挖掘分析, 得出关联规则如下:
Student_log (1000, “在线时间长”) , Student_log (1000, “讨论交流多”) →Study (“考试成绩好”) [0.33, 0.85]。
我们对此结果进行评价分析:该规则的含义是学生网络学习时间长、积极和教员进行讨论交流的, 最后网络考试成绩好的其支持度为0.33, 可信度为0.85。那么它包含的意思是“在1000名学生当中, 有33%的网络考试成绩不错, 而经常上网学习的、积极和教员学习交流互动的, 网络考试成绩好的占85%”。我们由此可以得出结论:要提高学生的学习成绩和网络学习的效果, 首先上网学习的时间要有一定的保证, 其次教员也要积极引导学生进行网络学习的交流互动。
五、小结
将关联规则数据挖掘技术应用于网络教学应用, 开展数据挖掘和知识获取, 可以更好地通过对大量的网络教学信息进行数据分析和挖掘, 为指导学生学习和教员实施网络教学提供一个更加合理的系统模式[5]。它势必会促进学校网络教学的进一步发展, 完善和改进网络教学的模式。
摘要：本文对关联规则数据挖掘的基本概念与方法作了简介, 并结合我校网络教学应用系统为背景, 对基于关联规则的数据挖掘在院校网络教学中的教师建设和学生学习等相关应用作了探讨, 并对其挖掘的结果进行了分析。
关键词：数据挖掘,网络教学,关联规则
参考文献
[1]陈文伟, 黄金才, 赵新昱.数据仓库与数据挖掘技术[M].北京:北京大学出版社, 2002.1-14.
[2]苏新林, 杨建林, 江念南, 粟湘.数据仓库和数据挖掘[M].清华大学出版社, 2006.149-151.