о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



ָĹھ
̼̻ʩ
ժҪϵЧ֪ʶоҪ.ͳĹھ㷨ȱھԣھٶھ⣬ھ޴ҪдɸѡԱȡù.˽ھУھЧʺھԵķ˸ָĹھ㷨CGARMʹݿиĽʽɷ.㷨CGARMǶԻڷھ㷨չ.ʵ㷨CGARMھȤԣھʱȴͳĶιھ㷨Cumulateһ.
ؼʡ֪ʶ֣ھ򣬹򣬸
ͼšTP18 TP311.13
CONCEPT-GUIDED ASSOCIATION RULES MINING
CHENG JiHua and SHI PengFei
(Institute of Image Processing & Pattern Recognition, Shanghai Jiaotong University, Shanghai 200030)
AbstractAssociation rules is an effective method for describing the dependency relations in data, and it is one of the important aspects of knowledge discovery. Traditional association rule mining methods lack of focus on the results, and the procedure is slow. Those algorithms express the regularities with low level primitive data, and the mining association results are difficult to understand. Furthermore, the desirable knowledge must be filtered out from huge results in a postprocessing step. A method for integrating concepts into the mining procedures to improve the interestingness of results and speeding up mining procedures is proposed, and the method for deriving concepts interactively in large database is proposed, a conceptguided association rules mining algorithm CGARM is given in the paper here. CGARM extends taxonomiesbased mining methods. Experiments show the execution speed of CGARM is about twice as faster as the traditional mining algorithm Cumulate, and the interestingness of results are also improved.
Key wordsknowledge discovery, data mining, association rules, concept
1
ݼϵ֪ʶоҪݣ12.ϢϵͳSΪԪ飺(UAVf)UǶ󼯺ϣA={a1,a2,ap}ԼϣV=V1V2VpԵֵ򼯺ϣf:UAVֵ3.ͨǿɷģݵķ(hierarchies)ʾԵϵĸ(generalization)Զµ⻯(specification)24.
ڷεĹھ㷨Ҫ㷨CumulateStratify4ݣ㷨MLT2L12ݣԼSrikant5ò޶Ŀĳ(ָʽ)ھԵ㷨.ڷķڵεӦ.
ӦУҪڶϵ߼ʽʾĸݵĸ6.߼֪ʶӣ䡢ְϵ߼ʽ(>60 ANDְ=߼ְ)ɵĸ.øݼĹϵ˵˼άʽ.
оøھĽ޶ھԵķ.˸ָĹھ㷨CGARM(concept guided association rules mining).㷨CGARMǻڷ෽չھЧʺͽȤ(interestingness).Ļ˴ݿиĽʽɷ.
2ھ
¼ʾΪ{id,(a1v1),(a2v2),,(apvp)}idΪ¼ʶţȫΨһaiAԣviaiֵ(i=1,2,p).ȫ¼ļϼΪD.
1. ʽݹ鶨Ϊ
 aiA,wiVi,ȡ{=,,,,,}ǶԪaiwiΪʽ.
 c1c2ʽc1ANDc2c1ORc2,NOTc1Ϊʽ.
2. ݹ鶨Ϊ
 aiAԣciΪʽ(ai,ci)Ϊ.
 T1T2ΪT1T2ΪСıʾ߼롱.
3. ģʽPΪT1T2TkTi(i=1,2,,k)Ǹ.ģʽPTiΪTiP.ģʽPĳΪi,Ϊ|P|=i.
4. ģʽP=T1T2TkģʽQ=Tl1Tl2TlmTlnQTlnPģʽQΪģʽPģʽΪQP.ģʽPУģʽQеĸɵģʽΪPQ.
5. ģʽPQPģʽSSQģʽģʽ(PS)QΪģʽPɸ.ģʽPɸģʽļϳΪPĿɸϣΪ.
6. ģʽP=T1T2Tk¼t={id,(a1v1),(a2v2),,(apvp)},(ai,ci)Pʽciaivi滻ʽciΪ桱t֧P.
ģʽPݿDе֧ʣABĿŶΪھЧ򣬶С֧ʦminϿŶȦmin.(P/D)>min,ģʽPƵģ2ݣΪiƵģʽϼΪLiL=kLk.
ھҳ㣺(AB/D)>min,(AB/D)>minĹAB.
ڲͬӦûھ񣬶ھ֪ʶвͬ.ھеĸΪмֵ.
7. T1T2TiTi+1TkΪȤ(interestingess)7ݣģʽT1T2TkΪõģõģʽܹȤĹ.ΪLģʽĿ.
AgrawalƵģʽķ1.۸ָƵģʽ.
3ָĹھ
3.1 
ھоǾ޴.޴ĴںݵĲԭ򣬴ͳĸӦھҪ.һֽʽĸ.
DȡӼϦDTڦDھС֧TƵģʽL=kLkLгȡмֵģʽ.ĲΪȽL1мֵģʽΪγɸS1LеģʽиLеģʽPģʽS1еĸPеģʽS1еĸ滻滻ģʽLУٽL2мֵģʽΪγɸS2γɸConceptSet=kSk.
㷨1.Concep_Dterive(㷨)
Input:ݿDT
OutputConceptSet
ݿDȡӼϦD
ڦDھС֧TƵģʽL=kLk
j=1
Whilej<=kDo
LjмֵģʽΪSj
n=j
Whilen<=kDO
For everyPLDo
IfPģʽSjеĸQThen
PеģʽøQ滻L
n=n+1

j=j+1

ConceptSet=kSk
3.2 ھ㷨CGARM
ȣǸģʽPĿɸģʽϵ㷨
㷨2. ALLG(ģʽPĿɸϵ㷨)
Input:ģʽPConceptSet
OutputPĿɸģʽ
={}
For everyQConceptSetDo
IfPģʽSQģʽThen
=+{(P-S)Q}
ΪģʽPĿɸϵٶȣԺʽ(aj,cj)еajֵ򣬶ԸConceptSetеĸ.
㷨3. CGARM(ָĹھ㷨)
Input:ConceptSetݿDС֧ʦminСŶȦmin.
Output򼯺AR
C1Aj,Cj|QConceptSet,(Aj,Cj)Q
k=1
WhileCk<>NILDo
={}
For every PCkDo
=+ALLG(PConceptSet)
Gk={X|XCk,|X|=k}
DCkGkģʽ֧
Lk={X|XCkGk,(X/D)>min}
Ck={XY|Lk-1,YLk-1,|XY=k|
ҪQ(XY)|Q|=k-1,QLk-1}
k=k+1

L=kLk
L_C={PL|QR,QConceptSet}
򼯺
㷨3ȼConceptSetийصġΪ1ĺѡƵģʽC1C1ĿɸG1ȻݿDΪ1ƵģʽL1L1쳤Ϊ2ĺѡƵģʽC2C2ĿɸG2D󳤶2ƵģʽL2ƵģʽL=kLkȥLвConceptSetиģʽõصƵģʽLC򼯺AR.
4㷨CGARMܷ
㷨CGARMԸConceptSet޶ģʽϽھ򣬼ģʽЧʣʡ˴洢ռ.ھøʽʾ.
Pentium 133/8MWindows 3.11Ļ£㷨CGARMԼȼݿ˷㷨Cumulate˱Ƚ.ʵ£
ݿУ¼32ԣĿĳɼABCD֣仮Ϊ14£1418꣬1935꣬3645꣬45.Կĳɼ䡢ڳкְҵз࣬=4.
ӿɼݿгȡ4K¼T=3%㷨Concept_DeriveнʽĸɣøConceptSet. ConceptSetа22˹3ConceptSetУ25漰ڵʡݣְҵѧԱ.磬(kq,kq="Ϻ")AND(dj,dj=3)ʾϺ3(dj,dj=2)AND (dj,dj=3)ʾϺ3(dj,dj=2) AND (xl,xl="ר")AND(nl,nl=3645)ʾרѧ35452.
ͼ1ڷΪ4Ϊ25min=15%£㷨CGARM㷨CumulateھĽĿ¼Ĺϵ.㷨CGARMھĿʴ㷨Cumulate.

ͼ1㷨CGARM㷨CumulateھĿʺͼ¼Ĺϵ
ͼ2˼¼=60K=25£㷨CGARMִʱС֧ʵĹϵͼ3ڷ=4=25,min=5%£㷨CGARM㷨Cumulateִʱ¼Ĺϵ.㷨CGARMھʴԼ㷨Cumulateһ.⣬㷨CGARMִʱСڼ¼.

ͼ2㷨CGARMִʱС֧ʵĹϵ

ͼ3㷨CGARM㷨Cumulateִʱ¼ĿĹϵ
5
˸ָĹھ㷨CGARMʾ֪ʶĸھУھԺھȤ.ʵָھ򷽷ڷķȣھٶȣھĿʣ㷨CGARMھٶȱȴͳĶιھ㷨Cumulateһ.
עõȻѧ(Ŀ69575012).
߼飺̼̻У1964ʿҪоΪھ֪ʶ֡ݿݿӻ.
ʩɣУ1939ڣʿʦҪоΪͼģʽʶ𡢼Ӿܼϵͳ.
ߵλϺͨѧͼģʽʶоϺ200030
ο
1Agrawal R, Srikant R. Fast algorithms for mining association rules. IBM Almaden Research Center, Tech Rep: RJ9839, 1994
2Han J, Fu Y. Discovery of multiplelevel association rules from large databases. In: Proc of 1995 Very Large Databases, Zurich, 1995. 420431
3Pawlak Z, Orlowska E. Expressive power of knowledge representation. Journal of ManMachine Studies, 1989, 30: 273285
4Srikant R, Agrawal R. Mining generalized association rules. In: Proc of 1995 Very Large Databases, Zurich, 1995. 314
5Srikant R, Vu Q, Agrawal R. Mining association rules with item constraints. In: Proc of the 3th Knowledge Discovery and Data Mining, California, 1997. 6773
6Dhar V, Tuzhilin A. Abstractdriven pattern discovery in databases. IEEE Trans on Knowledge and Data Engineering, 1993, 5(6): 926938
7Fayyad U, Piateskyshapiro G, Smyth P. From data mining to knowledge discovery: An overviews. In: Fayyad M, PiatetskyShapiro G, Smyth P eds. Advances in Knowledge Discovery and Data Mining. MA: The MIT Press, 1996. 134
ԭյڣ1997-11-25޸ĸյڣ1998-04-28.
