—56—
一种用于挖掘正负关联规则的可量化标准
赵 亮
1
,萧德云
1
,刘震涛
2
(1. 清华大学自动化系,北京 100084;2. 清华大学台湾研究所,北京 100084)
摘 要:传统的关联规则数据挖掘的支持度-置信度框架存在着弊端。一方面,它不能发现同时满足支持度和置信度而其前提和结论却相互
独立的规则;另一方面,也不能区分正负关联规则。该文提出了一种评价关联规则的可量化的标准,进一步提出一种同时挖掘正负关联规
则的框架,用此框架来分析调研问卷。
关键词:负关联规则;相关性;数据挖掘;问卷
Quantitative Criterion for Mining Both Positive and Negative
Association Rules
ZHAO Liang
1
, XIAO Deyun
1
, LIU Zhentao
2
(1. Department of Automation, Tsinghua University, Beijing 100084; 2. Institute of Taiwan Studies, Tsinghua University, Beijing 100084)
【Abstract】The conventional framework for mining association rules is the support-confidence framework which has some limitations. For one
thing, it can not prune such useless rules as satisfy both minimum support and minimum confidence with their antecedents and consequents
independent. For another thing, it can neither separate the negative association rules from the positive ones. The purposes of this paper are to find a
quantitative criterion for mining both positive and negative association rules, and further put forward a novel framework whose efficiency is tested in
analyzing a questionnaire.
【Key words】Negative association rules; Correlation; Data mining; Questionnaire
计 算 机 工 程
Computer Engineering
第 33 卷 第 2 期
Vol.33 No.2
2007 年 1 月
Januar
2007
·软件技术与数据库·
文章编号:1000—3428(2007)02—0056—03
文献标识码:A
中图分类号:TP311
关联规则的数据挖掘是从大量数据中挖掘出内在联系的
方法,常用在购物篮分析中。在调研问卷分析中也常有类似
的需求:哪些调查题目之间存在着内在的联系?本文尝试用
关联规则数据挖掘方法来分析一份甲地区对乙地区看法的调
研问卷。现在对于关联规则的挖掘多是侧重于基于支持度
-
置信度框架的正关联规则的挖掘。设有事件
A
和
B
,正关联
规则类似于“事件
A
导致事件
B
”,可以写成
B⇒
的形式。
如果得到这样的规则“事件
A
将导致
B
不发生”,这就是负
关联规则,记作
B⇒¬
(
符号“
”表示“非”或“不”等
否定含义
)
。对于负关联规则相关研究却比较少,但是负关联
规则同样可以给我们带来有价值的规则。本文提出一个分类
正、负关联规则可量化的标准,并藉此提出频繁集中挖掘有
用正负关联规则的框架。
1
负关联规则挖掘
1.1
支持度
-
置信度框架
评判关联规则是否有用的框架中,一般比较流行的是
R.
Agrawal
提出的支持度
-
置信度框架
(support-confidence)
[1]
。
设
12
{, ,..., }
m
ii i=
是项的集合。设任务相关的数据
D
是
数据库事务的集合,其中每个事务
T
是项的集合,使得
TI⊆
。
每个事务有一个标识符,称作
TID
。设
A
是一个项集,事务
T
包含
当且仅当
T⊆
。关联规则是形如
B⇒
的形式,
其中
I⊂
,
BI⊂
,并且
AB∩=∅
。规则
B⇒
在事物
D
中成立,具有支持度
,其中
是
D
中事务包含
AB∪
的百
分比。它的概率为
()
AB∪
。规 则
B⇒
在事务集
D
中具有
置信度
c
,如果
D
中包含的事务同时也包含
B
的百分比是
c
。
这是条件概率
(|)
BA
,即
()()
upp A B P A B∪= ∪
()(|)conf A B P B A⇒=
关联规则满足最小支持度,如果
频率大于或等于
min_conf
;关联规则满足最小置信度,如果
c
频率大于或等
于
min_conf
。同时满足最小支持度
(min_supp)
和最小置信度
(min_conf)
的规则称为强规则。
1.2
支持度
-
置信度框架的缺陷
在调研问卷的数据挖掘中,可以发现仅仅考虑正关联规
则是不够的。假设所考虑集合中有
10 000
个数据项,其中包
含事件
A
和
B
,同时包含事件
A
和
B
二者记为
B∪
。设
包含
A
的有
6 000
项,包含
B
的有
5 000
项,包含
B∪
的
有
2 500
项,
min_sup=0.2
,
min_conf=0.3
。那么
()
upp A B∪
=
0.25>min_supp
,
()conf A B⇒
=0.42>min_conf
,得到
B⇒
是
强关联规则。再考虑
AB⇒¬
。
()
upp A B∪¬
= 0.35>min_supp
,
()conf A B⇒¬
=0.58>min_conf
,这说明
B⇒¬
也是强关联规
则。然而这与
AB⇒
相矛盾,同时由于
()conf A B⇒¬
>
()conf A B⇒
,
B⇒¬
应该更可靠一些。
这是由于
()conf A B⇒
=
(|)
BA
<
()
B
,说明由于
A
的
发生
B
发生的概率反而下降了,因此
A
和
B
应该是相互削弱
的关系。然而这是支持度
-
置信度框架所无法识别的。
1.3
负关联规则
设任务相关的数据
D
是数据库事务的集合中有项集
A
和
作者简介:赵 亮(1980-),男,硕士,主研方向:数据挖掘;萧德
云,博士、教授、博导;刘震涛,教授
收稿日期:2006-01-29 E-mail:zhaoliang@sjtu.org
万方数据