Luận văn Phương pháp luận kết hợp và ứng dụng

phân cụm dữ liệu… - Đánh giá mẫu: Thành phần này sử dụng các độ đo và tương tác với modul khai phá dữ liệu để tập trung vào tìm các mẫu quan tâm. Giao diện người dùng Đánh giá mẫu Mô tả khai phá dữ liệu CSDL hay kho dữ liệu phục vụ Cơ sở dữ liệu Kho dữ liệu Cơ sở tri thức Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 - Giao diện người dùng: Đây là modul giữa người dùng và hệ thống khai phá dữ liệu. Cho phép người dùng tương tác với hệ thống trên cơ sở những truy vấn hay tác vụ, cung cấp thông tin cho việc tìm kiếm. 1.3.7. Quá trình khai phá dữ liệu Các thuật toán khai phá dữ liệu thường được mô tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với phương pháp máy học và thống kê trước đây, thường thì bước đầu tiên các thuật toán nạp toàn bộ tệp dữ liệu vào bộ nhớ. Khi chuyển sang các ứng dung công nghiệp liên quan đến việc khai thác các kho dữ liệu lớn, mô hình này không thể đáp ứng bởi vì không thể nạp hết dữ liệu vào bộ nhớ mà còn khó có thể chiết xuất ra những tệp đơn giản để phân tích. Quá trình khai phá dữ liệu (Hình 1.3) bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết. Tiếp đến là xác định dữ liệu liên quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu liên quan và xử lý chúng thành dạng sao cho thuật toán khai phá có thể hiểu được. Hình 1.3. Quá trình khai phá dữ liệu Xác định nhiệm vụ Xác định dữ liệu liên quan Thu thập và tiền xử lý dữ liệu Thuật toán khai phá dữ liệu Dữ liệu trực tiếp Mẫu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 Sau đó chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu để tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng (luật kết hợp, cây quyết định …) Kết quả thu được mẫu phải có đặc điểm mới. Độ mới có thể được đối sánh tương ứng với độ thay đổi trong dữ liệu hoặc bảng tri thức. Thường thì độ đo mới của mẫu được đánh giá bằng một hàm logic hoặc hàm độ đo mới. Ngoài ra mẫu còn có khả năng sử dụng tiềm ẩn. Với thuật toán và nhiệm vụ khai phá dữ liệu khác nhau thì dạng mẫu chiết xuất được cũng rất đa dạng. 1.3.8. Những khó khăn trong khai phá dữ liệu Việc nghiên cứu và ứng dụng kỹ thuật khai phá dữ liệu gặp nhiều khó khăn, nhưng không phải là không giải quyết được mà chúng cần được tìm hiểu để có thể phát triển tốt hơn. Những khó khăn phát sinh trong khai phá dữ liệu chính là dữ liệu trong thực tế thường động, không đầy đủ, lớn và bị nhiễu. Trong trường hợp khác, người ta không biết cơ sở dữ liệu có chứa thông tin cần thiết cho việc khai thác hay không và làm thế nào để giải quyết sự dư thừa thông tin không thích hợp này. - Dữ liệu lớn: Hiện nay các cơ sở dữ liệu với hàng trăm trường và bảng, hàng triệu bản ghi với kích thước rất lớn, có thể lên đến GB. Các phương pháp giải quyết hiện nay là đưa ra một ngưỡng cho cơ sở dữ liệu, lấy mẫu, các phương pháp tính xấp xỉ, xử lí song song. - Kích thước lớn: không chỉ có số lượng bản ghi mà số các trường trong cơ sở dữ liệu cũng nhiều. Vì vậy mà kích thước của bài toán trở nên lớn làm tăng không gian tìm kiếm. Hơn nữa, nó cũng làm tăng khả năng một thuật toán khai phá dữ liệu có thể tìm thấy các mẫu giả. Biện pháp khắc phục là làm giảm kích thước tác động của bài toán và sử dụng các tri thức biết trước để xác định các biến không phù hợp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 - Dữ liệu động: Đặc điểm cơ bản của hầu hết các cơ sở dữ liệu là nội dung của chúng thay đổi liên tục. Chẳng hạn như các biến trong cơ sở dữ liệu của ứng dụng đã cho chũng có thể bị thay đổi, bị xóa hoặc là tăng lên theo thời gian. Dữ liệu có thể thay đổi theo thời gian và việc khai phá dữ liệu bị ảnh hưởng bởi thời điểm quan sát dữ liệu, do đó có thể làm cho mẫu khai thác được trước đó mất giá trị. Vấn đề này được giải quyết bằng giải pháp tăng trưởng để nâng cấp các mẫu và coi những thay đổi như là cơ hội để khai thác bằng cách sử dụng nó để tìm kiếm các cẫu bị thay đổi. - Các trường dữ liệu không phù hợp: Một đặc điểm quan trọng khác là tính không thích hợp của dữ liệu – nghĩa là mục dữ liệu trở thành không thích hợp với trọng tâm hiện tại của việc khai thác. Bên cạnh đó, tính ứng dụng của một thuộc tính đối với một tập con của cơ sở dữ liệu cũng là một vấn đề đôi khi cũng liên quan dến độ phù hợp. - Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính dữ liệu phù hợp có thể ảnh hưởng đến việc khai phá dữ liệu. Trong hệ thống tương tác, sự thiếu vắng dữ liệu quan tọng có thể dẫn tới yêu cầu cho giá trị của nó hoặc kiểm tra để xác định giá trị của nó. Hoặc cũng có thể sự vắng mặt của dữ liệu được coi như một điều kiện, thuộc tính bị mất có thể được xem như một giá trị trung gian và gía trị không biết. - Các trường dữ liệu bị thiếu: Một quan sát không đầy đủ cơ sở dữ liệu có thể làm cho dữ liệu có giá trị bị xem như có lỗi. Việc quan sát cơ sở dữ liệu phải phát hiện được toàn bộ các thuộc tính có thể dùng để thuật toán khai phá dữ liệu có thể áp dụng để giải quyết bài toán. Giả sử ta có các thuộc tính để phân biệt các tình huống đáng quan tâm. Nếu chúng không làm được điều đó thì có nghĩa là đã có lỗi trong dữ liệu. Đây Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 cũng là vấn đề thường xảy ra trong cơ sở dữ liệu kinh doanh. Các thuộc tính quan trọng có thể sẽ bị thiếu dữ liệu không được chuẩn bị. - Quá phù hợp: Khi một thuật toán tim kiếm tham số tốt nhất cho một mô thình nào đó sử dụng một tập dữ liệu hữu hạn, nó có thể sẽ bị tình trạng “quá độ” dữ liệu (nghĩa là tìm kiếm quá mức cần thiết gây ra hiện tượng chỉ phù hợp với dữ liệu đó mà không có khả năng đáp ứng cho các dữ liệu lạ), làm cho mô hình hoạt động rất kém đối với các dữ liệu thử. Các giải pháp khắc phục như đánh giá chéo, thực hiện theo nguyên tắc nào đó hoặc sử dụng các biện pháp thống kê khác. - Khả năng biểu đạt mẫu: Trong rất nhiều ứng dụng, điều quan trọng là những điều khai thác được phải càng dễ hiểu với con người càng tốt. Vì vậy, các giải pháp thường bao gồm việc diễn tả dưới dạng đồ họa, xây dựng cấu trúc luật với các đồ thị có hướng, biểu diễn bằng ngôn ngữ tự nhiên và kỹ thuật khác nhằm biểu diễn các tri thức và dữ liệu. - Sự tương tác với người sử dụng các tri thức sẵn có: Rất nhiều công cụ và phương pháp khai phá dữ liệu không thực sự tương tác với người dùng và không dễ dàng kết hợp cùng với các tri thức đã biết trước đó. Việc sử sụng tri thức miền là rất quan trọng trong khai phá dữ liệu. Đã có nhiều biện pháp nhằm khắc phục vấn đề này như sử dụng cơ sở dữ liệu suy diễn để phát hiện tri thức, những tri thức này sau đó được sử dụng để hướng dẫn cho việc tìm kiếm khai phá dữ liệu hoặc sử dụng sự phân bố xác suất dữ liệu trước đó như một dạng mã hóa tri thức có sẵn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Chƣơng 2 LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU 2.1. Bài toán kinh điển dẫn đến việc khai phá luật kết hợp Bài toán giỏ mua hàng trong siêu thị. Giả định chúng ta có rất nhiều mặt hàng, ví dụ như “bánh mì”, “sữa”,…(coi là tính chất hoặc trường). Khách hàng khi đi siêu thị sẽ bỏ vào giỏ mua hàng của họ một số mặt hàng nào đó, và chúng ta muốn tìm hiểu các khách hàng thường mua các mặt hàng nào đồng thời, thậm chí chúng ta không cần biết khách hàng cụ thể là ai. Nhà quản lý dùng những thông tin này để điều chỉnh việc nhập hàng về siêu thị, hay đơn giản là để bố trí sắp xếp các mặt hàng gần nhau, hoặc bán các mặt hàng đó theo một gói hàng, giúp cho khắc đỡ mất công tìm kiếm. Bài toán này hoàn toàn có thể áp dụng trong các lĩnh vực khác. Ví dụ: - Giỏ hàng = văn bản. Mặt hàng = từ. Khi đó, những từ hay đi cùng nhau sẽ giúp ta nhanh chóng tìm ra các lối diễn đạt, hay các khái niệm có mặt trong văn bản. - Giỏ hàng = văn bản. Mặt hàng = câu. Khi đó, những văn bản có nhiều câu giống nhau giúp phát hiện ra sự đạo văn, hay những “website đúp” (mirror website). Khai phá luật kết hợp được môt tả như sự tương quan của các sự kiện- những sự kiện xuất hiện thường xuyên một các đồng thời. Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện trong một khối lượng giao dịch lớn của một cơ sở dữ liệu cho trước. Nói cách khác, thuật toán khai phá luật kết hợp cho phép tạo ra các luật mô tả các sự kiện xảy ra đồng thời (một cách thường xuyên) như thế nào. Các thuật toán này trải qua 2 pha: pha đầu là đi tìm các sự kiện xảy ra thường xuyên, pha hai là tìm luật. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 2.2. Định nghĩa về luật kết hợp Định nghĩa: Cho I={I1, I2, .., Im} là tập hợp của m tính chất riêng biệt. Giả sử D là CSDL, với các bản ghi chứa một tập con T các tính chất (có thể coi như T  I), các bản ghi đều có chỉ số riêng. Một luật kết hợp là một mệnh đề kéo theo có dạng XY, trong đó X, Y  I, thỏa mãn điều kiện XY=. Các tập hợp X và Y được gọi là các tập hợp tính chất (itemset). Tập X gọi là nguyên nhân, tập Y gọi là hệ quả. Có 2 độ đo quan trọng đối với luật kết hợp: Độ hỗ trợ (support) và độ tin cậy (confidence), được định nghĩa như phần dưới đây. Định nghĩa: Độ hỗ trợ Định nghĩa 2.1: Độ hỗ trợ của một tập hợp X trong cơ sở dữ liệu D là tỷ số giữa các bản ghi T  D có chứa tập X và tổng số bản ghi trong D (hay là phần trăm của các bản ghi trong D có chứa tập hợp X), ký hiệu là support(X) hay supp(X) (support sẽ tự sinh ra khi cài thuật toán) Supp(X)= |{ T D: Y X}| | |D   Ta có: 0  supp(X)  1 với mọi tập hợp X. Định nghĩa 2.2: Độ hỗ trợ của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi chứa tập hợp X  Y, so với tổng số các bản ghi trong D - Ký hiệu supp(XY) Supp(XY)= |{ T D: T X Y}| | |D    Khi chúng ta nói rằng độ hỗ trợ của một luật là 50%, có nghĩa là coc 50% tổng số bản ghi chứa X  Y. Như vậy, độ hỗ trợ mang ý nghĩa thống kê của luật. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Trong một số trường hợp, chúng ta chỉ quan tâm đến những luật có độ hỗ trợ cao (Ví dụ như luật kết hợp xét trong cửa hàng tạp phẩm). Nhưng cũng có trường hợp, mặc dù độ hỗ trợ của luật thấp, ta vẫn cần quan tâm (ví dụ luật kết hợp liên quan đến nguyên nhân gây ra sự đứt liên lạc ở các tổng đài điện thoại) Định nghĩa: Độ tin cậy Định nghĩa 2.3: Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi trong D chứa X  Y với số bản ghi trong D có chứa tập hợp X. Ký hiệu độ tin cậy của một luật là conf(r). Ta có 0  conf(r)  1 Nhận xét: Độ hỗ trợ và độ tin cậy có xác suất sau: Supp(XY)=P(X  Y) Conf (XY) = P(Y/X)=supp(X  Y)/supp(X) Có thể định nghĩa độ tin cậy như sau: Định nghĩa 2.4: Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi của tập hợp chứa X  Y, so với tổng số các bản ghi chứa X. Nói rằng độ tin cậy của một luật là 90%, có nghĩa là có tới 90% số bản ghi chứa X chứa luôn cả Y. Hay nói theo ngôn ngữ xác suất là: “ Xác suất có điều kiện để sảy ra sự kiện Y đạt 85%”. Điều kiện ở đây chính là: “Xảy ra sự kiện X”. Như vậy, độ tin cậy của luật thể hiện sự tương quan (correlation) gữa X và Y. Độ tin cậy đo sức nặng của luật, và người ta hầu như chỉ quan tâm đến những luật có độ tin cậy cao. Một luật kết hợp đi tìm các nguyên nhân dẫn tới hỏng hóc của hệ thống tổng đài, hay đề cập đến những mặt hàng thường hay được khách hàng mua kèm với mặt hàng chính mà độ tin cậy thấp sẽ không có ích cho công tác quản lý. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Việc khai thác các luật kết hợp từ cơ sở dữ liệu chính là việc tìm tất cảc các luật có độ hỗ trợ và độ tin cậy do người sử dụng xác định trước. Các ngưỡng của độ hỗ trợ và độ tin cậy được ký hiệu là minsup và mincof. Ví dụ: Khi phân tích giỏ hàng của người mua hàng trong một siêu thị ta được luật kiểu như: 85% khách hàng mua sữa thì cũng mua bánh mì, 30% thì mua cả hai thứ. Trong đó: “mua sữa” là tiền đề còn “mua bánh mì ” là kết luận của luật. Con số 30% là độ hỗ trợ của luật còn 80% là độ tin cậy của luật. Chúng ta nhận thấy rằng tri thức đem lại bởi luật kết hợp dạng trên có sự khác biệt rất nhiều so với những thông tin thu được từ các câu lệnh truy vấn dữ liệu thông thường như SQL. Đó là những tri thức, những mối liên hệ chưa biết trước và mang tính dự báo đang tiềm ẩn trong dữ liệu. Những tri thức này không đơn giản là kết quả của phép nhóm, tính tổng hay sắp xếp mà là của một quá trình tính toán khá phức tạp. Định nghĩa: Tập hợp Định nghĩa 2.5: Tập hợp X được gọi là tập hợp thường xuyên (Frenquent itemset) nếu có supp(X)  minsup, với minsup là ngưỡng độ hỗ trợ cho trước. Kí hiệu các tập này là FI Tính chất 2.1: Giả sử A,B  I là hai tập hợp với AB thì supp(A)  supp(B) Như vậy, những bản ghi nào chứa tập hợp B thì cũng chứa tập hợp A Tính chất 2.2: Giả sử A, B là hai tập hợp, A,B  I, nếu B là tập hợp thường xuyên và AB thì A cũng là tập hợp thường xuyên. Thật vậy, nếu B là tập hợp thường xuyên thì supp(B)  minsup, mọi tập hợp A là con của tập hợp B đều là tập hợp thường xuyên trong cơ sở dữ liệu D vì supp(A)  supp(B) (Tính chất 2.1) Tính chất 2.3: Giả sử A, B là hai tập hợp, A  B và A là tập hợp không thường xuyên thì B cũng là tập hợp không thường xuyên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Định nghĩa 2.6: Một tập mục X được gọi là đóng (closed) nếu không có tập cha nào của X có cùng độ hỗ trợ với nó, tức là không tồn tại một tập mục X’ nào mà X’X và t(X) = t(X’) (với t(x) và t(X’) tương ứng là tập các giao chứa tập mục X và X’). Ký hiệu tập phổ biến đóng là FCI. Định nghĩa 2.7: Nếu X là phổ biến và không tập cha nào của X là phổ biến, ta nói rằng X là một tập phổ biến lớn nhất (maximally frequent itemset). Ký hiệu tập tất cả các tập phổ biến lớm nhất là MFI. Dễ thấy MFI  FCI  FI. Khai phá luật kết hợp là công việc phát hiện ra (tìm ra, khám phá, phát hiện) các luật kết hợp thỏa mãn các ngưỡng độ hỗ trợ () và ngưỡng độ tin cậy () cho trước. Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ, hay như người ta thường nói, việc giải bài toán trải qua hai pha: Pha 1: Tìm tất cả các tập phổ biến (tìm FI) trong CSDL T. Pha 2: Sử dụng tập FI tìm được ở pha 1 để sinh ra các luật tin cậy (interesting rules). Ý tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta có thể xác định luật AB  CD với tỷ lệ độ tin cậy: conf = supp( ) supp( ) ABCD AB Nếu conf  minconf thì luật được giữ lại (và thỏa mãn độ hỗ trợ tối thiểu vì ABCD là phổ biến). Trong thực tế, hầu hết thời gian của quá trình khai thác luật kết hợp là thực hiện ở pha 1. Nhưng khi có những mẫu rất dài (mẫu chứa nhiều mục) xuất hiện trong dữ liệu, việc sinh ra toàn bộ các tập phổ biến (FI) hay các tập đóng (FCI) là không thực tế. Hơn nữa, có nhiều ứng dụng mà chỉ cần sinh tập phổ biến lớn nhất (MFI) là đủ, như khám phá mẫu tổ hợp trong các ứng dụng sinh học. Có rất nhiều nghiên cứu về các phương pháp sinh tất cả các tập phổ biến và tập phổ biến lớn nhất một cách có hiệu quả. Khi các mẫu phổ biến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 (frequent patterm) dài có từ 15 đến 20 items) thì tập FI, thậm chí cả tập FCI trở nên rất lớn và hầu hết các phương pháp truyền thống phải đếm quá nhiều tập mục mới có thể thực hiện được. Các thuật toán dựa trên thuật toán Apriori – đếm tất cả 2k tập con của mỗi k- itemsets mà chúng quét qua, và do đó không thích hợp với các itemsets dài được. Các phương pháp khác sử dụng “lookaheads” để giảm số lượng tập mục được đếm. Tuy nhiên, hầu hết các thuật toán này đều sử dụng tìm kiếm theo chiều rộng, ví dụ: tìm tất cả các k – itemsets trước khi tính đến các (k+1) – itemsets. Cách làm này hạn chế hiệu quả của lookaheads, vì các mẫu phổ biến dài hơn mà hữu ích vẫn chưa được tìm ra. Thuật toán 1 – Thuật toán cơ bản: Input: I, D, ,  Output: Các luật kết hợp thỏa mãn ngưỡng độ hỗ trợ , ngưỡng độ tin cậy . Algorithm: 1) Tìm tất cả các tập hợp các tính chất có độ hỗ trợ không nhỏ hơn ngưỡng . 2) Từ các tập hợp mới tìm ra, tạo ra các luật kết hợp có độ tin cậy không nhỏ hơn . Ví dụ minh họa: Xét 4 mặt hàng (tính chất) trong một cửa hàng thực phẩm với CSDL các giao dịch thuộc loại nhỏ, chỉ có 4 giao dịch (giỏ mua hàng), cho trong các bảng sau: Giao dịch Mua hàng gì? T1 Bánh mì, Bơ, Trứng T2 Bơ, Trứng, Sữa T3 Bơ T4 Bánh mì, Bơ Bảng 2.1. Giao dịch mua hàng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 Cho trước 2 ngưỡng  = 40% và  = 60% Ta tính độ hỗ trợ của các tập hợp các tính chất. Tập hợp Tập các bản ghi Tỷ lệ Độ hỗ trợ Vượt ngưỡng độ hỗ trợ 40% Bánh mì {1,4} 2/4 50% Đúng Bơ {1,2,3,4} 4/4 100% Đúng Trứng {1,2} 2/4 50% Đúng Sữa {2} 1/4 25% Sai Bánh mì, Bơ {1,4} 2/4 50% Đúng Bánh mì, Trứng {1} 1/4 25% Sai Bánh mì, Sữa {} 0/4 0% Sai Bơ, Trứng {1,2} 2/4 50% Đúng Bơ, Sữa {2} 1/4 25% Sai Trứng, Sữa {2} 1/4 25% Sai Bánh mì, Bơ, Trứng {1} 1/4 25% Sai Bánh mì, Bơ, Sữa {} 0/4 0% Sai Bánh mì, Trứng, Sữa {} 0/4 0% Sai Bơ, Trứng, Sữa {2} 1/4 25% Sai Bánh mì, Bơ, Trứng, Sữa {} 0/4 0% Sai Bảng 2.2. Tính độ hỗ trợ cho các tập hợp chứa các mặt hàng Luật kết hợp Tỷ lệ Độ tin cậy Vượt ngưỡng độ tin cậy 60% Bánh mì  Bơ 2/4 50% Sai Bơ  Bánh mì 2/2 100% Đúng Bơ  Trứng 2/2 100% Đúng Trứng  Bơ 2/4 50% Sai Bảng 2.3. Các luật kết hợp và độ tin cậy của chúng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Agrawal đã chỉ ra việc duyệt các tập hợp các tính chất để tính ra ngưỡng độ hỗ trợ của chúng và đánh giá có vượt ngưỡng  cho trước hay không, tốn rất nhiều thời gian tính toán (độ phức tạp hàm mũ). Còn một khi đã xác định xong các tập hợp thỏa mãn điều kiện trên (gọi là các tập hợp xuất hiện thường xuyên) thì việc KPLKH đỡ tốn thời gian hơn. Agrawal đề nghị một thuật toán như sau. Thuật toán 2- Tìm luật kết hợp khi đã biết các tập hợp thƣờng xuyên): Input: I, D, , , S Output: Các luật kết hợp thỏa mãn ngưỡng độ hỗ trợ , ngưỡng độ tin cậy . Algorithm: 1) Lấy ra một tập xuất hiện –thường xuyên S S, và một tập con X  S. 2) Xét luật kết hợp có dạng X  (S X), đánh giá độ tin cậy của nó xem có nhỏ hơn  hay không. Thực chất, tập hợp S mà ta xét đóng vai trò của tập hợp giao S = X Y, và do X  (S – X) = , nên coi như Y= S – X. Các thuật toán xoay quanh KPLKH chủ yếu nêu ra các giải pháp để đẩy nhanh việc thực hiện mục 1 của Thuật toán 1. Chương sau ta điểm qua một số thuật toán. 2.3. Một số hƣớng tiếp cận trong khai phá luật kết hợp Lĩnh vực khai thác luật kết hợp cho đến nay đã được nghiên cứu và phát triển theo nhiều hướng khác nhau. Có những đề xuất nhằm cải tiến thuật toán, có đề xuất tìm kiếm những luật có ý nghĩa hơn v.v… và có một số hướng chính sau đây: - Luật kết hợp nhị phân (Binary association rule): là hướng nghiên cứu đầu tiên của luật kết hợp. Theo dạng luật kết hợp này thì các items chỉ được quan tâm là có hay không xuất hiện trong cơ sở dữ liệu giao tác Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 (Transaction database) chứ không quan tâm về mức độ hay tần xuất xuất hiện. Thuật toán tiêu biểu nhất của khai phá dạng luật này là thuật toán Apriori. - Luật kết hợp có thuộc tính số và thuộc tính hạng mục (Quantitative and categorial association rule): các cơ sở dữ liệu thực tế thường có các thuộc tính đa dạng (như nhị phân, số, mục (categorial)...) chứ không nhất quán ở một dạng nào cả. Vì vậy để khai phá luật kết hợp với các cơ sở dữ liệu này các nhà nghiên cứu đề xuất một số phương pháp rời rạc hóa nhằm chuyển dạng luật này về dạng nhị phân để có thể áp dụng các thuật toán đã có. - Luật kết hợp tiếp cận theo hướng tập thô (mining association rule base on rough set): tìm kiếm luật kết hợp dựa trên lí thuyết tập thô. - Luật kết hợp nhiều mức (multi-level association ruls): với cách tiếp cận luật kết hợp thế này sẽ tìm kiếm thêm những luật có dạng: mua máy tính PC  mua hệ điều hành Window AND mua phần mềm văn phòng Microsoft Office,… - Luật kết hợp mờ (fuzzy association rule): Với những khó khăn gặp phải khi rời rạc hóa các thuộc tính số, các nhà nghiên cứu đề xuất luật kết hợp mờ khắc phục hạn chế đó và chuyển luật kết hợp về một dạng gần gũi hơn. - Luật kết hợp với thuộc tính được đánh trọng số (association rules with weighted items): Các thuộc tính trong cơ sở dữ liệu thường không có vai trò như nhau. Có một số thuộc tính quan trọng và được chú trọng hơn các thuộc tính khác. Vì vậy trong quá trình tìm kiếm luật các thuộc tính được đánh trọng số theo mức độ xác định nào đó. Nhờ vậy ta thu được những luật “hiếm” (tức là có độ hỗ trợ thấp nhưng mang nghiều ý nghĩa). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 - Khai thác luật kết hợp song song (parallel mining of association rule): Nhu cầu song song hóa và xử lý phân tán là cần thiết vì kích thước dữ liệu ngày càng lớn nên đòi hỏi tốc độ xử lý phải được đảm bảo. Trên đây là những biến thể của khai phá luật kết hợp cho phép ta tìm kiếm luật kết hợp một cách linh hoạt trong những cơ sở dữ liệu lớn. Bên cạnh đó các nhà nghiên cứu còn chú trọng đề xuất các thuật toán nhằm tăng tốc quá trình tìm kiếm luật kết hợp trong cơ sở dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Chƣơng 3 MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 3.1. Thuật toán AIS Thuật toán do Agrwal đề nghị năm 1993. Thuật toán này chú trọng khai phá luật kết hợp có dạng X Y, với Y là tập hợp chỉ bao gồm 1 tính chất (tập hợp 1 phần tử). Thuật toán tìm cách xây dựng dần dần các tập ứng cử viên cho “chức vụ” tập hợp xuất hiện  – thường xuyên. Với cách đánh số thứ tự từ điển cho từng tính chất, việc bổ sung phần tử cho tập ứng cử viên tránh được trùng lặp, do vậy tiết kiệm tối đa thời gian tính toán. Số lượng các tập ứng cử viên quá nhiều có thể gây ra hiện tượng tràn bộ nhớ. Thuật toán đề nghị một phương án quản lý bộ nhớ hợp lý đề phòng trường hợp này: không cho phép các ứng cử viên chiếm bộ nhớ, mà ghi thẳng chúng vào đĩa ở chế đồ thường trực (disk-resident). Dưới đây là nội dung chủ yếu của Thuật toán AIS: Input: CSDL D, minsup Output: các tập mục phổ biến 1. L1 = { các tập mục phổ biến}; 2. for (k=2; Luật kết hợpk-1   ; k++ ) do begin 3. Ck = ; 4. forall các giao dịch t  D do begin 5. Lt = Subset(Lk-1,t); // các tập mục phổ biến thuộc Lk-1 chứa trong giao dịch t 6. forall các tập mục phổ biến lt  Lt B do begin 7. Ct = tăng thêm một mục có trong giao dịch t; 8. forall các ứng cử viên c  Ct do 9. if (c  Ck) then add tăng biến đếm của c thêm 1 cho mục tương ứng của Ck Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 else add c và Ck và tăng biến đếm tương ứng thêm 1; 10. End 11. Lk = { c  Ck | c.count  minsup} 12. End 13. Trả lời = k Lk ; Thuật toán được áp dụng tỏ ra thành công cho cơ sở dữ liệu của các công ty bán lẻ hàng hóa và đã tìm ra các luật kết hợp đề cập đến mối quan hệ giữa hành vi ứng xử mua hàng của khách hàng với 63 gian hàng của công ty, sau khi nghiên cứu 46.873 giao dịch mua hàng. 3.2. Thuật toán SETM Thuật toán do Houtsma đề nghị năm 1995. Thuật toán này cũng sử dụng kỹ thuật bổ sung dần dần từng phần tử (từ tập hợp 1 phần tử) nhằm tìm kiếm các tập hợp ứng cử viên. Một cải tiến đáng kể là Thuật toán đề nghị lưu lại cả ID của giao dịch cùng với tập hợp ứng cử viên. Agrawal đã chỉ ra, Thuật toán này không những không có phương án quản lý bộ nhớ mà nó còn giả định nhét toàn bộ tập hợp ứng cử viên của bước trước vào bộ nhớ để bước sau tiện bề sử dụng. Sarawagi đã chỉ ra Thuật toán này không hiệu quả. Thuật toán SETM được mô tả hình thức như sau: Input: CSDL D, minsup Output: Các tập mục phổ biến 1. L1 = {các tập mục phổ biến}; 2. L1’={các tập mục phổ biến cùng các TID của nó được sắp xếp theo TID}; 3. for (k=2; Luật kết hợpk-1   ; k++ ) do begin 4. Ck = ; 5. forall các giao dịch t  D do begin Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 6. Lt = (l  L’k-1 | l.TID = t.TID); // các tập có (k - l) mục phổ biến trong giao dịch t 7. forall các tập mục phổ biến lt  Lt do begin 8. Ct = tăng lt thêm một mục có trong giao dịch t; //Các ứng cử viên có trong t 9. C’k +={| c  Ct}; 10. end 11. end 12. Sort C’k theo các tập mục; 13. delete các mục c  C’k có c.count<minsup đưa vào L’k ; 14. Lk ={ | l  Lk'}; //kết hợp với bước 13 15. Sort L’k theo TID; 16. end 17. Trả lời = k Lk ; 3.3. Thuật toán Apriori Thuật toán do Agrawal đề nghị năm 1994, được Cheung đánh giá mang tính chất lịch sử trong lĩnh vực KPLKH, vì đã vượt xa tầm của các thuật toán quen t