Trong phần này các kết quả thu được từ thử nghiệm với biểu diễn hàm thuộc
dang đơn thể hạt. Mỗi mục (thuộc tính) được chia làm 5 miền mờ có các nhãn tương
ứng trong ĐSGT là {0, 𝑐−, 𝑊, 𝑐+, 1}. Phương pháp sử dụng ĐSGT được so sánh với
3 phương pháp khác: Phương pháp do Herrera và cộng sự [53], phương pháp của
Hong và cộng sự [42] và phương pháp phân chia đều miền giá trị của thuộc tính bằng
các MF đồng dạng (là tam giác cân, giống nhau về mặt hình học và chia đều miền
xác định của mục)
109 trang |
Chia sẻ: tueminh09 | Ngày: 24/01/2022 | Lượt xem: 552 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận án Nghiên cứu phát triển phương pháp khai phá luật kết hợp mờ biểu thị bằng thông tin ngôn ngữ và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ình CHC: Mô hình giải thuật di truyền sẽ được sử dụng trong luận án để
tìm các tham số mờ của ĐSGT.
- Mã hóa tập MF: luận án đề xuất cách mã hóa các tham số mờ của ĐSGT được
sử dụng trong GA để tìm kiếm các tham số mờ của ĐSGT. Từ các tham số mờ này
có thể dễ dàng xây dựng được các MF như trình bày trong mục 3.2.
- Hàm mục tiêu (fitness function).
3.3.1. Mô hình giải thuật di truyền CHC
Luận án sử dụng giải thuật di truyền theo mô hình CHC [10] để tìm kiếm các
tham số tối ưu cho các ĐSGT. Mô hình giải thuật di truyền CHC tiếp cận theo hướng
sử dụng phép toán chọn lọc tự nhiên. Trong mô hình CHC, từ N bố mẹ và các nhiễm
sắc thể con tương ứng sẽ tạo ra N nhiễm sắc thể tốt nhất cho quần thể mới. Mô hình
CHC sử dụng phương pháp tránh lai tạo giữa các nhiễm sắc thể gần nhau và cơ chế
khởi tạo lại quần thể. Trong lược đồ mã hoá, mỗi gene sẽ được mã hoá thành Gray
Code với số bít cố định cho mỗi gene, số bít này có được dựa vào kinh nghiệm.
Ngưỡng giới hạn để khởi tạo lại quần thể được xác định như sau: L = (#Genes
BITSGENE)/4.0.
Với biến #Genes là số gene trong một nhiễm sắc thể, BITSGENE là số bít
dùng cho mỗi gene. Trong mô hình CHC, trong mỗi lần lặp nếu không tạo ra được cá
thể mới nào trong quần thể thì L sẽ giảm một lần, giá trị của L phụ thuộc vào #Genes
và BITSGENE, mỗi lần L giảm 𝜑% (được xác định bởi người dùng, thường là 10%).
Thuật toán được khởi tạo lại khi L <= 0.
Lược đồ thuật toán theo mô hình giải thuật di truyền CHC như Hình 3.6.
72
Hình 3.6: Mô hình giải thuật di truyền CHC
3.3.2. Mã hóa tập các MF
Để xây dựng các hàm thuộc cho các thuộc tính, trong luận án sử dụng ĐSGT
có cấu trúc 𝐴𝑋 = (𝑋, 𝐺, 𝐻,≤) trong đó:
- 𝐺 = {𝐶− = {𝐿𝑜𝑤} ∪ 𝐶+ = {𝐻𝑖𝑔ℎ}}
- 𝐻 = {𝐻− = {𝐿𝑖𝑡𝑡𝑙𝑒} ∪ 𝐻+ = {𝑉𝑒𝑟𝑦}}
Với:
- 𝛼 = 𝜇(𝐿𝑖𝑡𝑡𝑙𝑒) = 1 − 𝜇(𝑉𝑒𝑟𝑦), 𝛽 = 𝜇(𝑉𝑒𝑟𝑦)
- 𝑤 = 𝑓𝑚(𝐿𝑜𝑤) = 1 − 𝑓𝑚(𝐻𝑖𝑔ℎ).
Với cấu trúc ĐSGT trên gồm bộ bốn tham số: 𝜇(𝐿𝑖𝑡𝑡𝑙𝑒), 𝜇(𝑉𝑒𝑟𝑦), 𝑓𝑚(𝐶−),
𝑓𝑚(𝐶+). Tham số 𝛼 = 𝜇(𝑉𝑒𝑟𝑦) = 1 − 𝜇(𝐿𝑖𝑡𝑡𝑙𝑒), và 𝑤 = 𝑓𝑚(𝐿𝑜𝑤) = 1 −
𝑓𝑚(𝐻𝑖𝑔ℎ), vì vậy với mỗi ĐSGT chúng ta chỉ cần tìm hai tham số 𝛼 và 𝑤 thay vì
tìm cả bốn tham số.
Dựa vào các tham số của ĐSGT của các thuộc tính, chúng ta xây dựng các
hàm thuộc theo dạng đơn thể hạt như trình bày mục 3.2.1 hoặc biểu diễn đa thể hạt
như trình bày trong mục 3.2.2.
Chúng ta cần phải cần phải tìm kiếm các tham số mờ của các ĐSGT 𝐴𝑋𝑖 cho
n thuộc tính định lượng, mỗi ĐSGT gồm có hai tham số 𝛼𝑖 , 𝑤𝑖 (i=1,,n). Như vậy
để biểu diễn một nhiệm sắc thể cần một mảng số thực có kích thước 2*n. Cấu trúc
một gene như sau:
Khởi tạo quần
thể và Threshold
Khởi tại lại quần
thể và Threshold
Lại tạo N cá
thể cha mẹ
Threshold <= 0
Đánh giá các cá thể
mới
Lựa chọn N cá thể
tốt nhất
Nếu không có cá
thể mới, giảm giá
trị Threshold
Sai
Đúng
73
(𝛼1, , 𝛼𝑛, 𝑤1, , 𝑤𝑛) (3.1)
Dựa vào kinh nghiệm các tham số mờ của các ĐSGT 𝛼𝑖 và 𝑤𝑖 sẽ nhận giá trị
nằm trong đoạn [0.2, 0.8].
3.3.3. Đánh giá nhiễm sắc thể
Để đánh giá các nhiễm sắc thể, chúng ta sử dụng hàm mục tiêu được định
nghĩa trong [42]. Hàm mục tiêu của một nhiễm sắc thể 𝐶𝑞 được định nghĩa như sau:
𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝐶𝑞) =
∑ 𝑓𝑢𝑧𝑧y_support(x)𝑥∈𝐿1
𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞)
(3.2)
Với:
- 𝐿1 là tập phổ biến 1-ItemSet sử dụng tập các hàm MF trong 𝐶𝑞.
Chúng ta chỉ tính độ hỗ trợ của các 1-ItemSet để đảm bảo cân bằng giữa thời
gian thực hiện thuật toán và độ thú vị của các luật được tạo ra. Thông thường các mục
xuất hiện trong 1-ItemSet khả năng cao sẽ xuất hiện trong các tập mục k-itemset
(k>1). Vì vậy trong đánh giá chúng ta chỉ tính độ hỗ trợ của các tập mục trong 1-
ItemSet, sẽ nhanh hơn là tính độ hỗ trợ của tất cả các tập mục hoặc đánh giá toàn bộ
các luật kết hợp [83].
- 𝑓𝑢𝑧𝑧𝑦_𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝑥) độ hỗ trợ mờ của 1-ItemSet x được tính toán từ CSDL
giao dịch.
- 𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞) mức độ phù hợp phù hợp của MF trong 𝐶𝑞.
Mức độ phù hợp của tập các MF trong nhiệm sắc thể 𝐶𝑞 được định nghĩa như
sau:
𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞) = ∑[𝑜𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘) + 𝑐𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘)]
𝑛
𝑘=1
(3.3)
Với n là số lượng item, 𝑜𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘) là mức độ chồng lên nhau của
các MF của item 𝐼𝑘 trong nhiệm sắc thể 𝐶𝑞, và 𝑐𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘) là mức độ
bao phủ của các MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞.
𝑂𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟 biểu diễn tỷ lệ các MF chồng lên nhau của item 𝐼𝑘 trong
nhiễm sắc thể 𝐶𝑞. Tỷ lệ chồng lên nhau của hai MF: 𝑅𝑖 và 𝑅𝑗 (i<j) được định nghĩa là
lấy chiều dài chồng lên nhau chia cho giá trị nhỏ nhất của right span của 𝑅𝑖 và left
74
span của 𝑅𝑗. Nếu chiều dài chồng lên nhau lớn hơn giá trị nhỏ nhất của hai giá trị
span trên thì hai MF không được tốt, cần phải xem xét lại. Overlap factor của MF đối
với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 được định nghĩa như sau:
Overlap_factor(𝐶𝑞𝑘)
= ∑ ∑ [𝑚𝑎𝑥 (
𝑜𝑣𝑒𝑟𝑙𝑎𝑝(𝑅𝑖 , 𝑅𝑗)
𝑚𝑖𝑛 (𝑠𝑝𝑎𝑛𝑅𝑅𝑖 , 𝑠𝑝𝑎𝑛𝐿𝑅𝑗 , )
, 1) − 1]
𝑚
𝑗=𝑖+1
𝑚
𝑘=1
(3.4)
Với 𝑜𝑣𝑒𝑟𝑙𝑎𝑝(𝑅𝑖 , 𝑅𝑗) là chiều dài chồng lên nhau của 𝑅𝑖 và 𝑅𝑗, 𝑠𝑝𝑎𝑛𝑅𝑅𝑖 là
right span của 𝑅𝑖, 𝑠𝑝𝑎𝑛𝐿𝑅𝑗 là left span của 𝑅𝑗 và m là số hàm thuộc MF đối với item
𝐼𝑘.
𝐶𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟 biểu diễn tỷ lệ bao phủ của các MF đối với item 𝐼𝑘 trong
nhiễm sắc thể 𝐶𝑞. Tỷ lệ bao phủ của MF đối với item item 𝐼𝑘 được định nghĩa là độ
bao phủ của hàm chia cho giá trị lớn nhất của item trong giao dịch. Coverage_factor
của MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 được định nghĩa như sau:
Coverage_factor(𝐶𝑞𝑘) =
1
𝑅𝑎𝑛𝑔(𝑅1, , 𝑅𝑚)
𝑚𝑎𝑥(𝐼𝑘)
(3.5)
Với 𝑅𝑎𝑛𝑔(𝑅1, , 𝑅𝑚) là phạm vi bao phủ của MF và 𝑚𝑎𝑥(𝐼𝑘) giá trị lớn nhất
của 𝐼𝑘 trong giao dịch.
Hình 3.7: Tập các MF cho mục Ij
Với 𝑂𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟 tốt, ta có thể loại hoặc hạn chế trường hợp (a) của Hình
3.8, khi các hàm thuộc chồng nhau quá nhiều, ít mang tính phân biệt. Với
𝑐𝑜𝑣𝑒𝑟𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟 tốt, có thể hạn chế trường hợp như (b) trên Hình 3.8, khi tồn tại
nhiều khoảng trống trên miền xác định, không rơi vào tập mờ nào (độ thuộc lớn hơn
75
0). Ngoài ra, với hi vọng thu được tập các tập mờ được phân chia tốt, 𝑢𝑠𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟
là số đo tổng độ hỗ trợ của các tập phổ biến 1 thuộc tính (large 1-ItemSet) được sử
dụng. Với tổng độ hỗ trợ cao, hi vọng là ta sẽ nhận được nhiều luật kết hợp, tuy không
chắc như xem xét tất cả các tập phổ biến nhưng bù lại, thời gian xử lý sẽ ít hơn vì chỉ
xét các tập phổ biến 1-ItemSet.
Hình 3.8: Hai tập hàm thuộc phân bố không tốt
Gần đây, người ta còn sử dụng khái niệm phân hoạch mờ mạnh (strong fuzzy
partition) để xây dựng tập MF [15]. Khái niệm này được định nghĩa như sau: tập các
MF tạo nên một phân hoạch mờ mạnh nếu chúng phủ kín miền giá trị thuộc tính và
tại mỗi điểm bất kỳ trên miền xác định, tổng độ thuộc của điểm này đến tất cả các
MF trong phân hoạch đạt giá trị 1. Phân hoạch mờ mạnh cũng tạo ra các MF phân bố
tương đối tốt.
Với các độ đo như vậy, có thể sử dụng giải thuật di truyền để nhận được các
tập MF tối ưu (thường là xấp xỉ), có tính đến sự cân bằng giữa mức độ tốt của hệ
thống và thời gian tính toán.
3.4. Thuật toán tìm kiếm phân hoạch mờ tối ưu và luật kết hợp
Trong phần này luận án đề xuất thuật toán để tìm kiếm phân hoạch mờ tối ưu
theo hướng sử dụng ĐSGT thay cho cách tiếp cận sử dụng lý thuyết tập mờ của các
tác giả khác [28, 69] và khai phá luật kết hợp mờ.
Thuật toán gồm hai pha:
Pha 1: Tìm kiếm phân hoạch mờ tối ưu dựa vào CSDL giao dịch đầu vào.
Pha 2: Sử dụng thuật toán khai phá luật kết hợp mờ với các hàm thuộc có được
trong Pha 1.
76
Nội dung thuật toán:
Đầu vào: T giao dịch số, tập gồm n mục (thuộc tính), mỗi mục gồm m hạng
từ ngôn ngữ, độ hỗ trợ min_𝑠𝑢𝑝𝑝, và độ tin cậy min_𝑐𝑜𝑛𝑓 và kích thước quần thể N.
Đầu ra: Tập các luật kết hợp mờ và tập hàm thuộc MF.
Nội dung thuật toán:
Pha 1: Tìm kiếm phân hoạch mờ tối ưu từ CSDL giao dịch T
Bước 1: Khởi tạo quần thể gồm N nhiễm sắc thể ngẫu nhiên.
Nhiễm sắc thể biểu diễn có dạng (𝛼1, , 𝛼𝑛, 𝑤1, , 𝑤𝑛). Với mỗi cặp (𝛼𝑖 , 𝑤𝑖)
là một ĐSGT, với i=1,..,n.
Bước 2: Mã hóa các hàm thuộc thành chuỗi mã hóa như trình bày ở mục 3.3.2.
Dựa vào các ĐSGT có được trong Bước 1, xây dựng các hàm thuộc cho các
thuộc tính trong CSDL gốc như trình bày trong phần 3.2. Chúng ta có thể sử dụng
biểu diễn hàm thuộc dạng Đơn thể hạt hoặc Đa thể hạt.
Bước 3: Tính toán hàm mục tiêu cho mỗi nhiễm sắc thể trong quần thể như
sau:
Bước 3.1: Mỗi giao dịch và 𝐷𝑖, với i=1n, mỗi thuộc tính 𝐼𝑗, j=1m biến đổi
thành giá trị số 𝑣𝑗
(𝑖)
như sau: (
𝑓𝑗1
(𝑖)
𝑅𝑗1
+
𝑓𝑗2
(𝑖)
𝑅𝑗2
+⋯+
𝑓𝑗𝑙
(𝑖)
𝑅𝑗𝑙
) để biểu diễn tập hàm thuộc
của một nhiễm sắc thể.
Với 𝑅𝑗𝑘 là vùng mờ thứ k của item 𝐼𝑗, 𝑓𝑗𝑙
(𝑖)
: 𝑣𝑗
(𝑖)
là giá trị của hàm thuộc thứ j
của item 𝐼𝑗, l là số miền mờ.
Bước 3.2: Tính toán giá trị mỗi miền mờ:
𝑐𝑜𝑢𝑛𝑡𝑗𝑘 =∑𝑓𝑗
(𝑖)
𝑛
𝑖=1
(3.6)
Bước 3.3: Mỗi miền mờ 𝑅𝑗𝑘, 1 ≤ 𝑗 ≤ 𝑚, 1 ≤ 𝑘 ≤ |𝐼𝑗|, kiểm tra giá trị 𝑐𝑜𝑢𝑛𝑡𝑗𝑘
so với ngưỡng độ hỗ trợ tối thiểu min_supp. Nếu 𝑅𝑗𝑘 thỏa mãn điều kiện thì đưa vào
tập phổ biến 1-ItemSet (𝐿1).
𝐿1 = {𝑅𝑗𝑘| 𝑐𝑜𝑢𝑛𝑡𝑗𝑘 ≥ 𝛼, 1 ≤ 𝑗 ≤ 𝑚, 1 ≤ 𝑘 ≤ |𝐼𝑗|}
Bước 3.4: Giá trị mục tiêu của nhiễm sắc thể được tính theo công thức sau:
77
𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝐶𝑞) =
∑ 𝑓𝑢𝑧𝑧𝑦_𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝑥)𝑥∈𝐿1
𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞)
(3.7)
Bước 4: Thực hiện phép lai tạo trong quần thể.
Bước 5: Sử dụng phép chọn lọc theo điều kiện để chọn các cá thể trong quần
thể để tạo thế hệ tiếp theo.
Bước 6: Nếu điều kiện dừng chưa thỏa mãn thì quay lại Bước 3, ngược lại
thực hiện bước tiếp theo.
Bước 7: Hàm thuộc được lựa chọn từ cá thể có giá trị hàm mục tiêu lớn nhất
trong quần thể.
Pha 2: Khai phá luật kết hợp mờ
Sử dụng thuật toán khai phá luật kết hợp mờ như trong [53].
3.5. Kết quả thử nghiệm
Trong phần này sẽ mô tả CSDL dùng trong thử nghiệm và các kết quả thử
nghiệm với hai phương pháp luận án đề xuất: sử dụng biểu diễn dữ liệu dạng đơn thể
hạt và sử dụng biểu diễn dữ liệu dạng đa thể hạt.
Các tham số của giải thuật GA như sau: kích thước quần thể 50; số thế hệ
10000, số bít cho mỗi gen là 30, xác suất lai tạo 0.6.
3.5.1. Cơ sở dữ liệu sử dụng trong thử nghiệm
Bảng 3.4: CSDL thử nghiệm
CSDL Số thuộc tính Số bản ghi
Fam95 10 63756
Pollution 16 60
Stulong 5 1417
Basketball 5 96
Quake 4 2178
Stock 10 950
CSDL được sử dụng trong thử nghiệm gồm: FAM95, pollution, stulong,
basketball, quake, stock. Các CSDL này được lấy từ kho dữ liệu UCI
(https://archive.ics.uci.edu).
78
CSDL FAM95: thường được các nhà nghiên cứu coi là tập mẫu chuẩn để tiến
hành thử nghiệm, tiện so sánh kết quả. FAM95 chứa số liệu của 63756 gia đình Mỹ
(số liệu khảo sát năm 1995), bao gồm 63756 bản ghi, 23 mục. Ở đây luận án chọn 10
mục định lượng để tiến hành thử nghiệm. CSDL Pollution: bao gồm 60 bản ghi với
16 thuộc tính số. CSDL Stulong: bao gồm 1417 bản ghi với 5 thuộc tính số. CSDL
Basketball: bao gồm 96 bản ghi với 5 thuộc tính số. CSDL Quake: bao gồm 2178 bản
ghi, với 4 thuộc tính số. CSDL Stock: bao gồm 950 bản ghi, với 10 thuộc tính số.
3.5.2. Phân tích và đánh giá kết quả thử nghiệm với biểu diễn dữ liệu dạng đơn
thể hạt
Trong phần này các kết quả thu được từ thử nghiệm với biểu diễn hàm thuộc
dang đơn thể hạt. Mỗi mục (thuộc tính) được chia làm 5 miền mờ có các nhãn tương
ứng trong ĐSGT là {0, 𝑐−,𝑊, 𝑐+, 1}. Phương pháp sử dụng ĐSGT được so sánh với
3 phương pháp khác: Phương pháp do Herrera và cộng sự [53], phương pháp của
Hong và cộng sự [42] và phương pháp phân chia đều miền giá trị của thuộc tính bằng
các MF đồng dạng (là tam giác cân, giống nhau về mặt hình học và chia đều miền
xác định của mục).
3.5.2.1. Kết quả thử nghiệm với CSDL FAM95
Trong Bảng 3.5 là các tham số mờ của các ĐSGT của 10 thuộc tính số thu
được sau khi chạy giải thuật di truyền. Các tham số này được sử dụng để xây dựng
các hàm thuộc theo dạng biểu diễn đơn thể hạt như đã trình bày trong mục 3.2.1.
Bảng 3.5: Các tham số mờ của các ĐSGT được tối ưu của 10 thuộc tính với phương
pháp sử dụng biểu diễn đơn thể hạt
T
h
u
ộ
c tín
h
1
T
h
u
ộ
c tín
h
2
T
h
u
ộ
c tín
h
3
T
h
u
ộ
c tín
h
4
T
h
u
ộ
c tín
h
5
T
h
u
ộ
c tín
h
6
T
h
u
ộ
c tín
h
7
T
h
u
ộ
c tín
h
8
T
h
u
ộ
c tín
h
9
T
h
u
ộ
c tín
h
1
0
𝜇(𝐿) 0.679 0.350 0.610 0.649 0.214 0.379 0.202 0.704 0.231 0.213
𝜇(𝑉) 0.321 0.650 0.390 0.351 0.786 0.621 0.798 0.296 0.769 0.787
𝑓𝑚(𝐶−) 0.504 0.764 0.799 0.756 0.732 0.479 0.800 0.499 0.765 0.776
𝑓𝑚(𝐶+) 0.496 0.236 0.201 0.244 0.268 0.521 0.200 0.501 0.235 0.224
79
Kết quả thu được như trong Bảng 3.6, với 𝐹𝑠𝑢𝑝: Tổng độ hỗ trợ của các tập phổ
biến 1-ItemSet, Fit: Giá trị hàm mục tiêu, Suit: Độ phù hợp, #1I: Số lượng 1-ItemSet,
Interest: độ thú vị trung bình của các luật.
Từ kết quả trên có thể thấy:
Ở giá trị min_supp = 20%, số tập phố biến 1-ItemSet theo cách tiếp cận ĐSGT:
- So với phương pháp phương pháp do Herrera và cộng sự [53], phương pháp
của Hong và cộng sự [42] là như nhau.
- Phương pháp phân chia đều kém hơn phương pháp sử dụng ĐSGT.
Bảng 3.6: Kết quả thử nghiệm biểu diễn đơn thể hạt
Phương pháp đề xuất sử dụng ĐSGT
Min Sup (%) Fit Fsup Suit #1I
20 0.98 9.83 10 22
50 0.79 7.87 10 10
70 0.66 6.62 10 8
90 0.09 0.94 10 1
Phương pháp của Herrera và cộng sự
Min Sup (%) Fit Fsup Suit #1I
20 0.95 10.46 10.99 22
50 0.77 9.92 12.92 15
70 0.61 7.69 12.57 10
90 0.10 0.92 10.0 1
Phương pháp của Hong và cộng sự
Min Sup (%) Fit Fsup Suit #1I
20 0.53 10.22 19.27 22
50 0.38 7.95 20.63 12
70 0.20 3.96 19.54 5
90 0.06 0.90 15.01 1
Phương pháp phân chia đều
Min Sup (%) Fit Fsup Suit #1I
20 0.94 9.43 10 21
50 0.46 4.57 10 7
70 0.24 2.36 10 3
90 0.00 0.00 10 0
80
Với độ hỗ trợ min_supp = 50%, phương pháp ĐSGT có kém chút ít phương
pháp của nhóm Herrera và nhóm Hong về số tập phố biến 1-ItemSet. Với độ hỗ trợ
min_supp = 70% phương pháp sử dụng ĐSGT kém hơn phương pháp do Herrera đề
xuất, nhưng hơn hai phương pháp còn lại.
Với mục tiêu, xây dựng các hàm thuộc sao cho không chồng lên nhau quá
nhiều, và không rời rạc nhau. Giá trị Suit (độ phù hợp của các MF) trong hàm mục
giúp chúng ta tìm kiếm các hàm thuộc đảm bảo điều này. Trong Bảng 3.6 cho thấy,
phương pháp sử dụng ĐSGT có giá trị Suit thấp hơn phương pháp Herrera và Hong.
Giá trị Suit nhỏ giúp cho giá trị hàm mục tiêu càng lớn. Điều đó cho thấy, các hàm
thuộc được xây dựng bằng phương pháp sử dụng ĐSGT gia tử cho kết quả tốt hơn
(Hình 3.9). Kết quả của nhóm Herrera tuy có tốt hơn về mặt số tập phố biến 1-ItemSet
(trong Bảng 3.6 giá trị 1-ItemSet lần lượt là 22, 15, 10, 1) nhưng các tập MF thu được
sau khi chạy GA thì rất không tốt (xem Hình 3.14: hình vẽ MF với độ hỗ trợ tối thiểu
20% dưới đây để thấy rõ).
Hình 3.9: Quan hệ giữa độ phù hợp (Suit) của các hàm thuộc và Min Supp
Trong Hình 3.9 quan hệ độ phù hợp của ba phương pháp: sử dụng ĐSGT,
Herrera, Hong và phương pháp phân chia đều. Kết quả cho thấy độ phù hợp của các
MF của phương pháp sử dụng ĐSGT nhỏ hơn các phương pháp còn lại.
0
5
10
15
20
25
20% 50% 70% 90%
Đ
ộ
p
h
ù
h
ợ
p
c
ủ
a
cá
c
h
àm
t
h
u
ộ
c
Min support
PP đề xuất PP Herrera PP Hong
81
Hình 3.10: Quan hệ giữa giá trị hàm mục tiêu và Min Supp
Trong Hình 3.10 quan hệ giá trị hàm mục tiêu của ba phương pháp sử dụng
ĐSGT, Herrera, Hong và phương pháp phân chia đều. Kết quả cho thấy hàm mục tiêu
của phương pháp sử dụng ĐSGT tốt hơn các phương pháp còn lại.
Hình 3.11: Quan hệ giữa độ hỗ trợ tập mục 1-ItemSet và Min Supp
0
0.2
0.4
0.6
0.8
1
1.2
20% 50% 70% 90%
G
iá
t
rị
h
àm
m
ụ
c
ti
êu
Min support
PP đề xuất PP Herrera PP Hong PP Phân chia đều
0
2
4
6
8
10
12
20% 50% 70% 90%
Đ
ộ
h
ỗ
t
rợ
1
-I
te
m
S
et
Min support
PP đề xuất PP Herrera PP Hong PP phân chia đều
82
Hình 3.12: Quan hệ giữa số lượng 1-ItemSet và Min Supp
Trong Hình 3.12 cho thấy số lượng 1-ItemSet của phương pháp ĐSGT kém
hơn so với kết quả Herrera và hơn so với các phương pháp còn lại. Tuy nhiên dựa
vào giá trị Suit trong Bảng 3.6 và bằng trực quan trong Hình 3.14 cho thấy hàm thuộc
của nhóm Herrera có độ chồng lấn quá nhiều, có một số hai hàm thuộc gần như chồng
khít lên nhau.
Bảng 3.7: Quan hệ giữa độ thú vị trung bình của các luật
Min Supp 20% 30% 40% 50% 60% 70%
PP ĐSGT 0.383 0.516 0.585 0.713 0.771 0.820
PP Herrera 0.368 0.483 0.591 0.669 0.767 0.822
PP Phân chia đều 0.385 0.489 0.606 0.672 0.774 0.821
Trong thử nghiệm, độ thú vị của luật được tính theo công thức 2.5 trong mục
1.4.1. Từ kết quả trong Bảng 3.7 cho thấy độ thú vị trung bình của các luật của phương
pháp sử dụng ĐSGT cao hơn hoặc bằng hai phương pháp còn lại.
0
5
10
15
20
25
20% 50% 70% 90%
S
ố
l
ư
ợ
n
g
t
ập
l
ớ
n
1
-I
te
m
se
t
Min support
PP đề xuất PP Herrera PP Hong Phân chia đều
83
Hình 3.13: Quan hệ giữa độ thú vị trung bình và Min Supp
Trong Hình 3.14 có thể thấy, kết quả thu được tập các MF đều có 1 cặp MF
gần như chồng khít, không thỏa mãn tiêu chí về độ chồng lấn. Điều này chứng tỏ kết
quả phân chia miền mờ của phương pháp này không tốt (ở đây kết quả chỉ ra một
điều là có lẽ chia thành 4 miền mờ thì hợp lý hơn, khi đó các nhãn ngôn ngữ cũng sẽ
khác, chỉ có 4 thay vì 5). Vấn đề lựa chọn không chỉ các hàm MF phân chia miền xác
định của mục khi cố định số lượng (thí dụ như 5) mà hơn nữa, lựa chọn chính số
lượng đó cho từng mục là vấn đề đáng được quan tâm vì có thể thấy các chỉ số nêu
trên bảng trên phụ thuộc nhiều vào số lượng của các MF cho từng mục.
Trong chương này, luận án trình bày thuật toán tối ưu hóa cả số lượng lẫn
thông số các MF cho các thuộc tính định tính nhằm tới kết quả tốt nhất khi khai phá
dữ liệu thông qua việc sử dụng khái niệm đa thể hạt khi phân chia miền mờ. Các hình
ảnh cho tập MF theo phương pháp ĐSGT được đưa ra trong Hình 3.15. Tất nhiên,
các tam giác biểu diễn các MF ở đây vẫn tạo nên một phân hoạch mạnh theo cách ta
xây dựng.
-
0.200
0.400
0.600
0.800
1.000
20% 30% 40% 50% 60% 70%
Đ
ộ
t
h
ú
v
ị
tr
u
n
g
b
ìn
h
c
ủ
a
ác
l
u
ật
Min support
PP ĐSGT PP Herrera PP Phân chia đều
84
85
Hình 3.14: Tập hàm thuộc thu được sau khi thực hiện GA với phương pháp của
Herrera sử dụng lý thuyết tập mờ
Hình 3.15 là tập các hàm thuộc của 10 thuộc tính thu được sau khi thực hiện
tối ưu bằng giải thuật di truyền. Bằng trực quan chúng ta có thể thấy, các tập mờ có
sự phân bố đều đảm bảo độ chồng lấn giữa các tập mờ vừa phải và các tập mờ phủ
toàn bộ trên miền giá trị của thuộc tính.
86
Hình 3.15: Tập hàm thuộc thu được sau khi thực hiện GA với phương pháp sử dụng
biểu diễn đơn thể hạt và ĐSGT
3.5.2.2. Kết quả thử nghiệm với một số CSDL khác
Trong mục này, luận án sử dụng cấu trúc ĐSGT như trọng mục 3.5.2.1, và
trình bày kết quả thử nghiệm với 5 CSDL gồm: pollution, stulong, basketball, quake,
stock. Luận án trình bày so sánh kết quả đề xuất với hai phương pháp khác là: Phương
pháp do Herrera và cộng sự [53], phương pháp của Hong và cộng sự [42]. Trong
Bảng 3.8 là số lượng tập phổ biến 1-ItemSet, Bảng 3.9 là độ thú vị trung bình.
Bảng 3.8: Bảng số lượng tập phổ biến 1-ItemSet
87
CSDL Min Supp (%) PP đề xuất PP Herrera PP Hong
pollution
20 37 45 56
50 15 14 43
70 5 2 18
90 1 0 1
stulong
20 10 13 17
50 5 10 13
70 5 5 13
90 0 0 2
basketball
5 22 20 22
10 18 19 20
15 15 17 21
20 13 15 21
25 11 13 20
30 10 9 20
35 10 9 18
40 9 5 17
45 5 4 18
50 4 2 14
quake
5 14 16 16
10 15 14 13
15 11 11 14
20 9 9 13
25 8 9 11
30 8 8 11
35 7 8 11
40 6 8 11
45 4 6 11
50 4 3 10
stock
5 50 50 50
10 50 50 48
15 50 50 49
20 45 49 50
88
25 47 50 49
30 43 48 49
35 41 48 50
40 41 47 46
45 37 47 47
50 33 41 48
Hình 3.16: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Pollution
Hình 3.17: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Stulong
0
10
20
30
40
50
60
20% 50% 70% 90%S
ố
l
ư
ợ
n
g
t
ập
l
ớ
n
1
-I
te
m
S
et
Min support
PP đề xuất PP Herrera PP Hong
0
5
10
15
20
20% 50% 70% 90%
S
ố
l
ư
ợ
n
g
t
ập
l
ớ
n
1
-I
te
m
S
et
Min support
PP đề xuất PP Herrera PP Hong
89
Hình 3.18: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Basketball
Hình 3.19: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Quake
0
5
10
15
20
25
5% 10% 15% 20% 25% 30% 35% 40% 45% 50%S
ố
l
ư
ợ
n
g
t
ập
l
ớ
n
1
-I
te
m
S
et
Min support
PP đề xuất PP Herrera PP Hong
0
5
10
15
20
5% 10% 15% 20% 25% 30% 35% 40% 45% 50%S
ố
l
ư
ợ
n
g
t
ập
l
ớ
n
1
-I
te
m
S
et
Min support
PP đề xuất PP Herrera PP Hong
0
10
20
30
40
50
60
5% 10% 15% 20% 25% 30% 35% 40% 45% 50%S
ố
l
ư
ợ
n
g
t
ập
l
ớ
n
1
-I
te
m
S
et
Min support
PP đề xuất PP Herrera PP Hong
90
Hình 3.20: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL stock
Trong Hình 3.16, Hình 3.17, Hình 3.18, Hình 3.19, Hình 3.20 cho thấy số
lượng 1-ItemSet của phương pháp ĐSGT kém hơn so với kết quả của Hong, so với
phương pháp của Herrera có thử nghiệm số lượng 1-ItemSet lớn hơn, có thử nghiệm
số lượng ít hơn. Tuy nhiên bằng trực quan trong Hình 3.14 cho thấy hàm thuộc của
nhóm Herrera có độ chồng lấn quá nhiều, có một số hai hàm thuộc gần như chồng
khít lên nhau.
Bảng 3.9: Bảng Độ thú vị trung bình
CSDL Min Supp (%) PP đề xuất PP Herrera PP Hong
pollution
20 0.351 0.349 0.342
50 0.643 0.665 0.654
70 0.823 0.918 0.798
stulong
20 0.487 0.457 0.414
50 0.754 0.651 0.685
70 0.824 0.783 0.789
basketball
1 0.065 0.065 0.067
2 0.087 0.086 0.081
3 0.108 0.099 0.104
4 0.128 0.122 0.119
5 0.123 0.148 0.132
6 0.134 0.154 0.154
7 0.153 0.170 0.174
8 0.187 0.184 0.186
9 0.211 0.197 0.199
10 0.225 0.203 0.211
15 0.306 0.282 0.273
quake
1 0.071 0.099 0.075
2 0.108 0.117 0.077
3 0.096 0.136 0.105
4 0.137 0.153 0.131
5 0.155 0.174 0.161
6 0.204 0.190 0.188
7 0.218 0.207 0.198
8 0.214 0.218 0.205
91
9 0.196 0.226 0.211
10 0.212 0.234 0.218
15 0.310 0.289 0.287
20 0.388 0.330 0.332
25 0.424 0.399 0.394
30 0.486 0.415 0.431
stock
3 0.137 0.159 0.146
4 0.183 0.191 0.159
5 0.179 0.210 0.190
6 0.218 0.229 0.211
7 0.221 0.255 0.230
8 0.252 0.283 0.268
9 0.248 0.303 0.294
10 0.280 0.385 0.353
15 0.380 0.454 0.430
20 0.416 0.594 0.509
25 0.453 0.596 0.568
30 0.592 0.625 0.614
Hình 3.21: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Pollution
-
0.200
0.400
0.600
0.800
1.000
20% 50% 70%
Đ
ộ
t
h
ú
v
ị
tr
u
n
g
b
ìn
h
Min support
PP đề xuất PP Herrera PP Hong
92
Hình 3.22: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Stulong
Hình 3.23: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Basketball
Hình 3.24: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Quake
-
0.200
0.400
0.600
0.800
1.000
20% 50% 70%
Đ
ộ
t
h
ú
v
ị
tr
u
n
g
b
ìn
h
Min support
PP đề xuất PP Herrera PP Hong
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
1 2 3 4 5 6 7 8 9 10 15
Đ
ộ
t
h
ú
v
ị
tr
u
n
g
b
ìn
h
Min support (%)
PP đề xuất PP Herrera PP Hong
0
0.1
0.2
0.3
0.4
0.5
0.6
1 2 3 4 5 6 7 8 9 10 15 20 25 30
Đ
ộ
t
h
ú
v
ị
tr
u
n
g
b
ìn
h
Min support (%)
PP đề xuất PP Herrera PP Hong
93
Hình 3.25: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Stock
Trong thử nghiệm, độ thú vị của luật được tính theo công thức 2.5 trong mục
1.4.1. Từ kết quả trong Bảng 3.9 cho thấy độ thú vị trung bình của các luật kết hợp
thu được của phương pháp sử dụng ĐSGT cao hơn hoặc sấp sỉ bằng hai phương pháp
còn lại.
3.5.3. Phân tích và đánh giá kết quả thử nghiệm với biểu diễn dữ liệu dạng đa
thể hạt
Với mỗi thuộc tính trong CSDL được phân chia miền mờ sử dụng biểu diễn
đa thể hạt và mỗi thuộc tính sử dụng một cấu trúc ĐSGT như trình bày trong mục
3.5.2.2.
Các kết quả thử nghiệm được so sánh với các kết quả đã công bố trước đây
trong Bảng 3.10, thống kê số lượng tập phố biến với mỗ độ hỗ trợ khác nhau từ 20%
đến 80%. Bảng 3.11 là kết quả thử nghiệm với ba phương pháp: phương pháp đề xuất
sử dụng biểu diễn đa thể hạt, phương pháp biểu diễn đơn thể hạt đề xuất trong chương
3 và phương pháp Herrera (2009). Kết quả cho thấy phương pháp sử dụng biểu diễn
Đa thể hạt cho số lượng 1-ItemSet tốt hơn số với hai phương pháp còn lại (như Hình
4.3). Ở đây, (liệt kê các thuộc tính dùng so sánh: độ phủ, chồng lấn đã trình bày ở
trong mục 3.3.3) và các phương pháp dùng để so sánh đều thực hiện với biểu diễn
đơn thể hạt. Các kết quả thử nghiệm cho thấy ưu việt của việc sử dụng biểu diễn đa
thể hạt và ĐSGT, củng cố thêm cho các kết quả nghiên cứu liên quan đến sử dụng
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
3 4 5 6 7 8 9 10 15 20 25 30
Đ
ộ
t
h
ú
v
ị
tr
u
n
g
b
ìn
h
Min support (%)
PP đề xuất PP Herrera PP Hong
94
biểu diễn đa thể hạt (một số công trình công bố trong một số năm gần đây sử dụng
biểu diễn đa thể hạt [37, 66-68, 82, 84])
Bảng 3.10: Các tham số mờ của các ĐSGT được tối ưu của 10 thuộc tính với
phương pháp sử dụng biểu diễn đa thể hạt
T
h
u
ộ
c tín
h
1
T
h
u
ộ
c tín
h
2
T
h
u
ộ
c tín
h
3
T
h
u
ộ
c tín
h
4
T
h
u
ộ
c tín
h
5
T
h
u
ộ
c tín
h
6
T
h
u
ộ
c tín
h
7
T
h
u
ộ
c tín
h
8
T
h
u
ộ
c tín
h
9
T
h
u
ộ
c tín
h
1
0
𝜇(𝐿) 0.531 0.203 0.445 0.548 0.208 0.233 0.202 0.200 0.212 0.204
𝜇(𝑉) 0.469 0.797 0.555 0.452 0.792 0.767 0.798 0.800 0.788 0.796
𝑓𝑚(𝐶−) 0.202 0.501 0.562 0.457 0.617 0.316 0.800 0.798 0.586 0.651
𝑓𝑚(𝐶+) 0.798 0.499 0.438 0.543 0.383 0.684 0.200 0.202 0.414 0.349
Có thể thấy là dùng biểu diễn đa thể hạt sẽ cho kết quả tốt hơn hẳn. Ngoài ra,
như đã nói ở trên, về mặt ngữ nghĩa, dùng biểu diễn đa thể hạt sẽ cho chúng ta các
luật mang tính khái quát cao và các luật chi tiết. Luận án tiến hành thử nghiệm phương
pháp của Herrera với việc phân chia như vậy, kết quả tuy có tăng về chỉ số nhưng vẫn
kém phương pháp đề xuất (xem đồ thị so sánh Hình 3.27:). Cần nhấn mạnh rằng, với
phương pháp luận án đề xuất, việc tính toán liên quan đến biểu diễn đa thể hạt là tăng
thêm không đáng kể về mặt phức tạp cũng như mặt thời gian mà kết quả nhận được
lại tốt hơn rất nhiều.
Bảng 3.11: Quan hệ giữa số lượng tập mục và Min supp
Min Supp 20% 30% 40% 50% 60% 70%
80%
1-ItemSet 59 50 38 29 26 22
17
2-itemset 974 675 456 371 285 187
78
3-itemset 8890 4806 3111 2660 2518 772
150
4-itemset 50242 20719 13095 11890 4708 1774
167
5-itemset 187379 57461 36432 34995 9506 2528
167
Trong Bảng 3.11 là các tham số mờ của các ĐSGT của 10 thuộc tính số thu
được sau khi chạy giải thuật di truyền. Các tham số này được sử dụng để xây dựng
các hàm thuộc theo dạng biểu diễn đa thể hạt như đã trình bày trong mục 3.2.2.
95
Bảng 3.12: Quan hệ giữa số lượng 1-ItemSet và Min Supp
Min Supp 20% 30% 40% 50% 60% 70% 80% 90%
PP biểu diễn Đa thể hạt 54 46 35 27 23 14 12 5
PP biểu diễn Đơn thể hạt 21 17 13 8 7 6 3 1
PP Herrera và cộng sự 25 21 15 10 5 3 2 0
Hình 3.26: Quan hệ giữa số lượng tập phố biến và Min Supp
Hình 3.27: So sánh số lượng tập phổ biến và Min Supp
0
500
1000
1500
20% 30% 40% 50% 60% 70% 80%
T
ập
l
ớ
n
1
-I
te
m
se
t
Min support
1-itemset 2-itemset
0
20
40
60
20% 30% 40% 50% 60% 70% 80% 90%T
ập
l
ớ
n
1
-I
te
m
se
t
Min support
Phương pháp biểu diễn Đa thể hạt
Phương pháp biểu diễn Đơn thể hạt
PP Herrera và cộng sự
96
97
Hình 3.28: Tập hàm thuộc thu được sau khi thực hiện GA với phương pháp sử dụng
biểu diễn đa thể hạt và ĐSGT
Hình 3.28 tập các hàm thuộc biểu diễn dạng đa thể hạt của 10 thuộc tính thu
được sau khi thực hiện tối ưu bằng giải thuật GA. Có thể thấy các hàm thuộc được
xây dựng dựa trên ĐSGT của các thuộc tính có phân bố khá tốt, đảm bảo độ bao phủ
toàn miền giá trị và độ chồng lấn hợp lý.
3.6. Kết luận chương 3
Chương này luận án đề xuất phương pháp khai khá luật kết hợp mờ sử dụng
ĐSGT dựa trên cơ sở phân chia mờ miền giá trị thuộc tính với biểu diễn đơn thể hạt
và đa thể hạt. Với mỗi thuộc tính số sẽ sử dụng một cấu trúc ĐSDT để xây dựng các
hàm thuộc dạng đơn thể hạt hoặc đa thể hạt. Luận án sử dụng giải thuật di truyền để
tìm kiếm các thuộc tối ưu (hay xác định các tham số của các cấu trúc ĐSGT) dựa trên
CSDL cho trước. Kết quả nghiên cứu này cho thấy phương pháp xây dựng các tập
hàm thuộc để phân chia tập mục mờ trong bài toán khai phá luật kết hợp mờ, một
công đoạn quan trọng mà còn ít được đầu tư nghiên cứu. Việc mở rộng ĐSGT (không
chỉ có 5 hạng từ) để đáp ứng yêu cầu bài toán tối ưu hóa cả số lượng lẫn các thông số
các MF đã nêu trên sẽ vừa giải quyết tốt bài toán khai phá dữ liệu, vừa phát huy thế
mạnh của ĐSGT. Sử dụng ĐSGT có thể tăng dễ dàng số hạng từ mà vẫn đảm bảo có
được các phân hoạch mạnh dùng phân chia miền xác định của mục. Nội dung của
chương này được công bố trong các công trình [iii, iv].
Kết quả của luận án được thử nghiệm với 6 CSDL gồm: FAM95, pollution,
stulong, basketball, quake, stock. Các CSDL này được lấy từ kho dữ liệu UCI
(https://archive.ics.uci.edu).
98
Phương pháp này khá đơn giản nhưng hiệu quả trong việc xây dựng các tập
mờ phân chia miền giá trị thuộc tính. Cách phân chia miền mờ vừa đảm bảo đáp ứng
tốt các tiêu chí về hệ tập mờ, vừa mang lại sự đáp ứng tốt về mặt ngữ nghĩa cho các
luật khai phá được. Luận án đã thử nghiệm với hai phương pháp biểu diễn dữ liệu:
biểu diễn đơn thể hạt và biểu diễn đa thể hạt. Các luật khai phá được bao gồm cả các
luật mang tính khái quát cao và các luật chi tiết, phụ thuộc vào tầng biểu diễn dữ liệu
trong cấu trúc đa thể hạt ta xây dựng thông qua ĐSGT.
99
KẾT LUẬN VÀ KIẾN NGHỊ
Với mục tiêu tìm kiếm một phương pháp luận cho phép phát hiện tri thức dạng
luật mờ, như luật kết hợp mờ, luật mờ dạng ngôn ngữ, từ các kho dữ liệu số. Luận
án sử dụng ĐSGT thay cho lý thuyết tập mờ để nghiên cứu một số vấn đề về khai phá
luật kết hợp mờ. Luận án đề xuất phương pháp nhằm giảm thời gian, cũng như đề
xuất giải pháp tìm kiếm phân hoạch mờ tối ưu cho mỗi thuộc tính định lượng dựa vào
CSDL đầu vào theo một số ràng buộc cho trước. Luận án đề xuất sử dụng lý thuyết
ĐSGT và giải thuật GA áp dụng trong bài toán khai phá luật kết hợp mờ thay vì sử
dụng lý thuyết tập mờ như các phương pháp đã đề xuất trước đây.
Kết quả nghiên cứu chính của luận án là:
- Nhằm mục đích giảm thời gian khai phá luật kết hợp, luận án đề xuất phương
pháp sử dụng ĐSGT và giải pháp nén CSDL mờ. Các giao dịch mờ gần nhau sẽ được
gộp với nhau để tạo thành giao dịch mới. Ưu điểm của phương pháp này là giúp
CSDL có kích thước nhỏ hơn CSDL ban đầu giúp thời gian khai phá luật kết hợp
giảm.
- Luận án đề xuất sử dụng lý thuyết ĐSGT và giải thuật di truyền tìm kiếm hàm
thuộc dựa vào CSDL giao dịch đầu vào và một số mục tiêu của bài toán khai phá luật
kết hợp mờ. Phương pháp lập luận mờ sử dụng ĐSGT chỉ cần tập trung đến độ đo
tính mờ hay tối ưu được bộ số gia tử, số lượng tham số ít hơn so với một số phương
pháp đã đề xuất trước đây mà các tác giả sử dụng lý tuyết tập mờ giúp thời gian tối
ưu nhanh hơn. Luận án sử dụng biểu diễn tập mờ dạng đơn thể hạt để tính toán độ
thuộc của dữ liệu vào các miền mờ. Kết quả là chúng ta thu được tập các hàm thuộc
cho các thuộc tính định lượng và tập các luật kết hợp mờ.
- Luận án sử dụng biểu diễn đa thể hạt và ĐSGT cho bài toán khai phá luật kết
hợp mờ. Về mặt ngữ nghĩa, dùng biểu diễn đa thể hạt sẽ cho chúng ta các luật kết hợp
vừa có tính khái quát và có tính chi tiết. Với phương pháp luận án đề xuất, việc tính
toán liên quan đến biểu diễn đa thể hạt là tăng thêm không đáng kể về mặt phức tạp
cũng như mặt thời gian mà kết quả nhận được lại tốt hơn rất nhiều.
Mặc dù luận án đã đạt được những kết quả khá tốt, tuy nhiên các kết quả nghiên
cứu này chủ yếu tập trung vào giải pháp nén dữ liệu giao dịch và phân hoạch miền
xác định của thuộc tính thành các miền mờ dưới dạng biểu diễn đơn thể hạt và đa thể
100
hạt theo hướng tiếp cận sử dụng ĐSGT cho bài toán khai phá luật kết hợp mờ. Song,
một số nội dung liên quan đến bài toán khai phá luật kết hợp cần được tiếp tục nghiên
cứu hoàn chỉnh hơn: giải các bài toán tìm luật kết hợp phủ định, luật kết hợp có trọng
số, luật kết hợp song song, Đó là những vấn đề đặt ra cho chúng tôi cần phải có
những nghiên cứu trong thời gian tới.
101
CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN
LUẬN ÁN
i) Trần Thái Sơn, Nguyễn Tuấn Anh, Nâng cao hiệu quả khai phá luật kết hợp mờ theo
hướng tiếp cận đại số gia tử, Kỷ yếu hội nghị quốc gia lần VI về nghiên cứu cơ bản
và ứng dụng công nghệ thông tin (Fair) - Huế, 6/2013.
ii) Tran Thai Son, Nguyen Tuan Anh, Improve efficiency fuzzy association rule using
hedge algebra approach, Journal of Computer Science and Cybernetics, Vol 30, No
4, 2014.
iii) Tran Thai Son, Nguyen Tuan Anh, Hedges Algebras and fuzzy partition problem for
qualitative attributes, Journal of Computer Science and Cybernetics, V.32, N.4, 2016.
iv) Tran Thai Son, and Nguyen Tuan Anh, Partition fuzzy domain with multi-granularity
representation of data based on Hedge Algebra approach, Journal of Computer
Science and Cybernetics, vol 34, pp. 63-76, 2018.
102
TÀI LIỆU THAM KHẢO
TIẾNG VIỆT
[1] B. C. Cường, and N. D. Phước, Hệ mờ, mạng nơron và ứng dụng, Nhà xuất
bản Khoa học kỹ thuật, 2006.
[2] N. C. Hào, and N. C. Đoàn, Luật kết hợp mờ dựa trên ngữ nghĩa đại số gia tử,
Tạp chí khoa học - Đại học Huế, vol. 74A, no. 5, 2012.
[3] T. T. Sơn, Đ. N. Tiến, and P. Đ. Phong, Luật kết hợp theo cách tiếp cận Đại
số gia tử, Journal of Computer Science and Cybernetics, vol. 27, no. 4, 2012.
[4] H. V. Thông, N. C. Hồ, and N. Đ. Dư, Một phương pháp sinh hệ luật mờ
Mamdani cho bài toán hồi quy với ngữ nghĩa Đại số gia tử, Tin học và điều
khiển học, vol. 30, no. 3, pp. 227-238, 2014.
TIẾNG ANH
[5] C.-M. Lin, Y.-L. Hsieh, K.-C. Yin, M.-C. Hung, and D.-L. Yang, ADMiner:
An Incremental Data Mining Approach Using a Compressed FP-tree, Journal
of Software, vol. 8, no. 8, 2013.
[6] R. J. Kuo, C. M. Chao, and Y. Chiu, Application of particle swarm
optimization to association rule mining, Applied Soft Computing, vol. 11, no.
1, pp. 326-336, 2011.
[7] A. Agarwal, and N. Nanavati, Association rule mining using hybrid GA-PSO
for multi-objective optimisation, Computational Intelligence and Computing
Research (ICCIC), 2016 IEEE International Conference on, IEEE, 2016.
[8] R. J. Miller, and Y. Yang, Association rules over interval data, ACM
SIGMOD Record, vol. 26, no. 2, pp. 452-461, 1997.
[9] U. Can, and B. Alatas, Automatic Mining of Quantitative Association Rules
with Gravitational Search Algorithm, International Journal of Software
Engineering and Knowledge Engineering, vol. 27, no. 03, pp. 343-372, 2017.
[10] L. J. Eshelman, The CHC adaptive search algorithm: How to have safe search
when engaging in nontraditional genetic recombination, Foundations of
genetic algorithms, pp. 265-283: Elsevier, 1991.
[11] C.-H. Chen, V. S. Tseng, and T.-P. Hong, Cluster-based evaluation in fuzzy-
genetic data mining, IEEE transactions on fuzzy systems, vol. 16, no. 1, pp.
249-262, 2008.
[12] M. Kaya, and R. Alhajj, A clustering algorithm with genetically optimized
membership functions for fuzzy association rules mining, Fuzzy Systems,
2003. FUZZ'03. The 12th IEEE International Conference on, IEEE, 2003.
[13] L. A. Zadeh, The concept of a linguistic variable and its application to
approximate reasoning—I, Information sciences, vol. 8, no. 3, pp. 199-249,
1975.
[14] H. B. Yadav, and D. K. Yadav, Construction of membership function for
software metrics, Procedia Computer Science, vol. 46, pp. 933-940, 2015.
[15] C. Mencar, M. Lucarelli, C. Castiello, and A. M. Fanelli, Design of Strong
Fuzzy Partitions from Cuts, EUSFLAT Conf., 2013.
103
[16] P. Pulkkinen, and H. Koivisto, A dynamically constrained multiobjective
genetic fuzzy system for regression problems, IEEE Transactions on Fuzzy
Systems, vol. 18, no. 1, pp. 161-177, 2010.
[17] R. T. Ng, and J. Han, Efficient and Effective Clustering Methods for Spatial
Data Mining, Proceedings of VLDB, Citeseer, 1994.
[18] J.-Y. Dai, D.-L. Yang, J. Wu, and M.-C. Hung, An efficient data mining
approach on compressed transactions, World Academy of Science,
Engineering and Technology, vol. 3, pp. 76-83, 2008.
[19] N. C. Ho, and W. Wechler, Extended hedge algebras and their application to
fuzzy logic, Fuzzy sets and systems, vol. 52, no. 3, pp. 259-281, 1992.
[20] D. Meng, and Z. Pei, Extracting linguistic rules from data sets using fuzzy
logic and genetic algorithms, Neurocomputing, vol. 78, no. 1, pp. 48-54, 2012.
[21] R. Agrawal, and R. Srikant, Fast algorithms for mining association rules,
Proc. 20th int. conf. very large data bases, VLDB, 1994.
[22] C.-H. Chen, T.-P. Hong, Y.-C. Lee, and V. S. Tseng, Finding Active
Membership Functions for Genetic-Fuzzy Data Mining, International Journal
of Information Technology & Decision Making, vol. 14, no. 06, pp. 1215-
1242, 2015.
[23] A. Fu, M. H. Wong, S. C. Sze, W. C. Wong, W. L. Wong, and W. K. Yu,
Finding fuzzy sets for the mining of fuzzy association rules for numerical
attributes, Proceedings of the first international symposium on intelligent data
engineering and learning, 1998.
[24] A. Mangalampalli, and V. Pudi, FPrep: Fuzzy clustering driven efficient
automated pre-processing for fuzzy association rule mining, Fuzzy Systems
(FUZZ), 2010 IEEE International Conference on, IEEE, 2010.
[25] N. C. Ho, and N. V. Long, Fuzziness measure on complete hedge algebras and
quantifying semantics of terms in linear hedge algebras, Fuzzy Sets and
Systems, vol. 158, no. 4, pp. 452-471, 2007.
[26] N. C. Ho, T. T. Son, T. D. Khang, and L. X. Viet, Fuzziness Measure,
Quantified Sematic Mapping and Interpolative Method of Approximate
Reasoning in Medical Expert Systems, Journal of Computer Science and
Cybernetics, vol. 18, no. 3, pp. 237-252, 2002.
[27] A. Gyenesei, A fuzzy approach for mining quantitative association rules, Acta
Cybern., vol. 15, no. 2, pp. 305-320, 2001.
[28] J. Alcala-Fdez, R. Alcala, and F. Herrera, A fuzzy association rule-based
classification model for high-dimensional problems with genetic rule selection
and lateral tuning, IEEE Transactions on Fuzzy Systems, vol. 19, no. 5, pp.
857-872, 2011.
[29] A. Mangalampalli, and V. Pudi, Fuzzy association rule mining algorithm for
fast and efficient performance on very large datasets, Fuzzy Systems, 2009.
FUZZ-IEEE 2009. IEEE International Conference on, IEEE, 2009.
[30] C. Kuok, A. Fu, and M. Wong, Fuzzy association rules in large databases with
quantitative attributes, ACM SIGMOD Records, 1998.
[31] C. Kuok, A. Fu, and M. Wong, Fuzzy association rules in large databases with
quntitative attributes, ACM SIGMOD Records, 1998.
[32] C. A. Kumar, Fuzzy Clustering-Based Formal Concept Analysis for
Association Rules Mining, Applied Artificial Intelligence, vol. 26, no. 3, pp.
274-301, 2012.
104
[33] C.-H. Chen, A.-F. Li, and Y.-C. Lee, A fuzzy coherent rule mining algorithm,
Applied Soft Computing, vol. 13, no. 7, pp. 3422-3428, 2013.
[34] C.-W. Lin, T.-P. Hong, and W.-H. Lu, Fuzzy data mining based on the
compressed fuzzy fp-trees, Fuzzy Systems, 2009. FUZZ-IEEE 2009. IEEE
International Conference on, IEEE, 2009.
[35] W. Siler, and J. J. Buckley,Fuzzy expert systems and fuzzy reasoning: John
Wiley & Sons, 2005.
[36] K. Loquin, and O. Strauss, Fuzzy histograms and density estimation, Soft
methods for integrated uncertainty modelling, pp. 45-52: Springer, 2006.
[37] G. Castellano, A. M. Fanelli, and C. Mencar, Fuzzy Information Granulation
with Multiple Levels of Granularity, Granular Computing and Intelligent
Systems, pp. 185-202: Springer, 2011.
[38] G. Pradeep, and V. Ravi, Fuzzy Multi-Objective Association Rule Mining
Using Evolutionary Computation, Handbook of Research on Intelligent
Techniques and Modeling Applications in Marketing Analytics, pp. 119, 2016.
[39] H. Ishibuchi, and T. Yamamoto, Fuzzy rule selection by multi-objective
genetic local search algorithms and rule evaluation measures in data mining,
Fuzzy Sets and Systems, vol. 141, no. 1, pp. 59-88, 2004.
[40] L. A. Zadeh, Fuzzy sets, Information and control, vol. 8, no. 3, pp. 338-353,
1965.
[41] J. C. Bezdek, D. Dubois, and H. Prade,Fuzzy sets in approximate reasoning
and information systems: Springer Science & Business Media, 2012.
[42] T.-P. Hong, C.-H. Chen, Y.-C. Lee, and Y.-L. Wu, Genetic-fuzzy data mining
with divide-and-conquer strategy, IEEE Transactions on Evolutionary
Computation, vol. 12, no. 2, pp. 252-265, 2008.
[43] C.-H. Chen, T.-P. Hong, V. S. Tseng, and C.-S. Lee, A genetic-fuzzy mining
approach for items with multiple minimum supports, Soft Computing, vol. 13,
no. 5, pp. 521-533, 2009.
[44] K. Deb, Genetic Algorithm in Search and Optimization, Indian Institute of
Technology, Kanpur, India, 1998.
[45] W. Wang, and S. Bridges, Genetic algorithm optimization of membership
functions for mining fuzzy association rules, Department of Computer Science
Mississippi State University, vol. 2, 2000.
[46] C.-K. Ting, T.-C. Wang, R.-T. Liaw, and T.-P. Hong, Genetic algorithm with
a structure-based representation for genetic-fuzzy data mining, Soft
Computing, vol. 21, no. 11, pp. 2871-2882, 2016.
[47] N. C. Ho, W. Pedrycz, D. T. Long, and T. T. Son, A genetic design of linguistic
terms for fuzzy rule based classifiers, International Journal of Approximate
Reasoning, vol. 54, no. 1, pp. 1-21, 2012.
[48] R. Alcalá, J. Alcalá-Fdez, M. J. Gacto, and F. Herrera, Genetic learning of
membership functions for mining fuzzy association rules, Fuzzy Systems
Conference, 2007. FUZZ-IEEE 2007. IEEE International, IEEE, 2007.
[49] N. C. Ho, and W. Wechler, Hedge algebras: an algebraic approach to
structure of sets of linguistic truth values, Fuzzy sets and systems, vol. 35, no.
3, pp. 281-293, 1990.
[50] M. Martínez-Ballesteros, A. Troncoso, F. Martínez-Álvarez, and J. C.
Riquelme, Improving a multi-objective evolutionary algorithm to discover
105
quantitative association rules, Knowledge and Information Systems, vol. 49,
no. 2, pp. 481-509, 2015.
[51] M. J. Gacto, R. Alcalá, and F. Herrera, Interpretability of linguistic fuzzy rule-
based systems: An overview of interpretability measures, Information
Sciences, vol. 181, no. 20, pp. 4340-4360, 2011.
[52] M. Antonelli, P. Ducange, B. Lazzerini, and F. Marcelloni, Learning
concurrently data and rule bases of Mamdani fuzzy rule-based systems by
exploiting a novel interpretability index, Soft Computing, vol. 15, no. 10, pp.
1981-1998, 2011.
[53] J. Alcalá-Fdez, R. Alcalá, M. J. Gacto, and F. Herrera, Learning the
membership function contexts for mining fuzzy association rules by using
genetic algorithms, Fuzzy Sets and Systems, vol. 160, no. 7, pp. 905-921,
2009.
[54] R. Agrawal, T. Imieliński, and A. Swami, Mining association rules between
sets of items in large databases, Acm sigmod record, ACM, 1993.
[55] T.-P. Hong, C.-S. Kuo, and S.-C. Chi, Mining association rules from
quantitative data, Intelligent data analysis, vol. 3, no. 5, pp. 363-376, 1999.
[56] C. H. Cai, A. W.-C. Fu, C. Cheng, and W. Kwong, Mining association rules
with weighted items, Database Engineering and Applications Symposium,
1998. Proceedings. IDEAS'98. International, IEEE, 1998.
[57] K. C. Chan, and W.-H. Au, Mining fuzzy association rules, Proceedings of the
sixth international conference on Information and knowledge management,
ACM, 1997.
[58] S.-z. Li, and S.-l. Chen, Mining fuzzy association rules by using nonlinear
particle swarm optimization, Quantitative Logic and Soft Computing 2010, pp.
621-630: Springer, 2010.
[59] C. M. Kuok, A. Fu, and M. H. Wong, Mining fuzzy association rules in
databases, ACM Sigmod Record, vol. 27, no. 1, pp. 41-46, 1998.
[60] C.-K. Ting, R.-T. Liaw, T.-C. Wang, and T.-P. J. M. C. Hong, Mining fuzzy
association rules using a memetic algorithm based on structure
representation, Memetic Computing, vol. 10, no. 1, pp. 15-28, 2018.
[61] W. Zhang, Mining fuzzy quantitative association rules, Tools with Artificial
Intelligence, 1999. Proceedings. 11th IEEE International Conference on,
IEEE, 1999.
[62] D. L. Olson, and Y. Li, Mining fuzzy weighted association rules, System
Sciences, 2007. HICSS 2007. 40th Annual Hawaii International Conference
on, IEEE, 2007.
[63] B. Minaei-Bidgoli, R. Barmaki, and M. Nasiri, Mining numerical association
rules via multi-objective genetic algorithms, Information Sciences, vol. 233,
pp. 15-24, 2013.
[64] M. Kaya, and R. Alhajj, Mining optimized fuzzy association rules using multi-
objective genetic algorithm, 8th IEEE International Conference on Intelligent
Engineering Systems, Cluj-Napoca, Romania, 2004.
[65] R. Srikant, and R. Agrawal, Mining quantitative association rules in large
relational tables, Acm Sigmod Record, ACM, 1996.
[66] G. Wang, J. Xu, Q. Zhang, and Y. Liu, Multi-granularity intelligent
information processing, Rough Sets, Fuzzy Sets, Data Mining, and Granular
Computing, pp. 36-48: Springer, 2015.
106
[67] M. Antonelli, P. Ducange, B. Lazzerini, and F. Marcelloni, Multi-objective
evolutionary design of granular rule-based classifiers, Granular Computing,
vol. 1, no. 1, pp. 37-58, 2015.
[68] M. Antonelli, P. Ducange, B. Lazzerini, and F. Marcelloni, Multi-objective
evolutionary learning of granularity, membership function parameters and
rules of Mamdani fuzzy systems, Evolutionary Intelligence, vol. 2, no. 1-2, pp.
21, 2009.
[69] C.-H. Chen, T.-P. Hong, V. S. Tseng, and L.-C. Chen, Multi-objective genetic-
fuzzy data mining, International Journal of Innovative Computing Information
and Control, vol. 8, no. 10A, pp. 6551-6568, 2012.
[70] M. Kaya, Multi-objective genetic algorithm based approaches for mining
optimized fuzzy association rules, Soft computing, vol. 10, no. 7, pp. 578-586,
2006.
[71] A. Ghosh, and B. Nath, Multi-objective rule mining using genetic algorithms,
Information Sciences, vol. 163, no. 1-3, pp. 123-133, 2004.
[72] H. R. Qodmanan, M. Nasiri, and B. Minaei-Bidgoli, Multi objective
association rule mining with genetic algorithm without specifying minimum
support and minimum confidence, Expert Systems with applications, vol. 38,
no. 1, pp. 288-298, 2011.
[73] M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li, New Algorithms for Fast
Discovery of Association Rules, KDD, 1997.
[74] H. Kalia, S. Dehuri, A. Ghosh, and S.-B. Cho, On the mining of fuzzy
association rule using multi-objective genetic algorithms, International
Journal of Data Mining, Modelling and Management, vol. 8, no. 1, pp. 1-31,
2016.
[75] A. Gupta, S. Jain, and A. J. A. a. S. Tiwari, Optimization and Improvement of
association rule mining using genetic algorithm and fuzzy logic, 2019.
[76] U. K. Patel, Optimization of Association Rule Mining Using Genetic
Algorithm, Conference Proceeding of International Conference on Recent
Innovation in Science, Technology and Management, 2016.
[77] M. Saggar, A. K. Agrawal, and A. Lad, Optimization of association rule
mining using improved genetic algorithms, Systems, Man and Cybernetics,
2004 IEEE International Conference on, IEEE, 2004.
[78] H. Zheng, J. He, G. Huang, and Y. Zhang, Optimized fuzzy association rule
mining for quantitative data, Fuzzy Systems (FUZZ-IEEE), 2014 IEEE
International Conference on, IEEE, 2014.
[79] Z. Makani, S. Arora, and P. Kanikar, A Parallel Approach to Combined
Association Rule Mining, International Journal of Computer Applications, vol.
62, no. 15, 2013.
[80] S. Mishra, D. Mishra, and S. K. Satapathy, Particle swarm optimization based
fuzzy frequent pattern mining from gene expression data, Computer and
Communication Technology (ICCCT), 2011 2nd International Conference on,
IEEE, 2011.
[81] M. Fazzolari, R. Alcala, Y. Nojima, H. Ishibuchi, and F. Herrera, A review of
the application of multiobjective evolutionary fuzzy systems: Current status
and further directions, IEEE Transactions on Fuzzy systems, vol. 21, no. 1,
pp. 45-65, 2013.
107
[82] Y. Yao, A triarchic theory of granular computing, Granular Computing, vol.
1, no. 2, pp. 145-157, 2016.
[83] T.-P. Hong, C.-H. Chen, Y.-L. Wu, and Y.-C. Lee, Using divide-and-conquer
GA strategy in fuzzy data mining, Computers and Communications, 2004.
Proceedings. ISCC 2004. Ninth International Symposium on, IEEE, 2004.
[84] L. Yan, Z. Pei, and F. Ren, Constructing and Managing Multi-Granular
Linguistic Values Based on Linguistic Terms and Their Fuzzy Sets, IEEE
Access, vol. 7, pp. 152928-152943, 2019.
[85] N. C. Ho, T. T. Son, H. V. Thong, and N. V. Long, LFoC-Interpretability of
Linguistic Rule Based Systems and its Applications To Solve Regression
Problems, International Journal of Computer Technology & Applications, vol.
8, no. 2, pp. 94-117, 2017.