ѧ
JOURNAL OF SOFTWARE 
1999 10 5 Vol.10 No.5 1999



ݿлģʽķֺԤ
ˡܷ
ժҪȻдŴĻģʽ,Ӧ,ʾЩݿͬҲŻģʽ.һKDD,ģʽȷģʽ봿ϵ֮,ֳܴ,˶Ϊϵ.ͨʹJ.ZytkowĻͳƷForty-Niner˵һ.ͨԻģʽķ,һֻģʽֵ緽.÷жݿǷڻģʽ,ЧԤûģʽ.,㷨ǳʺϴݿ,ڵԾKDDо ой㷺Ӧǰ.
ؼʡKDD,ģʽԤ,ģʽ,ģʽ.
ͼšTP311
Discovery and Forecast of Chaotic Pattern in Databases 
DENG Chao1,2 XIONG Fan-lun1
1 (Institute of Intelligent Machines The Chinese Academy of S ciences Hefei 230031)
2(Department of Computer Science University of Science and Technology of Chi na Hefei 230027)
Abstract There exists a lot of chaotic patterns in the natural kingdom and social society. Databases recording this kind of data also c ontain the chaotic patterns. Generally, the chaotic patterns are characteristics of greatly random fluctuation although they often appear between deterministic and stochastic patterns in KDD. Therefore, the chaotic patterns are always treat ed as random fluctuation distributions and are ignored. Such viewpoint illustra ted by J.Zytkow's Forty-Niner is that a pattern discovery platform based on st atistics. A new network method to discover chaotic pattern in databases is propo sed in this paper. This method together with the Forty-Niner can not only disco ver the chaotic pattern, but also forecast it efficiently. In addition, this met hod is very suitable to deal with large databases and has extensive applicable p rospects in the vivid researching fields of KDD.
Key words KDD (knowledge discovery in databases), pa ttern discovery and forecasting, chaotic pattern, chaotic pattern discovery netw orks. 
,ӣͣݿԶ֪ʶKDDѾΪǹעȵ.ڸ ȻоɴݹɵĴݿ,иݾֳ ص,ֳµļ.о,ܶȻļ¼ ݣв𡢹Ʊ۸ȣ1.Щ µݹϵϵ,ʵ,̲ɼ򵥷ϵͳ Ļϵģʽ.
KDDֵ֪ʶʲô,Ĺϵȷģʽ, ϵΪϵ.Ȼ,ЩΪϵĹϵдںܴб ڴϵģ,Ƿδ֪ģʽأѧ۱,ڽȷ ϵʹϵ֮仹ŴĻϵ2,ģʽ.ģʽǿ ؽΪһֵͽ׷ԶѧϵͳʱлԹϵ,һеϵ; ɵزѧϢϵͳ,ǲþۿƵĶѧϵͳ.ģʽ͵ȷģ ʽ,봿ϵͬ.,ģʽǶȷģʽƹ,Ȼ ۴ڵһҪģʽ.
硢۵ĲͷչΪֺеɣϵṩ ۸ݺֶ.ͨûľ۷Լ,ܹԽϸߵľȰֹ ϵԤ.ֻͨģʽ,عҳڻģʽеݻ,ҿ Ըݻҵ,ʹеĳֿĿ,ΪKDDоṩһ ոµķ˼·.
ڴȷģʽϵ֮Ļģʽ,зѰ,˶ Ϊϵ.֪,ͳƷĿǰԺ֮ϵһҪ ֶ,չһϵģʽۺķ,ڷϵʮõЧ 3.Чؿ̻Ժֻ֮ϵ,ǳֻϵ Ϊϵ.Zytkow49erForty-Niner)ͳΪҪ,DBзģ ʽҪ֮һ4,5,Ķ˼Ҫ˵,ڶͻģʽķ. ЩԽȷģʽģʽ֮ĻģʽЧֺ.
һַֺԤģʽ緽chaos pattern discovery networks ,CPDN.㷨49erܷͳƷֵܷĻģʽ,ܶģʽ Ԥ.
1 ģʽķֺԤ
ͨͳط߼ģжϵȷڷǻģʽķźҪ,KDDзģʽ,49er,EXPLORAȾͳƷ ģʽķ.49erΪ,ҪͳƷҪ˼.ڻģʽϵ ֳµ״̬,оҲ,ģʽͳڰģʽ ,ʳڴģʽ1.,ԻģʽķֺԤ,ӦѰ .Թϵǲģʽĸ֮,ģʽֳһ״̬, һĹ,ֳʱʱ״̬ռе,ʹڻ Լϵƺĳּ,ͬʱùϵ߼Ŵͽֹ .Ϣʽ߱.ڴ,һַֻ ģʽ磨CPDN.÷ֻģʽȫģʽ,Ӷֻģʽ, һΧЧԤ.ҪоӰʱݵĹϵݿз Ի֮Ļģʽ.
1.1 ͳƷ
49erҪڴӹϵݿе֪ʶ,REGULARITIESֵ֪ ʶ.õREGULARITIEΪʽ:
ģʽPATTERN in ΧRANGE,
RANGEΪDBп¼ռһӼ.ģʽȿν,ֿƵʱ contingency tableʽ߼Ч.
49erĻΪ:ݼREGULARITIES,Ȼ,ݻΪ ͬӼ,ӼϽһREGULARITIES.ÿһӼ,49erûϿɵ ԶϽ2-D REGULARITIESļ.49erѳԣsignificanceǿȣst rengthͳƼ鷽Ӧм.Ԥ,򽫶Ӧ ΪREGULARITY.ԣsignificanceΪ:ɶĸģʽĸQ. QֵԽӽ0,ģʽԾԽС;෴,QֵԽӽ1,ģʽԽ.Qֵɸݦ2 ͳƺƵʱɶ.2Ƶʱʵֵֵ֮ľ:
  (1)
AijΪƵʱʵʷֲ,EijΪƵʱľֲֵ,ɱʾΪ
(2)
NΪ¼;nxi,nyjֱΪX=xiY=yjļ¼.
49erCramerVϵƵʱԤǿ.һСΪMrow McolƵʱ,CramerVϵɶ:
(3)
Vֵ,Ԥǿ,Ӧ֮Ծǿ.
ͨʹVQ,49erͿɶеÿһģʽԺԤ .һ,QֵĬΪQT=10-5,VVTΪ0.5.QֵVֵͬʱʹò ܾģʽЧ.,QQT,VVT,ģʽ;,ͽΪ ģʽ.
ף4ָ,49erкܺõ2-Dģʽʶ.100ϵӦ49er ģʽЧ,1ΪЧģʽ.99ģʽпܴڲٵĻ ģʽ,49erȴֿܽ.
1.2 緽
緽ڼСٶȿԼѧϰģʽȡǿ,ڽЩ չ,ʺڱʽĹϵ,нǿԤƹܹע. һֻRBFĻģʽ緽RBF-CPDN6,Ӧø÷ ִݿеĻģʽ.ֻģʽȿԴͬһ֮,ֿܴ ֮.
RBF緽ȸĸӶԤȶĽṹĹģ.෽ܽݿзģʽ,Ҳʺڴݿ. ΪKDDҪ:ģʽǷڣԼʲôģʽ
CPDNһǰ,ɱʾΪ
(4)
Цkkڵ֮Ȩֵ,KΪԪ;k(x)Ϊ,kڵxӦ,ͨȡΪGau ssianʽ:
(5)
UkRn,ʾk;kRΪkĿ,ռݵķֱ.*ΪRnռEuclidean.
CPDN㷨Ҫص:
1 CPDNڵѧϰǶ̬.ʼĻΪ0,ѧϰĹ иݹ۲ġϢnovelС̬ڵ,Ȼʵؽ ɵ.
2 CPDNлü,ڷֺжģʽǷ.
3 CPDNķʹнǿԤ.
CPDN㷨ɾ:
Initialize:=Ūmin and 0=y0
for (n=1;nSample Number; n++)
{computes f(xn),k(xn),en
find the nearest stored pattern unr
let n=max{Ūmaxn,Ūmin}
if enemin & xn-u nrn & eneCME
{allocate new hidden unit with
k+1=en,uk+1=x n,k+1=Kxn-unr
}else{ adjusting network parameters:,u,}
pruning the hidden unit acording to the pruning strategy
}
(x0,y0)ʾ1۲,ڳʼ.enΪ ;unrΪռxnڽĴ ģʽ;emineCMEΪ ;nΪڵֵ,ڦmaxͦmin֮.
2 ʵ鼰
2.1 ģʽ
49erܹЧб2-Dģʽ.ʵ,ǲԹϵA1,A2A1,A 3.A1Ϊľȷֲ,A2Ϊһľȷֲ ;A3A1ĹϵΪA3=a+bA21,a,bΪʵ.һ2 000¼., 49er֮ͳƲ2,VQ,ڱ1.
1A1,A2A1,A3ͳƲȽ

attributes relation2VQ
A1,A2 (noise)91.167 70.100 60.724 5
A1,A3 (function)4761.540.727 352.3e-057

ӱ1ɿ,A1,A2 QֵԶQT=10-5,VֵҲԶСVT, Ϊ;A1,A3QֵԶС,VֵҲԶVT.A1,A3֮ ȷģʽϵ.Ͻ49erģʽж׼ȫ,ٴγ˵49er Ч.
2.2 ģʽ
ڻģʽ,49erȴʧȥЧ.Ϊ,ʵвһMackey-Glass ģʽ˹DB.DB5 000Ԫ,5,ֱattri.1,attri.2,...,attri.5ʾ .attri.1attri.2֮ĹϵΪ,49erǵĸͳƲֵ, ģʽж,֤49erԻģʽж;ȻʹñCPDNģʽжϺͷ .ǰ,2¼й,QֵVֵҲ¼仯.,Ϊȷӳ 仯,ҪԲͬģʽQVֵ.
Ϊ˱Ƚ,ǻ3ģʽֱQֵVֵ¼ı仯.
1 ϵA1,A22.1ͬ;
2 ʼ򵥺ϵA1,A32.1ͬ;
3 ʸӺϵA1,A4,A4A1ĹϵΪ:A4=a+bA31*exp(A 21).
ģʽQVֵ¼仯߷ֱͼ1ͼ2ʾ.

ͼ1 Qֵ¼仯ϵ 

ͼ2 Vֵ¼仯ϵ
ͼ1ͼ2,š߱ʾA1,A2ϵQVֵ; +A1,A3 ļ򵥺ϵͳֵ;*߱ʾA1,A4Q Vֵ.𡱵ΪϵQVֵ.ͼԿ,ڴϵ,Qֵʼ ԶԶ10-5,VֵҲʼսӽ0;ȷģʽ,Qֵ±仯,Vֵ 1;ڻģʽ临,¼ʱ,Ϊȷģʽ,¼ ʱ,𽥱ֳϵ.ͼ1ͼ2Ҳɿ,ģʽǽȷģʽ ʹ֮һģʽ,49erЧطģʽ.
Ϊ˽ģʽз,Ѱ;.ݿе һ㲻,˾дӸݿзģʽķԵúҪ. ӦCPDNӴڻģʽݿзֻģʽ.CPDNܹЧֻģʽ ʹģʽ.㷨һְųӵĲԽлԴĺ,Ļ ݵġϢз,Ҿлɾ.ϵͳѧϰ ֪ʶҪ,ֽĳЩı͹ѧϰ;ʹѧϰϵͳ ѧϰϢ,ʹCPDNзȷģʽ,Ҿдзֻ ģʽ.,ʹCPDN3ģʽȷģʽA1,A3ģʽA1 ,A2ģʽжϺѧϰ.ѧϰ,ÿֱֵΪ,ֵ .ѧϰڵı仯ͼ3ʾ.

ͼ3,߱ʾCPDNѧϰȷģʽA1,A3ڵ仯,ϸʵ߱ʾѧϰ ϵA1,A2ڵ仯,ʵ߱ʾѧϰģʽattri.1attri.2֮Ĺϵ ڵ仯.ͼ3Կ,ϵA1,A2,CPDNڵʼ ,ҳ޹ұ仯.Ϊϵκǰݶ ,ϵͳ˵ǡ¡,,Ϊµڵ.ھȷϵ A1,A3˵,ڵı仯ƽ,ȶڵ.A1,A3ڹ ϵȷģʽ,ϵȻ޵,CPDN޵ڵ㽫 Чؿ̻.˵CPDNбģʽ봿.ڻģʽ,CPDNѧϰ 1 300۲ʱ,ڵı仯ͳȶ,˵24ڵԱ ʾѧϰĻģʽ.
2.3 Ԥģʽ
CPDNֲܷѧϰģʽ,ҾнǿģʽԤ.νģʽԤ ָĳģʽδݵԤ.ԤĺûӰ쵽ԽģʽжϵĿŶ. ʵ,һЧ,ǲҪܹЧطִڴݿеĸ ģʽ,ϣδݾкǿԤ,ǿģʽԤ.C PDNЩҪһЧ.
,ʵ,CPDNDBǰ3 000Ԫѧϰʵ,õʵ ģ,ȻʹѧϰõCPDN2 000ԪԤʵ.ͼ4attribut e 1attribute 2֮ԭݻĹϵ֮ĶԪϵCPDNԤ Ĺϵ.ͼ5Ϊattribute 1,attribute 2attribute 3֮3-Dϵ Ԫϵ.ͼ,ǿؿ,CPDNԻģʽҲ൱õԤ .


3  
ģʽǴݿжϵġδоһ ģʽ,Ȼ縴Եĺ.µģʽ,һֻھ CPDN,ڷֺѧϰģʽ.㷨д洢 ٺͼٶȿص.CPDNݿзֺԤģʽʵой㷺Ӧǰ .ĿǰӦС󲡳溦ݿеİ׷۲ĲģʽķֺԤ֮,ȡ˽ õӦЧ.йسɹı.
лWichitaѧѧϵJan M.Zytkowṩ й.лԱĵоָʹ.

оõȻѧ͹863߿ƼĿ.
ߵ˳,[ HT6SSŮ,1966,ʿ,ҪоΪ˹,֪ʶ,,Ŵ,ģʽ ʶ.
ܷ,1940,оԱ,ʿʦ,ҪоΪ˹, ѧϰ,֪ʶ,ģʶ.
ͨѶϵ:˳,Ϸ 230027,йѧѧ3-327

ߵλˡܷ йѧԺܻео Ϸ 230031)
ˡйѧѧϵ Ϸ 230027
ο
[1]Froyland J. Introduction to Chaos and Coherence. London: Institute o f Physics Publishing Ltd., 1992
[2]Casdagli M. Nonlinear prediction of chaotic time series. Physica D, 1989,35:335356
[3]Elder IV J F, Pregibon D. A statistical perspective on knowledge dis covery in databases. In: Fayyad U, Piatetsky-Shapiro G, Smyth P eds. Advances i n Knowledge Discovery and Data Mining. U.S.A: AAAI Press, 1996. 83113
[4]Zytkow J M. Database exploration in search of regularities. Journal of Intelligent Information Systems, 1993,(2):3981
[5]Zytkow J M. Creating a discoverer: autonomous knowledge seeking agen t. In: Zytkow J M ed. Machine Discovery. Netherlands: Kluwer Academic Publishers Group, 1997. 253283
[6]Deng Chao, Xiong Fan-lun et al. Sequential learning n eural networks and its application in agriculture. In: Proceedings of the IEEE I nternational Joint Conference on Neural Networks (IJCNN'98). Alaska: IEEE Press, 1998. 21182123
1998-03-30յԭ,1998-06-16յ޸ĸ
