Luận văn Nghiên cứu và ứng dụng phương pháp khai khoáng luật kết hợp trên dữ liệu giáo dục

-28- CHƯƠNG 3: KHAI KHOÁNG DỮ LIỆU BẰNG LUẬT KẾT HỢP 3.1 Sơ lược về khai khoáng dữ liệu [14] 3.1.1 Khái niệm khai khoáng dữ liệu và quá trình khám phá tri thức Khai khoáng dữ liệu ñược ñịnh nghĩa là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu ñược lưu trữ trong các cơ sở dữ liệu (CSDL), kho dữ liệu. Hiện nay, ngoài thuật ngữ khai khoáng dữ liệu, người ta còn dùng một số thuật ngữ khác có ý nghĩa tương tự như: Khai khoáng tri thức từ CSDL, trích lọc dữ liệu, phân tích dữ liệu/mẫu, khảo cổ dữ liệu, nạo vét dữ liệu. Nhiều người coi khai khoáng dữ liệu và một số thuật ngữ thông dụng khác như khám phá tri thức trong CSDL (Knowledge Discovery in Databases-KDD) là như nhau. Những người khác lại xem khai khoáng dữ liệu ñơn giản là một bước chủ yếu trong tiến trình KDD. Toàn bộ tiến trình KDD ñược mô tả trong hình sau: Hình 3.1: Tiến trình KDD 1) Làm sạch dữ liệu (data cleaning): Loại bỏ các dữ liệu không thích hợp. Cơ sở dữ liệu Làm sạch dữ liệu Tích hợp dữ liệu Kho dữ liệu Chọn dữ liệu Dữ liệu có liên quan Khai khoáng dữ liệu. Mẫu dữ liệu. Tri thức -29- 2) Tích hợp dữ liệu (data integration): Tích hợp dữ liệu từ các nguồn khác nhau như: CSDL, Kho dữ liệu, … 3) Chọn dữ liệu (data selection): Ở bước này, những dữ liệu liên quan sẽ ñược thu thập từ các nguồn dữ liệu ban ñầu. 4) Chuyển ñổi dữ liệu (data transformation): Trong bước này, dữ liệu sẽ ñược chuyển ñổi về dạng phù hợp cho việc khai khoáng bằng cách thực hiện các thao tác nhóm hoặc tập hợp. 5) Khai khoáng dữ liệu (data mining): Là giai ñoạn thiết yếu, trong ñó các phương pháp thông minh sẽ ñược áp dụng ñể trích xuất ra các mẩu dữ liệu. 6) ðánh giá mẫu (pattern evaluation): ðánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa vào một số phép ño. 7) Biểu diễn tri thức (Knowledge presentation): Sử dụng các kỹ thuật biểu diễn và trực quan hoá ñể biểu diễn tri thức khai khoáng ñược cho người sử dụng. Theo quan ñiểm khai khoáng dữ liệu là một tiến trình quan trọng trong tiến trình khai khoáng dữ liệu từ nhiều dữ liệu trong nhiều cơ sở dữ liệu, kho dữ liệu hoặc những nơi chứa thông tin khác. Vì vậy, kiến trúc của một hệ thống khai khoáng dữ liệu có thể gồm những thành phần sau ñây: Hình 3.2: Kiến trúc của một hệ thống Khai khoáng dữ liệu Cơ sở dữ liệu Kho dữ liệu Làm sạch và tích hợp dữ liệu. Lọc dữ liệu Máy chủ của cơ sở dữ liệu hoặc kho dữ liệu Bộ máy khai khoáng dữ liệu ðánh giá mẫu Giao diện ñồ họa dành cho người dùng Cơ sở tri thức -30-
Cơ sở dữ liệu, kho dữ liệu, hoặc những nơi chứa thông tin khác: Những kỹ thuật làm sạch và tích hợp dữ liệu có thể ñược thực hiện trên những dữ liệu này.
Server của cơ sở dữ liệu hoặc kho dữ liệu: Server của cơ sở dữ liệu hoặc kho dữ liệu phải ñáng tin cậy cho việc tìm nạp dữ liệu có liên quan, dựa trên yêu cầu người dùng.
Cơ sở tri thức: ðây là miền tri thức ñược dùng ñể ñịnh hướng tìm kiếm hoặc ñánh giá tính ñáng chú ý của những mẫu kết quả, có thể bao gồm những phân cấp về khái niệm, ñược dùng ñể tổ chức những thuộc tính hoặc giá trị thuộc tính thành những cấp của sự trừu tượng hoá.
Bộ máy khai khoáng dữ liệu: ðây là ñiểm cốt yếu nhất của hệ thống khai khoáng dữ liệu, gồm có một loạt những module chức năng như mô tả, phân tích tính kết hợp, phân loại, tiến hoávà phân tích ñộ lệch.
Module ñánh giá mẫu: Thành phần này thường dùng những giới hạn ñược lưu trong cơ sở tri thức ñể thực hiện ñánh giá.
Giao diện ñồ hoạ dành cho người dùng: Thành phần này cho phép người dùng chỉ ñịnh hoặc cung cấp thông tin cho việc khai khoáng dữ liệu, ngoài ra nó còn cho phép người dùng xem cơ sở dữ liệu, hoặc các cấu trúc ñể tực ñánh giá mẫu ñã khai khoáng ñồng thời có khả năng trình bày các mẫu kết quả theo những dạng khác nhau. 3.1.2 Các loại dữ liệu thường ñược khai khoáng Trên lý thuyết, khai khoáng dữ liệu ñược áp dụng trên tất cả các loại dữ liệu bao gồm: các cơ sở dữ liệu quan hệ, kho dữ liệu, những cơ sở dữ liệu giao tác, những hệ thống cơ sở dữ liệu tiên tiến, flat file (những tập tin không có cấu trúc), www. Một hệ cơ sở dữ liệu, còn gọi là hệ quản trị cơ sở dữ liệu (database management system (DBMS)), bao gồm một loạt những dữ liệu có sự tương quan, -31- ñược gọi là cơ sở dữ liệu, một tập những chương trình phần mềm ñể quản lý và truy cập dữ liệu.
Cơ sở dữ liệu quan hệ: Một cơ sở dữ liệu quan hệ là một tập những bảng dữ liệu, mỗi bảng có một tên phân biệt. Mỗi bảng bao gồm một tập các thuộc tính (các cột hoặc các trường) và thường lưu trữ rất nhiều mẫu tin. Mỗi mẫu tin trong một bảng quan hệ thể hiện một ñối tượng ñược xác ñịnh bởi một khoá phân biệt và mô tả bởi một tập các giá trị thuộc tính. Ví dụ: Một công ty bán hàng gia dụng có thể ñược mô tả bởi những bảng quan hệ sau: khách hàng, mặt hàng, nhân viên, chi nhánh mỗi bảng chứa các thuộc tính thể hiện các ñối tượng tương ứng. Các quan hệ có thể xảy ra giữa các bảng như mua hàng (khách hàng mua các mặt hàng nào tại cửa hàng nào do nhân viên nào thu ngân,…), làm việc tại (nhân viên làm việc tại cửa hàng nào), …
Kho dữ liệu: Một kho dữ liệu là nơi chứa thông tin ñược thu thập từ nhiều nguồn khác nhau ñược lưu trữ dưới một lược ñồ thống nhất và thường ñặt tại một vị trí xác ñịnh. Những kho dữ liệu ñược xây dựng hướng theo một tiến trình làm sạch dữ liệu, chuyển ñổi dữ liệu, tích hợp dữ liệu và làm mới dữ liệu ñịnh kỳ. Cấu trúc thực sự của kho dữ liệu có thể là một kho dữ liệu quan hệ hoặc một khối dữ liệu ña chiều. Ví dụ: Giả sử công ty hàng gia dụng trên là công ty ña quốc gia, họ có nhiều chi nhánh ở nhiều nơi, mỗi chi nhánh có một cơ sở dữ liệu riêng. Khi tích hợp lại, kho dữ liệu có thể ở dạng khối 3 chiều, bao gồm: ñịa chỉ chi nhánh (Việt Nam, Hàn Quốc, Thái Lan,…), thời gian (Quí 1, quí 2, quí 3, quí 4 (hoặc theo tháng, năm, …)) và mặt hàng (kem ñánh răng, dầu gội ñầu, …)
Cơ sở dữ liệu giao tác: Một cơ sở dữ liệu giao tác bao gồm một tập tin, trong ñó mỗi mẫu tin trình bày một cuộc giao dịch. Một giao tác thường bao gồm một số hiệu xác ñịnh và riêng biệt thể hiện cuộc giao dịch ñó (trans_ID)và một danh sách những mặt hàng tạo nên giao dịch ñó. Cơ sở dữ liệu giao tác có thể có thêm một số bảng phù hợp với nó bao gồm những thông tin về bán hàng như ngày thực hiện giao dịch, số hiệu khách hàng, số hiệu của người bán hàng,… -32-
Những hệ cơ sở dữ liệu tiên tiến và những ứng dụng cơ sở dữ liệu tiên tiến: Những ứng dụng cơ sở dữ liệu mới như việc nắm bắt những dữ liệu thuộc về không gian (như bản ñồ), dữ liệu thiết kế máy kỹ thuật (như xây nhà, làm các thành phần hệ thống, mạch tích hợp,…), những siêu văn bản, những dữ liệu ña phương tiện (như văn bản, hình ảnh, âm thanh, video,…), dữ liệu liên quan ñến thời gian và www. Những ứng dụng này yêu cầu có những cấu trúc dữ liệu hiệu quả, những phương pháp leo thang ñể nắm bắt những cấu trúc phức tạp của ñối tượng và những thay ñổi thường xuyên. ðáp ứng yêu cầu này, những hệ dữ liệu tiên tiến và những hệ dữ liệu hướng ứng dụng xác ñịnh ñã ñược phát triển. Những hệ thống này bao gồm các hệ cơ sở dữ liệu hướng ñối tượng và hướng quan hệ, những hệ cơ sở dữ liệu thuộc về không gian, … 3.2 Khai khoáng dữ liệu theo phương pháp luật kết hợp Việc khai khoáng luật kết hợp là việc tìm ra những sự kết hợp ñáng chú ý hoặc những mối quan hệ tương quan giữa những tập các mục dữ liệu khổng lồ. Việc khai khoáng những quan hệ này giúp ích nhiều trong việc ra các quyết ñịnh trong kinh doanh. Phương pháp khai khoáng bằng luật kết hợp ñược Agrawal ñưa ra vào năm 1993 [7] và Apriori [8] là một trong những thuật toán ñầu tiên ñược ñề xuất. 3.2.1 Khái niệm Giả sử I = {i1, i2, …,im} là tập các mặt hàng. D là tập hợp các lượt mua hàng T trong cơ sở dữ liệu. (D = {T1,T2,…Tn}) Trong ñó, T là tập con của I hoặc bằng I. A,B là tập những mặt hàng (A, B là tập con của I hoặc bằng I với A giao B bằng rỗng). Một lượt mua hàng T ñược xem là bao gồm A nếu và chỉ nếu A là con hoặc bằng T. Luật A => B [ñộ hỗ trợ, ñộ tin cậy] ñược xem là mạnh khi luật này có ñộ hỗ trợ và ñộ tin cậy lớn hơn ñộ hỗ trợ và ñộ tin cậy tối thiểu. -33- Tập những mặt hàng thường ñược gọi là itemset, một itemset bao gồm k mặt hàng ñược gọi là k-itemset. Mức ñộ diễn ra thường xuyên của một itemset là số lượt mua hàng bao gồm itemset ñó, hay chúng còn ñược gọi là mức phổ biến hoặc ñộ hỗ trợ. Một itemset ñược gọi là thoả ñộ hỗ trợ tối thiểu (min_sup) nghĩa là nó có ñộ hỗ trợ lớn hơn hoặc bằng ñộ hỗ trợ tối thiểu. Việc khai khoáng các luật kết hợp diễn ra trong 2 bước: Bước 1: Tìm những itemset phổ biến (nghĩa là có ñộ hỗ trợ thoả mãn min_sup) Bước 2: Tạo ra những luật kết hợp mạnh từ những itemset phổ biến (những luật có ñộ tin cậy cao hơn ñộ tin cậy tối thiểu). 3.2.2 Khai khoáng luật kết hợp một chiều từ cơ sở dữ liệu giao tác Trong phần này ta sẽ tìm hiểu cách phát hiện các luật ñơn giản nhất (một chiều, một cấp và luận lý) bằng phương pháp cơ bản FP_Growth. 3.2.2.1 Giải thuật FP-Growth: tìm kiếm những itemset phổ biến Thuật toán FP_Growth sử dụng một cấu trúc dữ liệu gọi là FP_tree (Frequent Pattern tree). FP_tree là một thể hiện cô ñộng các thông tin có liên quan ñến tính thường xuyên của các tập mục trong CSDL. Mỗi nhánh của cây FP_tree thể hiện một tập mục phổ biến. Các nút dọc theo các nhánh ñược lưu trữ theo thứ tự giảm dần của tính phổ biến . Các mục ở lá của cây có tính phổ biến thấp nhất. Cây FP_tree có một bảng header kết hợp với nó. Bảng header lưu các mục cùng với số lần xuất hiện của nó trong CSDL theo thứ tự giảm dần của tính phổ biến. Mỗi mục của bảng chứa một nút ñầu danh sách liên kết với tất cả các nút của cây FP_tree mà nút ñó có tên trùng với tên của nó. Phương pháp FP_Growth chỉ cần duyệt CSDL 2 lần ñể khai khoáng tất cả các tập mục phổ biến. Quét lần thứ nhất ñể xác ñịnh tần xuất của từng tập mục trong CSDL. Quét lần thứ hai ñể xây dựng cây FP_tree. Cấu trúc 1 nút của cây gồm: tên -34- mục, bộ ñếm, liên kết ñến các nút tiếp theo trên cây có cùng tên.. Ta dựa vào cây FP_tree ñể tìm các tập mục phổ biến. Các bước của thuật toán FP_Growth: Bước 1: Duyệt CSDL ñể tìm các mục riêng biệt trong CSDL và ñộ hỗ trợ tương ứng của nó. Loại bỏ các mục có ñộ hỗ trợ nhỏ hơn minsup. Sắp xếp các mục theo thứ tự giảm dần của ñộ hỗ trợ vào bảng Header Bước 2: Duyệt CSDL lần 2 ñể xây dựng cây FP_tree. Tạo nút gốc NULL cho cây T. Duyệt tập giao dịch thứ nhất sắp xếp theo thứ tự trong tập L. Chèn vào cây T . Nếu phần ñầu của tập mục không trùng với bất cứ phần ñầu của tập mục giao dịch ñã xét thì tập hợp các mục ñó ñược chèn vào cây như một nhánh của cây và bộ ñếm của mỗi nút ban ñầu là 1. Nguợc lại thì phần ñầu của tập mục của giao dịch ñang xét sẽ ñược chia sẻ với phần ñầu nhánh thể hiện giao dịch ñã xét. Mỗi nút trên ñoạn nhánh chia sẻ bộ ñếm ñược tăng lên 1 ñơn vị, phần còn lại với mỗi mục sẽ ñược tạo một nút và ñược nối liền với nhánh ñược chia sẻ ở phần ñầu. Tạo liên kết từ bảng Header ñến các mục tương ứng. Tiếp tục duyệt CSDL và chèn vào cây cho ñến khi hết CSDL. Thuật toán xây dựng cây FP_tree 1) Procedure INSERT_TREE(string[p], Tree có gốc T) 2) If T có nút con N mà N.itemname = p 3) Then N.Count ++ 4) ELSE 5) Tạo nút mới N 6) N.itemname = p, N.Count = 1; 7) Liên kết bảng từ p ñến N 8) If p khác rỗng 9) Then Insert_tree(N, p); p: là mục ñầu tiên trong danh sách các tập mục P của giao dịch ñang xét Ví dụ thuật toán FP_Growth Giả sử ta có tập dữ liệu D với Minsup=22%, minconf=70% -35- Bảng 3.1 Dữ liệu mẫu TID DANH SÁCH CÁC MỤC T1 1 2 5 T2 2 4 T3 2 3 T4 1 2 4 T5 1 3 T6 2 3 T7 1 3 T8 1 2 3 5 T9 1 2 3 Duyệt CSDL lần 1: tìm ñộ hỗ trợ tương ứng của 1 item Bảng 3.2 Kết quả duyệt lần 1 Mục (item) Số lần xuất hiện ðộ hỗ trợ 1 6 6/9*100%=66,6% 2 7 7/9*100%=77,7% 3 6 7/9*100%=77,7% 4 2 2/9*100%=22% 5 2 2/9*100%=22% Ở ñây ta không bỏ mục nào vì ñộ hỗ trợ ñều thỏa minsup. Sắp xếp lại các item theo thứ tự giảm dần của ñộ hỗ trợ vào bảng Header Bảng 3.3 Bảng Header Item ðộ hỗ trợ 2 7 1 6 3 6 4 2 5 2 Duyệt CSDL lần 2 : xây dựng cây FP_tree Duyệt tập giao dịch thứ 1 T1{1,2,5} và sắp theo thứ tự trong bảng Header  T1{2,1,5} Ta có ñược nhánh ñầu tiên của cây FP_tree với chỉ số mỗi nút là 1 -36- Hình 3.3: Bước 1 xây dựng cây FP Tương tự ta duyệt tập giao dịch thứ 2 T2{2,4} Ta thấy chỉ số của nút 2 tăng từ 1 lên 2 vì nút 2 dùng chung giữa T1 và T2 Hình 3.4: Bước 2 xây dựng cây FP Tiếp tục duyệt ñến hết CSDL ta thu ñược cây FP_tree -37- Hình 3.5: Cây FP Tìm tập mục thường xuyên từ cây FP_tree Dựa vào liên kết từ bảng Header ta ñi tìm cây FP_tree cho từng item VD: Ta xét item ”5” Hình 3.6: Tìm tập thường xuyên từ cây FP Dựa vào cây ta tìm ñược 2 phần ñược chọn là {(2:7),(1:4),(5:1)}, {(2:7),(1:4),(3:2),(5:1)}. Ở mỗi nhánh ta lấy minsup, ở ví dụ này minsup nhánh thứ nhất và thứ 2 là 1 {(2:1),(1:1),(5:1)}, {(2:1),(1:4),(3:1),(5:1)} -38- Giao 2 phần này lại ta có {(2:2),(1:2),(5:2)} tất cả các item ñều >= minsup (2/9*100% = 22%). Ta tìm ñược tập mục thường xuyên thứ nhất {2,1,5} với minsup=22%. Tương tự ta tìm hết tất cả các item trong bảng Header. Kết quả tìm ñược 2 tập thường xuyên {2,1,5}, {2,4}. Kế ñến là phần tìm luật kết hợp từ các tập mục thường xuyên. 3.2.2.2 Việc tạo ra những luật kết hợp từ những itemset phổ biến Sau khi ñã tìm ra những itemset phổ biến, những itemset này sẽ ñược dùng ñể tạo ra những luật mạnh (là những luật thoả mãn ñộ hỗ trợ tối thiểu (min_sup) và ñộ tin cậy tối thiểu (min_conf)) như sau:
Với mỗi itemset phổ biến L, tạo ra tất cả các tập con khác rỗng của L.
Với mỗi tập con khác rỗng s của L, cho ra một luật: “s => (L-s)” nếu ñộ tin cậy của nó lớn hơn hoặc bằng min_conf. Vì những luật này ñược tạo ra từ những itemset phổ biến nên nó hiển nhiên thoả ñiều kiện min_sup. VD: nếu {A,B,C,D} là itemset phổ biến thì có các luật dự kiến gồm: ABC →D, ABD →C, ACD →B, BCD→A, A →BCD, B →ACD, C →ABD, D→ABC AB →CD, AC → BD, AD → BC, BC→AD, BD →AC, CD →AB, Nếu L có k item thì có thể tạo ra 2k - 2 luật kết hợp dự kiến(bỏ qua luật L → ∅ và ∅ → L) Dựa vào tính chất của ñộ tin cậy ñể tạo ra luật có conf >= min_conf.
Nếu luật không ñược sinh ra từ cùng một itemset phổ biến thì: ñộ tin cậy của luật c(ABC →D) có thể lớn hơn hay nhỏ hơn ñộ tin cậy của luật c(AB →D)
Nhưng nếu luật ñược sinh ra từ cùng một itemset phổ biến L={A,B,C,D} thì ñộ tin cậy của các luật có thuộc tính: o c(ABC → D) ≥ c(AB → CD) ≥ c(A → BCD) -39- Hình 3.7: Trực quan về cách sinh ra luật kết hợp. 3.2.3 Khai khoáng luật kết hợp ña cấp từ cơ sở dữ liệu giao tác a. Những luật kết hợp ña cấp Trong một số ứng dụng, thật khó ñể tìm những luật kết hợp mạnh giữa những mục dữ liệu cấp thấp hoặc thô về mặt trừu tượng khi dữ liệu rải rác trong không gian tìm kiếm. Những luật mạnh ñược khám phá tại những cấp ñộ khái niệm cao có thể trình bày những tri thức về mặt ý thức chung. Tuy nhiên, những thứ có thể trình bày ý niệm chung cho một người dùng, lại là lạ lẫm với một người khác. Vì vậy những hệ thống khai khoáng dữ liệu phải cung cấp khả năng khai khoáng những luật kết hợp tại nhiều cấp trừu tượng và dễ dàng qua lại giữa những không gian trừu tượng khác nhau. b. Những phương pháp ñể khai khoáng những luật kết hợp ña cấp Ta tìm hiểu sơ qua những phương pháp khai khoáng dựa trên ñộ hỗ trợ và ñộ tin cậy. Các phương pháp này duyệt từ trên xuống ñồng thời tính toán các chỉ số về 2 giá trị này ñể tìm ra các itemset phổ biến tại mỗi cấp khái niệm. Ở mỗi cấp có thể Loại bỏ các luật Luật có ñộ tin cậy thấp -40- dùng bất kỳ phương pháp nào ñể tìm ra những itemset phổ biến. Một số kiểu phương pháp khai khoáng ña cấp:
Dùng cùng một ñộ hỗ trợ tối thiểu(min_sup) cho mọi cấp (còn gọi là uniform support)
Giảm min_sup dần tại mỗi cấp thấp hơn. Vài phương pháp giúp giảm min_sup: o ðộc lập từng cấp một: là một kiểu duyệt rộng, mỗi nút sẽ ñược duyệt, bất chấp nút cha của nó có phổ biến hay không. o Lọc chéo bằng những mục hàng ñơn. Một mục hàng thứ i chỉ ñược duyệt khi nút cha của nó là phổ biến. o Lọc chéo bằng k-itemset. Một k-itemset tại mức thứ i chỉ ñược duyệt chỉ khi k-itemset thứ k của nó tại cấp (i-1) 3.2.4 Khai khoáng luật kết hợp ña chiều từ cơ sở dữ liệu quan hệ và kho dữ liệu a. Những luật kết hợp ña chiều Trong các phần trước ta ñã ñược làm quen với những luật kết hợp một chiều dạng: Mua(x, “A”) => Mua(x,”B”) Nhưng giả sử chúng không ñược lưu trữ thành những bảng liệt kê những lượt mua hàng mà ñược lưu thành những thông tin có liên quan trong các cơ sở dữ liệu quan hệ hoặc các kho dữ liệu lớn thì những dữ liệu như vậy là ña chiều. Ví dụ: tuổi(x, “19-24”) ^ nghề nghiệp(x, “sinh vien”) => mua(x, “máy tính xách tay”) b. Việc khai khoáng những luật kết hợp ñịnh lượng Những luật kết hợp ñịnh tính là những luật kết hợp ña chiều mà trong ñó những thuộc tính bằng số ñược rời rạc hoá trong suốt quá trình khai khoáng ñể thoả -41- mãn một số tiêu chuẩn khai khoáng như cực ñại hoá ñộ tin cậy (confidence) hoặc rút gọn những luật tìm ñược. Phương pháp ñể khai khoáng những luật ña chiều (2-chiều) là phương pháp ARCS (Assiociation Rule Clustering System) mượn ý tưởng từ việc xử lý hình ảnh. Về bản chất phương pháp này ánh xạ những cặp thuộc tính ñịnh lượng trên một lưới 2 chiều cho những mẫu tin thoả ñiều kiện về thuộc tính xác ñịnh cho trước. Sau ñó, lưới 2 chiều này sẽ ñược duyệt ñể phân nhóm các ñiểm, từ ñó những luật kết hợp ñược tạo ra. c. Việc khai khoáng những luật kết hợp dựa trên khoảng cách Phương pháp như trên không nắm bắt ñược ngữ nghĩa của những dữ liệu theo khoảng thời gian vì thế nó không thể xét ñược những quan hệ về liên quan về khoảng cách giữa những ñiểm dữ liệu hoặc những khoảng thời gian. 3.2.5 Khai khoáng luật kết hợp dựa trên các ràng buộc Những ràng buộc bao gồm :
Ràng buộc về kiểu tri thức (Knowledge type constraints): Xác ñịnh kiểu tri thức nào ñược khai khoáng, ví dụ như sự kết hợp.
Ràng buộc về dữ liệu (Data constraint): Xác ñịnh tập hợp dữ liệu công việc có liên quan.
Ràng buộc về chiều/ cấp (Dimension/level constraint): Xác ñịnh kích thước của dữ liệu, hoặc cấp ñộ của cây phân cấp ñược sử dụng.
Ràng buộc về sự ñáng chú ý: ràng buộc này xác ñịnh các ngưỡng trên những số ño thống kê của những luật ñáng chú ý, như ñộ hỗ trợ (support) và ñộ tin cậy (confidence). Những ràng buộc về luật: Xác ñịnh dạng của luật dùng ñể khai khoáng, những luật này có thể là siêu luật (những khuôn mẫu về luật), hoặc việc xác ñịnh số thuộc tính lớn nhất hoặc nhỏ nhất có trong luật tổ tiên, hoặc sự thoả mãn của những thuộc tính ñặc biệt trên những giá trị thuộc tính, hoặc khối tập hợp của chúng. -42- 3.3 Một số trở ngại và giải pháp cho việc khai khoáng dữ liệu giáo dục bằng luật kết hợp [12]: Trong lĩnh vực khai khoáng luật kết hợp, hầu hết các nỗ lực nghiên cứu ñều tập trung vào hai hướng: một là cải tiến tốc ñộ các thuật toán, hai là làm nhỏ tập kết quả bằng việc áp dụng các ràng buộc vào tập kết quả sinh luật. Các thuật toán ñã ñược cải tiến rất nhiều bằng các ñề xuất mới trong chiến lược tìm kiếm, các kỹ thuật cắt tỉa và cả các cấu trúc dữ liệu. Trong khi hầu hết các thuật toán ñược cải tiến theo hướng tìm ra tất cả các luật có thể với ñộ hỗ trợ và ñộ tin cậy tối thiểu, một số thuật toán khác phát triển theo hướng cải tiến thời gian xử lý và tăng sự dễ hiểu cho người dùng thông qua việc giảm kích thước tập kết quả, kết hợp với tập tri thức liên quan. Các khó khăn trong việc áp dụng khai khoáng luật kết hợp vào dữ liệu giáo dục cũng tương tự như trên. Trong ñó, các trở ngại lớn là: thuật toán ñược sử dụng ñể khai khoáng có quá nhiều các tham số khiến người sử dụng không phải là chuyên gia khai khoáng sẽ gặp khó khăn; thứ hai là số lượng luật thu ñược thường quá nhiều và nhiều trong số ñó không thú vị cũng như khó hiểu. 3.3.1 Tìm kiếm các thông số thích hợp cho các thuật toán Các thuật toán khai khoáng luật kết hợp cần ñược cấu hình trước khi thực thi. Vì vậy, người sử dụng cần ñưa vào các giá trị phù hợp cho các tham số ñể thu ñược một số lượng luật phù hợp nhằm tránh xảy ra việc sinh ra quá nhiều hoặc quá ít luật. Một số thuật toán thông dụng cho bài toán luật kết hợp là: Apriori, FP-Growth, MagnumOpus, Closet. Hầu hết các thuật toán này ñều cần người sử dụng ñặt ra hai ngưỡng: ñộ hỗ trợ tối thiểu và ñộ tin cậy tối thiểu, sau ñó thuật toán sẽ thực thi tìm tất cả luật thỏa mãn hai ngưỡng này. ðiều này dẫn ñến việc người dùng sẽ phải thực hiện thuật toán với một số lần xác ñịnh ñể có thể tìm ra ngưỡng phù hợp cho dữ liệu của họ. Một giải phải khả thi cho vấn ñề này là sử dụng các thuật toán không cần tham số hoặc rất ít tham số. -43- 3.3.2 Khám phá ra quá nhiều luật Việc sử dụng các thuật toán luật kết hợp truyền thống thường ñơn giản và hiệu quả. Tuy nhiên, các thuật toán khai khoáng luật kết hợp lại thường cho ra một lượng khổng lồ các luật và cũng không ñảm bảo ñược tất cả các luật ñược sinh ra ñều hữu ích. ðộ hỗ trợ và ñộ tin cậy là hai yếu tố thường dùng ñể lọc ra tập luật thú vị hơn. Nhưng dù là hai tham số này ñã giúp cắt tỉa bớt rất nhiều luật, vẫn còn ràng buộc khác về các thuộc tính mà không thể hiện trực tiếp trên cả hai vế của luật. Một giải pháp khác cho vấn ñề này là lượng giá và hậu-cắt tỉa các luật ñã thu ñược ñể tìm ra những luật thú vị nhất cho vấn ñề ñang quan tâm. Theo truyền thống, người ta sử dụng các ñộ ño khách quan, ngoài hai ñộ ño hỗ trợ và tin cậy ñã nêu trên, còn có một số ñộ ño nổi tiếng khác như Laplace, chi-square, ñộ tương quan, entropy, gini, ñộ quan tâm, ñộ chắc chắn,... Các ñộ ño này có thể ñược dùng ñể xếp hạng các luật thu ñược theo thứ tự giúp người sử dụng có thể chọn ra các luật có giá trị cao nhất trong ñộ ño họ quan tâm. Các ñộ ño chủ quan cũng ngày càng trở nên quan trọng [3],[12]. Nói cách khác, các ñộ ño này dựa trên yếu tố chủ quan ñược người sử dụng kiểm soát. Một số ñộ ño chủ quan ñược sử dụng nhiều như:
ðộ không mong ñợi: các luật xem như thú vị nếu chúng chưa từng ñược biết tới hoặc nó mâu thuẫn với tri thức của người sử dụng.
ðộ tác ñộng: các luật xem như thú vị nếu chúng có thể ñược người sử dụng dùng ñể nâng cao bản thân họ. Gọi U là tập các ñặc tả thể hiện mảng tri thức của người sử dụng, A là tập các luật ñã ñược khám phá. Thuật toán sau ñây thể hiện một kỹ thuật cắt tỉa ñể loại bỏ các luật thừa hoặt luật không quan trọng, thông qua việc xếp hạng và phân các luật thành bốn loại:
Các luật thích nghi: một luật Ai ∈ A thích nghi với tri thức Uj của người dùng nếu cả hai vế của Ai ñều thuộc tập Uj. -44-
Các luật có hậu ñề không mong ñợi: luật Ai ∈ A chứa vế phải không mong ñợi liên quan ñến Uj ∈ U nếu vế trái của Ai khớp với Uj.
Các luật có tiền ñề không mong ñợi: luật Ai ∈ A chứa vế trái không mong ñợi liên quan ñến Uj ∈ U nếu vế phải của Ai khớp với Uj, nhưng khác với vế trái.
Các luật có hai vế không mong ñợi: luật Ai ∈ A chứa cả 2 vế không mong ñợi liên quan ñến Uj ∈ U nếu cả 2 vế của Ai không khớp với Uj. Người ta có thể dùng cơ sở dữ liệu tri thức như là một kho luật dùng cho việc ñánh giá chủ quan các luật ñã tìm ñược. Các lĩnh vực có thể cá nhân hóa dùng ñể phân tích chủ quan: phạm vi kiến thức, cấp ñộ giáo dục, ñộ khó của khóa học, ... Các kho luật sau khi ñược tạo ra, sẽ ñược các chuyên gia ñánh giá từng luật một trên cơ sở kinh nghiệm và cả yếu tố giáo dục. 3.3.3 Khám phá ra các luật rất khó hiểu Một yếu tố quan trọng ñể ñánh giá chất lượng của luật là sự dễ hiểu của nó [18]. Cho dù một trong những ñộng lực của việc rút trích luật là sự mô tả dễ hiểu trên cơ sở mô hình lý thuyết, khía cạnh chất lượng này của luật thường không thể ñược ñánh giá một cách ñộc lập bởi người sử dụng hệ thống. Kinh nghiệm và lĩnh vực kiến thức của người sử dụng ñóng vai trò quan trọng trong ñánh giá ñộ dễ hiểu. ðiều này trái ngược với ñộ chính xác ñã ñược xem như một thuộc tính bắt buộc của luật – ñược ñánh giá một cách ñộc lập với người sử dụng. Một giải pháp truyền thống là người ta tiến hành kỹ thuật ràng buộc số lượng phần tử ở hai vế của luật. Kích cỡ của mỗi vế của luật giảm xuống cũng ñồng nghĩa với việc luật sẽ dễ hiểu hơn. Một giải pháp khác là tiến hành rời rạc hóa các giá trị số dưới dạng các phân loại. Sự phân loại thì dễ hiểu hơn cho người dùng so với các con số chính xác. Một cách khác ñể cải tiến sự dễ hiểu của luật là kết hợp kiến thức và ngũ nghĩa và dùng những từ phổ biến, gần gũi với người dùng. Có thể xây dựng các bản thể học phù hợp với miền tri thức ñể khiến luật dễ hiểu hơn là ñể luật dưới góc ñộ -45- của việc nghiên cứu, ví dụ như ”thành công ở môn học A thì sẽ thành công ở môn học B”. 3.4 ðánh giá ñộ thú vị của luật trong khai khoáng dữ liệu giáo dục Dữ liệu dùng trong lĩnh vực giáo dục khác với mảng kiến thức truyền thống vốn ñược con người khám phá ở nhiều khía cạnh. Một trong số những khía cạnh là các dữ liệu ñó rất khó, ñôi khi là không thể, dùng trong so sánh nhiều phương pháp khác nhau hay ước chừng cái ñến sau và suy ra cái nào tốt nhất. Ví dụ như việc xây dựng một hệ thống chuyển ñổi văn bản viết tay sang tài liệu in. Hệ thống này cần phải tạo ra một bản in bức thư từ bản viết tay. Ta có thể thử ñược nhiều phương pháp ño ñạc hay thông số và kiểm nghiệm cái nào hoạt ñộng tốt nhất. Quá trình kiểm nghiệm khó khăn trong lĩnh vực giáo dục bởi vì dữ liệu rất linh ñộng, có thể khác biệt rất nhiều so với dữ liệu mẫu và giảng viên không thể cung cấp thời gian và liên kết tới ban kiểm ñịnh ñể thực hiện kiểm tra trên mỗi mẫu, nhất là trong thời gian thực. Ngoài ra, cần phải quan tâm ñến trực giác trong ño ñạc, các thông số hay phương pháp sử dụng trong khai khoáng dữ liệu giáo dục. Một ñiểm khác biệt khác là kích thước dữ liệu: Trong khi một lượng khổng lồ dữ liệu về quá trình học tập của sinh viên ñược thu thập, kích thước dữ liệu mẫu thường là nhỏ. ðặc thù trong các lớp học có hàng trăm sinh viên tham dự. Sinh viên có thể tất cả ñều không làm cùng bài tập hoặc cùng tham gia các hoạt ñộng. Việc thu thập dữ liệu nhiều năm là một tuỳ chọn, nhưng có nhiều ngoại lệ khi muốn phân tích các dữ liệu xưa cũ như dữ liệu từ năm ñầu tiên. Ngoài ra, thường xuyên có sự thay ñổi giữa việc cung ứng một khoá học có tác ñộng ñến các thuộc tính thường nhật của dữ liệu (chẳng hạn không cùng chính xác một chủ ñề / bài tập/ nguồn thông tin ñược cung ứng trong năm và các năm kế tiếp). Ngoài ra, cần phải cẩn thận tránh các phép ño, thông số và phương pháp mà các kích thước mẫu có tác ñộng nhiều ñến kết quả. Luật kết hợp ñược sử dụng ngày càng nhiều trong khai mỏ dữ liệu giáo dục [16]. Tuy nhiên, phép ño mức thoả mãn cần phải tính lại, ñược giải thích trong -46- [12]. Hai phương pháp ño ñạc, hỗ trợ và tin cậy, ñược sử dụng thường ñể trích ra luật kết hợp. Tuy nhiên vấn ñề này rất phổ biến ngay cả các luật có tính hỗ trợ và ñộ tin cậy mạnh có thể nằm trong danh mục không thoả mãn. ðó là lý do tại sao, khi mà luật kết hợp X  Y ñược rút trích, nó thực hiện kiểm tra hai lần ñộ tương quan của X và Y. Có khoảng 20 phép ño ñã ñược ñề xuất ñể làm ñiều ñó [24]. Không may là không có phép ño nào tốt hơn tất cả trong mọi trường hợp, mặc dù phép ño thể hiện ñược ñúng ñắn khi hỗ trợ cao. Meceron và Yacef năm 2008 ñã thực nghiệm và ñề xuất hai ñộ ño khách quan khá phù hợp với dữ liệu giáo dục, ñó là số cosine và lift [18]. 3.4.1 Tỉ số cosine Giả sử hai vector x và y và góc giữa chúng khi mà gốc vector của chúng trùng nhau. Khi góc ñó gần 0°, thì trị của hàm cosine gần 1, ví dụ 2 vector này cận kề nhau: toạ ñộ như nhau hoặc tỷ lệ nhau. Khi góc giữa chúng là 90°, 2 vector này vuông góc, không cận kề nhau và trị hàm cosine là 0. Coi vector x và y là vector ñộ dài của n: x=(x1, ... , xn), y=(y1, ... , yn). Thì ||)||.||(|| ).(),( yx yxyxsìneco = Với . là phép tính tích vô hướng ∑ = = n k kk yxyx 1 . và ||x|| ñộ dài của vector x: ∑ = = n k kxx 1 2|||| Xem X và Y của luật XY là hai vector, xk có trị 1 nếu giao dịch tk chứa X và 0 nếu ngược lại, tương tự cho yk và Y. Như vậy hàm cosine có thể ñịnh nghĩa như sau: -47- )())().(( ),(),( YXsìneco YPXP YXPyxsìneco →== cho luật kết hợp XY. Khi cosine(XY) càng gần 1, càng nhiều giao tác chứa X cũng chứa Y và ngược lại. Khi cosine(XY) càng gần 0, càng nhiều giao tác chứa X mà không chứa Y và ngược lại. ðơn giản n ta có ||.|| |,|)( YX YXYXsìneco =→ Sự tương ñương này thể hiện các giao tác không chứa cả X và Y không ảnh hưởng ñến kết quả của cosine(XY). ðiều này ñược biết ñến như là thuộc tính null bất biến. Lưu ý là cả hàm cosine cũng là phép ño ñối xứng. 3.4.2 Giá trị bổ sung và tỉ số lift Trị bổ sung trong luật XY ñược chứng tỏ bằng AV (XY) và ño tỷ lệ của các giao tác chứa Y và giao tác chứa X là lớn hơn tỷ lệ giữa giao tác chứa Y và toàn bộ giao tác. Sau ñó, chỉ khi xác suất tìm thấy Y khi mà X ñã tìm thấy là lớn hơn xác suất tìm thấy Y trong toàn bộ, chúng ta có thể nói là X và Y có tương quan và X bao hàm Y. AV ( XY)=P(Y / X) – P(Y) =conf ( XY) – P(Y). Kết quả là số dương cho biết X và Y có tương quan, trong khi kết quả âm cho biết sự xuất hiện của X ngăn ngừa Y xuất hiện. Trị bổ sung gần như tương ñồng với phương pháp ño ñạc phổ biến khác: tỉ số lift. )( )( )().( ),()( YP YXconf YPXP YXPYXlift →==→ Lưu ý nếu P(X, Y) = P(X).P(Y) thì giá trị của lift là 1. Theo ñịnh nghĩa xác suất, sự xuất hiện của X và Y trong cùng giao tác là 2 sự kiện ñộc lập, do ñó X và Y không có tương quan nhau. Dễ dàng ta thấy trị lift là 1 khi trị bổ sung là 0, trị lift lớn hơn 1 chính xác khi trị bổ sung là dương và khi trị lift nhỏ hơn 1, chính xác hơn khi trị bổ sung là âm. Và AV(XY)có xu hướng tiến về 1 khi lift(XY) tiến về vô cực và AV(XY) có xu hướng tiến về -1 khi lift(XY) có xu hướng tiến về 0. -48- Lưu ý là ||.|| .|,|)( YX nYXYXlift =→ cho nên kết quả tỷ lệ với n, tổng số giao tác. Ngược lại với hàm cosine, tỉ số lift không có thuộc tính null bất biến. 3.4.3 Các giá trị ñiển hình của cosine và lift Giả ñịnh giữa n giao tác, có m giao tác chứa X hoặc Y hoặc cả hai, với m<=n và n-m giao tác không chứa cả X và Y. ðầu tiên xét các trường hợp mà tất cả m giao tác chứa cả X và Y. Thì: cosine(XY)=1. Ngược lại, dễ dàng thấy cosine(XY) = 1 dẫn ñến toàn bộ m giao tác chứa cả X và Y. ðối với tỉ số lift, lift (XY)=(m.n)/(m.m)=n /m . Như vậy nếu m = n, lift(XY)=1. Nếu m = ½ * n, lift(XY)=2 và tiếp tục như vậy. Giả sử tất cả 90% trường hợp của m giao tác chứa cả X và Y trong khi 10% còn lại chỉ chứa X. Thì: 949.0 90 100 . 100 90 100 .90 . . 100 90 )( ===→ m m m YXsìneco m n mmnmYXlift ==→ ). 100 90 ./().. 100 90()( Giả sử tất cả 90% trường hợp của m giao tác chứa cả X và Y, nhưng 5% trong số còn lại chỉ chứa X và 5% còn lại chỉ chứa Y. Nói cách khác, X và Y ñược trải ñều trong số giao tác không chứa chỉ X hoặc chỉ Y. Thì: 947.0 95 100 . 100 90 100 .95 . 100 .95 . 100 90 )( ===→ mm m YXsìneco m n mmmnmYXlift 99.0). 100 95 .. 100 95 ./().. 100 90()( ==→ -49- Bảng 3.4 tổng kết các kết quả, (a,b,c) nghĩa là a% của m giao tác chứa cả X và Y, b% chứa X và c% chứa Y. Như vậy (75, 100, 75) nghĩa là 75% của m giao tác chứa cả X và Y, 25% còn lại chứa X nhưng không chứa Y (X xuất hiện trong toàn bộ giao tác và Y trong 75% chúng, trong khi (75, 87.5, 87.5) nghĩa là X hoặc Y ñược trải ñều trong 25% của phần giao tác còn lại. Thảo luận: Trong trường hợp ñối xứng mạnh mẽ của luật kết hợp nghĩa là |X|, |Y| và |X,Y| là các số lớn gần với n, hàm cosine và tỉ số lift không ñánh giá luật như nhau, như ñã ñề cập ở [17]. Trong trường hợp ñó, hàm cosine sẽ tốt hơn tỉ số lift. Trị bổ sung và tỉ số lift dựa trên xác suất, có vẻ hợp lý hơn khi mà số lượng khảo sát lớn. Ngoài ra, tỉ số lift và các trị bổ sung không như hàm cosine, phụ thuộc vào số lượng giao tác không chứa cả X và Y. Trong lĩnh vực giáo dục, vẫn chưa rõ là các giao tác rỗng có ñóng vai trò nhất ñịnh nào hay không. Kết luận ñược rút ra như sau: kiểm tra ñộ thoả mãn của luật kết hợp với hàm cosine trước, sau ñó với tỉ số lift nếu hàm cosine không ñưa ra ñược kết luận. Bảng 3.4 ñề nghị giá trị vào khoảng hoặc dưới 0.65 bị từ chối bởi cosine: như chúng ta có thể thấy 0.66 tương ứng với ngưỡng thấp nhất với 50% các trị thông thường (50, 75, 75). Trong trường hợp các kết quả mâu thuẫn thì quyết ñịnh sử dụng thông tin mà các phép ño thể hiện. Bảng 3.4 Các trị ñặc trưng của hàm cosine và tỉ số lift (3 thành tố trong cột ñầu tiên thể hiện phần trăm giao tác chứa cả X và Y, X, Y) % giao tác (X và Y, X, Y) cosine(XY) lift(XY) (100, 100, 100) 1 n/m (90, 100, 90) 0.949 n/m (90, 95, 95) 0.947 0.997.(n/m) (75, 100, 75) 0.87 n/m (75, 87.5, 87.5) 0.86 0.98.(n/m) (60, 100, 60) 0.77 n/m (60, 80, 80) 0.75 0.94.(n/m) -50- (50, 100, 50) 0.707 n/m (50, 75, 75) 0.66 0.88.(n/m) (40, 100, 40) 0.63 n/m (40, 70, 70) 0.57 0.82.(n/m) (30, 100, 30) 0.55 n/m (30, 65, 65) 0.46 0.71.(n/m) Luật kết hợp ñược ñánh giá ñộ thú vị bằng cosine và lift như sau: nếu cosine lớn hơn 0.65 thì ñạt, ngược lại nếu giá trị của lift lớn hơn 1 thì ñạt, ngược lại là không ñạt. Như vậy, ñộ thoả mãn của luật trước tiên cần phải ño bằng hàm cosine, sau ñó với tỉ số lift nếu cosine ñánh giá không thoả mãn. Trong trường hợp cả hai phép ño ñều không ñạt, người sử dụng cần phải thêm vào tính toán các thông tin mang tính trực giác cung cấp bởi các phép ño khác ñể quyết ñịnh ñúng ñắn. 3.5 Khám phá tri thức trên các nhóm con 3.5.1 Giới thiệu Khám phá nhóm con (Subgroup Discovery) [10] là một phương pháp mạnh và có khả năng ứng dụng rộng rãi. Phương pháp này tập trung vào việc khám phá các nhóm con thú vị riêng lẻ. Nó thường ñược ứng dụng vào việc khảo sát dữ liệu và miêu tả quy nạp, nhằm xác ñịnh các mối quan hệ giữa một biến ñích và tập các biến giải thích. Sau ñó, không chỉ các mối quan hệ hoàn chỉnh mà còn các mối quan hệ cục bộ, chẳng hạn các nhóm với các ñặc tính ñược quan tâm. Trước khi miêu tả về khám phá nhóm con, ñầu tiên ta ñề cập tới khái niệm cần thiết của biểu diễn tri thức: Tập ΩA là tập toàn bộ thuộc tính, mỗi thuộc tính a ∈ ΩA , miền giá trị của a: dom(a) ñược xác ñịnh trước. Ngoài ra, ta giả sử VA là tập thuộc tính vũ trụ dưới hình thức (a = v), a ∈ ΩA là thuộc tính và v ∈ dom(a) là giá trị ñược ñịnh trước. Ta xem các thuộc tính ñịnh danh chỉ là các thuộc tính số học cần ñể phân hoạch. Ta ñặt CB là tập cơ sở (data set) chứa tất cả các trường hợp có sẵn, ñồng thời có thể gọi là các thể hiện. Trường hợp c ∈ CB ñược cho bởi n-bộ c = -51- ((a1 = v1), (a2 = v2),…., (an = vn)) của n = |ΩA| giá trị thuộc tính, và vi ∈ dom(ai) của mỗi ai. Khám phá nhóm con dựa trên 4 thuộc tính chính liệt kê như sau: biến ñích, ngôn ngữ mô tả nhóm con, hàm ñánh giá và chiến lược tìm kiếm. Ta ñịnh danh các nhóm con lớn ñến mức có thể và có các ñặc tính bất thường trên quan ñến khái niệm thoả mãn cho bởi biến ñích. Ngôn ngữ mô tả chỉ ra các cá thể thuộc về các nhóm con. Trong trường hợp ngôn ngữ ñề xuất ra các mối tương quan ñơn, mô tả nhóm con ñược ñịnh nghĩa như sau: ðịnh nghĩa 1 (ðặc tả nhóm con): Tập các nhóm con sd = { e1, e2,….,en} ñược xác ñịnh bởi sự liên kết của tập các biểu thức chọn. Các chọn lựa ei = (ai, Vi) là các selection từ miền thuộc tính, ai ∈ ΩA, Vi ⊆ dom(ai). Ta ñịnh nghĩa Ωsd là tập các ñặc tả nhóm con. Một hàm ñánh giá chất lượng ño lường sự thú vị của nhóm con thường dựa trên các hàm lượng giá thống kê, chẳng hạn phép kiểm thống kê chi bình phương. Hàm ñánh giá ñược dùng ñể xếp hạng các nhóm con trong quá trình tìm kiếm. Tiêu chí chất lượng ñặc thù bao gồm sự khác biệt trong phân bổ các biến ñích liên quan ñến nhóm con và mật ñộ thông thường, kích thước của nhóm con. Ta giả sử người dùng thiết lập ngưỡng hỗ trợ thấp nhất ΤSupp tương ứng với số lượng các giá trị ñích trong nhóm con ñể chặn các mẫu nhóm con nhỏ và không thoả yêu cầu. ðịnh nghĩa 2 (Hàm ñánh giá) Cho trước một biến ñích t ∈VA, hàm ñánh giá q: Ωsd x VA → R ñược dùng ñể ñánh giá một ñặc tả nhóm con sd ∈ Ωsd, và xếp hạng các tập nhóm con thu ñược trong quá trình tìm kiếm. Hàm ñánh giá có thể là một phép kiểm tỉ lệ: )1.( ).( 00 0 pp nppqS − − = -52- Trong ñó p là ñộ phổ biến tương ñối của biến ñích trong nhóm con, p0 là ñộ phổ biến tương ñối của biến ñích trong toàn bộ không gian vũ trụ, N = |CB| là kích thước của toàn bộ không gian và n là kích thước nhóm con. Chiến lược hiệu quả cho việc tìm kiếm nhóm con là rất cần thiết, vì không gian tìm kiếm lên ñến số mũ cho tất cả các biến chọn ñối với từng ñặc tả nhóm con. 3.5.2 Thuật toán SD-Map So sánh với luật kết hợp ño ñộ tin cậy và hỗ trợ của luật, việc khám phá nhóm con sử dụng hàm ñánh giá ñặc biệt ñể ño mức ñộ thoả mãn của nhóm con. Mô phỏng trên FP-Growth ñể khám phá các nhóm con chỉ sử dụng phương pháp của FP-Growth ñể thu thập các mẫu phổ biến, sau ñó cần ñánh giá lại mẫu sử dụng hàm ñánh giá. Việc ñánh giá chất lượng sử dụng 4 thông số chính: ñộ tương quan thuận tp (các trường hợp chứa biến ñích t trong nhóm con s) và ñộ tương quan nghịch fp (các trường hợp không chứa biến ñích t) và ñộ tương quan thuận TP và tương quan nghịch FP trên toàn bộ dữ liệu (kích thước N). Ngoài ra, ta cần phải dùng phương pháp của FP-Growth, và tính toán các thông số: n = count(s), tp = support(s) = count(s ∧ t), fp = n – tp, p = tp/(tp + fp), TP = count (t), FP = N – TP, p0 = TP/(TP + FP). Tuy nhiên, một vấn ñề trong khai khoáng dữ liệu còn tồn tại: vấn ñề thiếu hụt dữ liệu. Nếu ñiều ñó xảy ra trong dữ liệu cơ sở, thì tất cả các trường hợp ko hẳn có ñầy ñủ các giá trị cho mỗi thuộc tính, ví dụ như dữ liệu chưa ñược ghi nhận kịp thời. ðối với khai khoáng dữ liệu ñiều này hầu như không xảy ra, vì ta không xem các phần tử như các giao dịch: phần tử có tồn tại hay không, hoặc chưa bao giờ thiếu -53- ñịnh nghĩa hay thiếu hụt. Ngược lại, các giá trị bị thiếu hụt là vấn ñề quan trọng trong mining nhóm con trong một vài lĩnh vực như y học. Nếu giá trị thiếu hụt ko thể bị loại bỏ, thì cần phải xác ñịnh lại trong phương pháp khám phá nhóm con khi tính toán chất lượng của chúng: Cơ bản ta cần xác ñịnh kích thước dữ liệu bằng ñịnh danh các trường hợp có các biến chọn hay biến ñích chưa xác ñịnh chẳng hạn như chúng bị thiếu. Vì vậy, cách tiếp cận ñơn giản ñề cập ở trên là dư thừa và cũng là không ñủ, vì (a) chúng ta có thể sẽ có một cây kích cỡ lớn hơn nếu sử dụng một node bình thường cho biến ñích; (b) nếu có giá trị bị thiếu, chúng ta cần phải giới hạn tham số TP và FP với những dòng dữ liệu mà ở ñó tất cả những thuộc tính của những biến chọn chứa trong mô tả nhóm con có một giá trị xác ñịnh (khác null); (c) hơn thế nữa, nếu tính toán fp=n-tp, chúng ta không phân biệt ñược những dòng dữ liệu mà biến ñích không có giá trị xác ñịnh. ðể cải tiến tình huống này và ñể giảm ñi kích thước của cây FP, chúng tôi xem xét 2 hướng tiếp cận quan trọng sau: 1. ðể ñánh giá chất lượng của nhóm con, chúng ta chỉ cần quan tâm ñến 4 tham số nhóm con cơ bản là tp, fp,TP và FP có sự tương ứng với những giá trị thiếu. Sau ñó, những thuộc tính còn lại có thể ñược suy ra như sau: n=tp+fp; N=TP+FP; 2. ðối với tác vụ khai phá nhóm con, khái niệm về ñộ thú vị, có nghĩa là, với một biến ñích cố ñịnh, thì ngược lại với “rule head” tùy ý của luật kết hợp. Vì vậy, những tham số cần thiết mô tả ở trên có thể ñược tính toán một cách trực tiếp, ví dụ như, xét một giá trị tp, nếu một dòng dữ liệu có chứa biến ñích và một biến chọn nào ñó, thì giá trị tp của node tương ứng trong cây FP sẽ ñược tăng lên 1 ñơn vị. Nếu tp, fp ñược lưu trữ trong những node của cây FP, chúng ta có thể tính toán chất lượng của nhóm con một cách trực tiếp trong khi tạo ra những mẫu phổ biến. Hơn thế nữa, chúng ta chỉ cần tạo ra những node cho những biến ñộc lập mà không cần tạo ra node cho biến ñích. Trong thuật toán SD-Map, chúng ta chỉ ñếm -54- cho mỗi node nếu biến ñích xuất hiện (tăng tp) hoặc không (tăng fp), giới hạn với những dòng dữ liệu mà biến ñích có một giá trị xác ñịnh. Những giá trị ñếm trên toàn bộ dữ liệu có thể ñược yêu cầu sau như là một phần phụ. ðể giải quyết vấn ñề những giá trị thiếu, một cấu trúc cây FP thứ 2 ñược ñưa ra, cây Missing-FP . Cây FP dùng ñể ñếm những giá trị thiếu có thể ñược giới hạn với những thuộc tính phổ biến của cây FP chính, bởi vì chỉ những thuộc tính này mới có thể tạo ra ñược những mô tả nhóm con mà sau ñó sẽ ñược kiểm tra những giá trị thiếu tương ứng. Sau ñó, cây Missing-FP ñược ñánh giá theo một cách ñặc biệt tương ứng với những giá trị thiếu. ðể ñiều chỉnh những giá trị thiếu, chúng ta chỉ cần ñiều chỉnh số lượng TP, FP tương ứng với toàn bộ dữ liệu, bởi vì số ñếm của cây FP nhóm con ñược lấy ra từ những dòng dữ liệu mà biết biến ñích có giá trị xác ñịnh, và mô tả nhóm con chỉ ñược tính trong những dòng dữ liệu mà những biến chọn có giá trị xác ñịnh. Sử dụng cây Missing-FP_tree, chúng ta có thể chỉ ra những tình huống mà ít nhất một trong những thuộc tính của mô tả nhóm con chưa ñược chỉ ra: Với một ñặc tả nhóm con sd = (e1 ∧ e2 ∧ ... ∧en), ei = (ai, Vi), Vi dom(ai) chúng ta cần tính toán các giá trị thiếu missing (a1 ∨ a2 ∨ ... ∨ an) cho một bộ thuộc tính M={a1, ..., an}. Cách tính như sau: ∑ ∑ = ∈ −=∨∨ n i m in M mmissìngamissìngaamissìng 1 2 1 )()()...( , với |m| ≥ 2. Vì vậy, ñể có thể nhận ñược những ñiều chỉnh cho giá trị thiếu tương ứng với bộ M chứa những thuộc tính của nhóm con, chúng ta cần thêm vào những mục của node header của cây Missing-FP tương ứng với những thuộc tính riêng biệt, và trừ ñi những mục của bất kỳ ñường ñi hậu tố nào kết thúc ở một thành phần của M mà có chứa ít nhất một phần tử của M. -55- Thuật toán SD-Map: Yêu cầu: biến ñích t, hàm ñánh giá q, tập các biến chọn E (không gian tìm kiếm) 1: Duyệt lần I: Thu thập các tập biến chọn phổ biến và xây dựng list L phổ biến cho cây FP chính: 1. ðối với mỗi biến ñích có giá trị ñịnh trước, ñếm cặp (tpe, fpe) cho mỗi biến chọn e ∈ E. 2. Loại bỏ các biến chọn không ñạt ñộ hỗ trợ tối thiểu TSupp, chẳng hạn tp(e) = frequency(e ∧ t) < TSupp 3. Các biến chọn còn lại e ∈ E, xây dựng và sắp xếp lại danh sách L phổ biến theo thứ tự hỗ trợ / phổ biến giảm dần. 2: Duyệt lần II: Xây dựng cây FP chính Chèn mỗi node trong danh sách phổ biến vào cây FP, tính cặp (tp, fp) cho mỗi node. 3: Duyệt lần III: Xây dựng cây Missing-FP (Bước này có thể tích hợp thành bước luận lý cho duyệt lần II). 1. ðối với mỗi thuộc tính phổ biến trong danh sách phổ biến L, tạo node ñại diện cho giá trị thiếu của thuộc tính này. 2. Xây dựng cây Missing-FP, tính cặp (tp, fp) cho mỗi thuộc tính 4: Thực hiện phương pháp của FP-GROWTH ñể tạo các mẫu nhóm con: 5: Lặp: 6: Với mỗi nhóm con si là mẫu phổ biến: 7: Tính toán các thông số TP’, FP’ theo công thức 8: Với các thông số tp, fp, TP’, FP’ ñánh giá chất lượng nhóm con q(si) sử dụng hàm ñánh giá q. 9: Cho ñến khi kết thúc FP-Growth. 10: Hậu xử lý tập các mẫu phổ biến, trả về k nhóm con tốt nhất hoặc trả về tập S = {s|q(s) >= qmin} với các ngưỡng ñánh giá qmin ∈R (Bước này tích hợp như là bước lọc luận lý trong vòng lặp khám phá mẫu (dòng 5-9)) -56- Bằng cách xem xét giá trị (tp,fp) chứa trong cây Missing-FP, chúng ta nhận ñược giá trị (TPmissing, FPmissing) với những dòng dữ liệu không thể ñược tính toán thống kê bởi vì ít nhất một giá trị của thuộc tính chứa trong M là chưa ñược chỉ ra. ðể ñiều chỉnh số ñếm trên toàn bộ dữ liệu, chúng ta tính toán chính xác chúng như sau: TP’ = TP – TPmissing, FP’ = FP - FPmissing Sau ñó, chúng ta có thể tính toán chất lượng nhóm con dựa trên những tham số tp,fp,TP’, FP’. Vì vậy, trái với phương thức FP-growth chuẩn, chúng ta không chỉ tính toán những mẫu phổ biến trong thuật toán FP-gowth, mà chúng ta còn có thể tính toán trực tiếp chất lượng của những mẫu phổ biến này, bởi vì tất cả những tham số cần thiết có thể ñược lấy ra trong bước FP-growth. Vì vậy, chúng ta thực hiện một bước xây dựng và kiểm tra tích hợp, tính toán nhóm con một cách trực tiếp. SD-Map bao gồm một bước tiền xử lý cho những bộ chọn và việc quản lý sự dư thừa tiềm tàng của những bộ nhóm con tìm ñược. Thông thường, người dùng chỉ quan tâm ñến những k nhóm con tốt nhất và không muốn phải kiểm tra toàn bộ những nhóm con tìm ñược. Vì vậy, chúng ta có thể chỉ phải chọn ra k nhóm con tốt nhất dựa trên ñánh giá của hàm ñánh giá. Một cách khác, chúng ta cũng có thể chọn ra tất cả những nhóm con trên một ngưỡng chất lượng nào ñó. Hơn thế nữa, ñể có thể giảm sự trùng nhau và những nhóm con dư thừa tiềm tàng, chúng ta có thể áp dụng tiền xử lý, ví dụ như, phương thức phân cụm hay là một hướng tiếp cận không trọng lượng. Bước tiền xử lý có thể ñược tích hợp luôn bên trong vòng lặp khám phá (trong quá trình áp dụng phương thức FP-growth).