当前位置：文档库 › 基于粗糙集的感性知识关联规则挖掘研究_石夫乾

基于粗糙集的感性知识关联规则挖掘研究_石夫乾

第14卷第2期计算机集成制造系统

Vol.14No.22008年2月

Computer Integrated Manufacturing Systems

Feb.2008

文章编号:1006-5911(2008)02-0407-05

收稿日期:2007-04-02;修订日期:2007-07-06。Received 02Apr.2007;accep ted 06July 2007.

基金项目:国家自然科学基金资助项目(60475025);教育部博士点专项基金资助项目(20050335096)。Foundation item:Project supported by

th e National Natu ral Science Foundation,China (No.60475025),and th e Specialized Research Fun d for the Doctoral Program of H igher Education,China(No.20050335096).

作者简介:石夫乾(1975-),男,浙江温州人,浙江大学计算机学院现代工业设计研究所博士研究生,讲师,主要从事计算机辅助设计与概念设

计、计算机网络的研究。E -mail:sawdu st_ghost@https://www.wendangku.net/doc/7e7800088.html, 。

基于粗糙集的感性知识关联规则挖掘研究

石夫乾,孙守迁,徐江

(浙江大学计算机学院现代工业设计研究所,浙江杭州 310027)

摘要:为有效获取概念设计中的感性信息,提出了一种基于粗糙集的感性知识关联规则挖掘方法。首先,在用户进行感性调查与产品造型特征组合评价的基础上,运用统计学方法,生成一个由感性词汇索引的决策表;其次,通过粗糙集理论对相关属性进行约简,以提取对相应感性评价贡献较大的造型特征;再次,进一步构造出基于粗糙集的关联运算法则及规则合并,以缩小决策表规模。最终得到了关键特征对感性描述的强关联规则集,并以此引导概念设计定位和开发。实例证明,该方法在手机产品的感性知识关联规则挖掘中得到了较好的应用。

关键词:感性工学;粗糙集理论;关联规则挖掘

中图分类号:T P182

文献标识码:A

Association rule mining of Kansei knowledge based on rough set

SH I Fu -qian,S UN Shou -qian,X U J iang

(Instit ute o f Co ntempor ary Industry Design,Schoo l of Co mputer Science &T echno lo gy ,

Zhejiang U niv ersity ,H angzho u 310027,China)

Abstract:T o acquire Kansei infor mation eff ectively in the co nceptual desig n,a new metho d of asso ciatio n r ule mining for Kansei know ledge based o n r ough set theor y was pr oposed.F ir stly ,with combinator ial ev aluation of the pro duct form featur es,a decisio n table index ed by K ansei wo rds w as generated by the statistical analysis o n user c s K ansei questionnaire.And then,r elev ant att ributes w ere simplified by ro ug h set theo ry so as to ex tract the key fo rm fea -tur es which co nt ributed lar gely to the cor respo nding K ansei evaluat ion.A ssociation co mputation r ules and their mer -g ence w ere constructed to r educe the scale o f the decision t able.Finally ,stro ng -asso ciatio n -r ule -sets w ere generated to g uide the or ientation and develo pment o f the concept ual desig n.T he proposed metho d w as implemented success -fully in t he cell pho ne design case.

Key words:K ansei eng ineering ;r ough set theo ry ;associat ion rule mining

0 引言

在各种各样的用户需求中,用户的感性需求分析极其重要,所以在产品设计中,应充分考虑用户的感性需求。所谓感性需求是指用户对产品的一种心理学反应。研究人员通过眼动、脑电等心理学实验技术手段,来获取用户在认同或者不认同某一概念产品的心理过程,如美国心理学家Osg ood 提出了能将用户感性认知信息量化为语义差分(Sem antic

Differential,SD)法[1]

。另外,在感性信息调查基础上还发展了运用多种数学建模技术获取感性知识规则,指导概念设计行为展开的感性知识发现方法。如美国和日本的专家学者分别从情感计算[2]和感性工学[3]的不同角度,研究如何利用数据库技术和人工智能技术提取有用的主观感性信息。国内也有专家提出了基于粗糙集(Rough Set,RS)的个性化配

置器规则提取模型[4]

。本文在用户进行感性调查与产品造型特征组合评价基础上,提出了一种基于粗

计算机集成制造系统第14卷

糙集的感性知识关联规则挖掘方法。该方法通过粗糙集理论对相关属性进行约简,以提取对相应感性评价贡献较大的造型特征;进一步构造出基于粗糙集的关联运算法则及规则合并来缩小决策表规模,获取关键特征对感性描述的强关联规则集,并以此引导概念设计定位和开发,优化产品概念设计过程,从而更好地满足用户情感需求。

1 研究框架

本文通过建立基于Web 的感性调查表,获得用户感性评价信息,然后运用统计学的方法对数据进

行预处理,汇总频繁出现的相同评价,当汇总值达到一定程度时,将该信息存入决策表。同时,本文确定造型特征集为决策表的条件属性集,进行评价的感性词汇集为决策属性集。然后通过粗糙集约简算法对属性进行约简,以提取关键的造型特征,删除冗余的属性。在基于关联规则的模块中,本文重新定义规则空间和关联运算相应指标体系,来挖掘相应造型特征对总体评价的强规则集,最终得到一个合并后的多阶强规则集,从而确定了由感性描述的某一产品与局部造型之间的关系。具体如图1

所示。

2 粗糙集理论

2.1 研究背景

数据库中的知识发现(Kno w ledge Discovery in Database,KDD)是近年来随着数据库技术和人工智能技术的发展而出现并发展起来的,它是利用机器学习的方法从数据库中提取有价值的知识的过程[5]

。粗糙集理论是由波兰学者Paw lak 在1982年提出的

[6]

,该理论已日益受到国际学术界的重视,己

经在模式识别、知识发现与机器学习[7]

、决策支持、

数据挖掘

[8]

等许多科学与工程领域得到了成功的应

用。粗糙集理论是一种刻画不完整和不确定性信息

的数学工具,能有效地分析和处理不精确、不一致、不完整等各种不完备的信息,并从中发现隐含的知识,揭示潜在的规律。

粗糙集理论将知识定义为不可分辨关系的一个族集,这使得知识具有了一种清晰的数学意义,并可使用数学方法进行处理。粗糙集理论能够分析隐藏在数据中的事实而不需要关于数据的任何附加信息。粗糙集理论认为,知识的粒度性(inform ation g ranules)是造成使用已有知识不能精确地表示某些概念的原因。通过引入不可分辨关系作为粗糙集理论的基础,并在此基础上定义了上下近似等概念,使粗糙集理论能够有效地逼近这些概念。模糊集和概率统计方法是处理不确定信息的常用方法,但这些方法需要一些数据的附加信息或先验知识,而粗糙集理论不需要先验知识。目前,粗糙集理论己成为人工智能领域中的一个较新的学术热点,引起了越来越多的科研人员的关注。2.2 定义

下面给出粗集约简算法中用到的一些基本定义:

定义1 X 中包含在R 中的最大可定义集称为X 的下近似(lo w er approx imation ):

R -(X )={x I U B [x ]R

定义2 X 中包含在R 中的最小可定义集称为X 的上近似(upper appro ximation ):

R -

(X )={x I U B [x ]R

定义3 X 的R 边界为集合:

BN R (X )=R -(X )-R -(X ),Pos R (X )=R -(X )表示X 的R 正域。

令N eg R (X )=U -R os R (X )表示X 的R 负域,BN R (X )表示X 的边界域。如果边界域为空集,则X 是R 可定义集。

定义4 若R 为一等价关系,且r I R ,当ind (R )=ind(R -{r})时称r 为R 中可省略的(dispen -sable),否则为不可省略(indispensable );当P r I R,R 不可省略,则族R 为独立的(independent)。

定义5 当Q 独立且ind (Q)=ind (P )时,Q

408

第2期石夫乾等:基于粗糙集的感性知识关联规则挖掘研究

2.3约简与核计算

决策表的约简包括属性约简与值约简,通过属

性约简来删除对决策结果不产生影响的条件属性,

以此达到约简的目的。约简后的决策表具有较少的

条件属性但保留约简前的功能。具体步骤如下:

步骤1删除重复行。

步骤2设c1,c2,,,c n为属性集C的属性子

集。分别计算A i=U/ind(c i),其中D为决策子集。

步骤3令族集R={A i|i=1,2,,,n},计算

U/ind(R)。

步骤4由族集R导出分类可得到Pos R(E)。

步骤5分别计算U/ind(R-A i),并判断其结

果是否与P os R-A

(E)相等。如果相等,则相应的A i

属性是可省略的,在决策表中将该条件属性删除;如

果不等,则该相应属性是不可省略的。所有不可省

略的条件属性集称为核。

3基于粗糙集的关联规则挖掘

3.1关联规则定义

(1)关联法则(asso ciation rule)在决策表DT

中,c I C为条件属性,d I D为决策属性,规则c]d

表示属性c对决策的关联;代表c的出现会导致d

的出现。

(2)支持度(suppor t)指某项目集在数据库中

出现次数的频率,常以S up(X)表示,其中X表示某

一项目集。支持度越高,代表此项目集在此数据库

中越受欢迎。在本文中,决策表中规则的支持度常

以Sup(c]d)表示;本文用统计学的方法对这条规

则在决策表中出现的次数来定义条件属性c与最终

决策d的关联支持度,其计算公式为

Sup(c]d)=

Count(c C d)

Count(CD|D i)

。(1)

其中,Count(CD|D i)表示决策属性为D i的记录集。

(3)最小支持度(m inimum support)在关联法则挖掘时,若某项目集的支持度太低,则不具代表性。因此,在利用算法挖掘规则前,先定一个支持度的门坎值,此门槛值称为最小支持度,记为Min-Sup。

(4)信心度(confidence)定义关联法则可信的程度。若关联法则为c]d,信心度是指c出现的条件下,d也会出现的条件机率,定义为

Conf(c]d)=Count(c C d)

Count(c)

。(2)

(5)最小信心度(m inimum confidence)与最

小支持度类似,使用者在挖掘关联规则前,必须先定

一个最低信心度值,将信心度未达门坎值的关联规

则直接删除,因为信心度太低的关联规则不具代表

性,记为M in-Conf。

(6)确定规则集如果S up(c]d)\M in-S up

且Conf(c]d)\M in-Conf,则本文称规则c]d是

确定规则集。

(7)强规则集确定规则集的联合(利用412节

的Apriori算法)。

3.2关联挖掘算法

设输入的决策表为DT,由第i阶规则合并的最

小支持度M in-S up(i)与最小信心度M in-Conf(i)

所产生的规则集为R k,本文参考的Apriori算法构

造如下:

步骤1对决策表进行属性约简(参见313

节)。

步骤2k=1。

步骤3计算候选集C k中每个规则支持度和

信心度。

步骤4若规则支持度小于最小支持度Min-

S up(i)和最小信心度Min-Conf(i),则将其从C k中

删除;反之,将该规则移入规则集R k。

步骤5将C k扩展为C k+1。先扫描C k,将C k

中的每两项组合成具有k+1个属性的候选项,插入

C k+1中;合并后的支持度与信心度都采用公式:

S up(c]d,e]f)

=min{Sup(c]d),Sup(e]f)}。(3)

Conf(c]d,e]f)

=min{Conf(c]d),Conf(e]f)}。(4)

然后本文使用M in-S up(i+1)和Min-Conf(i

+1)删除一些规则。

步骤6k=k+1,如果C k+1是空集,则转步骤

7,否则转步骤3。

步骤7结束。

4实例研究

4.1知识表示系统构建

近年来,一些学者从用户需求分析与设计行为

支持的角度,对手机产品造型特征和感性词汇知识

获取展开了深入研究。如文献[9]依据市场销售数

据记录,提取感性词汇和手机产品造型特征,M ing

从用户偏好的角度进行了手机产品的感性认知因素

409

计算机集成制造系统第14卷

研究[10]

。本文根据现有成果,以感性工学理论为指导来构建感性知识表示系统。令造型特征集为C ={C 1,C 2,C 3,C 4,C 5}={机身形状,音孔,屏幕盖面,方向键,按键},每一种造型本文给出了三种具有代表意义的造型特征(如图2),感性词汇集为D ={D 1,D 2,D 3,D 4,D 5}={休闲,可爱,轻薄,科技,运动}[11],则条件属性集为C,决策属性集为D,通过一个基于Web 的感性调查系统,获取了调查数据。用户对手机的造型进行选择,最后对其进行感性评价并存入数据库。通过对500人的调查,把产品造型选择与感性词汇选择均相同的记录进行自动汇总。如果记录出现的条数大于30,就认为该评价具有一定的代表性,可作为决策表的一条规则加入决策表。最终得到如表1所示的决策表。为方便描述,本文只列出对感性词汇D 1的决策表;接下来研

究整体的感性评价与各个局部造型之间的关系。

表1 决策表(D =D 1)

U C 1C 2C 3C 4C 5D 1112010020110113011000401000151222116122211710201182102209102001102011201100112112

续表1

1300102114

4.2 属性约简

首先,本文用粗糙集理论对决策表的属性进行约简,以提取对感性评价有重要贡献的属性。分别计算:Z 1=U/ind(C 1)={{2,3,4,11,13},{1,5,6,7,9,14},{8,10,12}},

Z 2=U/ind(C 2)={{7,9,10,11,13},{2,3,4,8,14},{1,5,6,12}},

Z 3=U/ind(C 3)={{1,4,8,12},{2,3,10,11,13},{5,6,7,9,14}},

Z 4=U/ind(C 4)={{2,3,4,7,9,13},{1,5,10,11,14},{6,8,12}},

Z 5=U/ind(C 5)={{1,3,4,9,12,14},{2,5,6,7},{8,10,11,13}},

Z 6=U/ind(D 1)={{1,3,5,8,10,12,14},{1,2,4,6,7,9,11,13}}。

令R ={Z 1,Z 2,Z 3,Z 4,Z 5},计算:

U/ind(R)={{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11},{12},{13},{14}},

P os R (Z 6)={1,2,3,4,5,6,7,8,9,10,11,12,13,14},

U/ind(R -Z 1)={{1},{2},{3},{4},{5},{6},{7},{8},{9},{10,11},{12},{13},{14}},

P os (R -Z 1)(Z 6)={{1},{2},{3},{4},{5},{6},{7},{8},{9},{12},{13},{14}}X P os R (Z 6)。因此Z 1是不可省略的。

U/ind(R -Z 2)={{1},{2},{3},{4},{5},{6},{7},{8},{9},{10,11},{12},{13},{14}},P os (R -Z 2)(Z 6)={{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11},{12},{13},{14}}=P os R (Z 6)。

因此Z 2是可省略的。通过计算P os (R -Z 3)(Z 6),P os (R -Z 4)(Z 6)和P os (R -Z 5)(Z 6),可知Z 3,Z 4,Z 5是不可省略的。因此Cor e ={Z 1,Z 3,Z 4,Z 5},删除C 2列。

4.3 强规则集提取

定义一个二元组形式(C i ,v )表示属性C i 的值是v ,决策属性D 1的值是dv;则规则转换成(C i ,v)](D 1,dv )。利用411节和412节中的定义与公式,得到24条一阶关联规则(如表2),如果一个规

410

第2期石夫乾等:基于粗糙集的感性知识关联规则挖掘研究

则的支持度(式(1))小于M in-S up(1),则不需计算其信心度(式(2));设定Min-S up(1)=3/14,M in-Conf(1)=0155,从表2得到八条规则,然后继续生成二阶关联规则C24@C12@C12=24条。如果两条形如(C1,0)](D1,1)和(C3,1)](D1,1),则利用412节描述的算法生成(C1,0),(C3,1)](D1,1);合并后的支持度与信心度用式(3),式(4)计算。根据Min-Sup(2)和Min-Conf(2),删除某些规则。同理,如果有两条二阶规则形如(C1,0),(C3,1)] (D1,0)和(C3,1),(C5,0)](D1,0),则可合并成(C1,0),(C3,1),(C5,0)](D1,0),继续该过程直到不能生成新的规则,最终得到感性知识强规则集(如表3),从规则集不难发现各感性词汇对应的造型特征(如图3)。

表2一阶关联规则

规则支持度信心度操作(C1,0)](D1,0)1/14-删除

(C1,1)](D1,0)3/143/6删除

(C1,2)](D1,0)3/141保留

(C1,0)](D1,1)4/144/5保留

(C1,1)](D1,1)3/143/6删除

(C1,2)](D1,1)0-删除

(C3,0)](D1,0)3/143/4保留

(C3,1)](D1,0)2/14-删除

(C3,2)](D1,0)2/14-删除

(C3,0)](D1,1)2/14-删除

(C3,1)](D1,1)3/143/5保留

(C3,2)](D1,1)2/14-删除

(C4,0)](D1,0)0-删除

(C4,1)](D1,0)4/144/5保留

(C4,2)](D1,0)2/14-删除

(C4,0)](D1,1)5/145/6保留

(C4,1)](D1,1)1/14-删除

(C4,2)](D1,1)1/14-删除

(C5,0)](D1,0)4/144/6保留

(C5,1)](D1,0)1/14-删除

(C5,2)](D1,0)2/14-删除

(C5,0)](D1,1)2/14-删除

(C5,1)](D1,1)3/143/4保留

(C5,2)](D1,1)2/14-删除

表3强规则集及相关造型特征分析

强规则集相关造型特征分析

(C1,2),(C4,1),(C5,0)](D1,0)

(C1,0),(C4,0),(C5,0)](D1,1)

休闲:造型机身形状为为矩

形,有小圆角;方向键排布相

对独立;音孔造型呈几何线条

排布

(C2,0),(C3,0),(C4,1)](D2,0)

(C2,1),(C3,1),(C5,1)](D2,1)

科技:屏幕盖面呈梭形;数字

键形状为规则矩形,排布紧

密;音孔造型为三角状排布

(C3,0),(C4,1),(C5,1)](D3,0)

(C1,2),(C3,1),(C5,0)](D3,1)

可爱:机身形状为中间凸起;

数字键形状为规则矩形,排布

紧密;有几何线条排布音孔

造型

(C2,2),(C4,1),(C5,0)](D4,0)

(C1,2),(C4,2),(C5,0)](D4,1)

运动:机身形状为不规则状;

方向键中含有大的键形,且排

布紧密;音孔造型为几何线条

排布

(C1,2),(C3,1),(C4,0)](D5,0)

(C1,1),(C2,1),(C3,2)](D5,1)

轻薄:机身形状为矩形,有小

圆角;屏幕盖面呈梭形;数字

键大小在垂直方向上依比例

渐变,

但形状不变

5结束语

通常情况下,运用粗糙集进行属性约简的方法较多,本文只是采用其中的一种,结合关联法则挖掘技术对用户的感性知识进行提取。研究重点在于对数据的预处理,使得决策表中的每一条记录都是大量用户认可的评价,在此基础上,粗糙集理论才能得到较好的应用;此外,关联法则的重新定义,特别是支持度与信心度的计算,经过实验验证是比较有效的。通过基于粗糙集的关联法则挖掘,本文得到了强规则集,这类集合给设计师与企业带来了产品设计的有用信息,使得企业能及时响应用户的需求。下一步的工作是如何开展全面调查,使得数据更加

(下转第416页)

411

计算机集成制造系统第14卷

[3]ZH ANG Y F,WONG Y S,LOH H T,et al.An adaptive s l-i

cing approach to m odeling cloud data for rapid pr ototyping [J].Journal of M aterials Proces sing Techn ology,2003,140 (1/3):105-109.

[4]PAN Haipeng,ZHOU Tianrui.Generation and optimiz ation

of s lice profile data in rapid prototyping and manufacturing [J].J ou rnal of M aterials Processing Techn ology,2007,187/ 188:623-626.

[5]ZH ANG Jiayi,L IU W eju n,W ANG Tianran,et al.Determ-i

nation of compensation dir ection for boundary curve in rapid prototyping direct slicing[J].Com pu ter In tegrated M anufac-turin g Sy stems,2003,9(10):906-909(in C hinese).[张嘉易,刘伟军,王天然,等.快速成型中直接切片边界曲线补偿方向判定[J].计算机集成制造系统,2003,9(10):906-909.]

[6]QI Liwei,ZHANG Biqiang,ZH AO Yi,et https://www.wendangku.net/doc/7e7800088.html, puter s imu-

lation of rapid prototyping process[J].Jou rnal of Shanghai Jiaotong University,2002,36(7):934-936(in C hinese).[亓利伟,张必强,赵毅,等.快速原型加工过程的计算机仿真[J].

上海交通大学学报,2002,36(7):934-936.]

[7]S HI Yush eng,LU Zhongliang,ZH ANG W enxian,et al.Th e

techn ology and equipment of selective laser meltin g[J].China S urface Engineering,2006,19(21):150-153(in Chin ese).[史玉升,鲁中良,章文献,等.选择性激光熔化快速成形技术与装备[J].中国表面工程,2006,19(21):150-153.]

[8]S HI Yush eng,ZH ONG Jianw ei,CAI Daosheng,et al.Inves-

tigation on the preheating temperatu re control based on part c s slicin g in selective laser sintering[J].Ch ines e J ou rnal of M e-chan ical E ngineering,2006,42(6):67-72(in Ch ines e).[史玉升,钟建伟,蔡道生,等.基于零件切片的选择性激光烧结预热温度控制方法[J].机械工程学报,2006,42(6):67-72.] [9]SH I Yusheng,ZHONG Qing,C HEN Xuebin,et al.Resear ch

and implemen t of a new kind of scanning mode for selective la-

ser s intering[J].C hinese J ournal of M echan ical Engineerin g, 2002,38(2):35-39(in Chinese).[史玉升,钟庆,陈学彬,等.选择性激光烧结新型扫描方式的研究及实现[J].机械工程学报,2002,38(2):35-39.]

[10]H UANG Shuh uai,XIAO Yuejia,M O Jianh ua,et al.Pros-

pects of rapid pr ototyping technology[J].Chin a M ech anical

Engineering,2000,11(1/2):195-200(in Chin ese).[黄树槐,

肖跃加,莫健华,等.快速成形技术的展望[J].中国机械工

程,2000,11(1/2):195-200.]

[11]ZH AO Jibin,LIU W eijun,W ANG Yuechao.Research on

beam radius compen sation algorithm for rapid prototypin g

technology[J].Computer In tegrated M anufactu ring Sys-

tems,2005,11(10):1475-1480(in Chin ese).[赵吉宾,刘伟

军,王越超.快速成型技术中的光斑半径补偿算法研究[J].计

算机集成制造系统,2005,11(10):1475-1480.]

[12]YU Gang,LIU Hehui.Error analysis and diagn os tics on

measu ring structure of a flexible laser mach ine sys tem[J].

Chin ese J ou rnal of M echan ical En gineering,2001,37(8):84-

87(in Chinese).[虞钢,刘荷辉.柔性激光加工系统中的测

量功能及其静态误差分析[J].机械工程学报,2001,37(8):

84-87.]

[13]LI Xu ejun,H U ANG W enqing.Fast trian gulation algorithm

for planar regions[J].Journal of Computer-Aided Design&

Computer Graphics,2003,15(2):233-238(in Chin ese).[李

学军,黄文清.平面区域三角化的快速算法[J].计算机辅助设

计与图形学学报,2003,15(2):233-238.]

[14]YAO Shan,YE Ch angk e,YE J ianan,et al.Research on pat-

tern-less quick casting based on laser rapid pr ototyping for

coated san d[J].Fou ndry Techn ology,2006,27(5):458-460

(in Chinese).[姚山,叶昌科,叶嘉楠,等.基于覆膜砂激光

快速成型的无模快速铸造方法研究[J].铸造技术,2006,27

(5):458-460.]

(上接第411页)

完备;另一方面,关联法则的算法和粗糙集的约简算法还有待进一步地研究。

参考文献:

[1]OSGOOD C,S UCI G,T ANNENBAUM P H.T he measur e-

m ent of m eaning[M].Urb ana,Ill.,USA:U nivers ity of Ill-i

nois Press,1957:15-18.

[2]PICARD R W.Affective computing[M].Camb ridge,M ass.,

U SA:M IT Pres s,1997:29-31.

[3]M ITS UO N.Kan sei engineering as a pow erful consum er-or-i

ented tech nology for pr odu ct development[J].Applied Ergo-nomics,2002,33(3):289-294.

[4]S UN Guozi,YU Dingw en,WU Zhijun.Research of individual

configu rator based on rough set[J].Compu ter Intergrated M anu facturing Systems,2005,11(2):168-172(in Chinese).

[孙国梓,郁鼎文,吴志军.个性化配置器的粗糙集方法研究[J].计算机集成制造系统,2005,11(2):168-172.]

[5]HS U S H,CH UANG M C.A seman tic differential s tudy of

designers c and u ser s c product form perception[J].International

Journ al of Indus trial Ergonomics,2000,25(4):375-391. [6]PAWL AK Z.Rough sets[J].In ternation al Journal of Com-

puter and Information S cien ces,1982,11(5):341-356.

[7]SKOWRON A.Rou gh sets and Boolean reas on ing[M]//Gran-

ular Computing:An Em erging Paradigm.Heidelb erg,Germa-ny:Physica-Verlag Gm bH,2001:95-124.

[8]YANG S M,NAGAM ACHI M,LEE S Y.Rule-based infer-

ence model for the Kansei engineering system[J].Internation-al J ou rnal of Indu strial Erg on om ics,1999,24(5):459-471. [9]KH ALID H M,HEL ANDER M G.A fram ew ork for affective

cus tom er needs in product design[J].T heor etical Iss ues in Er-gonomics Science,2004,5(1):27-42.

[10]CH UANGA M C,C HANG C C,HS U S H.Perceptu al fac-

tor s u nderlying u ser preferences tow ard product form of m o-

bile phone[J].Intern ational J ou rnal of In dustrial Ergonom-

ics,2001,27(2):247-258.

[11]JIAO J ianx in,ZH ANG Yiyang,H ELANDER M.A Kansei

minin g sys tem for affective design[J].E xpert Systems with

Applications,2006,30(4):658-673.

416

关联规则挖掘算法的研究

Ｖｏｌ．２９Ｎｏ．１Ｊａｎ．２０１３赤峰学院学报（自然科学版）ＪｏｕｒｎａｌｏｆＣｈｉｆｅｎｇＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）第29卷第1期（下） 2013年1月关联规则挖掘算法的研究目前是数据挖掘领域的一个重要方向，其中，Ａｐｒｉｏｒｉ算法就是一个经典的挖掘关联规则算法．１９９３年，Ａｇｒａｗａｌ等提出关联规则挖掘的相关概念，随后提出经典Ａｐｒｉｏｒｉ算法，它是一个采用两阶段挖掘思想的算法，且多次扫描事务数据库，直到寻找出给定数据集中数据项之间有趣的关联规则．1关联规则基本概念１．１关联规则关联规则是形如Ａ圯Ｂ的蕴含式，在关联规则中，有两个重要的概念：支持度和置信度．支持度是对关联规则的重要性的衡量，置信度是对关联规则的准确度的衡量，一般情况下，用户根据实际挖掘需要，预先给定最小支持度和最小置信度，通常情况下，如果规则的置信度和支持度大于用户指定的最小置信度和支持度，那么这个规则就是一条有效规则．事实上，有效规则并不一定具有实用性，还要参照关联规则的其他指标．定义1 设Ｉ＝｛Ｉ１，Ｉ２，…，ＩＭ｝是数据项的集合，Ｄ是全体事务的集合，一个事务Ｔ有一个唯一的标识ＴＩＤ．如果项集Ａ哿Ｔ，则称事务Ｔ支持项集Ａ，也称事务Ｔ包含项集Ａ．定义2 关联规则是形如Ａ圯Ｂ的蕴含式，其中Ａ奂Ｉ，Ｂ奂Ｉ，且Ａ∩Ｂ＝Φ．定义3 事务数据库Ｄ中有Ｎ条交易事务，关联规则Ａ圯Ｂ的支持度定义为：ｓｕｐｐｏｒｔ（Ａ圯Ｂ）＝ｓｕｐｐｏｒｔ（Ａ∪Ｂ）×１００％．定义4 置信度定义为：ｃｏｎｆｉｄｅｎｃｅ（Ａ圯Ｂ）＝ｓｕｐｐｏｒｔ（Ａ∪Ｂ）×１００％．引理1 在数据库中若有一事务Ｔ其长度小于Ｋ＋１，则由Ｋ项频繁集生成Ｋ＋１项频繁集时，事务Ｔ是没必要扫描的．１．２Ａｐｒｉｏｒｉ算法的基本思想Ａｐｒｉｏｒｉ算法是发现关联规则的经典算法．该算法分两个步骤发现关联规则：第一步通过迭代，找出事务数据库中的所有频繁项集，即支持度不低于最小支持度的项集；第二步利用频繁项集构造出满足用户最小可信度的规则．2 Apriori 算法的不足之处Ａｐｒｉｏｒｉ算法最大的优点是算法思路比较简单，它以递归统计为基础，生成频繁项集，易于实现．Ａｐｒｉｏｒｉ算法虽然能够从海量数据中挖掘出关联规则，但是算法在执行速度和效率上有一定的局限性，表现如下：２．１Ａｐｒｉｏｒｉ算法会产生大量的候选项集．该算法是由候选集函数Ａｐｒｉｏｒｉ－Ｇｅｎ利用Ｌｋ－１项产生候选项集Ｃｋ，所产生的Ｃｋ由ＣｋＬｋ－１项集组成．显然ｋ越大产生的候选项集的数目就越多．２．２Ｉ／Ｏ负载过大．Ａｐｒｉｏｒｉ算法需要多次扫描事务数据库，需要很大的Ｉ／Ｏ负载．对每次ｋ循环，候集Ｃｋ中的每个元素都必须扫描数据库１次来决定其是否加入Ｃｋ．例如，一个频繁大项目集包含１２个项，那么就至少扫描事务数据库１２遍．3 对Apriori 算法的改进算法改进的思路１．改变数据的存储结构，用二进制位存储各项目的事务集，矩阵的列代表频繁Ｋ－项集，矩阵的行代表事务，其中１表示该项目在某事务中出现，０表示该项目在某事务中没有出现．２．生成频繁１－项集．首先扫描源数据库，生成矩阵．统计每列中包含１的数目，得到该项目的支持事务数，如果该项的支持事务数大于最小支持事务数，则该项是频繁项集，否则是非频繁项集．从矩阵中将该列删除，并根据引理１，在矩阵中删除第９行，得出频繁１－项集．３．由频繁１－项集生成频繁２－项集．对频繁１－项集中的项两两连接得出候选２－项集，也就是对矩阵中第ｉ列所代表的项集和第ｊ列所代表的项集进行逻辑与操作．然后计关联规则挖掘算法的研究张丽（湖南文理学院经济与管理学院，湖南常德415000）摘要：本文介绍了数据挖掘中的关联规则经典Ap r i or i 算法.针对Ap r i or i 算法在执行速度和效率上的缺点，提出了一种改进的Ap r i or i 算法. 关键词：Ap r i or i ；算法；关联规则中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１６７３－２６０Ｘ（２０１３）０１－００２２－０２基金项目：湖南文理学院2010年度青年启动课题（QNQD1017）２２－－

关于关联规则挖掘综述

关联规则挖掘综述潮娇娇摘要：关联规则挖掘是数据挖掘中的一个很重要的研究内容之一，近年来很多国内外研究人员对其进行了大量的研究。为了更进一步的了解关联规则挖掘技术，并掌握其发展方向和目前的研究现状。本文对关联规则挖掘技术进行了相关综述。首先介绍了关联规则的基本概念，其次分析了近年来一些经典关联规则算法的改进，并概述了相关算法在实际中的应用。最后对关联规则挖掘技术未来的发展趋势进行了讨论。关键字：关联规则；算法；数据挖掘； Abstract: association rule mining is one of the important data mining research contents in this year, many domestic and foreign researchers have done a lot of research on it. In order to understand further the association rule mining technology, and grasp the development status and direction of research at present. This article of association rule mining technology related review. Firstly introduces the basic concepts of association rules, then analyzes the improvement of some classical algorithm of association rules in recent years, and summarizes the application of related algorithms in practice. At the end of the association rule mining technology development trend in the future are discussed. Key words: association rules; algorithms; data mining; 引言随着计算机技术与数据库技术的飞速地发展，数据资源越来越多。但巨大的数据，依然没有解决我们的信息需求问题，针对这种情况，产生了数据库的数据挖掘。与传统技术相比，数据挖掘技术是一种新型的信息处理技术，能够自动和智能地把位置数据或者大量数据中潜在信息转换成人们需要的信息和知识的技术。它可以从数据库提取有用的知识、规律以及更高层次的信息，对这些进行分析，帮助人们更有效的利用海量数据中存在的价值。目前对数据挖掘的发展趋势及研究方向主要集中在数据挖掘的数据总结、分类、聚类、关联规则等方面。而关联规则挖掘作为数据挖掘的核心内容之一，进来得到了很快的发展。并已经成为当今数据挖掘的热点。为此，对关联挖掘技术的研究具有重要的意义。本文将重点介绍关联规则挖掘技术的相关研究。主要对近年来关联规则挖掘技术的算法改进进行综述以及未来的发展方向。 1、关联规则基本概念 1.1 相关介绍关联规则作为数据挖掘的核心研究内容之一，它是大量数据中发现信息之间可能存在的某种关联或者相关联系。通过分析这些挖掘出的数据联系，可以在现实中帮助我们预测或决定某些事情将会发生。有效的提高了我们制定出准确的决策。目前，关联规则挖掘技术广泛应用于金融、互联网、医学等多个领域。最早的关联挖掘是未来发现交易数据库中不同商品之间的联系，通过分析这种联系获得有关购买者的一般的购买模式。从而有助于商家合理地安排进货、库存及货架设计，更好的制定发展计划和规避风险。

数据挖掘中关联规则挖掘的应用研究

数据挖掘中关联规则挖掘的应用研究吴海玲，王志坚，许峰河海大学计算机及信息工程学院，江苏南京（210098）摘要：本文首先介绍关联规则的基本原理，并简单概括其挖掘任务，然后说明关联规则的经典挖掘算法Apriori 算法，通过一个实例分析进一步明确关联规则在CRM 中的应用，最后展望了关联规则挖掘的研究方向。关键词：数据挖掘，关联规则，Apriori 算法，CRM 引言关联规则是表示数据库中一组对象之间的某种关联关系的规则，关联规则挖掘的主要对象是交易(Transaction)数据库。这种数据库的一个主要应用是零售业，比如超级市场的销售管理。条形码技术的发展使得数据的收集变得更容易、更完整，从而可以存储大量的交易资料。关联规则就是辨别这些交易项目之间是否存在某种关系。例如：关联规则可以表示“购买了商品A 和B 的顾客中有80％的人又购买了商品C 和D”。这种关联规则提供的信息可以用作商品目录设计、商场货架的布置、生产安排、具有针对性的市场营销等。 [1] 1 关联规则的基本原理设Ｉ＝｛i 1，i 2，……，i m ｝是项的集合，设任务相关的数据D 是数据库事务的集合，其中每个事务T 是项的集合，使得T I 。每一个事务有一个标识符，称作T ID 。设X 是一个项集，事务T 包含X 当且仅当X T 。关联规则是形如X Y 的蕴涵式，其中X I ，Y ?I ，并且X ∩Y ＝?。规则X Y 在事务集D 中成立，具有支持度s ，其中s 是D 中事务包含X ∪Y （即X 和Y 二者）的百分比，它是概率P （X ∪Y ）。规则X Y 在事务集中具有可信度c ，如果D 中包含X 的事务同时也包含Y 的百分比c 。这是条件概率P （X Y ∣）。即是 ??????support(X ?Y)= P （X Y ∪） confidence(X ?Y)= P （X Y ∣）同时满足最小支持度(minsup)和最小可信度阈值（minconf ）的规则称作强规则[1]。项的集合称为项集（itemset ）。包含k 个项的项集成为k －项集，例如集合{computer, software }是一个2—项集。项集的出现频率是包含项集的事务数，简称为项集的频率。项集满足最小支持度minsup ，如果项集的出现频率大于或者等于minsup 与D 中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集(frequent itemset) [2]。 2 关联规则的发现任务关联规则挖掘的问题就是要找出这样的一些规则，它们的支持度或可信度分别大于指定的最小支持度minsup 和最小可信度minconf 。因此，该问题可以分解成如下两个子问题[3]： 1．产生所有支持度大于或等于指定最小支持度的项集，这些项目集称为频繁项目集（frequent itemsets ），而其他的项目集则成为非频繁项目集（non-frequent itemsets ） 2．由频繁项集产生强关联规则。根据定义，这些规则必须满足最小支持度和最小可信度。关联规则挖掘的问题的主要特征是数据量巨大，因此算法的效率很关键。目前研究的重点在第一步，即发现频繁项目集，因此第二步相对来说是很容易的。

关联规则挖掘的过程

关联规则挖掘的过程关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(Frequentitemsets)，第二阶段再由这些高频项目组中产生关联规则(Association Rules)。关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。一项目组出现的频率称为支持度(Support)，以一个包含A与B两个项目的2-itemset为例，我们可以经由公式(1)求得包含{A,B}项目组的支持度，若支持度大于等于所设定的最小支持度(Minimum Support)门槛值时，则{A,B}称为高频项目组。一个满足最小支持度的k-itemset，则称为高频k-项目组(Frequent k-itemset)，一般表示为Large k或Frequent k。算法并从Large k的项目组中再产生Large k+1，直到无法再找到更长的高频项目组为止。关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(Minimum Confidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。例如：经由高频k-项目组{A,B}所产生的规则AB，其信赖度可经由公式(2)求得，若信赖度大于等于最小信赖度，则称AB为关联规则。就沃尔马案例而言，使用关联规则挖掘技术，对交易资料库中的纪录进行资料挖掘，首先必须要设定最小支持度与最小信赖度两个门槛值，在此假设最小支持度min_support=5% 且最小信赖度min_confidence=70%。因此符合此该超市需求的关联规则将必须同时满足以上两个条件。若经过挖掘过程所找到的关联规则「尿布，啤酒」，满足下列条件，将可接受「尿布，啤酒」的关联规则。用公式可以描述Support(尿布，啤酒)>=5%且Confidence(尿布，啤酒)>=70%。其中，Support(尿布，啤酒)>=5%于此应用范例中的意义为:在所有的交易纪录资料中，至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行为。Confidence(尿布，啤酒)>=70%于此应用范例中的意义为:在所有包含尿布的交易纪录资料中，至少有70%的交易会同时购买啤酒。因此，今后若有某消费者出现购买尿布的行为，超市将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据「尿布，啤酒」关联规则，因为就该超市过去的交易纪录而言，支持了“大部份购买尿布的交易，会同时购买啤酒”的消费行为。关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进行适当的数据离散化（实际上就是将某个区间的值对应于某个值），数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果。

关联规则挖掘英文PPT

INFO411/911 Laboratory exercises on Association Rule Mining Overview: Association rule mining can help uncover relationships between seemingly unrelated data in a transactional database. In data mining, association rules are useful in discovering consequences of commonly observed patterns within a set of transactions. What you need: 1.R software package (already installed on the lab computers) 2.The file "laboratory_week5.zip" on Moodle. Preparation: 1.Work in a group of size two to three (minimum size of a group is two. But no more than three students are to work together). Penalties apply if a group exeeds these limits. 2.Boot computer into Windows mode. 3.Download laboratory_week5.zip then save to an arbitrary folder, say "C:\Users\yourname\Desktop" 4.Uncompress laboratory_week 5.zip into this folder 5.Start "R" 6.Change the working directory by entering: setwd("C:/Users/yourname/Desktop") (Note that R expects forward slashes rather than backwars slashes as used by Windows.) Your task: Your are to submit a PDF document which contains your answers of the questions in this laboratory exercise. One document is to be submitted by each group. The header of the document must list the name and student number of all students in the group. Clearly indicate which question you have answered. The following link provides a documentation of the association rule module in R (called arules). The link can help you develop a better understanding of the usage and parameters of the association rule package in R: https://www.wendangku.net/doc/7e7800088.html,/web/packages/arules/arules.pdf Work through the following step and answer given questions: Step1: Familiarize yourself with the arules package in R. Start R and type: library(arules) to load the package. We shall start from the analysis of a small file sample1.csv that contains some transactional data. To load data into R enter: sample1.transactions <- read.transactions("sample1.csv", sep=",") To get information about the total number of transactions in a file sample1.csv enter: sample1.transactions To get a summary of data set sample1.csv enter: summary(sample1.transactions) The data set is described as sparse matrix that consists of 10 rows and five columns. The density of

关联规则挖掘综述

关联规则挖掘综述摘要：近年来国内外学者对关联规则进行了大量的研究。为了更好地了解关联规则的挖掘技术，对研究现状有更深入的了解，首先本文对数据挖掘技术进行了介绍，接着介绍了关联数据挖掘的基本原理，最后对经典的挖掘算法进行分类介绍。关键词：数据挖掘；关联规则；算法；综述 1.引言数据挖掘是从海量的数据里寻找有价值的信息和数据。数据挖掘中常用的算法[1]有：关联规则分析法（解决事件之间的关联问题）、决策树分类法（对数据和信息进行归纳和分类）、遗传算法（基于生物进化论及分子遗传学理论提出的）、神经网络算法（模拟人的神经元功能）等。数据挖掘最早使用的方法是关联分析，主要应用于零售业。其中最有名的是售货篮分析，帮助售货商制定销售策略。随着信息时代的到来，数据挖掘在金融[2]、医疗[3]、通信[4]等方面得到了广泛的应用。 2.关联规则基本原理设项的集合I = { I1 ，I2 ，...，Im }，数据库事务的集合为D，我们用|D|表示事务数据库所有事务的个数，其中用T

表示每个事务，使得T I。我们用TID作为每个事务的唯一标识符。用X表示一个项集，满足X T，那么交易T包含X。根据上述相关描述，给出关联规则的相关定义。 2.1项集支持度用X表示数据库事务D中的项集，项集X的支持度表示项集X在D中事务数所占的比例，用概率P（X）表示，那么Support（X）=P（X）=COUNT（X）/|D| （1） 2.2关联规则置信度 X Y关联规则的置信度是数据库事务D中包含X Y的事务数与包含X的事务数之比，表示方法如下： confidence（X Y）= support（X Y）/support（X）= P（Y|X）（2） 3.关联规则算法 3.1经典的Apriori挖掘算法大多数关联规则的算法是将关联规则挖掘任务分为两个子任务完成。一是频繁项集的产生，频繁项集的目的是找到大于等于给定的最小支持度阈值的所有项集，这些项集我们称之为频繁项集。二是规则的产生，即从频繁项集中找到置信度比较高的规则，我们称之为强规则。Apriori挖掘算法是众多挖掘关联规则中比较经典的算法，它采用布尔关联规则，是一种宽度优先算法。 3.2Apriori算法优化

浅谈关联规则挖掘技术的研究与应用

浅谈关联规则挖掘技术的研究与应用【摘要】数据挖掘技术是日前广泛研究的数据库技术，关联规则是表示数据库中一组对象之间某种关联关系的规则。本文简要介绍了关联规则挖掘的相关理论和概念、Apriori算法，最后介绍了关联规则数据挖掘的应用情况。【关键词】关联规则数据挖掘Apriori算法应用随着数据库技术的快速发展,全球范围内的数据存储量急骤上升,面对这一挑战,数据挖掘技术应运而生, 关联规则挖掘在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则的目标是发现数据集中所有的频繁模式，关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。一、关联规则的定义关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品(项)之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。二、关联规则挖掘的过程关联规则挖掘过程主要包含两个阶段：关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。根据定义，这些规则必须满足最小支持度和最小可信度。三、关联规则分类 1.基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理。 2.基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 3.基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维；而在多维的关联规则中，要处理的数据将会涉及多个维。

关联规则挖掘基本概念和算法--张令杰10121084

研究生课程论文关联规则挖掘基本概念和算法课程名称：数据仓库与数据挖掘学院：交通运输专业：交通运输规划与管理年级：硕1003班姓名：张令杰学号：10121084 指导教师：徐维祥

摘要 (Ⅰ) 一、引言 (1) 二、关联规则的基本描述 (1) 三、经典频繁项集挖掘的Apriori算法 (3) 四、提高Apriori算法的效率 (6) 五、由频繁项集产生关联规则 (8) 六、总结 (9) 参考文献 (9)

目前，数据挖掘已经成为一个研究热点。关联规则数据挖掘是数据挖掘的一个主要研究内容，关联规则是数据中存在的一类重要的可被发现的知识。其核心问题是如何提高挖掘算法的效率。本文介绍了经典的关联规则挖掘算法Apriori并分析了其优缺点。针对该算法的局限性，结合Apriori性质，本文对Apriori中连接的步骤进行了改进。通过该方法，可以有效地减少连接步产生的大量无用项集并减少判断项集子集是否是频繁项集的次数。关键词：Apriori算法；关联规则；频繁项集；候选集

一、引言关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析[1] 。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。最著名的关联规则发现方法是R. Agrawal 提出的Apriori 算法。关联规则挖掘问题可以分为两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集市关联规则发现算法的核心。二、关联规则的基本描述定义1. 项与项集数据库中不可分割的最小单位信息，称为项目，用符号i 表示。项的集合称为项集。设集合{}k i i i I ,,,21 =是项集，I 中项目的个数为k ，则集合I 称为k -项集。例如，集合{啤酒，尿布，牛奶}是一个3-项集。定义2. 事务设{}k i i i I ,,,21 =是由数据库中所有项目构成的集合，一次处理所含项目的集合用T 表示，{}n t t t T ,,,21 =。每一个i t 包含的的项集都是I 子集。例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以表示这些商品是同一顾客同一次购买的。我们称该用户的本次购物活动对应一个数据库事务。定义3. 项集的频数（支持度计数）包括项集的事务数称为项集的频数（支持度计数）。定义4. 关联规则关联规则是形如Y X ?的蕴含式，其中X ，Y 分别是I 的真子集，并且φ=?Y X 。 X 称为规则的前提，Y 称为规则的结果。关联规则反映X 中的项目出现时，Y 中的项目也跟着出现的规律

关联规则挖掘

数据挖掘的其他基本功能介绍一、关联规则挖掘关联规则挖掘是挖掘数据库中和指标（项）之间有趣的关联规则或相关关系。关联规则挖掘具有很多应用领域，如一些研究者发现，超市交易记录中的关联规则挖掘对超市的经营决策是十分重要的。 1、基本概念设},,,{21m i i i I =是项组合的记录，D 为项组合的一个集合。如超市的每一张购物小票为一个项的组合（一个维数很大的记录），而超市一段时间内的购物记录就形成集合D 。我们现在关心这样一个问题，组合中项的出现之间是否存在一定的规则，如A 游泳衣，B 太阳镜，B A ?，但是A B ?得不到足够支持。在规则挖掘中涉及到两个重要的指标： ①、支持度支持度n B A n B A )()(?=?，显然，只有支持度较大的规则才是较有价值的规则。 ②、置信度置信度) ()()(A n B A n B A ?=?，显然只有置信度比较高的规则才是比较可靠的规则。

因此，只有支持度与置信度均较大的规则才是比较有价值的规则。 ③、一般地，关联规则可以提供给我们许多有价值的信息，在关联规则挖掘时，往往需要事先指定最小支持度与最小置信度。关联规则挖掘实际上真正体现了数据中的知识发现。如果一个规则满足最小支持度，则称这个规则是一个频繁规则；如果一个规则同时满足最小支持度与最小置信度，则通常称这个规则是一个强规则。关联规则挖掘的通常方法是：首先挖掘出所有的频繁规则，再从得到的频繁规则中挖掘强规则。在少量数据中进行规则挖掘我们可以采用采用简单的编程方法，而在大量数据中挖掘关联规则需要使用专门的数据挖掘软件。关联规则挖掘可以使我们得到一些原来我们所不知道的知识。应用的例子： * 日本超市对交易数据库进行关联规则挖掘，发现规则：尿片→啤酒，重新安排啤酒柜台位置，销量上升75%。 * 英国超市的例子：大额消费者与某种乳酪。那么，证券市场上、期货市场上、或者上市公司中存在存在哪些关联规则，这些关联规则究竟说明了什么？

并行关联规则挖掘综述

关联规则是等人首先提出的的一个重要R.Agrawal KDD 研究内容，近年来受到了数据库界的广泛关注。关联规则是寻找在同一个事件中出现的不同项的相关性，即找出事件中频繁发生的项或属性的所有子集，以及它们之间应用相互关联性。关联规则最早用于发现顾客交易数据库中不同商品间的联系，后来诸多的研究人员对关联规则的挖掘问题进行了大量的拓展和研究。他们的工作包括对原有算法的优化，如引入并行的思想，以提高算法的效率，对关联规则的应用进行扩展。关联规则挖掘具有计算量大，负载集中的特点。而I/O 且许多关联规则的实际应用涉及到海量数据。在这种情况下，即使对算法进行了优化，在单处理机上使用串行算法进行挖掘所需要的时间可能也是无法接受的。其主要原因在于单处理器本身受到内存和带宽的限制。因此，必须依靠I/O 高性能并行计算来有效地完成挖掘任务。关联规则的基本概念 1 关联规则的形式化描述如下： {}12,,...,m i i i 令为项目集，为事物数据库，其中每I = D I T ?个事物是一个项目子集，并另有一个唯一的事物标 T ( )T X ?识符。如果，则事物包含项目集。 TID T X Y X ?I Y I X ??,一个关联规则是形如的蕴涵式这里并 , ,Y X ∩Y X ?且ф。规则在交易数据库中的支持度 = D (是交易数据库中和的交易数与所有交易数之比， support)X Y Y X ?记为，即support( )Y X ?{ }D D T T Y X T /,:∈?∪support( )= Y X ?规则在交易数据库中的可信度指包 D (confidence)含和的交易数与包含的交易数之比，记为 X Y X Y X ?，即 confidence( )confidence(Y X ?{}{}D T T X T D T T Y X T ∈?∈?∪,:/,: )= 给定一个交易集，关联规则的挖掘问题就是产生支持 D 度和可信度分别大于用户给定的最小支持度和最 (minsupp)小可信度的关联规则。 (minconf)关联规则的发掘分为两个步骤：找出所有支持度大(1)于最小支持度的频集；从频集中产生期望的规则。(2)串行关联规则挖掘算法2 目前所有并行关联规则算法都是在相应的串行算法的基础上提出的。本文首先对这些串行算法进行介绍和分析。算法2.1 Apriori-like 在各种关联规则挖掘算法中，最经典、最广泛使用的就是等Agrawal [2]设计的算法，其核心思想是基于频集理Apriori 论的递推方法。首先产生频繁项集，然后是频繁项集，1-2-直到有某个值使频繁项集为空，算法停止。这里在第次r r-k 循环中，过程先通过对两个只有一个项不同的属于的频 k-1集做连接产生候选项集的集合。然后验证候选项集 (k-2)-k-k-中的每个元素来决定是否将其加入频集，这里的验证过程k-是算法性能的一个瓶颈。这个方法要求多次扫描数据库，这就需要很大的负载。I/O 等提出了一个高效地产生频繁集的基于杂凑Park (hash)的算法：算法。通过实验Dynamic Hashing and Pruning(DHP)可以发现寻找频集的主要计算是在生成频繁项集上。2-DHP 利用一个杂凑表在计算频繁项集时先大概计算出项集的1-2-支持度，从而减少了候选项集的数量。还采用了数据2-DHP 库修剪技术，通过修剪掉那些不包含频集的事物集以减小下一次循环中数据库的大小。然而，这种修剪技术的优化并不显著。其主要原因在于只能通过过滤对数据库执行逻辑上的并行关联规则挖掘综述尚学群，沈均毅西安交通大学电信工程学院软件研究所，西安( 710049 ) 摘要：关联规则发现作为数据挖掘的重要研究内容，在许多实际领域内得到了广泛的应用。因为在挖掘过程中涉及到大量的数据和计算，高性能计算成为大规模数据挖掘应用的一个重要组成部分。该文介绍了当前并行关联规则挖掘方面的研究进展，对一些典型算法进行了分析和评价，从并行度、负载平衡以及和数据库的集成等方面展望了并行关联规则挖掘的研究方向。关键词：数据挖掘；关联规则；并行算法 Survey of Parallel Association Rule Mining ，SHANG Xuequn SHEN Junyi (Software Institute,School of Telecom Engineering, Xi'an Jiaotong University, Xi'an 710049) 【】Abstract Due to the huge size of data and amount of computation involved in data mining, high-performance computing is an essential component for any successful large-scale data mining application. This paper provides a survey of the study in parallel association rule generation, reviews and analyses some typical algorithms, views the trend of parallel association rule mining based on the kind of parallelism exploited, the load balancing strategy used, and the integration with databases. The goal of this paper is to serve as a reference for both researchers and practitioners interested in the state-of-the-art in parallel association rule mining.【】Key words ；；Data mining Association rules Parallel algorithms 第30卷　第14期Vol.30 № 14计　算　机　工　程Computer Engineering 2004年7月 July 2004 ?发展趋势/热点技术 ? 中图分类号： TP182 文章编号：1000—3428(2004)14 —0001—03 文献标识码：A

关联规则挖掘Apriori算法综述

文献综述课程名称：科技写作与文献检索完成题目：关联规则挖掘Apriori算法综述专业班级：姓名：学号：完成时间：批阅时间：指导教师：成绩：

关联规则挖掘Apriori算法综述摘要：关联规则挖掘是数据挖掘研究领域中的一个重要任务,随着大量数据不停的收集和存储,从数据库中挖掘关联规则变得极为重要。关联规则挖掘Apriori 算法是关联规则挖掘中的一种经典算法。为此，本文对国内外有关 Apriori 算法的研究现状、算法的原理、优化算法的思想进行了探讨，综述了Apriori算法的主要优化方法,并指出了Apriori算法在实际中的应用领域,提出了未Apriori 算法的研究方向和应用发展趋势。关键词：关联规则；数据挖掘；Apriori算法；综述 Abstract：The associative rule mining technique is an important technique in data mining research. Apriori algorithm is a classical algorithm of associative rules. How to dig out the rules of the associated data set from the database in the IT development process is important with increasing of massive data collection and storage. In this paper the principles and optimization idea of Apriori algorithm are discussed and several classical optimization algorithms are analyzed at the same time. Finally the trends of future development are forecasted. Key words：associative rules；massive data；optimization；developmental trends 1.引言数据挖掘也称数据库中的知识发现,是指从大型数据库或数据仓库中提取人们感兴趣的知识,这些知识是隐含的、事先未知的潜在有用信息,提取的知识一般可表示为概念、规则、规律、模式等形式[1]。大家知道,如今已可以用数据库管理系统来存储数据,还可用机器学习的方法来分析数据和挖掘大量数据背后的知识，而这两者的结合就促成了数据挖掘技术的产生。数据挖掘是一门交叉性的学科,涉及到机器学习、模式识别、归纳推理、统计学、数据库、数据可视化、高性能计算等多个领域。关联规则挖掘是数据挖掘中最活跃的研究方向之一，其本质是要找出隐藏在

数据挖掘算法之关联规则

数据挖掘算法之-关联规则挖掘(Association Rule) (2009-09-20 21:59:23) 转载标签：分类：DM dm 在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami 提出，是数据中一种简单但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。一、关联规则的定义和属性考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相互之间是否有规律可循呢？在数据库的知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响。现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间，顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有70 ％的人同时购买了铁钉。这些关联规则很有价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在40 岁以上，工作在A 区的投保人当中，有45 ％的人曾经向保险公司索赔过。在这条规则中，

关联规则挖掘综述

关联规则挖掘综述本文介绍了关联规则挖掘的研究情况，提出了关联规则的分类方法，对一些典型算法进行了分析和评价，指出传统关联规则衡量标准的不足，归纳出关联规则的价值衡量方法，展望了关联规则挖蔡伟杰张晓辉朱建秋朱扬勇2 （复旦大学计算机科学系上海 200433）摘要：本文介绍了关联规则挖掘的研究情况，提出了关联规则的分类方法，对一些典型算法进行了分析和评[1]价，指出传统关联规则衡量标准的不足，归纳出关联规则的价值衡量方法，展望了关联规则挖掘的未来研究方向。关键词：数据挖掘，关联规则，频集，OLAP 1 引言数据挖掘（Data Mining），又称数据库中的知识发现（Knowledge Discovery in Database），在最近几年里已被数据库界所广泛研究，其中关联规则（Association Rules）的挖掘是一个重要的问题。关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。 Agrawal等于1993年[1]首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。最近也有独立于Agrawal的频集方法的工作[18,19]，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。同时随着OLAP技术的成熟和应用，将OLAP 和关联规则结合[20,21]也成了一个重要的方向。也有一些工作[6]注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。本文第二部分是对关联规则基本概念的介绍，提出了关联规则的分类方法；第三部分是对挖掘算法的介绍，从经典的apriori开始，然后描述了对该算法的优化拓展，接着讲述脱离apriori算法的方法，最后是多层、多维的关联规则挖掘；第四部分归纳出关联规则价值衡量方法，主要从两个方面进行考虑：系统客观层面和用户主观层面；最后展望了关联规则挖掘的未来研究方向。

关联规则挖掘算法综述

关联规则挖掘算法综述
本文介绍了关联规则的基本概念和分类方法，列举了一些关联规则挖掘算法并简要分析了典型算法，展望了关联规则挖掘的未来研究方向。
1 引言
关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。 Agrawal 等于 1993 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题 [AIS93b]，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。最近也有独立于 Agrawal 的频集方法的工作[HPY00]，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。也有一些工作[KPR98]注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。
2 基本概念
设 I={i1,i2,..,im}是项集，其中 ik(k=1,2,…,m)可以是购物篮中的物品，也可以是保险公司的顾客。设任务相关的数据 D 是事务集，其中每个事务 T 是项集，使得 TÍI。设 A 是一个项集，且 AÍT。关联规则是如下形式的逻辑蕴涵：A Þ B，AÌI, AÌI，且 A∩B=F。关联规则具有如下两个重要的属性：支持度: P(A∪B)，即 A 和 B 这两个项集在事务集 D 中同时出现的概率。置信度: P(B｜A)，即在出现项集 A 的事务集 D 中，项集 B 也同时出现的概率。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一个事务集 D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。
3 关联规则种类