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

BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
HOÀNG MINH QUANG 
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 
LUẬN ÁN TIẾN SĨ KỸ THUẬT 
Hà Nội – Năm 2020 
BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
HOÀNG MINH QUANG 
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 
 Chuyên ngành : Hệ thống thông tin 
 Mã số: 09.48.01.04 
LUẬN ÁN TIẾN SĨ KỸ THUẬT 
 NGƯỜI HƯỚNG DẪN KHOA HỌC: 
1. GS. TS. VŨ ĐỨC THI 
2. GS. TSKH. NGUYỄN NGỌC SAN 
Hà Nội - Năm 2020 
iLỜI CẢM ƠN
Đầu tiên, nghiên cứu sinh xin được gửi lời cảm ơn sâu sắc tới hai người thầy hướng
dẫn; GS. TS. Vũ Đức Thi và GS. TSKH. Nguyễn Ngọc San đã định hướng nghiên cứu
và chỉ dẫn các giải pháp khoa học trong cả quá trình nghiên cứu sinh thực hiện luận
án.
Nghiên cứu sinh xin gửi lời cảm ơn tới lãnh đạo và tập thể cán bộ Viện Công nghệ
thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt nam cùng phòng Khoa học
dữ liệu và Ứng dụng nơi nghiên cứu sinh đang công tác. Nghiên cứu sinh cũng chân
thành gửi lời cảm ơn tới TS. Nguyễn Việt Anh đã đọc và góp ý vào phiên bản dự thảo
của luận án.
Nghiên cứu sinh xin cảm ơn lãnh đạo, các nhà khoa học Học viện Công nghệ Bưu
chính viễn thông đã tạo điều kiện, trợ giúp nghiên cứu sinh trong quá trình thực hiện
luận án. Nghiên cứu sinh cũng xin cảm ơn các bạn bè, đồng nghiệp, các nhà khoa học
đã có những đóng góp quý báu cho luận án.
Nghiên cứu sinh xin cảm ơn Cha, Mẹ đã động viên khuyến khích nghiên cứu sinh
trong quá trình nghiên cứu học tập. Cảm ơn vợ Bùi Thị Thuý Hà và hai con Hoàng
Hải Lâm và Hoàng Minh Thư, những hy sinh trong quá trình nghiên cứu sinh thực
hiện luận án đã tạo động lực để nghiên cứu sinh cố gắng phấn đấu đến ngày hôm nay.
ii
LỜI CAM ĐOAN
Nghiên cứu sinh xin cam đoan những công trình công bố trong luận án này là kết
quả của nghiên cứu sinh nghiên cứu dưới sự hướng dẫn khoa học của GS. TS. Vũ Đức
Thi và GS. TSKH. Nguyễn Ngọc San. Những kết quả được nghiên cứu sinh trình bày
trong luận án này là mới, duy nhất và chưa từng được công bố trong bất kỳ công trình
nào khác.
Nghiên cứu sinh xin hoàn toàn chịu trách nhiệm trước lời cam đoan của mình.
Hà Nội, ngày 31 tháng 12 năm 2019.
Nghiên cứu sinh
Hoàng Minh Quang
iii
MỤC LỤC
LỜI CẢM ƠN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
LỜI CAM ĐOAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
DANH MỤC HÌNH VẼ . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
DANH MỤC BẢNG BIỂU . . . . . . . . . . . . . . . . . . . . . . . . . . vi
DANH MỤC THUẬT NGỮ . . . . . . . . . . . . . . . . . . . . . . . . . . vii
LỜI MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 KIẾN THỨC CHUẨN BỊ 8
1.1 Lý thuyết cơ sở dữ liệu quan hệ . . . . . . . . . . . . . . . . . . . . . 8
1.2 Lý thuyết tập thô . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Tập có thứ tự và dàn giao (lattices) . . . . . . . . . . . . . . . . . . . 17
1.5 Phân tích khái niệm chính thức (FCA) . . . . . . . . . . . . . . . . . 18
1.6 Biến đổi và đồng biến đổi Mobius . . . . . . . . . . . . . . . . . . . 19
1.7 Lý thuyết Dempster-Shafer . . . . . . . . . . . . . . . . . . . . . . . 20
2 KHAI PHÁ DỮ LIỆU DẠNG BẢNG 23
2.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Loại bỏ thuộc tính dư thừa . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Rút gọn thuộc tính không heuristic . . . . . . . . . . . . . . . . . . . 30
2.4 Rút gọn đối tượng bảng quyết định nhất quán . . . . . . . . . . . . . 35
2.5 Xây dựng cây quyết định từ bảng rút gọn . . . . . . . . . . . . . . . . 40
2.6 Ví dụ thu gọn bảng và cây quyết định . . . . . . . . . . . . . . . . . . 44
2.7 Đánh giá thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.8 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
iv
3 KHAI PHÁ DỮ LIỆU ĐỒ THỊ 61
3.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Khai phá đồ thị con thường xuyên đóng . . . . . . . . . . . . . . . . 64
3.2.1 Ý tưởng đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2.2 Nhãn chuẩn hóa . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.2.3 Sinh tập ứng viên . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2.4 Kiểm tra đồ thị con đẳng cấu . . . . . . . . . . . . . . . . . . 75
3.2.5 Thuật toán PSI-CFSM . . . . . . . . . . . . . . . . . . . . . 85
3.3 Phân loại đa nhãn cho đồ thị . . . . . . . . . . . . . . . . . . . . . . 88
3.3.1 Ý tưởng đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.3.2 Xây dựng dàn giao khái niệm . . . . . . . . . . . . . . . . . 92
3.3.3 Thuật toán phân loại đa nhãn đồ thị . . . . . . . . . . . . . . 95
3.4 Ví dụ PSI-CFSM và phân loại đa nhãn . . . . . . . . . . . . . . . . . 98
3.5 Đánh giá thử nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.6 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
KẾT LUẬN, KIẾN NGHỊ . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
DANH MỤC CÔNG TRÌNH CÔNG BỐ . . . . . . . . . . . . . . . . . . . 110
TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
vDANHMỤC HÌNH VẼ
2.1 Cây quyết định được sinh ra từ thuật toán DecisionTree(DS) . . . . . . 55
3.1 Một cơ sở dữ liệu đồ thị giao tác GD . . . . . . . . . . . . . . . . . . 70
3.2 Cây đồ thị con thường xuyên: DFS Code Tree . . . . . . . . . . . . . 78
3.3 Cây đồ thị con thường xuyên: CAM Tree . . . . . . . . . . . . . . . . 79
3.4 Dàn giao khái niệm CL của các đồ thị gi P GD . . . . . . . . . . . . 101
3.5 Sinh ứng viên và tỉa đồ thị con 2-subgraph theo PSI-CFSM . . . . . . 104
3.6 Sinh ứng viên và tỉa đồ thị con 3-subgraph theo PSI-CFSM . . . . . . 104
3.7 Tỉa các đồ thị con ứng viên: không thường xuyên, không thoả mãn
DFSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
vi
DANHMỤC BẢNG BIỂU
2.1 Bảng quyết định nhất quán gốc . . . . . . . . . . . . . . . . . . . . . 45
2.2 Bảng quyết định không dư thừa thuộc tính từ bảng gốc 2.1 . . . . . . 46
2.3 Một rút gọn đối tượng của bảng quyết định nhất quán 2.2 . . . . . . . 51
2.4 Một rút gọn thuộc tính miền dương của bảng 2.2 . . . . . . . . . . . . 53
2.5 Kết hợp rút gọn đối tượng và thuộc tính của bảng 2.2 . . . . . . . . . 54
2.6 Bảng thực hiện một rút gọn thuộc tính . . . . . . . . . . . . . . . . . 56
2.7 Bảng thực hiện rút gọn đối tượng . . . . . . . . . . . . . . . . . . . . 56
2.8 Bảng so sánh tốc độ thực hiện IDRT và ID3 (millisecond) . . . . . . . 56
3.1 Quan hệ giữa đồ thị và tập tất cả đồ thị con thường xuyên đóng . . . . 99
3.2 Luật Dempster kết hợp các hàm cấp phát khối . . . . . . . . . . . . . 102
3.3 Khai phá đồ thị con thường xuyên (đơn vị thời gian: giây) . . . . . . . 106
vii
DANHMỤC THUẬT NGỮ
Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt
antikey phản khóa
antisymmetry phản đối xứng
attribute thuộc tính
attribute reduct rút gọn thuộc tính
belief function hàm niềm tin
β lower distribution reduct rút gọn phân phối cận dưới β
β upper distribution reduct rút gọn phân phối cận trên β
binary relation quan hệ hai ngôi
boudary vùng biên
capacity sức chứa
closed frequent subgraph đồ thị con thường xuyên đóng
closed set tập đóng
closure đóng
closure system hệ đóng
commonality function hàm tính chất chung
complete lattice dàn giao khái niệm
concept lattice dàn giao khái niệm
conjugate liên hợp
consistent nhất quán
co-Mo¨bius transform đồng biến đổi Mo¨bius
data mining khai phá dữ liệu
decision table bảng quyết định
Dempster’s rule of combination luật kết hợp Dempster
domain value miền giá trị
discernibility matrix ma trận phân biệt
viii
equality set tập bằng nhau
equivalent class lớp tương đương
extent phạm vi
plausibility function hàm sự thật
frame of discernment khung phân biệt
frequent subgraph đồ thị con thường xuyên
focal element phần tử tiêu điểm
formal concept khái niệm chính thức
formal concept analysis (FCA) phân tích khái niệm chính thức
formal context ngữ cảnh chính thức
full family họ đầy đủ
f-family họ f
functional dependency phụ thuộc hàm
Galois connection kết nối Galois
graph đồ thị
graph datatabase cơ sở dữ liệu đồ thị
graph edit distance khoảng cách sửa đổi đồ thị
greatest lower bound lớn nhất cận dưới
indiscernibility relation quan hệ bất khả phân biệt
information function hàm thông tin
information system hệ thông tin
intent ý định
interval khoảng
isomorphism đẳng cấu
isomorphism subgraph đẳng cấu đồ thị con
key khóa
ix
k-subgraph k-đồ thị con
labeled graph đồ thị được gắn nhãn
lattice dàn giao
least upper bound nhỏ nhất cận trên
lexicographic order thứ tự quy định
locally finite hữu hạn cục bộ
lower approximation xấp xỉ dưới
mass allocation function hàm cấp phát khối
maximal commonality subgraph đồ thị con chung lớn nhất
maxmimal equality system hệ bằng nhau cực đại
minimal key khóa tối tiểu
monotonicity đơn điệu
Mo¨bius transform biến đổi Mo¨bius
multi-label classification phân loại đa nhãn
object đối tượng
ordered set tập có thứ tự
partial order thứ tự bộ phận
partially ordered set tập thứ tự bộ phận
partition phân hoạch
positive region miền dương
powerset tập tất cả các tập
reduct rút gọn
relfexivity phản xạ
relation quan hệ
relational database cơ sở dữ liệu quan hệ
relational scheme lược đồ quan hệ
xrough set tập thô
set system hệ thống tập hợp
shortest path kernels các nhân đường đi ngắn nhất
Sperner system hệ Sperner
subconcept-superconcept relation quan hệ khái niệm con - khái niệm cha
subgraph đồ thị con
subset tập con
supergraph đồ thị cha
theory lý thuyết
transitivity bắc cầu
universal set tập vũ trụ
upper approximation xấp xỉ trên
variable precision rough set tập thô chính xác biến
1LỜI MỞ ĐẦU
1. TỔNG QUAN LUẬN ÁN VÀ LÝ DO CHỌN ĐỀ TÀI
Khai phá dữ liệu lớn [57] là một xu hướng phát triển công nghệ mang tính cách
mạng, ngày càng được ứng dụng rộng rãi, và đặc biệt còn nhiều tiềm năng phát triển
trên toàn thế giới. Trong báo cáo [13], dữ liệu lớn được được định nghĩa là "các công
nghệ dữ liệu lớn mô tả một thế hệ công nghệ và kiến trúc mới được thiết kế để trích
xuất các giá trị từ các khối lượng dữ liệu rất lớn và đa dạng bằng cách phân tích, khám
phá ở tốc độ cao"[101]. Khai phá dữ liệu lớn có thể được ứng dụng để cải tiến công
nghệ ở nhiều lĩnh vực quan trọng như: y tế, giao thông, tài chính, giáo dục, [28], [63]
nhằm đem lại lợi ích trong việc hỗ trợ ra quyết định, cắt giảm chi phí, và tạo ra các
sản phẩm, dịch vụ mới.
Mặc dù việc khai phá dữ liệu lớn đem lại giá trị to lớn và ý nghĩa, tuy nhiên, đây
cũng là một lĩnh vực đòi hỏi công nghệ cao, đầu tư lớn, với nhiều thách thức. Nguyên
nhân xuất phát từ hai đặc trưng cơ bản của dữ liệu lớn, đó là: tính lớn và tính đa dạng,
phức tạp. Do độ lớn của dữ liệu, việc khai phá thường mất nhiều thời gian và chi phí,
độ phức tạp tính toán của khai phá dữ liệu lớn thường là độ phức tạp hàm mũ. Hơn
nữa, vì dữ liệu lớn và phức tạp, nên việc khai phá dữ liệu cần trích xuất được các
thông tin cốt lõi để khai phá, thay vì xử lý cả tập hợp dữ liệu lớn, có nhiều dữ liệu dư
thừa, không mang giá trị hữu ích. Do vậy, vấn đề cơ bản của xử lý dữ liệu lớn là cải
tiến tốc độ xử lý dữ liệu và tăng giá trị của dữ liệu được khai phá.
Dữ liệu lớn, trước hết là độ lớn của dữ liệu được thu thập, tập hợp và lưu trữ trên
một cụm hệ thống máy tính phân tán, không thể lưu trữ trên các máy tính độc lập, khó
có thể khai phá được các giá trị tiềm ẩn. Với dữ liệu lớn, thời gian truy xuất thông tin
trong cả hai việc đọc và viết đều gặp khó khăn với một độ trễ cao. Nếu không tối ưu
thời gian truy xuất, giảm tập hợp dữ liệu thành một tập con thì khó xử lý do khai phá
2dữ liệu yêu cầu phải đáp ứng trong thời gian nhất định không thể kéo dài hơn. Chẳng
hạn không thể khai phá dữ liệu phòng chống xâm nhập máy tính trái phép trong khi
việc truy xuất dữ liệu đã mất hàng tiếng đồng hồ chưa kể thời gian khai phá dữ liệu.
Lúc đó kết quả khai phá dữ liệu sẽ không có ý nghĩa vì tội phạm đã vượt qua hệ thống
an ninh và kịp gây ra tất cả tác động xấu.
Liên quan đến tính đa dạng của dữ liệu. Dữ liệu được thu thập từ nhiều nguồn nên
kiểu biểu diễn của dữ liệu khác nhau. Dữ liệu lớn được thu thập từ nhiều nguồn dữ
liệu khác nhau như các hệ thống quản trị dữ liệu, mạng internet, mạng xã hội, kênh
thông tin giải trí, truyền hình kỹ thuật số, các thiết bị truyền thông đa phương tiện,
các thiết bị di dộng, các thiết bị vạn vật kết nối v.v. đã tạo ra tập hợp dữ liệu đa dạng
kiểu mà các thuật toán khai phá dữ liệu chưa thể áp dụng được. Mỗi thuật toán khai
phá dữ liệu chỉ có thể khai phá dữ liệu trên một tập hợp dữ liệu thống nhất về kiểu
dạng biểu diễn. Do vậy, trước khi khai phá dữ liệu thì tập hợp dữ liệu phải được đưa
về chung kiểu biểu diễn. Sau đó các kiểu biểu diễn phải được biến đổi về một dạng
cấu trúc dữ liệu chung đồng nhất. Theo một số công trình nghiên cứu, dữ liệu có thể
được phân chia vào ba kiểu dữ liệu là dữ liệu có cấu trúc, dữ liệu bán cấu trúc và dữ
liệu phi cấu trúc dựa trên biểu diễn từ việc thu thập từ các nguồn dữ liệu. Dữ liệu có
cấu trúc được hình dung như một lược đồ có sẵn cho một tập hợp dữ liệu. Dữ liệu bán
cấu trúc có một phần lược đồ định trước và một phần không có lược đồ định trước.
Dữ liệu phi cấu trúc là dữ liệu không có lược đồ định kiểu dữ liệu trước. Có thể lấy ví
dụ dữ liệu có cấu trúc là dữ liệu dạng bảng trong các hệ quản trị cơ sở dữ liệu quan
hệ, dữ liệu phi cấu trúc là dữ liệu không có bất kỳ lược đồ định nghĩa nào trước như
âm thanh, hình ảnh, video, văn bản tự do, email và dữ liệu bán cấu trúc là dữ liệu xml
có các đỉnh là lược đồ định trước còn thông tin mô tả là các dữ liệu không có lược đồ
định trước.
Các công trình khoa học đã chỉ ra rằng dù dữ liệu có lược đồ định trước như các
biểu diễn cấu trúc dữ liệu dạng bảng hay các dữ liệu không có lược đồ định trước như
3âm thanh, hình ảnh, video, văn bản,... thì tuỳ vào đặc trưng của dữ liệu và mục tiêu
cần khai phá, các tập hợp dữ liệu đều có khả năng sử dụng một kiểu biểu diễn dạng
đồ thị [35], [94], [95] để giải quyết vấn đề trong khai phá dữ liệu. Biểu diễn dữ liệu
đồ thị là biểu diễn phức tạp nhất về dữ liệu, có thể được coi là biểu diễn dữ liệu có
cấu trúc thông qua lược đồ định kiểu của đỉnh và cạnh trong đồ thị. Tương quan với
biểu diễn đồ thị phức tạp là thời gian khai khá rất chậm, chẳng hạn như trên các dữ
liệu biểu diễn dạng đồ thị như biểu diễn các cấu trúc hoá học, các cấu trúc sinh học,
các mạng máy tính và mạng xã hội. Các thuật toán khai phá trên dữ liệu đồ thị hầu
hết đều nằm trong vùng độ phức tạp thời gian không đa thức thậm chí có thể lên đến
độ phức tạp thời gian hàm mũ. Để khai phá được các tập dữ liệu có biểu diễn cấu trúc ...  In-
ternational Journal of Approximate Reasoning 48.2 (2008), pages 365–377.
[23] Thierry Denœux. “A k-nearest neighbor classification rule based on Dempster-
Shafer theory”. in: IEEE transactions on systems, man, and cybernetics 25.5
(1995), pages 804–813.
[24] Thierry Denœux and Marie-Hélène Masson. “Evidential reasoning in large
partially ordered sets”. in: Annals of Operations Research 195.1 (2012), pages 135–161.
[25] Thierry Denœux, Zoulficar Younes and Fahed Abdallah. “Representing un-
certainty on set-valued variables using belief functions”. in: Artificial Intelli-
gence 174.7 (2010), pages 479–499.
[26] Mukund Deshpande, Michihiro Kuramochi, Nikil Wale and George Karypis.
“Frequent substructure-based approaches for classifying chemical compounds”.
115
in: IEEE Transactions on Knowledge and Data Engineering 17.8 (2005),
pages 1036–1050.
[27] Chris HQ Ding, Xiaofeng He, Hongyuan Zha, Ming Gu and Horst D Simon.
“A min-max cut algorithm for graph partitioning and data clustering”. in:
Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference
on. IEEE. 2001, pages 107–114.
[28] Mohamed Elhoseny, Ahmed Abdelaziz, Ahmed S Salama, Alaa Mohamed
Riad, Khan Muhammad and Arun Kumar Sangaiah. “A hybrid model of in-
ternet of things and cloud computing to manage big data in health services ap-
plications”. in: Future generation computer systems 86 (2018), pages 1383–1394.
[29] David Eppstein. “Subgraph isomorphism in planar graphs and related prob-
lems”. in: SODA. volume 95. 1995, pages 632–640.
[30] Bernhard Ganter and Rudolf Wille. “Applied lattice theory: Formal concept
analysis”. in: In General Lattice Theory, G. Gra¨tzer editor, Birkha¨user. Cite-
seer. 1997.
[31] Michael R Garey and David S Johnson. “Computers and Intractability: An
Introduction to the Theory of NP-completeness”. in: San Francisco (1979).
[32] Vijay K Garg, Neeraj Mittal and Alper Sen. “Applications of lattice theory to
distributed computing”. in: ACM SIGACT Notes 34.3 (2003), pages 40–61.
[33] Xin Geng. “Label distribution learning”. in: IEEE Transactions on Knowledge
and Data Engineering 28.7 (2016), pages 1734–1748.
[34] Nadia Ghamrawi and Andrew McCallum. “Collective multi-label classifica-
tion”. in: Proceedings of the 14th ACM international conference on Informa-
tion and knowledge management. ACM. 2005, pages 195–200.
116
[35] Palash Goyal and Emilio Ferrara. “Graph embedding techniques, applica-
tions, and performance: A survey”. in: Knowledge-Based Systems 151 (2018),
pages 78–94.
[36] Michel Grabisch. “Belief functions on lattices”. in: International Journal of
Intelligent Systems 24.1 (2009), pages 76–95.
[37] Jiawei Han, Hong Cheng, Dong Xin and Xifeng Yan. “Frequent pattern min-
ing: current status and future directions”. in: Data Mining and Knowledge
Discovery 15.1 (2007), pages 55–86.
[38] Jiawei Han, Jian Pei andMicheline Kamber.Data mining: concepts and tech-
niques. Elsevier, 2011.
[39] Jiawei Han, Jian Pei, Yiwen Yin and Runying Mao. “Mining frequent pat-
terns without candidate generation: A frequent-pattern tree approach”. in:
Data mining and knowledge discovery 8.1 (2004), pages 53–87.
[40] John E Hopcroft and Robert Endre Tarjan. “Isomorphism of planar graphs”.
in: Complexity of computer computations. Springer, 1972, pages 131–152.
[41] Tamás Horváth, Jan Ramon and Stefan Wrobel. “Frequent subgraph min-
ing in outerplanar graphs”. in: Data Mining and Knowledge Discovery 21.3
(2010), pages 472–508.
[42] Qinghua Hu, Zongxia Xie and Daren Yu. “Hybrid attribute reduction based
on a novel fuzzy-roughmodel and information granulation”. in: Pattern recog-
nition 40.12 (2007), pages 3509–3521.
[43] J Huan, W Wang, A Washington, J Prins, R Shah and A Tropsha. “Accurate
classification of protein structural families using coherent subgraph analy-
sis”. in: Proceedings of the Ninth Pacific Symposium on Biocomputing (PSB).
2003, pages 411–422.
117
[44] Jun Huan, Wei Wang and Jan Prins. “Efficient mining of frequent subgraphs
in the presence of isomorphism”. in: Data Mining, 2003. ICDM 2003. Third
IEEE International Conference on. IEEE. 2003, pages 549–552.
[45] Jun Huan, Wei Wang, Jan Prins and Jiong Yang. “Spin: mining maximal fre-
quent subgraphs from graph databases”. in: Proceedings of the tenth ACM
SIGKDD international conference on Knowledge discovery and data mining.
ACM. 2004, pages 581–586.
[46] Akihiro Inokuchi, Takashi Washio and Hiroshi Motoda. “An apriori-based
algorithm for mining frequent substructures from graph data”. in: European
Conference on Principles of DataMining and Knowledge Discovery. Springer.
2000, pages 13–23.
[47] Akihiro Inokuchi, Takashi Washio, Kunio Nishimura and Hiroshi Motoda. A
fast algorithm for mining frequent connected subgraphs. techreport. Technical
Report RT0448, IBM Research, Tokyo Research Laboratory, 2002.
[48] Demetrovics Janos, Vu Duc Thi and Nguyen Long Giang. “On Finding All
Reducts of Consistent Decision Tables”. in:Cybernetics and Information Tech-
nologies 14.4 (2014), pages 3–10.
[49] Chuntao Jiang, Frans Coenen and Michele Zito. “A survey of frequent sub-
graph mining algorithms”. in: The Knowledge Engineering Review 28.01 (2013),
pages 75–105.
[50] Xiangnan Kong and S Yu Philip. “gMLC: a multi-label feature selection
framework for graph classification”. in: Knowledge and information systems
31.2 (2012), pages 281–305.
[51] Marzena Kryszkiewicz. “Rough set approach to incomplete information sys-
tems”. in: Information sciences 112.1-4 (1998), pages 39–49.
118
[52] Michihiro Kuramochi and George Karypis. “Frequent subgraph discovery”.
in: Data Mining, 2001. ICDM 2001, Proceedings IEEE International Confer-
ence on. IEEE. 2001, pages 313–320.
[53] Jure Leskovec, Jon Kleinberg and Christos Faloutsos. “Graph evolution: Den-
sification and shrinking diameters”. in: ACM Transactions on Knowledge Dis-
covery from Data (TKDD) 1.1 (2007), page 2.
[54] Guoliang Li, Beng Chin Ooi, Jianhua Feng, Jianyong Wang and Lizhu Zhou.
“EASE: an effective 3-in-1 keyword search method for unstructured, semi-
structured and structured data”. in: Proceedings of the 2008 ACM SIGMOD
international conference onManagement of data. ACM. 2008, pages 903–914.
[55] Xian-Tong LI, Jian-Zhong LI and Hong GAO. “An Efficient Frequent Sub-
graph Mining Algorithm”. in: Journal of Software 10 (2007), page 011.
[56] Min Liu, Mingwen Shao, Wenxiu Zhang and Cheng Wu. “Reduction method
for concept lattices based on rough set theory and its application”. in: Com-
puters & Mathematics with Applications 53.9 (2007), pages 1390–1410.
[57] James Manyika, Michael Chui, Brad Brown, Jacques Bughin, Richard Dobbs,
Charles Roxburgh and Angela H Byers. “Big data: The next frontier for inno-
vation, competition, and productivity”. in: (2011).
[58] Brendan D McKay andothers. Practical graph isomorphism. Department of
Computer Science, Vanderbilt University Tennessee, US, 1981.
[59] Ju-Sheng Mi, Wei-Zhi Wu and Wen-Xiu Zhang. “Approaches to knowledge
reduction based on variable precision rough set model”. in: Information sci-
ences 159.3 (2004), pages 255–272.
[60] Fan Min, Huaping He, Yuhua Qian andWilliam Zhu. “Test-cost-sensitive at-
tribute reduction”. in: Information Sciences 181.22 (2011), pages 4928–4942.
119
[61] Bernard Monjardet. “The presence of lattice theory in discrete problems of
mathematical social sciences. Why”. in: Mathematical Social Sciences 46.2
(2003), pages 103–144.
[62] Viet Anh Nguyen and Akihiro Yamamoto. “Learning from graph data by
putting graphs on the lattice”. in: Expert Systems with Applications 39.12
(2012), pages 11172–11182.
[63] Rickard Nyman, Sujit Kapadia, David Tuckett, David Gregory, Paul Ormerod
and Robert Smith. “News and narratives in financial systems: exploiting big
data for systemic risk assessment”. in: (2018).
[64] Zdzislaw Pawlak. “Rough sets”. in: International Journal of Computer & In-
formation Sciences 11.5 (1982), pages 341–356.
[65] Zdzislaw Pawlak. “Rough sets and intelligent data analysis”. in: Information
sciences 147.1 (2002), pages 1–12.
[66] Zdzislaw Pawlak, Jerzy Grzymala-Busse, Roman Slowinski and Wojciech
Ziarko. “Rough sets”. in:Communications of the ACM 38.11 (1995), pages 88–95.
[67] Zdzislaw Pawlak andAndrzej Skowron. “Rough sets and Boolean reasoning”.
in: Information sciences 177.1 (2007), pages 41–73.
[68] Yuhua Qian and Jiye Liang. “Combination entropy and combination granula-
tion in rough set theory”. in: International Journal of Uncertainty, Fuzziness
and Knowledge-Based Systems 16.02 (2008), pages 179–193.
[69] Yuhua Qian, Jiye Liang, Witold Pedrycz and Chuangyin Dang. “Positive ap-
proximation: an accelerator for attribute reduction in rough set theory”. in:
Artificial Intelligence 174.9-10 (2010), pages 597–618.
[70] Jesse Read, Bernhard Pfahringer and Geoff Holmes. “Multi-label classifi-
cation using ensembles of pruned sets”. in: 2008 Eighth IEEE International
Conference on Data Mining. IEEE. 2008, pages 995–1000.
120
[71] Jesse Read, Bernhard Pfahringer, Geoff Holmes and Eibe Frank. “Classi-
fier chains for multi-label classification”. in: Machine learning 85.3 (2011),
pages 333–359.
[72] Ronald C Read and Derek G Corneil. “The graph isomorphism disease”. in:
Journal of Graph Theory 1.4 (1977), pages 339–363.
[73] John E Savage. “Models of computation”. in: Exploring the Power of Com-
puting (1998).
[74] Glenn Shafer andothers. Amathematical theory of evidence. volume 1. Prince-
ton university press Princeton, 1976.
[75] Andrzej Skowron andCecylia Rauszer. “The discernibility matrices and func-
tions in information systems”. in: Intelligent Decision Support. Springer, 1992,
pages 331–362.
[76] Dominik S´lezak. “Approximate entropy reducts”. in: Fundamenta informati-
cae 53.3-4 (2002), pages 365–390.
[77] N Talukder and MJ Zaki. “A distributed approach for graph mining in mas-
sive networks”. in:DataMining and Knowledge Discovery (2016), pages 1–29.
[78] Vu Duc Thi. “The minimal keys and antikeys”. in: Acta Cybernetica 7.4
(1986), pages 361–371.
[79] Vu Duc Thi andNguyen Long Giang. “AMethod to Construct Decision Table
from Relation Scheme”. in: Cybernetics and Information Technologies 11.3
(2011), pages 32–41.
[80] Vu Duc Thi and Nguyen Long Giang. “Some Problems concerning Condi-
tion Attributes and Reducts in Decision Tables”. in: Proceeding of the fifth
National Symposium Fundamental and Applied Information Technology Re-
search. FAIR, Dong Nai, Vietnam, 2012, pages 142–152.
121
[81] Lini T Thomas, Satyanarayana R Valluri and Kamalakar Karlapalem. “Mar-
gin: Maximal frequent subgraph mining”. in: ACM Transactions on Knowl-
edge Discovery from Data (TKDD) 4.3 (2010), page 10.
[82] Konstantinos Trohidis, Grigorios Tsoumakas, George Kalliris and Ioannis P
Vlahavas. “Multi-Label Classification of Music into Emotions.” in: ISMIR.
volume 8. 2008, pages 325–330.
[83] Grigorios Tsoumakas and Ioannis Katakis. “Multi-label classification: An
overview”. in:Dept. of Informatics, Aristotle University of Thessaloniki, Greece
(2006).
[84] Julian R Ullmann. “An algorithm for subgraph isomorphism”. in: Journal of
the ACM (JACM) 23.1 (1976), pages 31–42.
[85] Celine Vens, Jan Struyf, Leander Schietgat, Sasˇo Dzˇeroski andHendrik Bloc-
keel. “Decision trees for hierarchical multi-label classification”. in: Machine
Learning 73.2 (2008), pages 185–214.
[86] Takashi Washio and Hiroshi Motoda. “State of the art of graph-based data
mining”. in: Acm Sigkdd Explorations Newsletter 5.1 (2003), pages 59–68.
[87] Wei Wei, Junhong Wang, Jiye Liang, Xin Mi and Chuangyin Dang. “Com-
pacted decision tables based attribute reduction”. in: Knowledge-Based Sys-
tems 86 (2015), pages 261–277.
[88] Xifeng Yan and Jiawei Han. “gspan: Graph-based substructure pattern min-
ing”. in: Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE Interna-
tional Conference on. IEEE. 2002, pages 721–724.
[89] Xifeng Yan and Jiawei Han. “CloseGraph: mining closed frequent graph pat-
terns”. in: Proceedings of the ninth ACM SIGKDD international conference
on Knowledge discovery and data mining. ACM. 2003, pages 286–295.
122
[90] Xifeng Yan, Philip S Yu and Jiawei Han. “Graph indexing: a frequent structure-
based approach”. in: Proceedings of the 2004 ACM SIGMOD international
conference on Management of data. ACM. 2004, pages 335–346.
[91] Xifeng Yan, Feida Zhu, Jiawei Han and Philip S Yu. “Searching substructures
with superimposed distance”. in: 22nd International Conference on Data En-
gineering (ICDE’06). IEEE. 2006, pages 88–88.
[92] Yiyu Yao and Yan Zhao. “Attribute reduction in decision-theoretic rough set
models”. in: Information sciences 178.17 (2008), pages 3356–3373.
[93] Yiyu Yao and Yan Zhao. “Discernibility matrix simplification for construct-
ing attribute reducts”. in: Information sciences 179.7 (2009), pages 867–882.
[94] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamil-
ton and Jure Leskovec. “Graph convolutional neural networks for web-scale
recommender systems”. in: Proceedings of the 24th ACM SIGKDD Inter-
national Conference on Knowledge Discovery & Data Mining. ACM. 2018,
pages 974–983.
[95] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton
and Jure Leskovec. “Hierarchical graph representation learning with differ-
entiable pooling”. in: Advances in Neural Information Processing Systems.
2018, pages 4800–4810.
[96] Ronghui You, Zihan Zhang, Yi Xiong, Fengzhu Sun, Hiroshi Mamitsuka and
Shanfeng Zhu. “GOLabeler: improving sequence-based large-scale protein
function prediction by learning to rank”. in: Bioinformatics 34.14 (2018),
pages 2465–2473.
[97] Zoulficar Younes, Fahed Abdallah and Thierry Denœux. “An evidence-theoretic
k-nearest neighbor rule for multi-label classification”. in: International Con-
ference on Scalable Uncertainty Management. Springer. 2009, pages 297–308.
123
[98] Zoulficar Younes, Thierry Denœux andothers. “Evidential multi-label clas-
sification approach to learning from data with imprecise labels”. in: Inter-
national Conference on Information Processing and Management of Uncer-
tainty in Knowledge-Based Systems. Springer. 2010, pages 119–128.
[99] Min-Ling Zhang and Zhi-Hua Zhou. “A k-nearest neighbor based algorithm
for multi-label classification”. in: 2005 IEEE international conference on
granular computing. volume 2. IEEE. 2005, pages 718–721.
[100] Kai Zheng, Jie Hu, Zhenfei Zhan, Jin Ma and Jin Qi. “An enhancement for
heuristic attribute reduction algorithm in rough set”. in: Expert Systems with
Applications 41.15 (2014), pages 6748–6754.
[101] Zhenyu Zhou, Caixia Gao, Chen Xu, Yan Zhang, ShahidMumtaz and Jonathan
Rodriguez. “Social big-data-based content dissemination in Internet of vehi-
cles”. in: IEEE Transactions on Industrial Informatics 14.2 (2018), pages 768–777.