Khai khoáng dữ liệu bằng luật kết hợp

-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à c