ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



ڹԵݿɵ޻㷨
šࡡɡ
ժҪ˻ڹ֪ʶַ޻㷨.ѱ֪ʶΪ߼,ӾչΪȫӾ䣬ȻûҪ,岢ȷÿԵǡ.ÿԵĶֵΪǡеֵ,ֻһɨ,.
ؼʡ֪ʶ,,޻㷨.
ͼšTP181,TP311
A Nonbacktracking Algorithm for the Rule Based 
Attribute-oriented Database Induction Approach
ZHOU Sheng-bing1ZHANG Bo2CHENG Dong3
1Air Force Telecommunication Engineering Institute Xi'an 710077
2Department of Computer Science and Technology Tsinghua University Beijing 100084
3Business SchoolRenmin University of ChinaBeijing100872
AbstractIn this paper, a nonbacktracking algorithm is presented for the rule based attribute-oriented database induction approach. The background knowledge is considered as a limited logic program, and every clause of it is expanded as a complete resolution clause. Then, the concept of exact level for an attribute in the concept hierarchies is defined and specified according to its threshold required by the users. The values of each attribute are inducted as ones in its exact level by only one pass without backtracking.
Key wordsKnowledge discovery in databases, concept hierarchies, nonbacktracking algorithm.
Դӵһй֪ʶ֣knowlegde discovery in databases,KDDļ1ݳ,йKDDݲɾdata miningоõ㷺Ĺע24.J.Hanԣattribute-oriented)ĸ(AO.,ΧAOһϵĹ511.ף5,ǽAOƹΪڹrule-based)AO(RBAO,ҪصǸݹݿɨ.,֪ʶɿ߼,ڰÿչΪȫ,ԸûҪ,ȷÿԸǡ,Ӷһɨ輴ɸ,˻.ȽRBAO,Ȼ޻㷨.
1ڹAO
AOĹؼøαʾרṩı֪ʶ.õĸǸ6,7,12,и.,ĳЩ,ûϣĸ,⣬ڱĸ.,ڳ񾭼״,600ԪũǸ,Գое,ĳЩеľǵ.ڴ,W.D.Cheung˰AOƹΪڹAO,ǿAOı͹5,13.
ڻڹAO,֪ʶһ鷺ʾ.
C(x)A(x)&B(x).
˼,Ԫx,ĳaĸֵAƹ㵽C߼ֵ,xB.BB1&...&Bn,Biǲͬaĳbiĸ,ʾȽϹϵ.ڹAORBAOΪ.һ˵.
1. ӳʼϵϵ
ܵذֵͷ,ϲͬԪ,õĹϵϵprime-relation.

ͼ1
һѧѧݿģʽStudent(Name,Status,Sex,Age,Birthplace,GPA),ѧϰǷּרҵѧ.GPAĸͼͼ1ʾ,Ӧķ,ɵϵ1.
R1:poor{0.0-1.99};
R2:poor{2.0-2.49}&{graduate};
R3:average{2.0-2.49}&{undergraduate};
R4:average{2.5-2.99};
R5:good{3.0-3.49};
R6:good{3.49-3.8}&{graduate};
R7:excellent{3.49-3.8}&{undergraduate};
R8:excellent{3.9-4.0};
R9:weak{poor};
R10:weak{average}&{senior,graduate};
R11:strong{average}&{freshman,sophomore,junior};
R12:strong{good};
R13:strong{excellent}.
1

StatusSexAgeBirthplaceGPAVote
UndergraduateM1625CanadaAverage40
UndergraduateM1625CanadaGood20
UndergraduateF1625CanadaExcellent10

GraduateM2530CanadaPoor6
GraduateM2530CanadaGood4
GraduateF2530CanadaExcellent4


2. ϵĳЩӦһ,ֱϵĹģСڷϵֵ.ڵ1,ʧһЩϢ.,1е1ԪǰR10weak,ǰR11strong޷ȷ,ΪϢfreshman,sophomore,junior,seniorڵ1жʧ.ʵ,ϲԪ40ѧпи꼶ѧ.,2Ӧû㷨ָʧϢ.
ϵ,һԪǳʼϵһԪ鼯ϺϲĽ,Ԫ鼯ΪԪԴ,ԪΪԪ.㷨ԭ£
(1) ϵеԪݵǵԴ.ڳʼϵмһcovering-tuple-idԪʶ¼ӦĸԪ.
Ա1еϵӦһ,2.
(2) ѡĳЩ߼,һڱ2ʾĳʼϵн. 
2

NameStatusSexAgeBirthplaceGPACovering-tuple-id
-juniorM20Vancouver2.31

-sophomoreM21Calgary2.31
-freshmanM18Toronto2.41

-juniorM19Ottawa3.12
-Ph.DM30Waterloo3.940


(3) ȽϺϲԪ.Ծͬcovering-tuple-idͱѡֵԪбȽ,ϲͬԪ,õĽΪǿϵ(enhanced-prime relation).ļǿϵ3. 
3

Covering-tuple-idGPAVote
1Strong10
1Weak30
2Strong20

40Strong4


(4) ϲԪӳϵϵеԪ.ǿϵоͬcovering-tuple-idԪӳΪϵжӦĸԪ.ϵеԪ˷ΪɸԪ,Voteͬʱ,ԪĳЩԷΪǿϵеĶӦֵ.һĽ4. 
4

StatusSexAgeBirthplaceGPAVote
UndergraduateM1625CanadaStrong10
UndergraduateM1625CanadaWeak30
UndergraduateF1625CanadaStrong20

GraduateF2530CanadaStrong4


(5) ϲϵеĹԪ. 
2 RBAO޻㷨
ȷֵһ㵽ϵ,ȷ֮ϵ.,GPAStatus.RBAO׶㷨ûпһ,˻Ǳ.,߼ĳЩԷб任,ϵ,˳Խз,ɱ.
дΪʽ
(a(x)=C)(a(x)=A)&B1(x)&...&Bn(x)B1x&...& Bn(x).(1)
a(x)=CΪ1ͷ,(a(x)=A)&B1(x)&...&Bn(x)B1(x)&...&Bn(x)Ϊ1壻Bi(x)bi(x)=Bibi(x)*Bi,*ǱȽ,a,bi.˼ǣԪx,aֵA߼ֵC,biֵΪBibiֵBiϵ*С,ڵȣ.
aB1&...&Bnгֵbiabi,Ϊa<bi,дԣa<b,b<c,a<c.,ֻǲ֮ͬϵ,ǲֵ֮ͬϵ.κa,b1,...,bn,ʹa<b1,b1<b2,...,bn-1<bn,bn<a,Ʒǲѭ.
Թ
(a(x)=C)(a(x)=A)&B1&...&Bn,(2)
ʽĹ
(a(x)=A)(a(x)=D)&E1&...Em(3)

bi(x)=Eibi(x)=Fi&H1&...&Hk,(4)
ô,
(a(x)=C)(a(x)=D)&E1&...&Em&B1&...&Bn (5)

(a(x)=C)(a(x)=A)&B1&...&Bi-1&bi(x)=Fi&H1&...&Hk&Bi+1&...&Bn (6)
Ϊ2һᣨresolution.2ڹ,һȫ.
aĹ򼯺,CĶa(x)=CΪͷйļ.
ڹϵģʽR(a1,...,an)е,aԣΪԣ,ô,Ƿڸ,ĴAOͬ.,a1<a2<...<anΪ.
޻㷨ĹؼԹaiĹȫʼ,a1,...,an˳и.Ϊ˿Ʒ̵ֹ,ҪԵĸͼÿһĽڵ.
L(a)ʾaйļ,
nodea(0)={Aa(x)=AL(a)Ĺг},
nodea(i+1)={C(a(x)=C)(a(x)=A)&B1&...&BnL(a)Anodea(i)},
maxa={Ca(x)=Cڹͷг,г}.
Th(a)ʾaֵ,aǡSa£
.nodea(0)Th(a),Sa=nodea(0);
.nodea(k)ȣnodea(i)maxa>T h(a),ңnodea(k+1)ȣnodea(i)max aTh(a),Sa=nodea(k+1)ȣnodea(i) maxa.
ΪЩڸͼбȽϵ͵Ĳ,,,ǡβͼĳһĽڵȫͬ,ÿֵͲ.
Щ׼֮,޻㷨ͺܼ.
a1<a2<...<an,ÿaiָһֵTh(ai).a1ʼ,SaÿC,a1=CĶÿȫ,Щȫa1ֵΪC.ٶa2,...,anظ,ԾǡĲ.ȻȥȽֵ϶ڸε.
޻㷨Ӧǰ.
ڹϵStudent,GPA<status,ԶǶ.GPAstatusֵΪ2,SGPA={weak,strong},Sstatus={undergraduate,graduate},weak,strongȫΪ:
 (1) (GPA=weak)(GPA{2.5-2.99})&(status=senior);
 (2) (GPA=weak)(GPA{2.0-2.49})&(status=senior);
 (3) (GPA=weak)(GPA{2.5-2.99})&(status=graduate);
 (4) (GPA=weak)(GPA{2.0-2.49})&(status=graduate);
 (5) (GPA=weak)(GPA{0.0-1.99});
 (6) (GPA=strong)(GPA{3.0-3.49};
 (7) (GPA=strong)(GPA{2.0-2.99})&(status=freshman);
 (8) (GPA=strong)(GPA{2.0-2.99})&(status=sophomore);
 (9) (GPA=strong)(GPA{2.0-2.99})&(status=junior);
(10) (GPA=strong)(GPA{3.5-3.79})&(status=graduate);
(11) (GPA=strong)(GPA{3.8-4.0});
(12) (GPA=strong)(GPA{3.5-3.79})&(status=freshman);
(13) (GPA=strong)(GPA{3.5-3.79})&(status=sophomore);
(14) (GPA=strong)(GPA{3.5-3.79})&(status=jounior);
(15) (GPA=strong)(GPA{3.5-3.79})&(status=senior).
GPA,5Age,BirthplaceķAOһ,ٶѾɣ.
5

StatusSexAgeBirthplaceGPA
JuniorM1625Canadastrong
SophomoreF1625Canadastrong

SeniorM1625Canadaweak



ٷStatus,6. 
6

StatusSexAgeBirthplaceGAP
UndergraduateM1625Canadastrong
UndergraduateF1625Canadastrong

GraduateM1625Canadaweak



ڷ,ͬԪʱϲ,¼Vote.
㷨ĸԷֽΪɲֺﲿֵĴ.ɲЧ,ף5.ݿĹģ,򼯺ϵĹģҪСö,ҴǼ򵥵,,ⲿָԿԺԲ.
H.HuangW.C.FuAORBAOһЧʵ֣13.ǵ㷨Ҫͼƽ,ÿӼСڵ㵽ڵ·ĳ.,÷ܴȽ.ǵ޻㷨ͳһȽ,ǵ㷨. 
оõȻѧйʿѧ.,1962,ʿ,ʦ,ҪоΪ˹,߼,֪ʶ.,1935,ڣʿʦйѧԺԺʿ,ҪоΪ˹,,Ӧ.ɶ,1968,ʿ,,ҪоΪݲֿ⼼ӪеӦ.
ͨѶϵˣ,710077,վѶѧԺϵ
ߵλվѶѧԺ710077šࣨ廪ѧѧ뼼ϵ100084ɡйѧ̹ѧԺ100872
ο
1Piatetsky-Shapiro G, Frawley W J. Knowledge Discovery in Databases. Menlo Park, CA: AAAI/MIT Press, 1991
2Chen M, Han J, Yu P S. Data mining: an overview from database perspective. IEEE Transactions on Knowledge and Data Engineering, 1996,8(6):866883
3Silberschatz A, Stonebraker M, Ullman J D. Database research: achievements and opportunities into the 21st century. SIGMOD Record, 1996,25(1):5263
4Ziarko W. Rough Sets, Fuzzy Sets and Knowledge Discovery. Berlin: Springer-Verlag, 1994
5Cheung D W, Fu A W C, Han J. Knowledge discovery in databases: a rule based attribute oriented approach. In: Zbigniew R ed. Methodologies for Intelligent systems: 8th International Symposium. Berlin: Springer-Verlag, 1994. 164173
6Han J, Cai Y, Cercone N. Data driven discovery of quantitative rules in relational databases. IEEE Transactions on Knowledge and Data Engineering, 1993,5(1):2940
7Han J. Towards efficient induction mechanisms in database systems. Theoretical Computer Science, 1994,133(1):161185
8Han J, Fu Y. Dynamic generation and refinement of concept hierarchies for knowledge discovery in databases. In: Fayyad U M, Uthurusamy R eds. Proceedings of the KDD'94: the AAAI'94 Workshop on Knowledge Discovery in Databases. AAAI Technical Report, WS-94-03. Menlo Park, CA: AAAI Press, 1994. 157168
9Han J, Fu Y. Exploration of the power of attribute-oriented induction in data mining. In: Fayyad U M et al eds. Advances in Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI/MIT Press, 1996. 399421
10Han J, Huang Y, Cercone N et al. Intelligent query answering by knowledge discovery techniques. IEEE Transactions on Knowledge and Data Engineering, 1996,8(3):373390
11Hu X, Cercone N. Learning in relational databases: a rough set approach. Computational Intelligence, 1995,11(2):323338
12Godin R, Missaoui R. An incremental concept formation approach for learning from databases. Theoretical Computer Science, 1994,133(2):387419
13Huang Y, Fu W C. Efficient algorithms for attribute-oriented induction. In: Fayyad U M, Uthurusamy R eds. Proceedings of the 1st International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press, 1995. 168173
1998-01-06յԭ塡
1998-09-02յ޸ĸ
