Phát hiện luật kết hợp liên kết chuỗi thời gian từ cơ sở dữ liệu định lượng có yếu tố thời gian

GIAN M – FTIQ
ARM (FUZZY TIME  INTERVAL QUANTITATIVE IN TIME SERIES – 
ASSOCIATION RULE MINING) 
A. Bài toán ñt ra 
 Cho trưc cơ s d liu ñnh lưng có yu t thi gian D, ngưng cc tiu min_sup, 
 ñ tin cy cc tiu min_conf, tp m v khong cách thi gian LT cùng các hàm thành 
 viên tương ng, tp m cùng các hàm thành viên tương ng vi các thuc tính trong D. 
 Bài toán ñt ra là phát hin các lut chui liên kt thi gian m có ñ h tr không nh 
 hơn ngưng cc tiu min_supp và ñ tin cy không nh hơn ñ tin cy cc tiu min_conf. 
B. Thut toán FTIQARM 
 Thut toán FTIQARM tìm tt c các lut chui liên kt thi gian m t cơ s d liu 
ñnh lưng có yu t thi gian. 
 a) Ý tưng thut toán 
 Đu tiên, cơ s d liu ñnh lưng có yu t thi gian D ban ñu ñưc chuyn ñi 
thành cơ s d liu m có yu t thi gian D’ da vào vic m hoá các thuc tính ñnh 
lưng. Tip theo, thut toán FTIQARM tìm các chui liên kt thi gian m ph bin. Quá 
trình tìm các chui liên kt thi gian m ph bin ñưc phát trin theo thut toán Apriori: 
lp li 2 giai ñon trong quá trình sinh chui liên kt thi gian m ph bin cho ñn khi 
không th sinh ñưc.  giai ñon 1, các chui ng c viên ñ dài k, kí hiu là C k ñưc sinh 
ra t tp các chui liên kt thi gian m ph bin ñ dài k1, kí hiu là L k1. Giai ñon 2, 
các chui ng c viên trong C k ñưc tính ñ h tr ñ xác ñnh tp các chui liên kt thi 
 gian m ph bin ñ dài k, L k. 
 Vic sinh tp ng c viên C k ñưc thc hin c th như sau: 
 Trưng hp k=1 : Đưa tt c thuc tính ca cơ s d liu m D’ vào C 1, tp các ng c 
viên ñ dài 1. 
 Trưng hp k=2 : Tp các ng c viên ñ dài 2, C2, s ñưc sinh ra bng cách kt hp 
2 mc thuc L1 và LT là L1 ×LT ×L1. Chng hn, gi s L1={fb,fc} và LT={lt1,lt2,lt3} thì 
9 ng c viên ñưc sinh ra là (fb,lt1,fb), (fb,lt2,fb), (fb,lt3,fb), (fb,lt1,fc), (fb,lt2,fc), 
(fb,lt3,fc), (fc,lt1,fc), (fc,lt2,fc), (fc,lt3,fc). 
 Trưng hp k >2 : Gi s (b1,lt1,b2,lt2,,ltk2,bk1) và (b2,lt2, b3,lt3,,ltk1,bk) là 
2 chui liên kt thi gian m ph bin thuc Lk1, khi ñó ta s sinh ra ñưc chui ng c 
viên ñ dài k cho Ck là α=(b1,lt1,b2,lt2,b3,lt3,,bk1,ltk1,bk) [4]. Tương t như vy, tt 
c các chui ng c viên thuc Ck ñưc sinh ra. 
74 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Tip theo là giai ñon tính ñ h tr ca các ng c viên thuc C k: 
 Mt mng danh sách giá tr thi gian ñưc s dng. Trưc tiên, b sung tt c các giao 
dch ti thi ñim t có cha b 1 vào phn t ñu tiên ca mng danh sách là lst [i] [1] (i là 
 chui th i cha b 1), mi phn t ca mng gm cp giá tr (time  thi ñim xy ra, value
 giá tr m). Tip theo, tt c các giao dch t có cha b 2 vào phn t th 2 ca mng danh 
sách lst[i][2] nu t>lst[i][1].time. Tip tc như vy ta ln lưt sinh ra các phn t lst[i][m] 
(3≤m≤k) nu tho mãn giao dch t cha b m và t> lst[i][m1].time. Kt qu thu ñưc là các 
danh sách có ñ dài k tương ng chui α và lst[i][r].time lst[i][r1].time (2≤r≤k) là khong 
cách thi gian gia 2 phn t ca chui. Công thc (3) ñưc s dng ñ tính ñ h tr ca 
chui α. 
 Sinh các lut chui liên kt thi gian m t các tp ph bin có ñ dài ≥2 tìm ñưc. 
 Các lut sinh ra ñưc tính ñ tin cy theo công thc (4) và loi b các lut có ñ tin cy 
 nh hơn min_conf. Tp các lut tìm ñưc còn li chính là kt qu cn tìm. 
 b) Thut toán FTIQARM 
 Input: Cơ s d liu ñnh lưng có yu t thi gian D, tp các tp m v khong cách 
 thi gian LT, tp m và các hàm thành viên tương ng vi các thuc tính trong D, ñ h 
 tr cc tiu min_sup, ñ tin cy cc tiu min_conf. 
 Output: Các lut chui liên kt m thi gian có ñ tin cy ≥min_conf. 
 Thut toán ñưc mô t như sau: 
 Chuyn D thành cơ s d liu m D’ 
 C1={các mc trong D’} 
 L1={c ∈C1|Supp(c)≥min_sup} 
 C2=∅; 
 for each a 1∈L1 
 for each a 2∈L1 
 for each ltd ∈LT{ 
 c=a 1*ltd*a 2; 
 add c to C 2; 
 } 
 for each c ∈C2 
 c.count=Supp(c); 
 L2={c ∈C2|c.count ≥min_sup} 
 for (k>2;L k1≠∅;k++) 
 { 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 75 
 Ck=fuzzy_apriori_gen(L k1); 
 for each c ∈Ck 
 c.count=Supp(c); 
 Lk={c ∈Ck|c.count ≥min_sup} 
 } 
 return gen_rules( ∪Lk); 
 Supp(c)//Hàm tính ñ h tr ca chui 
 { 
 m=0; 
 for each t j∈T 
 If (b i∈tj){ 
 m++; 
 lst[m][1].time=j; 
 lst[m][1].value=b i(t j);//fuzzy value of b i in transaction t j in D’ 
 } 
 for (i=2;i≤|c|;i++) 
 For each t j∈T 
 If (b i∈tj) and j≥lst[m j][i1].time) 
 { 
 lst[m j][i].time=j; 
 lst[m][i].value=b i(t j); 
 } 
 count=0; 
 for (i=1;i≤m;i++) 
 { 
 if (|lst[i]|=|c|) 
 { 
 s=1; 
 v=1; 
 for (j=1;j<|c|;j++) 
 { 
 s=min(s, ); 
 v=min(v,lst[i][j].value); 
 } 
76 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 v=min(v,lst[i][|c|].value); 
 } 
 count=count + v*s; 
 } 
 return count/|D|; 
 } 
 fuzzy_apriori_gen(L k1)//Hàm sinh ng c viên 
 { 
 Ck=∅; 
 for each a ∈Lk1 
 for each b ∈Lk1 
 { 
 c= ∅; 
 for (i=2;i<=k2;i++) 
 { 
 if (a i≠b i or alt i≠blt i) break; 
 c=c*a i*alt i; 
 } 
 if (i=k1 and a k1=b k1) 
 { 
 c=a 1*alt 1 * c*a k1*blt k1*b k; 
 add c to C k; 
 } 
 return C k; 
 } 
 gen_rules(L)//Hàm sinh lut 
 { 
 R= ∅; 
 for each p ∈L 
 { 
 r=(p 1,plt 1,p 2,plt 2,..p |p|1)→p|p| (plt |p|1); 
 if (Supp(p)/Supp(p |p| )>=min_conf) 
 add r to R; 
 } 
 return R; 
 } 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 77 
 Trong thut toán trên phép * là phép kt hp các giá tr ñ ñưc chui thi gian m. Ví 
 d: a 1*Short*a 2 s tr li chui liên kt thi gian m (a 1, Short, a 2) vi Short ∈ LT là tp 
 m, a 1,a 2 là các mc d liu. |p| là ñ dài ca chui liên kt thi gian m p, p |p| là mc d 
 liu cui cùng ca chui liên kt m p. 
4. KT QU TH NGHIM 
 Môi trưng ñưc s dng ñ th nghim thut toán là Chip Intel Core i5 2.5 GHz, 
 RAM 4 GB, h ñiu hành Windows7. Thut toán ñưc lp trình bng ngôn ng C#. 
 D liu th nghim ly ti [8] bao gm kt qu ca Istanbul Stock Exchange vi 07 
ch s chng khoán ca các th trưng: SP, DAX, FTSE, NIKKEI, BOVESPA, 
MSCE_EU, MSCI_EM t ngày Jun 5, 2009 ñn Feb 22, 2011 có mô t như trong bng 3. 
 BBBBngng 3. Cơ s d liu th nghim 
 S thuc tính S giao dch 
 Tên cơ s d liu 
 (I) (D) 
 ISTANBUL STOCK EXCHANGE 8 537 
 Tp LT= { Short , Medium, Long } ñưc gn vi khong cách thi gian và các hàm 
thành viên tương ng vi 3 tp m Short, Medium, Long thuc LT ñưc ñnh nghĩa như 
trong ñnh nghĩa 3. 
 Mi thuc tính ñnh lưng ñưc phân hoch thành 3 giá tr m (K=3) và các hàm 
 thành viên ñưc ñnh nghĩa theo công thc (1). 
 Kt qu th nghim ñu tiên th hin s lut sinh ra tương ng vi các ñ h tr cc 
 tiu và ñ tin cy cc tiu ñưc mô t trong bng 4. 
 BBBBngng 4. Kt qu s lut sinh ra tương ng vi ñ h tr cc tiu (min_supp) 
 và ñ tin cy cc tiu (min_conf) 
 min_conf 
 0.60 0.65 0.70 0.75 0.80 0.85 
 min_supp 
 0.15 1676 1655 1481 1028 501 131 
 0.17 615 594 490 291 130 23 
 0.20 195 177 137 61 18 1 
 0.25 41 32 17 4 0 0 
 0.30 9 9 5 0 0 0 
 0.33 1 1 1 0 0 0 
78 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Da vào bng 4, hình 1 là biu ñ th hin mi quan h gia ñ tin cy cc tiu và s 
 lut sinh ra vi các ñ h tr cc tiu khác nhau. T hình 1, ta thy s lưng các lut gim 
 mnh khi ñ tin cy cc tiu tăng dn ñi vi cùng ñ h tr cc tiu thp. Khi ñ h tr 
 cc tiu cao thì mi quan h gia s lut và ñ tin cy cc tiu tr nên mn hơn. 
 Hình 1. Biu ñ th hin mi quan h gia ñ tin cy cc tiu min_conf 
 và s lut sinh ra vi các ñ h tr cc tiu khác nhau 
 Tip theo, hình 2 mô t mi quan h gia s lưng lut sinh ra và ñ h tr cc 
tiu ñi vi các ñ tin cy cc tiu khác nhau. Hình 2, s lưng lut tăng nhanh khi ñ h 
tr gim. 
 Hình 2. Biu ñ th hin mi quan h gia ñ h tr cc tiu min_supp 
 và s lut sinh ra vi các ñ h tr cc tiu khác nhau 
 Cui cùng, mi quan h gia chi phí thi gian thc hin thut toán và ñ h tr cc 
 tiu ng vi ñ tin cy cc tiu là 0.6 ñưc th hin như trong bng 5 và hình 3. 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 79 
 Bng 5. Mi quan h gia thi gian chc hin và ñ h tr cc tiu vi min_conf=0.6 
 Đ h tr cc tiu Thi gian thc hin (s) 
 0.15 118.01 
 0.17 50.14 
 0.20 17.909 
 0.25 6.306 
 0.30 3.179 
 0.33 3.565 
 Hình 3. Biu ñ th hin mi quan h v thi gian thc hin và ñ h tr cc tiu 
 ng vi ñ tin cy cc tiu min_conf=0.6 
 T hình 3, ta thy chi phí thi gian tăng rt nhanh khi gim ñ h tr cc tiu. Điu 
 này là hp lí do khi gim ñ h tr cc tiu thì s lưng tp ph bin ñưc sinh ra s tăng 
 theo rt nhanh. 
5. KT LUN 
 Bài báo ñã ñ xut thut toán FTIQARM nhm phát hin các lut liên kt thi gian 
m ph bin t cơ s d liu ñnh lưng có yu t thi gian. Thut toán FTIQARM ñưc 
ci tin t thut toán Apriori ñ tìm các chui liên kt m thi gian ph bin. Bài báo ñã 
trình bày thut toán dưi dng gi mã. Kt qu thc nghim ñã ch ra mi quan h gia s 
lưng các lut kt qu và ñ h tr cc tiu, ñ tin cy cc tiu cũng như thi gian thc 
hin. Nghiên cu ca bài báo ñã góp phn gii quyt vn ñ phát hin các mi quan h v 
thi gian gia các s kin trong cơ s d liu ñnh lưng có yu t thi gian. 
80 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 TÀI LIU THAM KHO 
1. R. Agrawal, T. Imielinski, A.Swami, "Mining association rules between sets of items in large 
 database", In: P.Buneman, S. Jajodia eds. Proc. of 1993 ACM SIGMOD Conf on Management 
 of Data . Washington DC: ACM Press, 1993. pp.207216. 
2. R. Agrawal, R. Srikant (1994), "Fast algorithms for mining association rules ", In: J.Bocca, 
 M.Jarke, C.Zaniolo eds. Proc. of the 20th Int’l Conf on Very Large DataBases (VLDB’94) , 
 Santiago: Morgan Kaufmann, pp. 487499. 
3. Y. L. Chen, M. C. Chiang, and M. T. Ko (2003), "Discovering timeinterval sequential 
 patterns in sequence databases", Expert Syst. Applicat. , vol. 25, no. 3, pp.343354. 
4. YenLiang Chen, ChengKui Huang (2005), "Discovering fuzzy timeinterval sequential 
 patterns in sequence databases", IEEE Transactions on Systems, Man, and Cybernetics, Part 
 B: Cybernetics 35, pp.959972. 
5. Attila Gyenesei (2000), "A Fuzzy Aproach for Mining Quantitative Association Rules", Turku 
 Centre for Computer Sciences , TUCS Technical Report, No 336. 
6. Kuod. M, Ada. P (1998), "Mining Fuzzy Association Rules", In SIGMOD Record , 27(1). 
7. L. Qin, P. Luo, Z. Shi (2004), "Efficiently mining frequent itemsets with compact FPtree". In: 
 Z.Shi and Q.He eds. Proc. of Int’l Conf. on Intelligent Information Processing 2004 (IIP2004) , 
 Beijing, China. Springer Press, pp.397406. 
8. UCIMachine Learning Repository,  
9. LiangXi Qin, ZhongZhi Shi (2006), "Efficiently mining association rules from time series", 
 International Journal of Information Technology , Vol.12 No.4. pp.3038. 
10. Saravanan, M.S.; Sree, R.J.R (2011), "A Simple Process model generation using a new 
 Association Rule Mining algorithm and Clustering Approach", Advanced Computing (ICoAC) , 
 2011 Third International Conference on Digital Object Identifier, pp.265269. 
11. R. Srikant and R. Agrawal (1995), "Mining Sequential Patterns", Proc. of the 11th Int’l 
 Conference on Data Engineering , Taipei, Taiwan. 
12. Zadeh, L. A. (1995), "Fuzzy sets", Information and Control , Vol. 8, pp.338353. 
13. M. J. Zaki and C.J. Hsiao (1999), "CHARM: An efficient algorithm for closed association 
 rule mining", Technical Report 9910, Computer Science Dept. , Rensselaer Polytechnic 
 Institute, October.. 
14. Sumathi, R. and Kirubakaran, E. (2012), "Architectural perspective of parallelizing association 
 rule mining", Advances in Engineering, Science and Management (ICAESM) , International 
 Conference, pp.437442. 
15. YiChung Hu, GwoHshiung Tzeng, ChinMi Chen, "Deriving twostage learning sequences 
 from knowledge in fuzzy sequential pattern mining", Information Sciences 159 (2004) , 
 pp.6986. 
16. Fu A, Wong MH, Sze SC, Wong WC, Wong WL, Yu WK (1998) "Finding fuzzy sets for the 
 mining of fuzzy association rules for numerical attributes", In: IDEAL98, 1st International 
 symposium on intelligent data engineering and learning , Hong Kong, pp.263268. 
17. ShuYue J, Tsang E, Yengg D, Daming S (2000) "Mining fuzzy association rules with 
 weighted items" . In: Proceedings of the IEEE international conference on systems, man, and 
 cybernetics. Nashville, TN, pp.19061911. 
TẠP CHÍ KHOA HỌC −−− SỐ 8/2016 81 
18. ChungI Chang; HaoEn Chueh; Lin, N.P. "Sequential Patterns Mining with Fuzzy Time
 Intervals", Fuzzy Systems and Knowledge Discovery , 2009. FSKD '09. Sixth International 
 Conference on, On page(s): 165169 Volume: 3, 1416 Aug, 2009. 
 19. W. H. Au and K. C. C. Chan, "FARM: A data mining system for discovering fuzzy association 
 rules", Proc. FUZZ IEEE , vol. 3, pp.2225, 1999. 
 20. W. Zhang (1999), "Mining fuzzy quantitative association rules", Proc. 11th Int. Conf. Tools 
 Artificial Intelligence, pp.99102. 
 21. ChungI Chang; HaoEn Chueh; YuChun Luo (2013), "An integrated sequential patterns 
 mining with fuzzy timeintervals", Systems and Informatics (ICSAI) , International Conference 
 on, On page(s): 2294 – 2298 
 22. Weng, ChengHsiung; Chen, YenLiang (2010), "Mining fuzzy association rules from 
 uncertain data", Knowledge and Information Systems , Volume.23, Issue.2, pp.129. 
 23. CHANG, Joong Hyuk; PARK, Nam Hun (2013), "Finding Interesting Sequential Patterns in 
 Sequence Data Streams via a TimeInterval Weighting Approach", IEICE Transactions on 
 Information and Systems , Volume.E96.D, Issue.8, pp.1734. 
 24. Chang JH (2011) "Mining weighted sequential patterns in a sequence database with a time
 interval weight", Know Based Syst 24(1):19. 
 25. Moskovitch R, Walsh C, Hripsack G, Tatonetti N (2014) "Prediction of biomedical events via 
 time intervals mining", ACM KDD Workshop on Connected Health in Big Data Era , NY, 
 USA. 
 26. C.H. Chen, T.P. Hong, and V.S. Tseng (2012), "Fuzzy data mining for timeseries data", Appl. 
 Soft Comput. , 12(1):536542. 
 OPTICAL MODES IN A FREE STANDING QUANTUM WIRE 
 AbstractAbstract: A continuum model is employed to describe the allowed longitudinaloptical 
 (LO) phonons of a cylindrical freestanding GaAs wire. The confinement of optical 
 modes in a quantum wire of polar material is described by a theory involving the triple 
 hybridization of LO, transverse optical (TO) phonon, and IP (interface polariton) modes. 
 In this work, we tried to calculate the LO, TO, and IP modes in a quantum wire using 
 conditions of both mechanical and electromagnetic boundary. 
 KeywordsKeywords: LO, TO, IP, mechanical and electromagnetic boundary.