Một số vấn đề về khai phá đồ thị con thường xuyên đóng

p dữ liệu đồ thị được gắn nhãn, D = { G1, ..., Gn}, tập FS 
chứa tất cả các đồ thị con thường xuyên tức là độ hỗ trợ mọi đồ thị g trong FS là supg≥σ (với σ ngưỡng độ hỗ trợ tối 
thiểu hoặc gọi là min_sup). Tập tất cả các đồ thị con thường xuyên đóng, ký hiệu CS = { g | g ∈ FS \wedge \not \exists 
g' ∈ FS: g \subset g' \wedge supg = supg' } tập tất cả các đồ thị con thường xuyên mà trong đó không có đồ thị nào là đồ 
thị cha của đồ thị khác đồng thời lại có cùng độ hỗ trợ với nó. Như vậy, CS ⊆ FS và vấn đề khai phá đồ thị con thường 
xuyên đóng là tìm tập đầy đủ của CS trong tập dữ liệu đồ thị D với ngưỡng độ hỗ trợ tối thiểu min_sup (σ). 
 Tương tự như thuật toán gSpan-Miner, thuật toán CloseMining sử dụng cùng một phương pháp chỉ khác ở chỗ 
kiểm tra điều kiện trong dòng 10 đến 12 của thủ tục đệ quy CloseGraph xem có tồn tại một đồ thị cha nào mà có cùng 
độ hỗ trợ với nó hay không. Về mặt bản chất, việc sinh tập ứng viên và vấn đề xác định đồ thị con đẳng cấu không có 
gì thay đổi vẫn thuộc lớp NP. 
476 MỘT SỐ VẤN ĐỀ VỀ KHAI PHÁ ĐỒ THỊ CON THƯỜNG XUYÊN ĐÓNG 
 VI. THUẬT TOÁN PSI-CFSM 
 Trong bài báo này, chúng tôi đưa ra một phương pháp về mặt tính toán là tối ưu hơn so với gSpan và FFSM. 
Chúng tôi cũng sử dụng thứ tự cho nhãn của đỉnh và cạnh giống gSpan và FFSM. gSpan sử dụng mã DFS để xác định 
mỗi đồ thị con chỉ có một biểu diễn duy nhất, FFSM sử dụng CAM để biểu diễn sự duy nhất của đồ thị con. Chúng tôi 
sử dụng CAM để biểu diễn sự duy nhất của đồ thị con và áp dụng một phương pháp khai phá đồ thị con thường xuyên 
mới và gọi tên là Polynomial Subgraph Isomorphism Closed Frequent Subgraph Mining (PSI-CFSM). 
 Như trên đã đề cập, thuật toán gSpan sử dụng mã DFS để xác định biểu diễn duy nhất cho một đồ thị. Mã này 
được gọi là Minimum DFS Code (M-DFSC). Cho một đồ thị, giả sử coi mỗi đỉnh là một gốc thì từ gốc đó theo phương 
pháp duyệt theo độ sâu sẽ có rất nhiều cây bao trùm của đồ thị đó. Như vậy ở đây không có tính duy nhất về mặt biểu 
diễn. Vì vậy, [Yan và Han 2002] đã đề xuất một phương pháp mã chuẩn dựa trên nhãn của đồ thị bằng cách gán mỗi 
định danh duy nhất cho mỗi đỉnh và mỗi cạnh của đồ thị trong mã DFS sẽ được biểu diễn bởi một bộ 5 thành phần (i, j, 
li, le, lj) với i và j là định danh của đỉnh, li và lj là các nhãn tương ứng, le là nhãn của cạnh nối giữa hai đỉnh tương ứng. 
Dựa trên một thứ tự gọi là DFS lexicographic order, M-DFSC của đồ thị g được gọi là mà chuẩn của g. Mã chuẩn này 
chính là mã nhỏ nhất theo phương pháp duyệt cây theo độ sâu mà mỗi bước sẽ thêm vào một cạnh trong mã DFS. 
 Thuật toán FFSM thì sử dụng CAM để biểu diễn sự duy nhất của một đồ thị. Với một đồ thị g sẽ có (n!) ma trận 
kề của đồ thị g với n là số đỉnh của đồ thị. Cho một ma trận kề M của một đồ thị g, mã của ma trận M là một chuỗi các 
phần tử của phần tam giác dưới hoặc trên của một ma trận M bao gồm cả các phần tử nằm trên đường chéo chính. Với 
mỗi hoán vị của ma trận M ta sẽ thu được một mã của ma trận M. Tuân theo một thứ tự được xác định trên tập nhãn 
của đỉnh và tập nhãnh của cạnh của đồ thị g ta sẽ tìm được mã lớn nhất hoặc nhỏ nhất trong tất cả các hoán vị của ma 
trận M. Mã lớn nhất hoặc nhỏ nhất này sẽ được coi là mã chuẩn để biểu diễn duy nhất cho một đồ thị g thay cho (n!) 
biểu diễn của một đồ thị g. Ma trận kề mà lớn nhất hoặc nhỏ nhất được gọi là dạng chuẩn ma trận kề (Canonical 
Adjacency Matrix, hoặc gọi tắt là CAM) [Inokuchi 2000, 2002; Kuramuchi 2001; Huan 2003]. Theo đó, một CAM 
biểu diễn duy nhất cho một đồ thị g và một đồ thị g chỉ có một CAM. Với các phương pháp vét cạn việc xác định CAM 
của một đồ thị cũng có độ phức tạp tính toán là O(n!) thuộc lớp NP. Tuy nhiên, với việc sử dụng thứ tự nhãn của đỉnh 
và cạnh của đồ thị thì việc xác định CAM sẽ có độ phức tạp tính toán thời gian đa thức. 
 Định lý. Cho tập đồ thị gắn nhãn cho cả đỉnh và cạnh GD với một thứ tự toàn phần trên nhãn của đỉnh và cạnh. 
Tồn tại một thuật toán tìm tập chứa tất cả các đồ thị con thường xuyên đóng của GD mà vấn đề xác định đồ thị con 
đẳng cấu trong quá trình sinh tập ứng viên và đếm độ hỗ trợ của đồ thị con được thực hiện trong thời gian đa thức. 
Hoàng Minh Quang, Vũ Đức Thi, Phạm Quốc Hùng 477 
 Chúng tôi đưa ra phương pháp xác định đồ thị con đẳng cấu bằng cách sử dụng CAM để biểu diễn duy nhất cho 
một đồ thị g trong tập dữ liệu đồ thị đầu vào GD. Cùng với CAM chúng tôi chia tách vấn đề khai phá đồ thị con thường 
xuyên thành khai phá đồ thị con thường xuyên theo từng mức. Bắt đầu từ mức đồ thị chỉ có 1 cạnh tức là chỉ có 2 đỉnh 
và chúng tôi gọi các đồ thị này là 2-subgraph. Đầu tiên sẽ khai phá tất cả các đồ thị 2-subgraph, tìm tất cả các đồ thị 2-
subgraph là thường xuyên và lưu lại. Ở đây chúng tôi sử dụng nhiều tập lưu trữ các 2-subgraph thường xuyên. Tập CS2 
 i
sẽ lưu toàn bộ các 2-subgraph thường xuyên đóng của toàn bộ tập dữ liệu đồ thị GD và các tập FS 2 sẽ lưu các 2-
 i
subgraph thường xuyên của các đồ thị gi∈ GD. Cùng với đó chúng tôi cũng sẽ dùng C 2 để lưu toàn bộ ứng viên 2-
 i i
subgraph của đồ thị gi∈ GD. Tiếp theo từ FS 3 trở đi chúng ta chỉ lưu các tập đồ thị con thường xuyên đóng nên FS 3 bị 
 i
thay thế bằng CS 3. Tại mỗi bước khai phá đồ thị con thường xuyên đóng mức k (k >= 2) ta sẽ kết hợp các đồ thị nằm 
 i i i i
trong FS 2 và CS k-1để sinh ra các ứng viên nằm trong C k, mỗi thành viên nằm trong C k khi sinh ra sẽ được đưa vào 
một danh sách liên kết được sắp xếp sẵn tạo thành một danh sách liên kết được sắp thứ tự theo CAM. Khi cần xác định 
 i
một ứng viên trong C k có phải là đồ thị con thường xuyên hay không thì chúng ta áp dụng chiến thuật tìm kiếm nhị 
 j
phân được coi là tối ưu nhất hiện nay để tìm sự xuất hiện của nó trong các C k khác. Rõ ràng, ta thấy ở đây mỗi đồ thị 
 n
con ứng viên sẽ được tìm bằng tìm kiếm nhị phân. Giả sử mỗi đồ thị gi có m = 2 đồ thị con ứng viên mức k thì việc 
 n
tìm kiếm một đồ thị con trong nó là O(log22 ) nên dù m có lớn đến đâu thì thuật toán xác định đồ thị con đẳng cấu và 
đếm độ hỗ trợ của một đồ thị con ứng viên vẫn thuộc lớp P tức là giải quyết trong thời gian đa thức. 
 Đánh giá độ phức tạp thuật toán PSI-CFSM. Dòng 1 xây dựng danh sách liên kết được sắp thứ tự theo CAM các 
 i
đồ thị 2-subgraph tạo thành C 2 cho mỗi đồ thị gi. 2-subgraph là 2 đỉnh nên chỉ có duy nhất 1 cạnh bởi chúng ta chỉ 
quan tâm đến các đồ thị liên thông. Do vậy bước này sẽ chỉ là xác định tất cả các cạnh của tất cả các đồ thị gi trong GD. 
 i j
Dòng 2 đến 4 là đối với mỗi đồ thị con u trong C 2 của một đồ thị gi ta sẽ so sánh với các đồ thị v của C 2 theo tìm kiếm 
 j
nhị phân thì thời gian tính toán tồi nhất là O(log2 |C 2|) và nếu tìm thấy thì ta sẽ tăng độ hỗ trợ của u và v lên 1 và đánh 
 i
dấu là đã xét để lần sau chúng ta không tìm đến nó nữa. Như vậy bước 2 đến 4 sẽ tính toán trong O(n log2 max(|C 2|)) 
với n là số lượng các đồ thị trong GD. Từ dòng 6 đến dòng 13 là một vòng lặp mà nếu vẫn sinh ra ứng viên mức k thì 
vẫn tiếp tục. Nghĩa là vòng lặp này sẽ chạy tối đa là max(|Vgi|) bước, mỗi bước của vòng lặp chính là tìm tập đồ thị con 
 i
thường xuyên đóng ở mức k. Trong vòng lặp ta thực hiện công việc tương tự như với 2-subgraph là xây dựngC k là một 
danh sách liên kết được sắp xếp theo thứ tự của CAM, việc xây dựng danh sách liên kết này cũng chỉ tính toán trong 
 k
thời gian tồi nhất là O(log2 C |Vgi|) và vẫn là đa thức. Các công việc tiếp theo ở mức k là tìm kiếm các đồ thị ứng viên 
nào thỏa mãn là đồ thị con thường xuyên theo tìm kiếm nhị phân cũng chỉ thực hiện trong thời gian tồi nhất là O(n log2 
 i
max(|Vgi|)) và cũng thực hiện trong thời gian đa thức. Dòng thứ 10, kiểm tra v ∈ CS k-1 có tồn tại đồ thị nào có độ hỗ trợ 
bằng với độ hỗ trợ của đồ thị con đang xét u hay không thì từ đồ thị u ta phải xây dựng các đồ thị con mức (k-1) của u 
 i
và xác định tất cả các con này có con nào trùng với v thì ta loại v khỏi CS k-1. Vậy độ phức tạp tính toán ở dòng 10 là 
 i
O(m log2 |CS k-1|) với m là số đồ thị con mức (k-1) được sinh ra của u. Mà số đồ thị con mức (k-1) của u chính là lần 
 u u
lượt bỏ đi các đỉnh của u cùng với cạnh gắn với nó ta sẽ được tập S k-1 và lực lượng lớn nhất của max(|S k-1|) = (k-
1)*(k-2) nên số đồ thị con mức (k-1) của u là NSu = |Vu|*(k-1)*(k-2). Vậy tổng hợp lại ta sẽ có độ phức tạp tính toán 
của PSI-CFSM là 
478 MỘT SỐ VẤN ĐỀ VỀ KHAI PHÁ ĐỒ THỊ CON THƯỜNG XUYÊN ĐÓNG 
 VII. KẾT LUẬN 
 Với kết quả xây dựng được thuật toán khai phá đồ thị con thường xuyên đóng với xác định đồ thị con đẳng cấu 
thực hiện trong thời gian đa thức mang lại một ý nghĩa lớn trong việc khai phá dữ liệu nói chung và khai phá đồ thị nói 
riêng. Tiếp theo bài báo này, chúng tôi sẽ thực hiện thử nghiệm thuật toán để chứng minh tính hiệu quả của thuật toán 
mới được đề xuất. 
 VIII. LỜI CẢM ƠN 
 Chúng tôi xin gửi lời cảm ơn tới đề tài CS16.17 ―Nghiên cứu một số phương pháp khai phá quan điểm và ứng 
dụng vào bài toán tổng hợp ý kiến theo tính năng sản phẩm của người tiêu dùng Việt Nam‖ - Viện Công nghệ Thông tin - 
Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện, trợ giúp một phần kinh phí để hoàn thiện bài báo này. 
 TÀI LIỆU THAM KHẢO 
1. E. Barbu, P. Héroux, S. Adam, and E. Trupin. Clustering document image using graph summaries. In Proceedings of the 5th 
 International Conference on Learning and Data Mining, pages 194-202, 2005. 
2. C. Chen, X. Yan, P.S. Yu, J. Han, D. Zhang, and X. Gu. Towards graph containment search and indexing. In Proceedings of 
 the 33rd International Conference on Very Large Data Bases (VLDB'07), pages 926-937, 2007. 
3. Y. Chi, Y. Yang, Y. Xia, and R.R. Muntz. 2004. HybridTreeMiner: An Efficient Algorithm for Mining Frequent Rooted Trees 
 and Trees using Canonical Forms, In Proceedings of the 16th International Conference on Scientific and Statistical Database 
 Management, 11–20. 
4. M.J. Chung. O(n2.5) time algorithm for the subgraph homomorphism problem on trees. Journal of Algorithms, 13:106-112, 
 1987. 
5. D.J. Cook and L.B. Holder. Substructure discovery using minimum description length and background knowledge. Journal of 
 Artificial Intelligence Research, 1:231-255, 1994. 
6. M. Deshpande, M. Kuramochi, and G. Karypis. Frequent substructure based approaches for classifying chemical compounds. 
 IEEE Transactions on Knowledge and Data Engineering, 17(8):1036-1050, 2005. 
7. M. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and 
 Company, New York, 1979. 
8. J.E. Hopcroft and R.E. Tarjan. Isomorphism of planar graphs. In R.E. Miller and J.W. Thatcher, editors, Complexity of 
 Computer Computations, pages 131-152. Plenum Press, 1972. 
9. J. Huan, W. Wang and J. Prins. Effcient mining of frequent subgraph in the presence of isomorphism. In Proceedings of the 
 2003 International Conference on Data Mining (ICDM'03), pages 549-552, 2003. 
10. J. Huan, W. Wang, A. Washington, J. Prins, R. Shah, and A. Tropsha. Accurate classification of protein structural families 
 based on coherent subgraph analysis. In Proceedings of Pacific Symposium on Biocomputing, pages 411-422, 2004. 
11. Inokuchi, T.Washio, and H. Motoda. An apriori-based algorithm for mining frequent substructure from graph data. In 
 Proceedings of the Fourth European Conference on Principles and Practice of Knowledge Discovery in Databases, pages 13-23, 
 2000. 
12. Inokuchi, T. Washio, K. Nishimura, and H. Motoda. A fast algorithm for mining frequent connected subgraphs. Research 
 Report RT0448, IBM Research, Tokyo Research Laboratory, 2002. 
13. S.W. Lu, Y. Ren, and C.Y. Suen. Hierarchical attributed graph representation and recognition of handwritten chinese 
 characters. Pattern Recognition, 24:617-632, 1991. 
14. D.W. Matula. Subtree isomorphism in O(n5/2). Annals of Discrete Mathematics, 2: 91-106, 1978. 
15. B.D. McKay. Practical graph isomorphism. Congress Numerantium, 30:45-87, 1981. 
16. M. Kuramochi and G. Karypis. 2001. Frequent Subgraph Discovery, In Proceedings of International Conference on Data 
 Mining, 313–320. 
17. Pearce, T. Caelli, and W.F. Bischof. Rule-graphs for graph matching in pattern recognition. Pattern Recognition, 27(9):1231-
 1246, 1994. 
18. D.C. Schmidt and L.E. Druffel. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. 
 Journal of the ACM, 23(3):433-445, 1976. 
19. R. Shamir and D. Tsur. 1999. Faster Subtree Isomorphism, Journal of Algorithms 33(2), 267–280. 
20. D. Shasha, J.T.L. Wang, and R. Giugno. Algorithms and applications of tree and graph searching. In Proceedings of the 
 twenty-first ACM SIGMOD-SIGACT-SIGART Symposium on Principles on Database Systems (PODS'02), pages 39-52, 
 2002. 
21. J.R. Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM, 23(1): 31-42, 1976. 
22. X. Yan and J.W. Han. gSpan: Graph-based substructure pattern mining. In Proceedings of the 2002 International Conference 
 on Data Mining, page 721, 2002. 
23. X. Yan and J. Han. Close graph: Mining closed frequent graph patterns. In Proceedings of the 9th ACM SIGKDD 
 International Conference on Knowledge Discovery and Data Mining, pages 286-295, 2003. 
24. X. Yan, P.S. Yu, and J. Han. Graph indexing: A frequent structure-based approach. In Proceedings of the 2004 ACM 
 SIGMOD International Conference on Management of Data (SIGMOD'04), pages 335-346, 2004. 
25. X. Yan, P.S. Yu, and J. Han. Sub-structure similarity search in graph databases. In Proceedings of the 2005 ACM SIGMOD 
 International Conference on Management of Data (SIGMOD'05), pages 766-777, 2005. 
26. X. Yan, F. Zhu, J. Han, and P.S. Yu. Searching substructures with superimposed distance. In Proceedings of the 22nd 
 International Conference on Data Engineering (ICDE'06), page 88, 2006. 
Hoàng Minh Quang, Vũ Đức Thi, Phạm Quốc Hùng 479 
 SOME PROBLEMS ON CLOSED FREQUENT SUBGRAPH MINING 
 Hoang Minh Quang, Vu Duc Thi, Pham Quoc Hung 
ABSTRACT— Frequent patterns mining is an important problem is more likely into practical applications. The diversity of data 
structures such as chemical structures of the drug ingredients, cell gene structures, animal protein structures and other structures, 
causes many difficulties in frequent itemsets mining. The good news is that these data can be represented by many structured data 
formats known as graphs, trees or lattices. Therefore, the study of frequent subgraph mining is significantly useful in the medical 
field. In this paper, we review and evaluate some current frequent subgraph mining algorithms and recommend some improvememt 
in the implementation of frequent subgraph mining in order to increase the efficiency of frequent subgraphs mining algorithms, 
especially closed frequent subgraphs mining algorithms. 
Keywords— Data mining, frequent subgraph, graph mining, structured data, closed frequent subgraph, complexity computation.