Luận án Nghiên cứu, phát triển một số phương pháp khai phá dữ liệu trên dữ liệu có cấu trúc

 tượng của U, theo
định nghĩa 1.2.6 thì tập tất cả các rút gọn của C phải là hệ Sperner nên REDU 1 pCq “
tB P P; EA P P; A Ă Bu mà rõ ràng trong P tồn tại hw Ă ohw khơng thỏa mãn hệ
 53
Sperner nên phải xĩa bỏ hw khỏi P thì P trở thành một hệ Sperner. Đặt REDU 1 pCq “
P ´ thwu “ totw; ohwu. Rõ ràng là REDU 1 pCq “ REDU pCq với REDU 1 pCq là tập
tất cả các rút gọn miền dương của DS1 “ pt5; 6; 8; 9; 12; 14u; tothwu Y tdu; V; fq và
REDU pCq là tập tất cả các rút gọn miền dương của DS “ pU; tothwu Y tdu; V; fq.
 Khác với sử dụng rút gọn miền dương theo định nghĩa 1.2.6 để tìm tập tất cả
các tập rút gọn REDpCq của C “ tothwu cĩ độ phức tạp tính tốn thời gian NP-
complete, thuật tốn AnAttributeReduct(DS) sẽ tìm một rút gọn theo miền dương của
C từ bảng quyết định nhất quán 2.2 với độ phức tạp tính tốn thời gian đa thức:
temp “ Hp0q ´ tou “ tthwu “ B1 P Md đ Hp1q “ Hp0q,
temp “ Hp1q ´ ttu “ tohwu Ę tB P Mdu đ Hp2q “ temp,
temp “ Hp2q ´ thu “ towu “ B3 P Md đ Hp3q “ Hp2q,
temp “ Hp3q ´ twu “ tohu Ď B2 P Md đ Hp4q “ Hp3q
 Đặt H “ Hp4q “ tohwu và thuật tốn AnAttributeReduct(DS) dừng, khi đĩ
H P REDpCq. Đạt được một bảng rút gọn thuộc tính theo miền dương là bảng 2.4
từ bảng quyết định nhất quán 2.2. Tuy nhiên, bảng quyết định rút gọn thuộc tính này
khơng cịn là nhất quán vì cĩ hàng 1; 8 trùng nhau và hàng 5; 10 trùng nhau. Mặc dù
vậy, bảng rút gọn thuộc tính 2.4 vẫn sinh ra các luật quyết định đúng theo các luật
quyết định được sinh ra từ bảng 2.2.
 Bảng 2.4: Một rút gọn thuộc tính miền dương của bảng 2.2
 No. Outlook Humidity Windy d
 1; 8 Sunny High Weak No
 2 Sunny High Strong No
 3 Overcast High Weak Yes
 4 Rain High Weak Yes
 5; 10 Rain Middle Weak Yes
 54
 No. Outlook Humidity Windy d
 6 Rain Middle Strong No
 7 Overcast Middle Strong Yes
 9 Sunny Middle Weak Yes
 11 Sunny Middle Strong Yes
 12 Overcast High Strong Yes
 13 Overcast Middle Weak Yes
 14 Rain High Strong No
 Kết hợp hai thuật tốn AnAttributeReduct(DS) và AnObjectReduct(DS) sẽ thu
được bảng quyết định rút gọn thuộc tính miền dương và thu gọn đối tượng mà vẫn bảo
tồn các luật quyết định được sinh ra là đúng và ngắn gọn cĩ nghĩa là sinh ra được cây
quyết định nhỏ (cĩ thể là nhỏ nhất cũng cĩ thể khơng nhỏ nhất nhưng vẫn là nhỏ). Từ
bảng 2.2 áp dụng hai thuật tốn này thu được bảng quyết định nhất quán với tập vũ
trụ U1 “ t5; 6; 8; 9; 12; 14u trên tập thuộc tính tohwu là thu gọn theo cả chiều ngang
và chiều dọc đảm bảo sinh ra đủ một bộ luật quyết định như kết quả là bảng 2.5.
 Bảng 2.5: Kết hợp rút gọn đối tượng và thuộc tính của bảng 2.2
 No. Outlook Humidity Windy d
 1 Rain Middle Weak Yes
 2 Rain Middle Strong No
 3 Sunny High Weak No
 4 Sunny Middle Weak Yes
 5 Overcast High Strong Yes
 6 Rain High Strong No
 Một cây quyết định được sinh ra từ bảng quyết định nhất quán tối thiểu 2.5 là sự
kết hợp hai thuật tốn AnObjectReduct(DS) và AnAttributeReduct(DS) từ bảng quyết
 55
định nhất quán 2.2. Ma trận phân biệt tìm được theo định nghĩa 1.2.7 trên bảng 2.3 vì
|U 1| “ 6 ă 14 “ |U|.
 H
 » w H fi
 — ffi
 — oh HH ffi
 — ffi
 — ffi
 — ffi
 — H otw th H ffi
 — ffi
 — ffi
 — H oth otw HH ffi
 — ffi
 — ffi
 —thw HH ohw o Hffi
 — ffi
 – fl
 Tập CORE được tính theo định nghĩa 1.2.8 COREpCq “ tw; ou sử dụng thuật
tốn DecisionTree(DS) sinh ra cây quyết định như hình 2.1. Dễ dàng kiểm chứng
được cây quyết định này trùng với trùng với cây quyết định được sinh ra theo thuật
tốn ID3 từ bảng quyết định nhất quán 2.1.
 Outlook
 Sunny Overcast Rain
 Humidity Yes Windy
 Middle High Weak Strong
 Yes No Yes No
 Hình 2.1: Cây quyết định được sinh ra từ thuật tốn DecisionTree(DS)
2.7 Đánh giá thực nghiệm
 Trong phần này, nghiên cứu sinh chứng tỏ bằng thực nghiệm kết quả đánh giá các
thuật tốn nghiên cứu sinh đề xuất trong chương khai phá dữ liệu dạng bảng. Các kết
quả thực nghiệm được thực hiện nhanh với ngơn ngữ lập trình Nodejs, Javascript với
một số tập dữ liệu dạng txt từ kho dữ liệu UCI.
 56
 Bảng 2.6: Bảng thực hiện một rút gọn thuộc tính
 Tập dữ liệu Thuộc tính gốc Thuộc tính rút gọn Thời gian(s)
 Examples 4 3 0.006
 Breast cancer 9 8 0.161
 Balance 4 3 0.248
 Car Evaluation 6 5 0.673
 Bảng 2.7: Bảng thực hiện rút gọn đối tượng
 Tập dữ liệu Đối tượng gốc Đối tượng rút gọn Thời gian(s)
 Examples 14 6 0.005
 Breast cancer 286 2 0.158
 Balance 625 6 0.171
 Car Evaluation 1728 9 0.771
 Thực nghiệm chỉ ra rằng tốc độ tính tốn của thuật tốn IRDT là nhanh vượt trội
so với thuật tốn ID3. Cĩ thể dễ dàng nhận thấy rằng vấn đề đếm số lượng phần tử
trong các tập quan hệ bất khả phân biệt là các phép tính tốn số nguyên nên rõ ràng
nhanh hơn tính hàm độ đo thơng tin (Entropy và tính Information Gain) vốn là các
cơng thức tính tốn số thực.
 Bảng 2.8: Bảng so sánh tốc độ thực hiện IDRT và ID3 (millisecond)
 Datasets (Atts/Objs) ID3 (ms) IRDT (ms)
 Examples (4/14) 3 1
 Breast cancer (9/286) 53 13
 Car Evaluation (6/1728) 64 30
 Phân tích rõ hơn về tốc độ thực hiện của thuật tốn IRDT nhanh hơn thuật tốn
 57
ID3 một số điểm như sau:
 Lấy ví dụ với bảng quyết định nhất quán 2.2, IRDT sử dụng các phân hoạch tương
đương của các thuộc tính đếm số phần tử mà phân hoạch của một thuộc tính bất kỳ A
nằm trong phân hoạch của thuộc tính quyết đinh d.
 Phân hoạch tương đương của thuộc tính quyết định d: t1; 2; 6; 8; 14u cĩ 5 phần tử
No và t3; 4; 5; 7; 9; 10; 11; 12; 13u cĩ 9 phần tử Yes.
 Phân hoạch tương đương của thuộc tính Outlook: t1; 2; 8; 9; 11u cĩ 5 phần tử
Sunny, t3; 7; 12; 13u cĩ 4 phần tử Overcast và t4; 5; 6; 10; 14u cĩ 5 phần tử Rain
 Phân hoạch tương đương của thuộc tính Temperature: t1; 2; 3; 13u cĩ 4 phần tử
High, t4; 7; 9; 10; 11; 12; 14u cĩ 7 phần tử Middle và t5; 6; 8u cĩ 3 phần tử Low.
 Phân hoạch tương đương của thuộc tính Hummidity: t1; 2; 3; 4; 8; 12; 14u cĩ 7
phần tử High và t5; 6; 7; 9; 10; 11; 13u cĩ 7 phần tử Middle.
 Phân hoạch tương đương của thuộc tính Windy: t1; 3; 4; 5; 8; 9; 10; 13u cĩ 8 phần
tử Weak và t2; 6; 7; 11; 12; 14u cĩ 6 phần tử Strong.
 So sánh giữa hai thuật tốn IRDT và ID3: IRDT chỉ đếm phần số phần tử max
trong phân hoạch của thuộc tính để chọn thuộc tính tốt nhất trong khi ID3 sử dụng
phép tính logarit để xác định thuộc tính tốt nhất.
 • IRDT chọn thuộc tính Outlook làm thuộc tính gốc của cây quyết định vì trong
 phân hoạch của Outlook cĩ t3; 7; 12; 13u là tập con của t3; 4; 5; 7; 9; 10; 11; 12; 13u
 trong phân hoạch của d. Các thuộc tính khác như Temperature, Humidity, Windy
 khơng cĩ tập nào trong phân hoạch là tập con của một tập trong phân hoạch của
 d.
 58
 • ID3 sẽ tính hàm độ đo thơng tin (Information Gain) cho các thuộc tính bằng
 cơng thức logarit cho các thuộc tính Outlook, Temperature, Humidity, Windy.
 Ví dụ về tính hàm độ đo thơng tin (Information Gain) cho thuộc tính Outlook
 như sau:
 5 5 9 9
 Hpdq “ ´ log ´ log
 14 14 14 14
 5 4 5
 InfoGainpOutlookq “ Hpdq ´ O ´ O ´ O
 14 S 14 O 15 R
 3 3 2 2
 O “ ´ log ´ log
 S 5 5 5 5
 4 4 0 0
 O “ ´ log ´ log
 O 4 4 4 4
 3 3 2 2
 O “ ´ log ´ log
 R 5 5 5 5
 InfoGainpOutlookq “ 0:247
 InfoGainpT emperatureq “ 0:029
 InfoGainpHummidityq “ 0:152
 InfoGainpW indyq “ 0:048
 Các bước tiếp theo sẽ giống như bước đầu tiên sử dụng phép đếm đối với thuật
tốn IRDT và sử dụng phép tính số thực với ID3 cho tập đối tượng đã bị rút nhỏ lại
sau bước tính tốn trước đĩ.
 Từ kết quả trên cĩ thể thấy rõ rằng nếu thực hiện hai thuật tốn IRDT và ID3 trên
máy tính thì phép đếm số nguyên luơn thực hiện với tốc độ nhanh hơn so với tính tốn
số thực của thuật tốn ID3.
 59
 Bộ dữ liệu trong thực nghiệm được lấy từ kho dữ liệu UCI như Breast Cancer (các
bệnh nhân ung thư vú cĩ 286 đối tượng và 9 thuộc tính được phân thành 2 lớp với
một lớp cĩ 201 đối tượng và lớp cịn lại cĩ 85 đối tượng phân loại tái phát hay khơng
tái phát), Balance (tập dữ liệu sinh ra mơ hình kết quả thí nghiệm tâm lý cĩ 625 đối
tượng và 4 thuộc tính gồm: trọng lượng bên trái, khoảng cách bên trái, trọng lượng
bên phải, khoảng cách bên phải phân loại trái, phải hay cân bằng), Car Evaluation
(mơ hình đánh giá xe ơ tơ theo cấu trúc khái niệm cĩ 1728 đối tượng và 6 thuộc tính
hỗ trợ ra quyết định chấp nhận, khơng chấp nhận, tốt, rất tốt) và Examples (tập dữ liệu
mẫu về ra quyết định đi chơi golf hay khơng với 14 đối tượng và 6 thuộc tính). Các
tập dữ liệu được lấy ngẫu nhiên phù hợp với khai phá dữ liệu trên bảng quyết định đầy
đủ và nhất quán.
2.8 Kết luận chương
 Rút gọn thuộc tính là một mục tiêu quan trọng hàng đầu trong khai phá dữ liệu
bảng quyết định. Trong bối cảnh dữ liệu ngày càng tăng lên về số lượng đối tượng,
vấn đề rút gọn thuộc tính bị ảnh hưởng kéo theo tốc độ xử lý khơng đáp ứng được nhu
cầu thực tiễn. Vấn đề tìm tất cả các rút gọn thuộc tính cĩ độ phức tạp thời gian hàm
mũ là khơng khả thi, các cơng trình cơng bố sử dụng nhiều phương pháp để tìm một
rút gọn thuộc tính theo heuristic. Dù sử dụng phương pháp heuristic để tìm được một
rút gọn thuộc tính thì bản chất độ phức tạp tính tốn vẫn phải duyệt tồn bộ đối tượng
trong bảng quyết định. Trong chương này, nghiên cứu sinh đề xuất phương pháp tìm
một rút gọn đối tượng trong thời gian đa thức mà kết quả là thu được bảng quyết định
với số đối tượng ít hơn nhiều lần so với bảng quyết định nhất quán gốc và vẫn đảm
bảo quá trình tìm các rút gọn thuộc tính khơng bị ảnh hưởng. Thêm vào đĩ, nghiên
cứu sinh cũng đề xuất một phương pháp tìm một rút gọn thuộc tính khơng heuristic
và một phương pháp cải tiến sinh cây quyết định từ bảng quyết định nhất quán với tốc
độ thực hiện nhanh hơn thuật tốn sinh cây quyết định ID3. Các đề xuất của nghiên
 60
cứu sinh được thực hiện trong thời gian đa thức, được chứng minh tính đúng đắn và
đầy đủ theo lý thuyết cùng thực nghiệm.
 61
 CHƯƠNG 3
 KHAI PHÁ DỮ LIỆU ĐỒ THỊ
 Trong chương này, nghiên cứu sinh trình bày về thuật tốn đề xuất là kết quả mới
của luận án về khai phá đồ thị con thường xuyên đĩng trong đĩ chứng minh vấn đề
đẳng cấu đồ thị con được giải quyết trong thời gian đa thức. Thêm nữa, nghiên cứu
sinh cũng trình bày kết quả mới của luận án về độ đo tương tự trên dàn giao khái niệm
sử dụng trong vấn đề phân loại đa nhãn cho đồ thị.
 Nội dung chương này dựa trên các cơng trình số [1], [3], [5], [7] trong danh mục
cơng trình cơng bố của nghiên cứu sinh.
3.1 Đặt vấn đề
 Dữ liệu đồ thị là cấu trúc dữ liệu phức tạp hơn nhiều lần dữ liệu dạng bảng. Do đĩ,
các cơng trình khai phá dữ liệu trên đồ thị gặp nhiều khĩ khăn với độ phức tạp thời
gian khơng đa thức. Nhiều vấn đề cĩ thể được giải quyết trong bảng với thuật tốn độ
phức tạp thời gian đa thức nhưng khi chuyển sang dạng dữ liệu đồ thị thì chỉ cĩ thể
giải quyết bằng các thuật tốn độ phức tạp thời gian khơng đa thức. Bằng một số các
phép biến đổi, các thuật tốn khai phá dữ liệu đồ thị cĩ thể tối ưu để giảm thời gian
tính tốn trong quá trình khai phá dữ liệu. Các phép biến đổi này đơi khi sẽ áp dụng
một số điều kiện ràng buộc đặc trưng cho tập dữ liệu cụ thể và mục tiêu khai phá dữ
liệu để đạt được tối ưu về mặt giảm thời gian tính nhưng cĩ thể sẽ phải trả giá bằng
tăng khơng gian tính tốn. Chương này đặt trọng tâm vào tối ưu thời gian tính tốn
cho một số bài tốn khai phá dữ liệu đồ thị cụ thể như khai phá đồ thị con thường
xuyên và phân loại đa nhãn cho đồ thị.
 Thứ nhất, khai phá mẫu thường xuyên là đi tìm tất cả các mẫu là một biểu diễn
 62
cấu trúc con của một biểu diễn cấu trúc cha (chẳng hạn như biểu diễn cấu trúc tập hợp
trong khai phá tập mục thường xuyên [3], biểu diễn cấu trúc cây trong khai phá cây
con thường xuyên, biểu diễn đồ thị trong khai phá đồ thị con thường xuyên [44], [46],
[52], [88], [89] thỏa mãn tần suất xuất hiện của mẫu con này lớn hơn một ngưỡng
mà người dùng tự định nghĩa [37]. Tìm các cấu trúc con thường xuyên đĩng vai trị
quan trọng trong khai phá dữ liệu kết hợp, tương quan và nhiều quan hệ khác của dữ
liệu. Hơn nữa, các mẫu thường xuyên trợ giúp trong việc đánh chỉ mục dữ liệu, phân
lớp, phân cụm, và các nhiệm vụ khai phá dữ liệu khác. Như vậy, khai phá mẫu thường
xuyên trở thành nhiệm vụ khai phá dữ liệu quan trọng và trọng tâm trong lĩnh vực khai
phá dữ liệu. Khai phá mẫu thường xuyên dựa trên một tính chất “Downward Closure
Property” hay cịn được gọi là tính chất phản đơn điệu. Tính chất này thể hiện rằng
nếu mẫu cha thỏa mãn tính chất thường xuyên thì tất cả các mẫu con của nĩ cũng
thỏa mãn tính chất thường xuyên và nếu mẫu con là khơng thỏa mãn tính chất thường
xuyên thì mọi mẫu cha của nĩ cũng khơng thỏa mãn tính chất thường xuyên. Khai phá
mẫu thường xuyên hiện nay cĩ hai hướng tiếp cận là tuân theo nguyên lý Apriori [46]
hoặc theo nguyên lý FP-Growth [88]. Dù cĩ tuân theo nguyên lý nào thì khai phá mẫu
thường xuyên cũng cĩ độ phức tạp tính tốn thời gian thuộc lớp khơng đa thức NP.
 Sự giống nhau giữa khai phá mẫu tập mục thường xuyên và khai phá mẫu đồ thị
con thường xuyên ở vấn đề sinh và kiểm tra một ứng viên là tập mục con hay đồ thị
con cĩ thỏa mãn tính chất thường xuyên hay khơng. Sự khác nhau chính là ở khai phá
mẫu tập mục thường xuyên thì mỗi tập mục ứng viên được sinh ra chỉ cĩ duy nhất
một mình nĩ vấn đề kiểm tra nĩ cĩ nằm trong một tập mục giao tác hay khơng chỉ
thực hiện trong thời gian đa thức, nhưng trong khai phá mẫu đồ thị con thường xuyên
thì vấn đề sinh một đồ thị con ứng viên lại khơng phải là duy nhất và vấn đề kiểm tra
một đồ thị con ứng viên cĩ nằm trong một đồ thị giao tác hay khơng chính là vấn đề
đẳng cấu đồ thị con và vấn đề này được các nhà khoa học xác định là phải tính tốn
trong thời gian cĩ độ phức tạp thuộc lớp khơng đa thức đầy đủ NP-complete [31]. Để
 63
giải quyết tối ưu thời gian tính vấn đề đẳng cấu đồ thị con, nghiên cứu sinh thực hiện
một số điều kiện ràng buộc về thứ tự nhãn của đỉnh và cạnh cùng với biểu diễn chuẩn
hĩa cùng kỹ thuật máy ngẫu nhiên để đạt thời gian tính tốn tối ưu nhất.
 Thứ hai, học máy là lĩnh vực rất quan trọng trong khai phá dữ liệu. Các dữ liệu
ngày càng đa dạng về mặt cấu trúc, các phương pháp khai phá dữ liệu trên bảng gặp
nhiều khĩ khăn như dữ liệu cấu trúc tế bào, cấu trúc mạng nơron, cấu trúc protein,
cấu trúc dữ liệu mạng máy tính, mạng xã hội. Để giải quyết các vấn đề này các nhà
khoa học đã áp dụng biểu diễn dữ liệu cấu trúc đồ thị, cây, dàn giao và áp dụng các
phương pháp khai phá dữ liệu hiện cĩ với các loại biểu diễn dữ liệu khác lên các biểu
diễn dữ liệu đồ thị. Học máy áp dụng trên đồ thị là một hướng đi đúng đắn cho xu thế
dữ liệu đa dạng và phức tạp ngày nay.
 Do tính chất đa dạng của dữ liệu và đa dạng các mục tiêu, các phương pháp phân
lớp dữ liệu trong học máy dần chuyển từ phân loại đa lớp đơn nhãn sang phân loại
đa lớp đa nhãn. Nhiều cơng trình cơng bố về phân loại đa nhãn trên biểu diễn dữ liệu
dạng bảng, trong đĩ nhiều mơ hình tính tốn phân loại đa nhãn hiệu quả dựa trên
lý thuyết Dempster Shafer. Mơ hình phân loại đa nhãn dựa trên lý thuyết Dempster
Shafer tăng độ chính xác phân loại, giảm thời gian thực hiện và ngày càng nhiều cơng
trình cơng bố. Tuy nhiên để áp dụng phân loại đa nhãn cho đồ thị là khá khĩ khăn vì
bản chất biểu diễn dữ liệu đồ thị khĩ cĩ thể chuyển đổi về biểu diễn véctơ để áp dụng
các thuật tốn phân loại đa nhãn. Các cơng nghệ thu thập dữ liệu ngày càng được cải
tiến, nhiều lĩnh vực ứng dụng phải đối mới với dữ liệu đa dạng và đa cấu trúc như
cấu trúc hĩa học, cấu trúc luồng chương trình, tài liệu XML, web. Khác với dữ liệu
truyền thống trong khơng gian đặc trưng, các dữ liệu này khơng thể biểu diễn dưới
dạng véctơ mà chỉ cĩ thể biểu diễn dưới dạng đồ thị dẫn đến một thách thức cơ bản
của khai phá dữ liệu đồ thị là thiếu biểu diễn véctơ dẫn đến khĩ xác định được độ
đo tương tự của đồ thị để áp dụng các mơ hình phân loại đa nhãn dựa trên lý thuyết
Dempster Shafer. Nghiên cứu sinh đề xuất một độ đo tương tự cho các dồ thị dựa trên
 64
dàn giao khái niệm từ tập đồ thị con thường xuyên đĩng và áp dụng độ đo tương tự
này trên các mơ hình phân loại đa nhãn đồ thị dựa trên lý thuyết Dempster Shafer.
Nghiên cứu sinh cũng chứng minh lý thuyết độ đo tương tự trên dàn giao khái niệm
là đúng đắn và đầy đủ.
3.2 Khai phá đồ thị con thường xuyên đĩng
 Khai phá đồ thị là một vùng chính được quan tâm trong lĩnh vực khai phá dữ liệu
những năm gần đây. Một lớp con quan trọng của khai phá dữ liệu đồ thị là khai phá
đồ thị con thường xuyên. Vấn đề trọng tâm của khai phá đồ thị con thường xuyên là
khái niệm đẳng cấu đồ thị con. Nghiên cứu đẳng cấu đồ thị con trước đây chủ yếu là
vấn đề về độ phức tạp tính tốn. Thơng thường, vấn đề đẳng cấu đồ thị con là vấn đề
NP-complete [31]. Các cơng trình nghiên cứu trước đây về khai phá đồ thị con thường
xuyên chưa giải quyết được vấn đề NP-complete trong đẳng cấu đồ thị con. Do đĩ,
trong luận án này nghiên cứu sinh đề xuất thuật tốn mới giải quyết vấn đề đẳng cấu
đồ thị con trong thời gian đa thức trong khai phá dữ liệu đồ thị. Hơn nữa thuật tốn
mới cũng được chứng minh về mặt lý thuyết tính hiệu quả hơn các cơng trình trước đĩ
trong khai phá đồ thị con thường xuyên đĩng.
 Thơng thường, khai phá đồ thị con thường xuyên đặt mục tiêu vào xác định tất
cả các mẫu đồ thị con mà cĩ tần suất xuất hiện bên trong một tập dữ liệu đồ thị trên
một ngưỡng người dùng định nghĩa. Những mẫu đồ thị con này được gọi là đồ thị con
thường xuyên. Theo lý thuyết, khai phá đồ thị con thường xuyên cĩ thể được cơng thức
hĩa như tìm kiếm trong khơng gian tìm kiếm, được mơ hình như một dàn giao, gồm
tất cả các mẫu đồ thị con cĩ khả năng. Bởi vì số lượng các đồ thị con thường xuyên
cĩ thể tăng theo cấp số mũ với kích thước của đồ thị, duyệt đầy đủ khơng gian tìm
kiếm là khơng thể tính tốn được bởi nguyên do “bùng nổ tổ hợp”. Một ngưỡng độ hỗ
trợ người dùng tự định nghĩa thường được dùng để tỉa khơng gian tổ hợp để phân tách
 65
các đồ thị con khơng thường xuyên và các đồ thị con thường xuyên. Khai phá đồ thị
con thường xuyên đã nhận được nhiều sự quan tâm đáng kể [44],[46], [52],[88], [89].
Các kỹ thuật khai phá đồ thị con thường xuyên được phân vào hai hướng tiếp cận: (i)
tiếp cận dựa trên Apriori (cũng được gọi là tiếp cận dựa trên chiến lược tìm kiếm theo
bề rộng) [46] và (ii) tiếp cận dựa trên phát triển mẫu (cũng được gọi là tiếp cận dựa
trên chiến lược tìm kiếm theo độ sâu) [88]. Cả hai hướng tiếp cận đều cĩ những ưu
điểm và khuyết điểm tuy nhiên chúng đều bao gồm sinh tập ứng viên và kiểm tra đẳng
cấu đồ thị con để quyết định đồ thị con cĩ phải là thường xuyên hay khơng. Trong lý
thuyết khoa học máy tính, vấn đề đẳng cấu đồ thị con là tác vụ tính tốn trong đĩ cho
hai đồ thị con G và H, cần phải xác định G cĩ chứa một đồ thị con mà đẳng cấu với
H hay khơng. Một số trường hợp của đẳng cấu đồ thị cĩ thể giải quyết trong thời gian
đa thức [29], [40] cho các đồ thị phẳng.
 Một số lượng lớn các cơng trình đã được cơng bố về đẳng cấu đồ thị con trong vấn
đề khai phá đồ thị con thường xuyên [29], [40], [44], [58], [84]. Cĩ một số cơng trình
nghiên cứu chỉ ra đẳng cấu đồ thị con thường xuyên trong thời gian đa thức cho đồ
thị phẳng [29], [40] nhưng hầu hết các đồ thị trong khai phá mẫu đồ thị con thường
xuyên là khơng phẳng. Những nghiên cứu này gĩp phần giảm độ phức tạp đẳng cấu
đồ thị con. Việc dùng ma trận kề mặc dù đơn giản khơng vay mượn cấu trúc tự nĩ đã
cĩ phát hiện đẳng cấu vì các đỉnh (và cạnh) cĩ thể được liệt kê theo nhiều cách khác
nhau [86]. Đối với quá trình kiểm tra đẳng cấu tuân theo chiến lược gắn mã nhất quán
đảm bảo hai đồ thị bất kỳ được gán nhãn theo cùng một cách trong trật tự của đỉnh và
cạnh (chiến lược gắn nhãn chuẩn). Một chiến lược gắn nhãn chuẩn xác định duy nhất
một mã cho một đồ thị cho trước [72]. Gắn nhãn chuẩn tạo điều kiện kiểm tra đẳng
cấu vì nĩ đảm bảo nếu một cặp đồ thị là đồng dạng thì mã chuẩn của chúng là giống
nhau hồn tồn [52]. Một cách đơn giản để sinh ra mã chuẩn là làm phẳng các ma
trận kề bằng cách nối các cột hoặc hàng để xuất ra một mã bao gồm các số theo thứ
tự quy định. Để giảm kết quả tính tốn hốn vị c