兴趣关联规则的挖掘（精选8篇）
兴趣关联规则的挖掘 篇1
关联规则挖掘是Agrawal等人[1]首先提出的, 此后许多学者对对关联规则的挖掘问题进行了研究, 提出了大量的挖掘算法[2,3,4]。数据挖掘的目的是有效识别出存在于数据库中的有效的、新颖的、具有潜在效用的模式 。支持度和可信度指标是对关联规则在统计意义上的有效性度量, 但它们不能作为有用性的指标[5]。 从数据库中挖掘出的大量规则中, 有一些是没有实际意义的。如何去除这些无意义的规则, 文章给出了关联规则问题的形式化的定义, 讨论支持度/可信度指标存在的问题, 引入了关联规则兴趣度的概念, 提出了一种兴趣关联规则的挖掘算法。实验证明该算法可以避免无意义关联规则的产生。
1 关联规则问题的形式化定义
我们假设I={i1, i2, …, im}是由m个不同的项目组成的集合。给定一个事务数据库D, D中的每一个事务T都是由I中的一些项目组成的集合, 即T⊆I, T有一个唯一的标示符TID, 关联规则就是形如X⇒Y的蕴涵式, 其中X⊆I, Y⊆I, 且X∩Y=ф, X⇒Y的支持度和可信度分别大于用户指定的最小支持度 (minsupp) 和最小可信度 (minconf) 。支持度和可信度的定义如下: X 是I的一个子集, 其补集记为Xc。如果满足X⊆T, 则称事务T支持X。否则, 如果Xc⊆T, 称T支持Xc, 设X是I的一个子集, X的支持度是指数据库D中支持X的记录数与总记录数之比, 记为P (X) , 也可理解为X在D中发生的概率, 蕴涵式X⇒Y的支持度是指数据库中同时支持X和Y的记录数与总记录数之比, 记为SX⇒Y, 则SX⇒Y =P (XY) ;蕴涵式X⇒Y的可信度是指数据库中同时支持X和Y的记录数与支持X的记录数之比, 记为CX⇒Y, 即:
undefined
由此可见关联规则的支持度给出了该规则发生的频度, 其可信度给出了规则发生的强度。
从统计学的角度解释, 关联规则的开采问题就是在事务数据库D中找出具有用户给定的最小支持度和最小可信度的关联规则[6], 可以分解为以下两个问题。
(1) 找出事务数据库D中所有具有用户指定最小支持度的项目集。
(2) 利用频繁项目集生成规则。
2 支持度和可信度存在的问题的提出
已有的研究大多数是基于支持度和可信度框架的完善和改进[2,3,4,7], 在实际应用中, 发现用支持度和可信度为标准来产生关联规则, 会产生大量不相关、甚至是误导的关联规则, 有一些规则即使满足用户指定的最小支持度和可信度, 但仍没有给我们提供有用的信息, 这些规则是没有实际意义的。下面通过例子来说明。
例1:设事务数据库D由以下事务组成:
T1={i1, i2, i3, i4},
T2={i1, i4, i5, i7, i9},
T3={i1, i2, i3, i6, i9},
T4={i0, i1, i2, i3, i8},
T5={i0, i1, i4, i7, i8},
T6={i0, i1, i9},
T7={i0, i1, i2, i3, i6, i7, i9},
T8={i0, i1, i6, i7, i9},
T9={i1, i2, i3, i4, i5, i6, i7, i8},
T10={i1, i4, i5, i6}。
假如最小支持度和可信度分别为45%、90%, 通过计算我们可以得到以下两条规则:
i2 ⇒ i3, 其支持度为50%, 可信度为100%。
i0 ⇒ i1, 其支持度为50%, 可信度为100%。
观察数据库D我们可以发现, i2和i3总是同时出现, 因此i2和i3具有很强的关联性, 所以关联规则i2 ⇒ i3被挖掘出来;而对于i0和i1来说, 不管i0是否出现总有i1出现, 也就是说i0和i1之间没有关联性, 因此规则i0 ⇒ i1是错误的。但在现有的关联规则挖掘算法中, 它仍被挖掘了出来。
下面再来看一个关系数据库的例子。
例2:如下表:
其中im表示男性, iw 表示女性, ie表示工程师, iot表示工程师之外的其他职称。
通过计算支持度和可信度, 我们可以得到以下规则:i1 ⇒ i2, 其支持度为40%, 可信度为66%。然而, 挖掘出的这一条规则并没有提供给我们更多的信息, 因为事先我们从数据库中已经知道了男性职工中大部分是工程师。
从例1和例2中可看出, 一条即使可信度和支持度都很高的规则, 它的实际价值已经没有人们期望的那么高了, 更严重的话, 这条规则确实会是误导性的。因此, 人们引入了新的标准——兴趣度来加强对关联规则的判定[8]。
3 兴趣关联规则
通过上面的例子可以看出, 挖掘出的关联规则X⇒Y, 尽管满足用户指定的最小支持度和可信度, 但当Y与X不相关或先验知识知道较多的情况下, 这些关联规则是没有现实意义的, 或者说我们对这些关联规则并不感兴趣。为了克服这些问题, 引入关联规则的兴趣度概念。
规则X⇒Y的兴趣度为:
undefined
其中:
undefined
当规则X⇒Y的支持度和可信度分别大于用户指定的最小支持度minsupp和可信度minconf, 并且它的兴趣度大于用户指定的最小兴趣度minint时, 称规则X⇒Y为兴趣关联规则。
分析I的含义:
当I>0时有C-C’>0, 即P (XY) >P (X) P (Y) , 从而有:
undefined
说明X的发生对Y的发生起积极作用。特别当I=1时, 有P (XY) =P (X) 成立, 说明X发生时必然有Y发生。
当I<0时有C-C’<0, 即P (XY)
undefined
说明X的发生对Y的发生起抑制作用, 也可理解为Xc的发生对Y的发生起积极作用。特别I=-1时, 有 P (XcY) =P (Xc) 成立, 说明X不发生时必然有Y发生。
当I=0时有C-C’=0, 整理得P (XY) =P (X) P (Y) 。
说明X与Y没有关系, 即Y的发生独立于X的发生。
当I的值越接近1时, X与Y的关联性越强, 规则X⇒Y越具有现实意义。
当I的值越接近-1时, Xc 与Y的关联性越强, 规则Xc⇒Y越具有现实意义。
当I的值越接近0时, X与Y越不相关, 规则X⇒Y没有提供太多有用的信息, 这些规则没有实际的意义。
再来看上面的例子。对于例1来说, 由于I=0, 所以规则i1 ⇒ i2将不被发现。对于例2来说, 如果设最小兴趣度为30%, 由于I=-23.85%, 因此规则i1 ⇒ i2也不被发现。
4 关联规则挖掘算法的修改
下面将只考虑支持度和可信度的关联规则挖掘算法进行修改, 将它运用到引入兴趣度之后的情况。
由于关联规则的挖掘分为搜寻频繁项目集和产生关联规则两步。对于第一步, 我们可以采用现有的挖掘算法如Apriori等, 来产生频繁项目集。对于第二步, 找到的规则, 除了满足用户指定的支持度和可信度之外, 还要满足兴趣度阈值。
兴趣关联规则的挖掘算法描述如下:
(1) 利用Apriori等算法得到所有频繁项目集[9,10]L。
(2) 对L中的频繁项目集A和A的每一个非空子集B, 计算支持度P (A) 、P (B) 和P (A-B) 。
计算规则B⇒A-B的可信度C和兴趣度I的值。
undefined
其中:
undefined
(3) 根据C、I的值输出规则
如果C≤minconf, 说明规则B⇒A-B的可信度较低, 淘汰。
如果C> minconf, |I|
如果C>minconf, I>minint, 说明B对 (A-B) 具有积极作用, 规则B⇒ (A-B) 的兴趣度较高, 具有实际意义, 输出。
如果C>minconf, I<-minint, 说明B对 (A-B) 具有抑制作用, 此时我们对规则Bc ⇒ (A-B) 感兴趣, 输出此规则。
整个兴趣度关联挖掘算法描述如下:
输入: 最小支持度、最小可信度、有趣度阈值: minsupport、minconfidence、ri。
输出: 所有有趣的强关联规则。
首先利用经典 Apriori产生出大项目集:
再利用大项目集产生有兴趣度约束的关联规则:
5 应用结果说明
在用引入兴趣度的关联规则挖掘方法对局部的学生成绩数据库挖掘后, 得出了以下所示的兴趣度阈值和挖掘出的规则数目的关系如表1。
根据表1可以看出, 随着兴趣度阈值的提高, 挖掘出的规则的数量急剧减少, 成功的实现了无用规则的过滤。
6 结束语
文章对现有关联规则进行了分析, 指出了其不足之处:有些关联规则即使支持度和可信度都很高, 但仍没有实际意义。提出了一种度量关联规则兴趣度的方法, 并给出了兴趣关联规则的挖掘算法。通过对关联规则兴趣度的度量, 在挖掘关联规则时可以避免无意义规则的产生。
参考文献
[1]Agrawal R, Imielinski T, Swami A.Mining associationrules between sets of items in Large databases.[J].Pro-ceedings of the ACM SIGMOD Conference on Manage-ment of Data.Washington D.C, 1993, :207-216.
[2]Wu Xindong, Zhang Chengqi, Zhang Shichao.Miningboth positive and negative association rules[C]//Pro-ceedings of the 19th International conference on MachineLearning (ICML-2002) .San Francisco:Morgan Kauf-mann Publishers, 2002:658-665.
[3]张梅峰, 张建伟, 张新敬.基于Apriori的有效关联规则挖掘算法的研究[J].计算机工程与应用, 2003 (19) :196-198.
[4]宋海声.关联规则增量式更新算法[J].兰州大学学报 (自然科学版) , 2004 (2) :47-50.
[5]刘渊, 吴以才.基于效益度的高效关联规则挖掘算法[J].浙江大学学报 (工学版) , vol.41 No.6 Jun.2007:909-914.
[6]史忠植.知识发觋[M].北京:清华大学出版社, 2002.
[7]Han Jiawei, Kamber M.数据挖掘:概念与技术[M].北京:机械工业出版社, 2001.
[8]李伟东, 倪志伟, 刘晓.基于兴趣度的关联规则挖掘[J].计算机技术与发展, 2007 (6) :80-82.
[9]王珊等.数据仓库技术与联机分析处理[M].科学出版社, 1998.
[10]宋海声.快速开采最大频繁项目集[J].计算机应用研究, 2004 (3) :45-46.
兴趣关联规则的挖掘 篇2
摘 要：关联规则挖掘是挖掘研究领域的一项重要技术，高职院校教学管理系统产生海量数据，这些数据中隐藏着大量有价值的信息。文章采用改进的Apriori算法对高职院校计算机专业学生成绩进行关联规则分析，挖掘出课程之间的相关性，为高职院校更科学的制定教学计划提供有力的决策支持，进而提高教育教学质量。
关键词：关联规则；高职院校；计算机专业
中图分类号：TP393 文献标志码：A 文章编号：1673-8454（2014）20-0075-03
一、引言
随着高职院校快速发展，规模不断扩大，造成高职院校在课程设置、教学内容、学生管理、招生就业等方面面临严峻的考验，传统的教学管理理念已经不能够适应高职院校发展的需要，但是，许多高职院校在专业课程设置上都是在以往的专业课程设置基础上结合教学实际情况简单的进行修改，很少高职院校在专业课程设置上听取企业的建议或者遵循市场对人才的需求，导致课程应该在哪个学期开设或者是否继续开设等方面存在不少问题。
目前，基本上所有的高职院校都是采用基于WEB的教学管理系统对学生成绩信息进行有效管理，随着时间的推移，教学管理系统将产生海量的数据，大量的数据没有被充分的利用，因此，如何利用关联规则挖掘技术发掘隐藏在海量学生成绩数据背后有价值的信息或者规则，如课程之间的联系，学生成绩与课程之间的联系等等，为教师授课、学生学习、教育管理决策提供有用的理论指导。
二、关联规则挖掘和改进的Apriori算法
1.基本概念
数据挖掘（Data Mining），就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又潜在有用的信息和知识的过程。[1]关联规则挖掘是从大量数据中挖掘出有价值的、描述数据项之间相互联系的有关知识。[2]关联规则是数据挖掘研究领域的一项重要技术，其目的是从数据库中挖掘出不低于预先给定min-support阈值和min-confi阈值的关联规则。[3]
关联规则描述为：设I={i1，i2，……，im}为M个项目集，D为交易数据集合，其中事务T是I项目子集（T?I），对应的每一个事务交易都有唯一的标识TID。关联规则形如X?Y的逻辑蕴涵式，其中X?I，Y?I，且X∩Y=ф。如果事务数据库D中有s%的事务包含X∪Y，则称关联规则X?Y的支持度为s%，若项集X的支持度记为support（X），规则的信任度为support（X∪Y）/ support（X）。[4]也就是：
support（XY）=P（X∪Y）
confidence（XY）=P（Y/X）
2. Apriori算法
Apriori算法是关联规则挖掘中重要的算法之一，它的核心思想是采用逐层搜索的迭代的方法通过多次扫描数据库D来找出所有的频繁项集。其算法描述如下：
L1={频繁1—项集}；
For（k=2；Lk-1≠ф；k++）do begin
Ck=apriori_gen（Lk-1）；//新的潜在频繁项集
for all transactions t∈D do begin
Ct=subset（Ck ，t）； //事务t中包含的潜在频繁项集
for all candidates c∈Ct do
c.count++；
end；
Lk={c∈Ck|c.count≥minsup}
end；
Answer=YkLk；
Apriori算法虽然简单明了，容易实现，但是存在许多不足之处，一是对数据库D扫描次数过多，二是会产生大量的中间项集。针对这两个问题，笔者对Apriori算法做了相应的改进，将整个数据库进行分段，挖掘过程只需在段内进行，接着各子数据库挖掘结果汇总，最终刷选出关联规则。
三、关联规则挖掘在高职院校计算机专业课程设置中的应用
高职院校计算机专业课程包括有图像处理、网页设计、动画制作、网站制作与维护、C语言程序设计等。采用改进的Apriori算法对计算机专业课程进行分析，分析流程包括数据选择、数据刷选、数据转换、数据挖掘及结果分析。
1.数据准备
本研究选取某高职院校计算机专业10级到12级学生成绩表作为数据源，挖掘课程之间的关联性。为了减少冗余数据，将一些对专业课程影响较小的字段删除，删除了思政类、人文类、体育类和公共基础课成绩，最终选取了《图像处理》、《网页设计》、《动画制作》等15门专业基础、专业骨干、专业核心课程学生成绩作为研究对象。
2.数据筛选
采集的数据往往存在数据冗余、数据不完整性等现象，不能直接进行挖掘，需要对数据进行筛选处理。例如对于学生成绩表中含有学生的电话、地址、出生年月等字段，一一进行删除；对于学生成绩表中的学生退学、转学等记录一一删除；对于学生成绩表中缺考的信息，采用忽略元组的方法删除；对于个别空缺值，采用人工填充的简单方式，其填充值为该字段的中值；对于补考、重修通过的学生成绩，采用替换的方式填充为50分，便于数据转换。经过数据筛选的数据如表1所示。
3.数据转换
从表1中可以看出，每一条元组代表一名学生的课程成绩，表中成绩都是采用0-100的数值表示，如果直接进行数据挖掘，难以取得满意的结果，所以，需要对每一条元组对应的属性值进行量化，如采用区间量化，使每名学生每门课的成绩值落入到特定的区间，最终转换成离散属性。因此，本文将学生各门课程成绩分为优秀、良好、中、及格、差五等，分别用A、B、C、D、E表示，90-100分为A类，80-89分为B类，70-79分为C类，60-69分为D类，60分以下为E类，同时，为了便于书写，本文将表中各属性的字段名用英文字母替代，其中KC1为《图像处理》、KC2为《网页设计》，KC3为《动画制作》、KC4为《网站制作与维护》、KC5为《C语言程序设计》等等，数据转换后如表2所示。
4. Apriori算法的应用
要对上述学生课程成绩进行课程关联规则挖掘，本文采用的算法运行的硬件平台：Intel 酷睿2双核 E7500、2GB内存，软件平台：Windows XP、SQL Server 2000、SPSS Clementine。经过数据转换的学生成绩数据已经满足Apriori算法对数据的要求，可以直接使用Apriori模型进行挖掘。为了能够得到准确有效的课程关联规则，经过反复验证处理，将最小支持度设定为30%，最小置信度设定为60%。部分挖掘结果如图1所示。
5.挖掘结果及分析
上面挖掘出来的98条结果并非每条关联规则都有意义，我们对某些无价值的关联规则进行处理，无价值关联就是一门课程的成绩在A、B、C、D类中的其中一类能够同时推出另外一门课程的成绩为A、B、C、D类中的两类或者两类以上的规则。例如，《图像处理》成绩为A的学生可以推出《网页设计》课程的学生成绩即为A或者C等，这类规则就没有意义。关联规则分析主要有两个参考依据：支持度与置信度，若数据集中D有C比例的事务T满足“包含A事务的同时包含B事务”，则称规则A→B具有C置信度，置信度的高低代表关联规则强弱，置信度越高，关联越强。
通过整理98条，剩下64条有价值的规则，分析这些关联规则，得到部分主要的关联规则如下：
规则1：C语言程序设计=A→网页设计=A，置信度为69.2%，图像处理=A、C语言程序设计=A→网页设计=A，说明C语言程序设计、图像处理是网页设计的前导课程，因此，在课程设置中，网页设计排在C语言程序设计、图像处理课之后。
规则2：动画制作=A→网页设计=C，置信度为70.5%，通过查看课程的安排学期发现，网页设计课程安排在动画制作课程的前面，导致动画制作课程为优秀的学生，网页设计课程的学生不一定为优秀，因此，动画制作课程应该安排在网页设计的前面。
以下几条规则的含义相似，不在详述。
规则3：网页设计=A、C语言程序设计=A→网站制作与维护=A，置信度为85%。
规则4：数据结构=D、C语言程序设计=D→数据库技术=D，置信度80.3%。
规则5：C语言程序设计=A、操作系统=A→网站制作与维护=A，置信度76.5%。
规则6：计算机基础=A、计算机组装与维护=A、C语言程序设计=A→信息系统分析与设计=A，置信度82%。
从以上规则可以看出，C语言、数据结构对于计算机专业的学生来说是一门基础课，比较重要。笔者通过分析某高职院校计算机专业课程设置是否合理，简单的得出计算机专业课程体系，其中基础课程为计算机基础、计算机组装与维护、计算机网络技术、办公自动化高级应用、图像处理、动画制作、C语言程序设计等，骨干课程为数据库技术、网页设计、操作系统、网站制作与维护等，核心课程为动态WEB技术、信息系统分析与设计等。
四、结束语
高职教育是培养符合市场需求的高技能型人才，通过关联规则挖掘算法，能够有效地挖掘出课程之间的关联关系，为高职院校课程设置、教学计划和教学方案提供有力地决策支持，也为学生学习提供方向性指导意见。
参考文献：
[1]J Han， M Kamber. Data Mining：Concepts and Techniques[M]. San Mateo， CA：Morgan Kaufmann， 2001.
[2]付沙，周航军.关联规则挖掘Apriori算法的研究与改进[J]. 微电子学与计算机，2013（9）.
[3]孙志刚，朱小冬，王毅刚.基于改进关联规则的维修专业组合与优化模型[J].计算机应用研究，2013（2）.
[4]屈展，陈雷.一种改进的APRIORI算法在电子商务中的应用[J].西安石油大学学报（自然科学版），2012（1）.
关联规则挖掘兴趣度模型研究 篇3
在介绍兴趣度模型之前,先对关联规则的两个传统阈值作一个简单介绍:假设关联规则描述为X为规则前件,Y为规则后件,规则支持度表示为(1)式,置信度表示为(2)式,而兴趣度正是本文讨论的内容。
其中D表示事务数据库,N表示事务数据库D中各项事务数的总和,Count(X)表示事务X在事务数据库D中的出现次数,Count其中D表示事务数据库,N表示事务数据库D中各项事务数的总和,Count(X)表(X∪Y)表示事务X、Y在事务数据库D中同时出现的次数。 (X∪Y)表示事务X、Y在事务数据库D中同时出现的次数。
1 概率兴趣度
1.1 概率兴趣度模型
文献[2]提出了基于概率的关联规则兴趣度模型,其值表示为(3)式。
其中P(X)表示事务X在事务库中出现概率Count(X)/N,P(Y)表示事务Y在事务其中P(X)表示事务X在事务库中出现概率Count(X)/N,P(Y)表示事务Y在事务库中出现概率Count(Y)/N,P(Y|X)表示事务X其中P(X)表示事务X在事务库中出现概率Count(X)/N,P(Y)表示事务Y在事务库中出现概率Count(Y)/N,P(Y|X)表示事务X出现条件下事务X和Y同时出现概率Count(X∪Y)/Count(X)。
1.2概率兴趣度模型的特点分析
使用Visual FoxPro编程实现基于概率兴趣度模型的关联规则挖掘算法,并且在取不同兴趣度值情况下记录显示关联规则数,具体见表1所示。概率兴趣度与规则数关系如图1所示。
从图1可看出,兴趣度I函数值越大,规则越有价值。在兴趣度I的定义中,考虑到了规则的前项X和后项Y的耦合,同时考虑到如果对大概率事件产生的原因知道得较多,而可能对大概率事件导致的结果更加感兴趣的特点;但是兴趣度与信任度C不同,兴趣度重点对S(Y)小的规则赋予大的兴趣度[3]。基于概率兴趣度模型主要考虑规则的简洁性、支持度以及后项的影响,却没有考虑规则前项对规则的影响。
2 差异思想兴趣度
2.1差异思想兴趣度模型
文献【4】提出了一种基于差异思想的兴趣度模型,用以指导关联规则的发现,将关联规则的兴趣度表示为:
其中,为关联规则的置信度,其值为(2)式所示;S(Y)为关联规则中Y的支持度,其值为Count(X)/N。
2.2差异思想兴趣度模型特点分析
使用Visual FoxPro编程实现基于差异思想兴趣度模型的关联规则挖掘算法,并且在取不同兴趣度值情况下记录显示关联规则数,具体见表2所示。差异思想兴趣度与规则数关系如图2所示。
是一个标准,保证此兴趣度模型把支持度和信任度联系了起来,反映了在X影响下事务Y在发生的概率。当Y支持度与规则的置信度的差异越大时，大于阈值,规则使用价值大;反之则小于阈值,规则使用价值小。基于差异思想的兴趣度模型是由规则信任度与后项支持度的差异来定义的,这种方法的好处是消除了后项高支持率导对规则高信任度的影响,达到删除不感兴趣规则的目的。
3 相关性兴趣度
3.1 相关性兴趣度模型
根据文献[5]描述,将基于相关性的兴趣度模型定义为:
其中,S(X∪Y)=Count(X∪Y)/N,S(X)=Count(X)/N,S(Y)=Count(Y)/N。
3.2 相关性兴趣度模型特点分析
使用Visual FoxPro编程实现基于相关性兴趣度模型的关联规则挖掘算法,并且在取不同兴趣度值情况下记录显示关联规则数,具体见表3所示。将相关性兴趣度与规则数如图3所示。
兴趣度反映了关联规则中X与Y间的关系,是X和Y密切程度的体现;而可信度和支持度分别体现了规则依赖方向和规则在事务集中出现的频率。基于相关性的兴趣度模型是从规则前项与后项相关性来定义的,从概率的角度分析规则前项和后项相关性,若前项与后项在概率上不相关,或者相关性小,则用户对规则没有兴趣或兴趣较小,反之则用户对规则有很大的兴趣。
4 信息量兴趣度
4.1 信息量兴趣度模型
早在1992年美国学者Padhaic Symth等人在论文《An Information Theoretie Approach to Rule Induction from Database》中将关联规则的兴趣度定义为:
其中,P(X)=Count(X)/N,P(Y)=Count(Y)/N,P(Y|X)=Count(X∪Y)/N。
4.2信息量兴趣度模型特点分析
使用Visual FoxPro编程实现基于信息量兴趣度模型的关联规则挖掘算法,并且在取不同兴趣度值情况下记录显示关联规则数,具体见表4所示。将信息量兴趣度与规则数关系如图4所示。
基于信息量兴趣度模型主要对规则的简洁性和信息量进行综合度量的,综合考虑了前件X和后件Y概率分布的相似程度,X出现的概率P(X)作为规则前项简洁程度的衡量。规则越简洁,则X数量越少,兴趣度也越高。这种兴趣度模型考虑了前项和后项的藕合度,藕合度越高,兴趣度也越高。
5 影响兴趣度
5.1 影响兴趣度模型
西南交通大学陈安龙的硕士论文《基于兴趣度的关联规则挖掘算法的研究》中将兴趣度描述为(7)式。
其中,为关联规则的置信度,
5.2 影响兴趣度模型特点分析
使用Visual FoxPro编程实现基于影响兴趣度模型的关联规则挖掘算法,并且在取不同兴趣度值情况下记录显示关联规则数, 具体见表5所示。将影响兴趣度与规则数关系如图5所示。
在总事务数N和其它不变情况下,当Count(Y)增大时兴趣度将降低,反之则上升;当Count(X∪Y)增大时兴趣度将上升,反之则降低;当Count(X)增大时兴趣度将降低,反之则上升。这种兴趣度模型使用前项对规则的影响来确定规则兴趣度,考虑了接近于阀值的强关联规则和弱关联规则的选择。
除了以上介绍的5种兴趣度模型外,还有目标兴趣度、正负项目兴趣度、卡方独立性兴趣度、Symth函数兴趣度、Gimi指标兴趣度、Piantesky-Shapiro兴趣度模型等,在此就不一一介绍了。
本文通过查阅相关文献资料,收集整理了基于概率兴趣度、差异思想兴趣度、相关性兴趣度、信息量兴趣度、影响兴趣度模型的相关知识,并利用Visual FoxPro编程语言实现这些兴趣度的关联规则算法。通过实验分析了各种兴趣度模型的取值与规则显示的关系,并简要分析总结了各种兴趣度模型的基本特点。
摘要：通过查阅相关文献资料,收集整理了基于概率兴趣度模型、差异思想兴趣度模型、相关性兴趣度模型、信息量兴趣度模型、影响兴趣度模型的计算公式,并利用Visual FoxPro编程语言实现这些兴趣度模型的关联规则挖掘算法。通过实验分析了各种兴趣度模型的取值与规则显示间的关系,并简要分析总结了各种兴趣度模型的基本特点。
关联规则挖掘研究 篇4
关联规则是发现交易数据库中不同商品(项)之间的联系,这些规则找出顾客购买行为模式,如购买了某一商品对购买其它商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。
关联规则是关联分析中的一种常用技术。关联规则是寻找在同一个事件中出现的不同项的相关性。其形式如下[1]。
设L=邀i1,i2,...im妖是所有项的集合。D是交易集合,其中每个交易T是一个项的集合并且T哿L。每一个交易T都有一个唯一的标识TID。如果项集合X哿L且X哿T,则交易T包含X。一个关联规则就是这样一种形式的关系:X==>Y,其中X奂L,Y奂L,并且X∪Y=φ。
另外两个和关联规则有关的概念是支持度和可信度。
根据文献[1]的定义,对于一个关联规则X==>Y,在交易集合D中,Txy=邀T|(X∪Y)哿T∩T∈D妖,Tx=邀T|X奂T∩T∈D妖,支持度为s,|Txy|/|D|=s%;可信度为c,|Txy|/|Tx|=c%。
举例说明,有一个特定的关联规则,锤子==>钉子,这个规则可能意味着买锤子的人也有倾向买钉子。有10000条交易记录的交易数据库中,若有300条记录既包含了锤子又包含了钉子,则关联规则的支持度为300/10000=3%,这个支持度是比较高的,但并不能就此作出这个关联有意义的结论。但是假如只有600人购买了锤子,则其中有一半的人又去购买了钉子,这个现象就值得关注了。
另一个更详细的例子来自于文献[2]:
总交易笔数:1000;
包含“锤子”:50;
包含“钉子”:80;
包含“钳子”:20;
包含“锤子”和“钉子”:15;
包含“钳子”和“钉子”:10;
包含“锤子”和“钳子”:10;
包含“锤子”,“钳子”和“钉子”:15。
则可以计算出:
“锤子和钉子”的支持度=1.5%(15/1000);
“锤子,钉子和钳子”的支持度=0.5(5/1000);
“锤子==>钉子”的可信度=30%(15/50);
“钉子==>锤子”的可信度=19%(15/80);
“锤子和钉子==>钳子”的可信度=33%(5/15);
“钳子==>锤子和钉子”的可信度=25%(5/20)。
数据挖掘得到的关联规则,只是对数据库中数据之间相关性的一种描述。还没有其它数据来验证规则的正确性。
除了支持度和可信度外关联规则评价标准还有改善度和兴趣度。
2 关联规则的种类
(1)基于规则中处理的变量的类别,分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。例如:性别=“女”=>职业=“秘书”,是布尔型关联规则;性别=“女”=>avg(收入)=2300,是一个数值型关联规则。
(2)基于规则中数据的抽象层次,分为单层关联规则和多层关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。例如:IBM台式机=>Sony打印机,是一个细节数据上的单层关联规则;台式机=>Sony打印机,是一个较高层次和细节层次之间的多层关联规则。
(3)基于规则中涉及到的数据维数,分为单维的和多维的。在单维的关联规则中,只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。换句话说,单维关联规则是处理单个属性中的一些关系;多维关联规则是处理各个属性之间的某些关系。例如:啤酒=>尿布,这条规则只涉及到用户购买的物品;性别=“女”=>职业=“秘书”,这条规则就涉及到两个字段的信息,是两个维上的一条关联规则。
给出了关联规则的分类之后,在分析过程中,就可以考虑某个具体的方法适用于哪一类规则的挖掘,某类规则又可以用哪些不同的方法进行处理。
3 关联规则挖掘的算法
3.1 经典频集方法
Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题[3],其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。其工作包括对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;提出各种变体,如泛化的关联规则、周期关联规则等,对关联规则的应用进行推广。
(1)核心算法Agrawal等设计了一个基本算法[3],提出了挖掘关联规则的一个重要方法,将关联规则挖掘算法的设计分解为两个子问题:(1)找到所有支持度大于最小支持度的项集,这些项集称为频集;(2)使用(1)找到的频集产生期望的规则。
(2)频集算法的几种优化方法:(1)基于划分的方法;(2)基于hash的方法;(3)基于采样的方法;(4)减少交易的个数。
3.2 其它的频集挖掘方法
前面介绍的都是基于Apriori的频集方法。即使进行了优化,Apriori方法一些固有的缺陷还是无法克服。
(1)可能产生大量的候选集。当长度为1的频集有1-0000个的时候,长度为2的候选集个数将会超过10M。当要生成一个很长的规则的时候,要产生的中间元素也是巨大量的。
(2)无法对稀有信息进行分析。由于频集使用了参数minsup,因此就无法对小于minsup的事件进行分析;如果将minsup设成一个很低的值,那么算法的效率将很难处理。
4 结束语
关联规则可以在下面一些方向上进行深入研究:在处理极大量的数据时,如何提高算法效率的问题;对于挖掘迅速更新数据的挖掘算法的进一步研究;在挖掘的过程中,提供一种与用户进行交互的方法,将用户的领域知识结合在其中;对于数值型字段在关联规则中的处理问题;生成结果的可视化方面等等。
参考文献
[1]Rakesh Agrawal,Ramakrjshnan Srjkant.Fast Algorithms for Mining Association Rules.[S.l].:Proceedings of the20th VLDB Conference,c19xx/20xx.
[2]朱扬勇.数据挖掘入门.http://datamining.126.com.
时态文本挖掘的关联规则研究 篇5
现代化的企业搜集了大量时态文本数据, 但信息超载和无结构化, 使得企业决策部门无法有效利用现存的信息, 时态数据挖掘技术便应运而生。目前有关时态关联规则算法已较多, 但是如果运用到时态文本关联规则的挖掘中则时间复杂度都太高。所以本文将对时态文本关联规则挖掘进行研究。
1. 时态文本预处理
1.1 时态文本处理
在挖掘时态文本关联规则之前, 需要先对文本进行预处理, 对英文而言需进行Stemming处理[5], 中文的情况则不同, 因为中文词和词之间没有固定的间隔, 需进行分词处理。
对于本文研究的是医学病毒论文数据库, 是一个英文数据库, 文本预处理的具体内容如下:
(1) 英文大写换小写 (都以小写字母表示, 方便文本识别) ; (2) 删除空白记录; (3) 将论文信息中的标题和摘要进行 (可以提高关键词的比重, 增加提取文本向量的精度) ; (4) 处理论文发表时间DP列, 只保留年份数字, 方便提取有效时间; (5) 对于记录太多的库, 适当拆分表格 (否则在程序处理时会内存溢出) ; (6) 根据文本内容提取合适的停用词表, 对文本内容进行去停用词处理。
1.2 时态文本表示
在对时态文本进行清理后, 需将其进行表示。在文本处理时我们已提取论文的发表时间, 所以将时间和文本分列处理, 然后将文本单独表示。本文采用向量空间模型 (VSM, Vector Space Model) 进行表示[6]。
2. 时态关联规则算法概述
以前的算法不能有效应用到时态文本数据库中, 主要原因有:1) 这些算法计算时时间复杂度仍太高。2) 没有考虑每个独立文本项各自存在的有效时间;3) 每个项目缺少一个合理的可以浮动的支持度数。所以本文根据时态事件模型及Apriori原则, 本文在快速更新算法思想上产生新的算法:SP-FM (Segment-Progressive-Filter-Miner)
该算法主要包括三步:1.数据库不断更新;2.对数据库按不同时间段进行划分;3.对每个时间段的事务集挖掘频繁项集。拆分后的数据库, 每个阶段部分有不同的支持度阈值, 我们按不同的支持度阈值进行计算来产生候选项集。
SPFM算法主要有三个特点:1) 算法预处理时将文本数据转换成垂直数据格式, 可大大提高程序效率;2) 在挖掘时态数据库的频繁项集时, 通过更新不同时间粒度的支持度数来确定频繁项集, 并判断频繁项集在时间粒度上的连续性;3) 如2) 所述, 时态数据库是和时间粒度有关的, 那么从时态数据库挖掘出的关联规则也应该是和时间粒度有关的, 即存在“有效时间”, 本算法引入一种判断机制, 使得发现的有效时间是由频繁项集本身决定的, 最终我们获得的是一组浮动的“有效时间”。
3. 实验测试
为了测试SPFM的算法性能, 用Visual C++进行编程。对象为医学病毒论文数据库中1970~2010年间约50万条的记录, 每条记录的属性包括fileno (论文标号) 、TI (标题) 、AB (摘要) 、DP (发表时间) 等。以“年”作为时间粒度, 将数据库划分为40个阶段部分。minsup为0.5‰, minconf为35%, 然后进行频繁项集的挖掘, 并确定每个频繁项集的有效时间, 依次循环直至2010年为止。
比如rous (含铁血黄素) 和sarcoma (1979年、1981年、1983年) , 都是强关联规则, 且COS判断值为0.8165>0.5, 说明该规则有意义, 这两者在1979~1983年是一个共同研究热点, 它们之间有可能存在一些密切的联系, 在医学上也可以深入研究。
通过对医学文本数据库的挖掘, 我们挖掘出上百条时态文本关联规则, 从这些规则当中我们能得到近40年学者们对病毒研究的规律以及病毒的发展规律, 这些规律会是对以往病毒研究的较好总结, 也会有助于更有效地治疗已产生的病毒。
在文本数据挖掘技术已经日渐成熟的背景下, 把时态数据与文本挖掘联合起来, 可将时态文本数据挖掘应用于医学、经营、管理等各个方面, 通过对海量的时态文本数据进行关联分析, 为管理者做决策提供参考数据;还能为新的经营模式提供目标和思路, 减少盲目性, 以获得更大利益。
4. 结束语
本文提出了对医学病毒论文数据库中的时态文本如何进行预处理, 需先将时间和文本分为不同的列, 将文本表示为向量空间模型。然后确实频繁项集的有效时间, 将文本数据转换成垂直数据格式, 再通过新的算法挖掘频繁项集, 最后对时态文进行强关联规则的挖掘。该实验是对时态文本进行预处理后再进行关联规则挖掘的, 最后验证了该算法的有效性。
摘要：由于现代企业的数据库频繁更新, 且大部分数据库为文本数据库, 所以需要挖掘时态文本的关联规则。本文以时态文本为对象进行了时态关联规则的研究, 最后通过实验进行了有效性验证, 结果表明该研究方法是正确可行的。
关键词：文本,时态,关联规则,垂直数据,有效时间
参考文献
数值属性关联规则的挖掘算法 篇6
关联规则作为数据挖掘的一个重要研究分支,其主要的研究目的是从大型数据集中发现隐藏的、有趣的、属性间存在的规律。目前,从布尔描述的数据中挖掘关联规则已经有了比较成熟的系统和方法,而对于量化关联规则则不然,这方面的研究仍然比较欠缺。本文提出了先不考虑数值属性,在找到所有频繁项集后,再在此基础上,找出数值属性的最佳分区的解决方法。
1 数据挖掘、关联规则的相关研究
1.1 数据挖掘
数据挖掘(Data Mining),也称知识发现KDD(knowledge discovery in database),是从大量原始数据中挖掘出隐含的、有用的、尚未发现的信息和知识(如知识规则,限制等),被认为是目前解决“数据爆炸”和“数据丰富,信息贫乏(Data Rich and Information Poor)”的一种有效方法,它为大量数据的利用提供了有效的工具[1]。
数据挖掘的一般包含数据抽取、数据清理、数据设计、算法设计、算法运行、结果分析六大步骤。
从数据库中发掘的规则可以有以下几种:特征规则、区分规则、聚类规则、关联规则和进化规则等。关联规则是比较新的一种,它的形式简洁,易于解释和理解并可有效捕捉数据间的重要关系。
1.2 关联规则
1.2.1 关联规则
关联规则(Association Rules)是数据挖掘研究的一个重要分支,是数据挖掘的众多知识类型中最为典型的一种。Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,是数据挖掘的一个重要研究领域。它反映出一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其它事物预测到。具体描述为:
设I={i1, i2, …, im}是二进制文字的集合,其中的元素称为项(item)。记任务相关的数据D为交易T(transaction)的集合,这里交易T是项的集合,并且T⊆I。每个交易都有一个唯一的标识,如交易号,记作TID。设X是一个I中项的集合,如果X⊆T,那么称交易T包含X。
1.2.2 关联规则挖掘的算法
Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。工作包括对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;提出各种变体,如泛化的关联规则、周期关联规则等,对关联规则的应用进行推广[3]。
(1)经典频集方法
为了生成所有频繁项集,Agrawal等人在1993年设计了Apriori算法,使用了递推的方法。其核心思想如下:
这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库,即如果频繁项集最多包含10个项,那么就需要扫描交易数据库10遍,这需要很大的I/O负载。
(2)FP-tree算法
Han等人提出FP-tree算法,此算法是不产生候选项集作法的代表,因为不用产生候选项集,只需扫描数据库两次,因此节省了大量I/O的时间,整体的效能大幅提升,而且已运用在实际的产品中。
FP-tree算法和上述算法最主要的差别在于:FP-tree算法不用产生候选项集,且将数据库压缩在FP-tree的结构中,改进了扫描多次数据库的高成本。
FP-tree具体算法如下:
FP-tree 算法:使用FP-tree通过模式段增长,挖掘频繁项集。
输入:数据库D;最小支持度阀值。
输出:频繁模式的完全集。
方法:
按照前述的步骤构造FP-tree
输出满足最小支持度阀值的频繁1项集,并按其支持度大小,从小到大调用FP-growth(FP-tree,null)过程来挖掘FP-tree,该过程实现如下:
对FP-tree方法的性能研究表明:对于挖掘长的和短的频繁模式,它都是有效的和可伸缩的,并且大约比Apriori算法快一个数量级。但其缺点为实现起来较复杂,且若是从稀疏资料库中找出所有的频繁项集时效率较差。
2 多维量化关联规则
Apriori、FP-tree等现有关联规则挖掘算法都是在单维、单层、布尔关联规则下讨论的,是最简单形式的关联规则。而实际应用中,数据库中绝大部分数据是多属性的,并且又多是类别与数值属性的混合型。如何有效挖掘含有数值项目的关联规则是关联规则挖掘中一个急需解决的问题。
2.1 数值属性
数据属性可能是多值的,目前许多文献讨论关联规则的例子只是定性地描述一个交易是否包含某物品,属于挖掘布尔型关联规则问题BARP(Boolean Association Rules Problem),但它可以看作是挖掘多值量化关联规则问题QARP(Quantitative Association Rules Problem)的基础和特例,它是在属性值为布尔量的关系表中寻找属性值为“1”的属性之间的关系[2]。
实际生活中,数据属性不仅仅只有逻辑型这样—种取值类型,它可以是多值的。属性依类型又可分为类别(categorical)属性和数值(numeric)属性两种,逻辑属性可以看作是类别属性(只有“1”和“0”两个值)的一个特例。
2.2 多维量化属性关联规则挖掘任务
单维布尔关联规则的挖掘是最简单、最基本形式的关联规则的挖掘。目前许多文献都讨论了挖掘布尔型关联规则问题,它是挖掘量化关联规则问题QARP的基础,是在属性值为布尔量的关系表中寻找属性值为“1”的属性之间的关系。QARP比较复杂,一种自然的想法是将它转换为BARP。当全部属性的取值数量都是有限的时候,只需将每个属性值映射为一个布尔型属性;当属性的取值范围很宽时,则需将其分为若干区段,然后将每个区段映射为一个布尔型属性,映射为项目集,之后再用类似于布尔关联规则的挖掘算法进行挖掘,产生支持度大于等于最小支持度的频繁项目集,在频繁项目集中产生大于或等于最小信任度的规则,从产生的规则中确定出有价值的规则[4]。
挖掘多属性量化关联规则存在两个难题:
(1)如何对属性分区。
(2)如何发现频繁项目集,找出关联规则。
举例:表1为一个简单的多维量化数据表。
设:Min Support=40%,Min Confidence=50%,就可以得到形如下两式的关联规则:
(1)Age:(30-39 )and Married: Yes ⇒NumCars:2(Support:40%,conf:100%)
(2)NumCars:(0-1)⇒Married: No(Support 40%,conf:66.6%)
其中Age属性与NumCars属性为量化属性,它们要分区,将每个属性值映射为一个布尔型属性。将表1转化为属性均为布尔型的表2。
对于类别属性,可以根据相关知识在挖掘前就将相关属性概化,而在毫无相关知识的未知数值属性上时,采取这种对数值属性先分区,再归纳关联规则,将面临两大互相牵制的问题:划分区间过小会使它包含的元素变少,许多规则因支持度低于阀值而不成立,这类问题称为最小支持度问题;而区间的划分粒度过大会使许多规则因信任度过小,信息丢失而不能成立,这类问题称为最小信任度问题,如在表2中:NumCars:0=>Married:No有100%confidence,NumCars 属性减少区间数目,扩大了区间,NumCars:(0-1)=>Married: No只有66%confidence。对于minimum support问题,可以通过合并相邻的区间,减少区间数目,扩大区间来解决;增加区间数目又可以解决minimum confidence问题。但这样又会增加运行时间缓慢、产生无用规则、如何确定新的平衡的新问题。
在本文中,采用先找出其它属性的频繁项集,再对数值属性进行分区的方法来挖掘含有数值属性的多属性关联规则,希望能从含有数值属性的数据中,以自动化的方式准确找出该数值属性的最佳分区。
2.3 数据概化
数据概化是一个过程,它将大的任务相关的数据集从较低的概念层抽象到较高的概念层。对于数值属性而言,(x,l,v)表示数量属性x的值在区间[l,v]上,如果l’
大的数据集有效的、灵活的概化方法可以分为两类:数据立方体方法、属性导向归纳法。
属性导向归纳法于1989年首次提出,是一种以归纳为基础的数据分析的技术,将相关联数据集合中的每一个属性,检查其数据的分布,判断应归纳到那个相关的抽象层级。
归纳技术包括属性移除、概念树爬升、属性阀值控制和其他整合函数值等。
2.4 数值数据分区
布尔型关联规则问题BARP可以看作是挖掘多属性关联规则问题QARP的基础和特例。Agrawal提出了以“Boolean association rules”为基础的处理方法,把数量属性分成多个细小的区间,将这些区间视为不同的属性值,再把各属性所有的属性值域皆当作Boolean属性,利用Apriori算法来处理产生关联规则[5]。
常见的数值属性分区方法有:分箱、直方图分析、聚类分析、基于熵的离散化、自然分区等等。
3 数值属性关联规则挖掘
3.1 方法分析
基于上述论述,对在挖掘含有未知数值属性多维关联规则一般步骤做了一些修改。先不考虑无法被分区的未知数值属性,而将其它属性分区并找到相应的频繁项集,再在它们的基础上,针对用户感兴趣的规则,找出数值属性上有意义的区间,有意义的区间在这里定义为大于或等于最小信任度且有最大支持度的区间[6],流程如下:
取出相关数据→先不处理数值属性→对其它属性概化→其它属性由QARP到BARP转变→找出其它属性频繁项集→根据找出的频繁数据项集,引入规则约束,指定要挖掘的规则形式,在数值属性上找出有意义的数值范围,从而得到用户想要的关联规则。
从处理过程来看,有两个难点:
(1)如何找出其它属性频繁项集
寻找频繁项集是挖掘关联规则的关键,算法的总体性能是由这一步来决定的。经过比较,决定采用FPL算法。由于此算法需二次扫描数据库,在大的数据库中搜寻数据,即使多遍历一次,也是很浪费时间的,这个算法本身还存在可优化的空间。况且,在寻找的所有频繁项集时,用来过滤频繁项集的最小支持度的值的制订非常重要[6],如果定得不恰当,会造成产生过多无用的频繁模式。因此在挖掘频繁项集过程中,反复修改此值,无论此值改动的幅度是大或小,FPL算法都必须重新构建FPL结构,这相当重新挖掘一遍,是很浪费时间的,所以FPL算法必须作一些修改,来解决这个问题。
(2)如何对数值属性分区
本文采用先找出其它属性的频繁项集,再对数值属性进行分区,找出有意义的区间,挖掘含有数值属性的多属性关联规则。并可以通过调节最小信任度,找到用户满意的最佳区间。有意义的数值区间定义为超过minimum confidence且有最大support的区间。
3.2 算法实现
3.2.1 改进的FPL方法分析与描述
在产生频繁项集时,如果采用前述的FPL方法需要二次扫描数据库,在非常庞大的数据库中读取数据。基于以上,提出的挖掘频繁项集的算法将在FPL的基础上进行一些修改,将二次扫描改为一次扫描,也利用简单线性串行结构来储存数据,并在此串行上执行简单运算,以快速找出所有频繁项集。另外,FPL算法还有一个缺点:每当最小支持度的值一有变动,无论此值改动的幅度是大或小,都必须重新构建FPL结构,这相当重新挖掘一遍,是很浪费时间的。而在寻找的所有频繁项集实际操作中,往往需要反复修改此值,才能得到自己满意的结果。所以本文所提出的算法主要是针对以上两处改进了的FPL算法。具体描述如下:
第一个阶段读入每条记录,构建DB-BIT表和FPL串行。在DB-BIT表新增每个属性列,检查每条记录中的属性是否已存在FPL的串行中,若此属性已存在,则将此节点(Ni)支持度值加1,并且将DB-BIT上数据 BIT值设为1,若不存在,则新增此项目节点(Ni),此Ni支持度为1,并且将DB-BIT上数据BIT值设为1,接着将FPL串行节点依支持度值由大到小做排序。
第二个阶段检查串行节点(Ni)支持度是否大于或等于最小支持度,若是则产生Ni的频繁模式。并从满足于大于或等于最小支持度这个条件的支持度最小的串行节点开始直到只剩下一个拥有最大支持度的节点为止,构建Ni下的子串行节点,检查其支持度是否满足条件,重复上面的步骤,直至所有子串行节点只剩下一个为止,挖掘出所有频繁项集。与FPL算法相比,改进了的FPL算法不删除串行节点。
当调整了最小支持度的阀值,可以从以前串行中拷贝一份,不必重新扫描数据库,不必 重新构建FPL。大大节约了时间,具体算法如下:
算法:FPLM。使用改进的FPL算法挖掘频繁模式。
输入:数据库;最小支持度阀值;决策值。
输出:频繁模式的全集及其支持度。
方法:
(1)如果是第一次挖掘时,根据前述的方法构建DB-BIT表和FPL串行(串行包括节点的名字及出现次数)。
(2)检查FPL串行每一个节点(Ni)支持度值,若此Ni支持度值大于或等于最小支持度值则将此Ni拷贝至FPLM串行中。
(3)对于FPLM串列行的挖掘,通过调用GenFreItem(FPLM串行,null)来实现,该过程如下:
3.2.2 寻找有意义的区间
利用探索式的方法来寻找最佳的数值区间,将会有大量计算。为了简化算法,先将要考虑的数值属性分成n个小区间,将计算所需的数据预先存入一个数组中,如表3所示。
其中,an表示频繁数据项集和决策属性在数值属性上的第n个区间上包含的记录个数,bn表示频繁数据项集在数值属性上的第n个区间上包含的记录个数。
根据关联规则定义,第n个区间上的支持度为an/数据的总记录数,信任度为an/bn,区间[f,r](f≤r)上的支持度为(af+…+ar)/数据的总记录数,信任度为(af+…+ar)/(bf+…+br)。
算法的任务就是要寻找有意义的区间,作为关联规则输出。
先搜索[0,n]整个区间,如果是有意义区间,根据有意义区间定义,就不必再继续找下去,整个区间作为有意义区间输出,否则缩小区间[0,n-1],试探是否是有意义的区间,如果不是,继续缩小区间[0,n-2],要是找到有意义区间[f,q](0≤f≤q≤n),作为有意义区间输出,相邻的以q+1开始的区间肯定没有最有意义的区间,否则,两个区间合并,会在上一个有意义区间寻找中被找出。接着从[f+1,n]区间搜索。
具体算法如下:
算法:在一个已知的频繁项集上寻找最有意义的区间。
输入:已知的频繁项集;最小信任度阀值;决策值。
输出:有意义区间。
方法:
(1)将数值属性的区间分为n个足够小的区间。
(2)将计算所需的数据预先存入数组中。
(3)寻找有意义的区间,该过程procedure btnApply()如下:
4 结束语
提高挖掘的效率是关联规则挖掘的核心问题,通常效率指的是运行时间和结果的可用性,现有的算法在两者之间很难做到有效的平衡,运行时间过长,或是规则的数量过大,这都为使用者带来了很大的不便。在此改进了的FPL算法寻找频繁项集,提高了算法的效率;引入约束,使挖掘的目的朝着以用户需求为核心的方向进行,避免了泛泛的挖掘。这些都是围绕如何提高关联规则挖掘效率这一核心问题展开的。
摘要：文中研究一种如何有效挖掘含有未知数值属性的多属性数据关联规则方法。对FPL算法进行了改进,扫描一次数据库,就可以找出所有频繁项集,且当最小支持度变动时,不需重新构建FPL,能快速找出所有频繁项集。
关键词：数值属性,关联规则,数据挖掘
参考文献
[1]何华灿,等.泛逻辑学原理[M].科学出版社,2001:15-24.
[2]Zhang Zhao-hui,Lu Yu-chang.An effective partitioning-combiningalgorithm for discovering quantitative association rules[C].Pro-ceedings of PAKDD,Singapore:World Scientific Publishing Co,2008:241-251.
[3]Cheung D.Efficient mining of association rules in distributed data-bases[J].IEEE Transactions on Knowledge and Data Engineering,2006,8(6):911-922.
[4]Lin D,Kedem Z M.Pincer-search A new algorithm for discoveringthe maximum frequent set[C].Proceedings of the 6th InternationalConference on Extending Database Technology,2008:105-119.
[5]王君,任永功.基于FP-tree最大频繁模式超集挖掘算法[J].郑州大学学报,2011(3).
兴趣关联规则的挖掘 篇7
1 概化处理
数据挖掘的目的是从大量日常业务数据中抽取一些有价值的知识或信息。原始业务数据是知识和信息提取的源泉,对于数据挖掘十分重要。数据挖掘算法中的数据往往受噪声数据、丢失数据和不一致数据的侵扰,一般都具有不完整性、冗余性和模糊性,很少能直接满足数据挖掘算法的要求。对财务报表来说,由于每个公司季度报表推出时间不一致,在行业内的公司没有全部推出季报时进行数据挖掘分析,就存在数据不完整的现象。所以对不理想的原始数据进行有效的归纳和预处理成为数据挖掘的关键问题。
数据预处理是数据挖掘前的准备工作,一方面保证挖掘数据的正确性与有效性;另一方面通过对数据格式和内容的调整,使数据更符合挖掘的需要。对财务报表预处理包括对财务报表进行数据清理与数据变换。数据清理目的是填写缺失的报表数据,数据变换是对连续的财务指标数据进行离散化,进而进行概化处理。
概化处理完成数据预处理工作,其获取行业内个股财务信息,求取行业平均值,并存入数据库,利用行业均值,对个股财务记录信息做数值型数据转化处理,生成事务表。
1.1 数据清理
对于每一项财务报表指标,求取一个行业平均水平值,所有的财务指标均值,即统计中的算数平均值,组成的报表,也在此称为行业均值报表。
对每一个行业,查询行业内上市公司财务报表中的各指标值,统计和并计算均值,构成均值报表后写入数据库保存。例如:资产负债的行业均值表,如表1。
每项均值的计算为所统计的上市公司该项财务指标值的和除于参加统计公司数,例行业的流动比率均值为:
因为上市公司的财务报表公布不同步,对于未公布数据的空缺项,用均值来补充,即假定该公司在该项取得行业均值。这样处理后,为后续的处理过程准备完整的数据。
1.2 数据概化处理
由于财务报表指标数据为数值型数据,所以首先概化处理为布尔型,以便在后续的数据挖掘中用布尔型关联规则挖掘方法进行挖掘。进行布尔型转换的第一步是将数值型数据进行概念分层,将数值型财务指标概化为三个数值区间{Ei-K=
例如:取某个行业的某季度的主营业务收入增长率,流动比率,每股收益增长率构成数据挖掘前的事务表,该数据转化规则表如表3。
该行业内上市公司该季度的这三项实际数据表,如表4。
该行业内上市公司该季度的这三项转化后的财务指标的布尔数据表,如表5。
在表中如果有多个取值一样的行,则添加一个属性统计记录相同行数,而证劵代码的属性取值较多,由数据概化中基于属性的归纳法原理可知当一个属性的属性值有许多个不同的值,且没有合适的泛化操作,应该做删除该属性处理。如表6所示。
2 关联规则挖掘
对之前做的概化处理都是为关联规则的挖掘做准备工作的,关联规则的挖掘工作将在概化处理形成的事务表上进行。将前面的布尔数据表每行中列为1的项取出组成一个事务,如表5第一行{FIN11,FIN22,FIN32},下面对数据挖掘的基础知识做简要介绍。
2.1 关联规则理论概述
定义1关联规则挖掘的数据集记为D(D一般为事务数据库D={t1,t2,t3,t4,t5,…tn},tk(k=1,2,…,n)称为事务,im(m=1,2,…,p)称为项。
定义2 I={i1,i2,i3,…,ip}是D中全体数据项组成的集合,I的任何子集X称为D中的项集,若|X|=k,称集合X为k-项集。tK和X分别为D中的事务和项集,如果X t K,称事务tK包含项集X。
定义3数据集D中包含项集X的事务数称为项集X的支持数,记为σX。项集X的支持度记为support(X),
support(X)=σX/|D|×100%(1-1)
其中,|D|是数据集D中的事务数,若support(X)不小于用户指定的最小支持度阈值minsup,则称为X为频繁项集,否则成X为非频繁项集。
对于项集和其子集在支持度上的关系有定理如下:
定理1 X、Y是数据集D中的项集
(1)X Y,则support(X)≥support(Y)
(2)X Y,如果X是频繁项集,则Y也是频繁项集
(3)X Y,如果Y是频繁项集,则X也是频繁项集
频繁项集是进行关联规则挖掘的基础,找出频繁项集后,关联规则的定义如下:
定义4若X、Y为项集,且X∩Y=ø,蕴涵式X=>Y称为关联规则,X、Y分别称为关联规则X=>Y的前提与结论。项集X∪Y的支持度称为关联规则X=>Y的支持度,记为support(X=>Y)
support(X=>Y)=support(X∪Y)(1-2)
关联规则X=>Y的置信度记为:confi dence(X=>Y)
confidence(X=>Y)=support(X∪Y)/support(X)×100%(1-3)
最小置信度阈值记为minconf。
定义5若support(X=>Y)≥minsup且confi dence(X=>Y)≥minconf,称为关联规则X=>Y为强关联规则。
上述两个定义中的X、Y项集在应用中为频繁项集的子集。所以关联规则的挖掘分为两个问题:
(1)根据minsup找出数据集D中的所以频繁项集
(2)在频繁项集的子集中找出满足minconf的子集
对于第二步在实际应用中,对于每个找出的频繁项集S,输出所有的规则a=>S–a,其中a是S的一个子集,检验confi dence(a=>S–a)≥minconf成立,则a=>S–a为强关联规则。根据定理1,若果有a的子集ã,则ã的支持度不小于a的支持度,所以confi dence(ã=>S–ã)≥minconf如果成立,则confi dence(a=>S–a)≥minconf也成立,因为confi dence(a=>S–a)大于confi dence(ã=>S–ã)。
频繁项集的寻找采用算法Apriori,Apriori使用逐层搜索的迭代算法,利用k-项集来探索(k+1)-项集。
2.2 行业财务指标的关联规则挖掘
由上节中表6某行业的某季度财务指标转化后的布尔数据统计表,来说明采用算法Apriori寻找频繁项集。设最小支持度为20%,最小置信度阈值为60%。
首先由表6得到事务集表,如表7:
最小支持度minsup=(2+2+3+4+5+2+3)×20%=4.2
(1)所有的项构成候选1-项集,如表8。
构成频繁项集支持度个数要满足大于4.2,项集中的支持度计数大于4.2的项集构成频繁1-项集,如表9。
(2)对表9频繁1-项集中的项集做连接操作得到候选2-项集,在这里有一个数据类型约束条件,即同类型属性的不同取值的连接操作是无效的,如{FIN11,FIN12},或{FIN12,FIN13},因为FIN11,FIN12,FIN13是同一个财务指标的不同取值,一个财务指标不可能有两个值,所以他们的连接是无效的。候选2-项集如表10。
提取支持度个数满足大于4.2的项集构成频繁2-项集如表11。
(3)对表11频繁2-项集中的项集做连接操作得到候选3-项集,在连接时同理要考虑到数据类型约束条件,候选3-项集如表12。
提取支持度个数满足大于4.2的项集构成频繁3-项集如表13。
(4)因为事务表项中事务最大项集个数为3,不可能有包含频繁4-项集,即频繁4-项集为空。算法停止。
根据所得频繁3-项集生成关联规则如下:
FIN12=>FIN22∪FIN32置信度为:
满足最小置信度60%要求的规则有FIN12=>FIN22∪FIN32,
根据上述项集与其子集的关联规则关系,ã为a的子集,则confi dence(ã=>S–ã)≥minconf如果成立,则confi dence(a=>S–a)≥minconf也成立。所以可知,因为FIN12=>FIN22∪FIN32能满足最小置信度,所以其超集FIN12∪FIN22,FIN12∪FIN32构成的规则:
都能满足最小置信度,所以得到上述两个满足条件的关联规则。
对于不满足最小置信度的两条规则
FIN22的超集有FIN12∪FIN22和FIN2∪FIN32,FIN32∪FIN12,这里只有FIN2∪FIN32=>FIN12未知其置信度是否满足最小置信度。
FIN22∪FIN32=>FIN12的置信度为:
该规则不满足最小置信度,舍弃。最后得到的符合条件的关联规则有:
由FIN12,FIN22,FIN32的财务指标意义来看,FIN2是主营业务收入增长率的取值,FIN22是流动比率取值,FIN32是每股收益增长率取值。
规则(1)说明了当主营业务收入增长率取得平均水平时,该行业的流动比率或每股收益增长率取值也会取得平均水平。
规则(2)说明了当主营业务收入增长率或每股收益增长率取得平均水平时,该行业的流动比率或取值也会取得平均水平。
规则(3)说明了当主营业务收入增长率或流动比率取得平均水平时,该行业的流动比率或每股收益增长率取值也会取得平均水平。
在实际应用中,因为每股收益是企业经营成果的指标,是对某个季度结束后经营结果的综合体现。而主营业务收入增长率或流动比率是反映企业财务某一方面的指标,所以规则(1)和规则(3)更有应用意义。根据挖掘出来的关联规则在查询该行业时的上市公司财务是,就可以进行有目的选择主营业务收入增长率和流动比率进行查看,从而形成该企业经营成果是否有增长的佐证。
每次将挖掘出来的关联规则进行存储进数据库,以便查询时提供给用户参考。
摘要：在一个行业的财务报表中,蕴含着行业的经营规律,找出这些规律对投资者在做财务分析时有潜在的价值。本文介绍一种运用数据挖掘理论中的关联规则挖掘算法来发现这些行业经营规律的方法,文中重点讨论了如何在财务报表数据的支持下运用关联规则算法探寻这些规律。
关键词：数据挖掘算法,关联规则,概化处理事务表,频繁项集,置信度
参考文献
[1]lan H.Witten Eibe Frank.Data Mining Practical Machine Learning Tools and Techniques with Java Implementations.China Machine Press.2003.9,57-116.
[2]朱济生,徐全智,朱宏.概率论与数理统计[M].成都:电子科技大学出版社,1995,155-156.
[3][美]Pang-Ning Tan,Michael Steinbach.,Vipin Kumar.数据挖掘导论[M].北京:人民邮电出版社,2006,53-83.
挖掘空间关联规则算法的应用研究 篇8
1 GIS数据库中SDMKD可以使用的方法
笔者认为，在现阶段，至少有以下方法适用于GIS数据库中的SDMKD。
1.1 归纳与演绎的方法
这是从数据库中获取知识的最基本的方法，即从多个已存在的事实中归纳出规则。在GIS中，无论是属性数据还是空间拓扑关系，若进行抽象和概括时，均可用到此方法。
1.2 空间分析的方法
空间分析是指分析对象的位置和对象的属性。空间分析的主要目的是从空间关系中开发数据，以得到空间的内部关系并加以理解。GIS数据库中的空间数据提供了空间分析所需要的位置，非空间数据提供了对象的属性数据，因此GIS数据库提供了空间分析所需要的各种数据，利用GIS数据库中的数据可以进行空间分析。
1.3 统计的方法
统计的方法一直是SDMKD中最主要的方法。如在遥感影像分析中，对影像进行监督分类和非监督分类，都是利用统计的方法得出影像模式后，再按此模式对影像分类。实际上，遥感影像的计算机自动分类也可算是较简单的数据挖掘过程，只是其数据为一些以栅格方式存储的影像数据，而不是像关系数据库中的数据那样以关系元组的方式存储。
1.4 Rough集方法
Rough集理论(Rough Sets Theory)是波兰华沙大学Z.Pawlak教授在1982年提出的一种智能数据决策分析工具，被广泛研究并应用于不精确、不确定、不完全的信息的分类分析和知识获取。Rough集理论可用于GIS数据库属性表的一致性分析、属性的重要性、属性依赖、属性表简化、最小决策和分类算法生成等。Rouxh集方法与其它知识发现方法相结合，可以在GIS数据库中数据不确定情况下获取多种知识。
2 基于空间关联规则挖掘算法的数据挖掘软件的体系结构
数据挖掘软件的体示结构如图1所示，各部件的功能如下:
(1)数据库管理模块：主要贮存、管理和提取GIS空间数据库中的数据;
(2)方法库管理模块：主要存放、管理和提取挖掘方法库中的各种算法构件;
(3)知识库管理模块：主要贮存、管理和提取基础知识库中的知识，如概念树;
(4)工作空间：为空间数据挖掘进程运行提供场所;
(5)衍生知识库;临时存放数据挖掘结果。
3 空间关联规则算法
空间关联规则是空间数据库中普遍存在的一种重要的知识类型，将事务数据库中常用的关联规则挖掘算法与空间数据访问方法以及表达背景知识的概念树相结合，可有效地挖掘高频发生和获得多数案例支持的多层强空间关联规则，其算法描述如下。
输入:空间数据库、挖掘查询和一组阀值。
(1)数据库由3部分组成： (1) 包含一组空间对象的空间数据库，SDB; (2) 一个描述空间对象的非空间属性的关系数据库，RDB; (3) 一组概念树集合。
(2)查询由以下几部分组成: (1) 被描述对象的参照集S; (2) 用于描述S中对象的与任务相关的空间对象C1，…，C2的集合; (3) 与任务相关的空间关系的集合。
(3)概念树的每一层描述中有两个阀值:最小支持度(minsup[L])和最小可信度(minconf[L])。
输出:与对象集和关系集相关的强多层空间关联规则。
方法:挖掘空间关联规则过程如下:
第一步通过执行空间查询，将所有与任务相关的对象收集到数据库Task_relevant_DB中;
第二步计算所有对象的最小边界矩形(MBR)的交，抽取MBRS间距离落在预设阀值之内的对象，并将描述对象间空间关系的渭词存贮在数据库Coarse_predicate_DB中;
第三步为Coarse_predicate_DB中的谓词计算支持度，并过滤掉支持度低于最小支持度阀值的对象，从而形成数据库Fre quent_coarse_DB;
第四步在Frequent_coarse_DB上执行精确空间计算形成数据库Fine_predicate_DB;
第五步采用常规关联规则挖掘算法在Fine_predicate_DB上抽取强空间关联规则。
上述算法的第二步到第五步的最坏时间复杂度为O (n*logn+m+Cf*m+Cnon-spatial)，其中n为数据库中的空间对象数目，m为参与精确空间计算的空间对象数目，Cf为每个空间对象执行精确空间计算的成本，Cnon-spatial是从Fine_predicate_DB中抽取的关联规则的成本。
4 应用
基于SDMKD的数据挖掘软件从湖北农产品市场信息系统中挖掘油菜籽价格与铁路、国道和河流位置之间的关联规则。湖北农产品与市场信息系统由交易(包括品种名、价格、地理位置等，共210条记录)、铁路(包括铁路名、地理位置等)、国道(包括国道名、地理位置等)和河流(包括河流名、地理位置等)等表格组成。
利用该软件的空间规则挖掘方法，并设定不同空间对象间符合接近关系的距离阀值为25公里，最小值支持度阀值为0.3，最小可信度阀值为0.85，则可在概念树顶层发现如下所示的关联规则。
is_a (X，交易市场)^high(价格)→g_close_to (X，铁路)^g_close (X，国道)(25.5%，100%)
此规则意味着：油菜籽价格高的交易市场100%接近铁路和国道，它覆盖数据库中的28.5%的纪录。
调整最小支持度阀值为0.15，在概念树第二层可发现如下的关联规则:
is_a (X，交易市场)^g_close_to (X，京广线)→high(价格) (18%, 100%)
此规则意味着：接近京广线的交易市场100%油菜籽价格高，它覆盖数据库中的18%的纪录。上述规则对预测和指导农产品交易具有重要的实用价值。
5 结束语
从GIS数据库中挖掘空间关联规则是数据挖掘也是空间数据挖掘研究的一个特例，存在于计算机世界到现实世界的反馈过程中，需要充分理解GIS的有关知识，并涉及到地理空间认知的相关理论和内容。研究空间数据的处理方法，特别是从数据库技术角度探讨空间数据挖掘对空间数据的处理方法具有非常重要的理论和现实意义。
参考文献
[1]李德仁, 王树良, 史文中.论空间数据挖掘和知识发现[J].武汉大学学报 (信息科学版) , 2001 (6) .
[2]马荣华, 黄杏元, 朱传耿.用ESDA技术从GIS数据库中发现知识[J].遥感学报, 2002 (3) .
[3]马荣华, 马晓冬, 蒲英霞.从GIS数据库中挖掘空间关联规则研究[J].遥感学报, 2005 (6) .