Đề tài Khai phá dữ liệu bằng luật kết hợp

g như một vòng lặp qua phương pháp tìm kiếm tham số: Mô tả mô hình bị thay đổi tạo nên một họ các mô hình. = > Với mỗi một mô tả mô hình, phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn nữa các giải pháp đơn giản không dễ đạt được. 1.7.2. Một số phương pháp khai thác dữ liệu phổ biến 1.7.2.1. Phương pháp quy nạp (Induction). Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp. • Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin trong cơ sở dữ liệu. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. • Phương pháp quy nạp: .Phương pháp quy nạp suy ra các thông tin được sinh ra từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tượng trong cơ sở dữ liệu. Phương pháp này liên quan đến việc tìm kiếm các mẫu trong CSDL. Trong khai phá dữ liệu, quy nạp được sử dụng trong cây quyết định và tạo luật. 1.7.2.2. Cây quyết định và luật • Cây quyết định: Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với các giá trị, thuộc tính của đối tượng tới lá. • Tạo luật: Các luật được tạo ra nhằm suy diễn một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng Nếu P thì Q, với P là mệnh đề đúng với một phần trong CSDL, Q là mệnh đề dự đoán. Cây quyết định và luật có ưu điểm là hình thức mô tả đơn giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó là mô tả cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn về cả độ chính xác của mô hình. 1.7.2.3. Phát hiện các luật kết hợp Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Ta có thể lấy một ví dụ đơn giản về luật kết hợp như sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A = > B. Việc phát triển một thuật toán phải phát hiện luật này trong cơ sở dữ liệu lớn là không khó. Tuy nhiên, vấn đề là ở chỗ có thể có rất nhiều luật kiểu này hoặc là ta chỉ biết một tập nhỏ dữ liệu trong cơ sở dữ liệu lớn thoả mãn tiền đề của luật. Ví dụ chỉ có số ít người mua sách tiếng anh mà mua thêm đĩa CD. Số lượng các luật kết hợp trong một số cơ sở dữ liệu lớn gần như vô hạn. Do vậy thuật toán sẽ không thể phát hiện hết các luật và không phân biệt được luật nào là thông tin thực sự có giá trị và thú vị. Vậy chúng ta đặt ra câu hỏi là luật kết hợp nào là thực sự có giá trị? Chẳng hạn ta có luật: Âm nhạc, ngoại ngữ, thể thao = > CD, nghĩa là những người mua sách âm nhạc, ngoại ngữ, thể thao thì cũng mua đĩa CD. Lúc đó ta quan tâm đến số lượng trường hơp khách hàng thoả mãn luật này trong cơ sở dữ liệu hay độ hỗ trợ cho luật này. Độ hỗ trợ cho luật chính là phần trăm số bản ghi có cả sách âm nhạc, ngoại ngữ, thể thao và đĩa CD hay tất cả những người thích cả ba loại sách trên. Tuy nhiên giá trị hỗ trợ là không đủ. Có thể có trường hợp ta có một nhóm tương đối những người đọc cả ba loại sách trên nhưng lại có một nhóm với lượng lớn hơn những người thích sách thể thao, âm nhạc, ngoại ngữ mà không thích mua đĩa CD. Trong trường hợp này tính kết hợp rất yếu mặc dù độ hỗ trợ tương đối cao. Như vậy chúng ta cần thêm một độ đo thứ hai đó là độ tin cây (Confidence). Độ tin cậy là phần trăm các bản ghi có đĩa CD trong số các bản ghi có sách âm nhạc, thể thao, ngoại ngữ. Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật dạng X => B sao cho tần số của luật không nhỏ hơn ngưỡng Minsup cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng Minconfi cho trước. Từ một cơ sở dữ liệu ta có thể tìm được hàng nghìn và thậm chí hàng trăm nghìn các luật kết hợp. 1.7.2.4. Mạng Neuron Mạng Neuron là tiếp cận tính toán mới liên quan tới việc phát triển cấu trúc toán học và khả năng học. Các phương pháp là kết quả của việc nghiên cứu mô hình học của hệ thống thần kinh con người. Mạng Neuron có thể đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết xuất các mẫu và phát hiện ra các xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Khi đề cập đến khai thác dữ liệu, người ta thường đề cập nhiều đến mạng Neuron. Tuy mạng Neuron có một số hạn chế gây khó khăn trong việc áp dụng và phát triển nhưng nó cũng có những ưu điểm đáng kể. Hình 1.4.Thể hiện sơ đồ khai phá dữ liệu bằng mạng Neunon. Một trong số những ưu điểm phải kể đến của mạng Neuron là khả năng tạo ra các mô hình dự đoán có độ chính xác cao, có thể áp dụng được cho rất nhiều loại bài toán khác nhau, đáp ứng được nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, gom nhóm, mô hình hóa, dự báo các sự kiện phụ thuộc vào thời gian, v.v. 1.7.2.5. Giải thuật di truyền Giải thuật di truyền, nói theo nghĩa rộng là mô phỏng lại hệ thống tiến hóa trong tự nhiên, chính xác hơn đó là giải thuật chỉ ra tập các cá thể được hình thành, được ước lựợng và biến đổi như thế nào? Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào sẽ bị loại bỏ. Giải thuật cũng mô phỏng lại yếu tố gen trong nhiễm sắc thể sinh học trên máy tính để có thể giải quyết nhiều bài toán thực tế khác nhau. Giải thuật di truyền là một giải thuật tối ưu hóa. Nó được sử dụng rất rộng rãi trong việc tối ưu hóa các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng Neuron. Sự liên hệ của nó với các quá trình khai phá dữ liệu. Ví dụ như trong kỹ thuật cây quyết định, tạo luật. Như đã đề cập ở phần trước, các luật mô hình hóa dữ liệu chứa các tham số được xác định bởi các giải thuật phát hiện tri thức. Giai đoạn tối ưu hóa là cần thiết để xác định xem các giá trị tham số nào tạo ra các luật tốt nhất. Và vì vậy mà giải thuật di truyền đã được sử dụng trong các công cụ khai phá dữ liệu. 1.8. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực liên quan tới nhiều ngành học khác như: Hệ CSDL, thống kê, trực quan hoá.v.v. Hơn nữa, tuỳ vào cách tiếp cận được sử dụng, khai phá dữ liệu còn có thể áp dụng một số kỹ thuật như mạng nơron, lý thuyết tập thô, tập mờ, biểu diễn tri thức, v.v.So với các phương pháp này, khai phá dữ liệu có một số ưu thế rõ rệt. So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ, khai phá dữ liệu có thể sử dụng với các CSDL chứa nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục. Trong khi đó phương pháp học máy chủ yếu được áp dụng trong các CSDL đầy đủ, ít biến động và tập dữ liệu không qua lớn. Phương pháp hệ chuyên gia: Phương pháp này khác với khai phá dữ liệu ở chỗ các ví dụ của chuyên gia thường ở mức cao hơn nhiều so với các dữ liệu trong CSDL, và chúng thường chỉ bao hàm được các trường hợp quan trọng. Hơn nữa các chuyên gia sẽ xác nhận giá trị và tính hữu ích của các mẫu phát hiện được. Phương pháp thống kê là một trong những nên tảng lý thuyết của khai phá dữ liệu, nhưng khi so sánh hai phương pháp với nhau ta có thể thấy các phương pháp thống kê còn tồn tại một số điểm yếu mà khai phá dữ liệu khắc phục được. Các phương pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều CSDL. Các phương pháp thống kê hoạt động hoàn toàn theo dữ liệu, nó không sử dụng tri thức có sẵn về lĩnh vực. Kết quả phân tích của hệ thống sẽ rất nhiều và khó có thể làm rõ ra được. Phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu. Với nhưng ưu điểm đó, khai phá dữ liệu hiện đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau như: Marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet.v.v.rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn. Một số ứng dụng của khai phá dữ liệu trong lĩnh vực kinh doanh: Brandaid: Mô hình Marketing linh hoạt tập chung vào hàng tiêu dùng. Callpla: Giúp nhân viên bán hàng xác định số lần viếng thăm của khách hàng triển vọng và khách hàng hiện có. Detailer: Xác định khách hàng nào nên viếng thăm và sản phẩm nào nên giới thiệu trong từng chuyến viếng thăm. Geoline: Mô hình thiết kế địa bàn tiêu thụ và dịch vụ. Mediac: Giúp người quảng cáo mua phương tiện trong một năm, lập kế hoạch sử dụng phương tiện bao gồm phác hoạ khúc thị trường, ước tính tiềm năng. 1.9. Một số thách thức đặt ra cho việc khai phá dữ liệu Các cơ sở dữ liệu lớn. Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp nữa. Dữ liệu bị thiếu hoặc nhiễu. Quan hệ giữa các trường phức tạp. Giao tiếp với người sử dụng và kết hợp với các tri thức đã có. Tích hợp với các hệ thống khác… * Kết luận chương I Qua chương I chúng ta đã biết được thế nào là tổng quan về khai phá dữ liệu. Nó bao gồm một số nội dung sau: Khai phá dữ liệu và phát hiện tri thức: Là quá trình khám phá tri thức tiềm ẩn trong cơ sở dữ liệu. Quá trình phát hiện tri thức từ cơ sở dữ liệu: Là một quá trình có sử dụng nhiều phương pháp và công cụ tin học để tìm ra một cơ sở dữ liệu có ích cho người sử dụng. Khai phá dữ liệu có lợi ích gì: Cung cấp tri thức và hỗ trợ việc ra quyết định, dự báo, khái quát dữ liệu. Các kỹ thuật khai phá dữ liệu: Có rất nhiều các kỹ thuật nhưng thường sử dụng kỹ thuật mô tả và dự đoán. Nhiệm vụ của khai phá dữ liệu: Phân lớp, hồi quy, gom nhóm, tổng hợp, mô hình ràng buộc, dò tìm biến đổi và độ lệch. Các phương pháp khai phá dữ liệu: Phương pháp quy nạp, cây quyết định và luật, phát hiện các luật kết hợp, mạng Neuron, giải thuật di truyền. Ứng dụng của khai phá dữ liệu: Marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Một số thách thức đặt ra cho việc khai phá dữ liệu: Cơ sở dữ liệu lớn, dữ liệu bị thiếu hoặc nhiễu, quan hệ giữa các trường phức tạp.v.v. Chương II: TẬP PHỔ BIẾN VÀ LUẬT KẾT HỢP 2.1. Mở đầu Hiện nay các công ty, doanh nghiệp đang lưu trữ một lượng thông tin lớn về bán hàng. Một bản ghi trong cơ sở dữ liệu này chứa các thông tin về ngày mua bán, số lượng hàng bán,... Từ cơ sở dữ liệu bán hàng, chúng ta có thể tìm ra các mối quan hệ giữa các cặp thuộc tính- giá trị thuộc tính. Đó là luật kết hợp tiêu biểu: Ví dụ có 80% khách hàng mua sách ngoại ngữ thì sẽ mua đĩa CD hoặc VCD. 2.2. Các khái niệm cơ bản 2.2.1. Định nghĩa 2. 2.1: Ngữ cảnh khai phá dữ liệu Cho tập O là tập hữu hạn khác rỗng các giao tác và I là tập hữu hạn khác rỗng các mặt hàng, R là một quan hệ hai ngôi giữa O và I sao cho với oO và iI, (o,i)R= > giao tác.o có chứa mặt hàng i. Ngữ cảnh khai phá dữ liệu (dưới đây sẽ gọi tắt là NCKPDL) là bộ ba (O, I, R). 2.2.2. Định nghĩa 2. 2. 2: Các kết nối Galois Cho NCKPDL (O, I, R), xét hai kết nối Galois ρ và λ được định nghĩa như sau: ρ : P (I) →P (O) và λ : P (O) →P (I): Cho S I, ρ (S) = {oO |iS, (o, i) R} Cho X O, λ (X) = {i I | oX, (o, i) R} Trong đó P (X) là tập các tập con của X. Cặp hàm (ρ, λ) được gọi là kết nối Galois. Giá trị ρ (S) biểu diễn tập các giao tác có chung tất cả các mặt hàng trong S. Giá trị λ (X) biểu diễn tập mặt hàng có trong tất cả các giao tác của X. 2.2.3. Định nghĩa 2.2.3: Độ hỗ trợ (Support) 2.2.3.1. Độ hỗ trợ của một tập mục X trong cơ sở dữ liệu D là tỉ số giữa các giao tác T D có chứa tập X là tổng số giao tác trong D (hay là phần trăm của các giao tác trong D có chứa tập mục X), kí hiệu là Supp (X). Supp (X)= Ta có 0 Supp (X) với mọi tập X. Hay có thế nói Support chỉ mức độ “thướng xuyên xảy ra” của mẫu. 2.2.3.2. Độ hỗ trợ của luật X→Y là tỉ số của số giao tác có chứa XY và số giao tác trong cơ sở dữ liệu D, kí hiệu là Supp (X→Y). Supp (X→Y)= Như vậy độ hỗ trợ của một luật bằng 50% nghĩa là có 50% số giao tác có chứa tập mục XY. Độ hỗ trợ có ý nghĩa thống kê của luật kết hợp. 2.2.4. Định nghĩa 2 2.4: Độ tin cậy ( Confidence) 2.2.4.1. Tính chất 2. 2.4.1: Hỗ trợ của tập con. Giả sử A,B I là tập các tập mục với A B thì Supp (A) Supp (B). Thật vậy, tính chất này có thể suy ra trực tiếp từ khái niệm tập mục phổ biến, vì tất cả các giao tác hỗ trợ B thì cũng hỗ trợ A. Như vậy giao tác nào chứa tập mục B thì cũng chứa tập mục A. 2.2.4.2. Tính chất 2.2.4.2 Giả sử A, B là hai tập mục, A, B I. Nễu B là tập mục phổ biến và A B thì A cũng là tập mục phổ biến. Thật vậy, nếu B là tập mục phổ biến thì Supp (B) Minsup, mọi tập mục A là tập mục con của tập mục B đều là tập mục thường xuyên trong cơ sở dữ liệu D vì Supp (A) Supp (B) (Theo tính chất 2.3.1). 2.2.4.3. Tính chất 2.2.4.3 Giả sử A, B là hai tập mục A B và A là tập mục không phổ biến thì B cũng là tập mục không phổ biến. Thật vậy, A là tập mục không thường xuyên nên Supp (A) Minsup mà A B nên Supp (A) Supp (B). Suy ra Supp (B)< Minsup vậy B là tập mục không phổ biến. 2.2.4.4. Tính chất 2. 2.4.4 Giả sử X, Y, Z I là những tập mục, sao cho X Y = Æ. Thì: Conf (XY) Conf (X/ZY Z). Thật vậy, từ X Y và X/Z X ta có: Độ tin cậy của một luật r = X→Y là tỉ số (phần trăm) của số giao tác trong D chứa XY với số giao tác trong D có chứa tập mục X. Kí hiệu độ tin cậy của một luật là Conf (r). Ta có 0 conf 1. Nhận xét: Độ hỗ trợ và độ tin cậy chính là xác suất sau: Supp (X→Y) = P (XY). Conf (X→Y) = P (Y/X) = Supp (XY)/Supp (X). Ta nói rằng với luật có độ tin cậy 85% thì có nghĩa là 85% các giao tác có chứa X thì cũng chứa Y. Độ tin cậy của một luật là thể hiện mức độ tường quan trong dữ liệu giữa hai tập X và Y. Độ tin cậy là độ đo mức độ tin cậy của một luật. 2.2.5. Định nghĩa 2.2.5: Tập mặt hàng phổ biến Cho NCKPDL (O, I, R) và Minsup (0, 1] là ngưỡng phổ biến tối thiểu. Cho S I, độ phổ biến của S ký hiệu là SP (S) là tỉ số giữa số các giao tác có chứa S và số lượng giao tác trong O. Nói cách khác SP (S)= |ρ (S)| / |O|. Cho S I, S là một tập các mặt hàng phổ biến theo ngưỡng Minsup nếu và chỉ nếu SP (S) ≥ Minsup. Trong các phần sau tập mặt hàng phổ biến sẽ được gọi tắt là tập phổ biến. Ký hiệu FS (O, I, R, Minsup) = {S P (I) | SP (S) ≥ Minsup). 2.2.6. Định nghĩa 2.2.6: Luật kết hợp Cho NCKPDL (O, I, R) và ngưỡng Minsup (0, 1]. Với một S FS (O, I, R, Minsup), gọi X và Y là các tập con khác rỗng của S sao cho S = XY và X Y = Æ. Luật kết hợp X với Y có dạng X→Y phản ánh khả năng khách hàng mua tập mặt hàng Y khi mua tập mặt hàng X. Độ phổ biến của luật kết hợp X→Y với S = X→Y là SP (S). Độ tin cậy của luật kết hợp X→Y được ký hiệu là CF (X→Y) và được tính bằng công thức CF (X→Y) = SP (XY)/SP (X) Nguyên lý Apriori. • Cho S FS (O, I, R, Minsup), nếu T S thì T FS (O, I, R, Minsup). • Cho T FS (O, I, R, Minsup), nếu T S thì S FS (O, I, R, Minsup). 2.2.6.1. Tính chất 2.2.6.1: Luật kết hợp không có hợp thành. Nếu XY và YZ thoả mãn trên D thì không nhất thiết X Y Z là đúng. Thật vậy, nếu xét trường hợp X Y= Æ và các giao dịch trên D hỗ trợ Z khi và chỉ khi chúng hỗ trợ X hoặc hỗ trợ Y. Khi đó Supp (X Y) = 0 và Conf (X Y) = 0. Tương tự, trường hợp có X Y và X Z, ta suy ra X Y Z. 2.2.6.2. Tính chất 2.2.6.2: Luật kết hợp không có tính tách. Nếu X Y Z thì X Z và Y Z chưa chắc xảy ra. Chẳng hạn xét trường hợp Z có mặt trong giao tác chỉ khi cả tập X và Y cũng có mặt, tức là Supp (X Y) = Supp (Z). Nếu độ hỗ trợ X, Y đủ lớn hớn Supp (X Y) tức là Supp (X) Supp (X Y) và Supp (Y) Supp (X Y ) thì hai luật riêng biệt sẽ không đủ độ hỗ trợ. Tuy nhiên trương hợp ngựơc lại X Y Z thì suy ra được X Y và X Z. Để giải thích cho tính chất này ta phân tích ví dụ sau: T(Y) T(Z) T(X) Hình 2.5. Minh họa luật kết hợp không có tính tách Khi Z thể hiện trong một giao dịch chỉ nếu cả X và Y đều thể hiện giao dịch đó, nghĩa là Supp (X Y) = Supp (Z). Nếu Supp cho X và Y lớn hơn Supp (X Y), thì hai luật trên sẽ không có Conf yêu cầu. Nhưng nếu X Y Z thỏa mãn trên D thì có thể suy ra X Y và X Z cũng thỏa mãn trên D vì Supp (XY) Supp (XYZ) và Supp (XZ) Supp (XYZ). 2.2.6.3. Tính chất 2.2.6.3: Luật kết hợp không có tính bắc cầu. Nếu XY và YZ thoả mãn trên D thì không thể khẳng định X Z thoả mãn trên D. Giả sử T (X) T (Y) T (Z) và Conf (X Y) = Conf (Y Z) = Minconf. Khi đó Conf (X Z) = Minconf2 < Minconf (vi 0 < Minconf < 1), suy ra luật X Z không có Conf tối thiểu, tức là X Z không thoả mãn trên D. 2.2.6.4. Tính chất 2.2.6.4 Nếu luật X (L-X) không thoả mãn độ tin cậy cực tiểu thì luật Y (L-Y) cũng không thoả mãn với các tập mục Y X L. 2.3. Tìm tập phổ biến 2.3.1. Một số khái niệm Cho NCKPDL (O, I, R) và Minsup (0, 1], tìm FS (O, I, R, Minsup). Thuật toán được xây dựng dựa trên nguyên lý Apriori. Đầu tiên thuật toán sẽ tìm các tập phổ biến có một phần tử. Sau đó các ứng viên của các tập phổ biến có hai phần tử sẽ được tạo lập bằng cách hợp các tập phổ biến có một phần tử. Một cách tổng quát, các tập ứng viên của tập phổ biến có k phần tử sẽ được tạo từ các tập phổ biến có k-1 phần tử. Gọi Fk = {S P (I) | SP (S) ≥ Minsup và |S|= k}. Thuật toán sẽ duyệt từng ứng viên để tạo Fk bao gồm các ứng viên có độ phổ biến lớn hơn hoặc bằng ngưỡng Minsup. - Tập các hạng mục (Itemset) I = {i1, i2, …, im}: VD : I = {sữa, bánh mì, ngũ cốc, sữa chua} Tập k hạng mục (k-Itemset). - Giao dịch t : tập các hạng mục sao cho t Í I VD : t = {bánh mì, sữa chua, ngũ cốc} - CSDL D = {t1, t2, …, tn}, ti= {ii1, ii2, …, iik} với iij Î I : CSDL giao dịch - Giao dịch t chứa X nếu X là tập các hạng mục trong I và X Í t VD : X = {bánh mì, sữa chua} - Độ phổ biến (supp) của tập các hạng mục X trong CSDL D là tỷ lệ giữa số các giao dịch chứa X trên tổng số các giao dịch trong D. Supp (X) = count (X) / | D | Tập các hạng mục phổ biến S hay tập phổ biến (Frequent Itemset) là tập các hạng mục có độ phổ biến thỏa mãn độ phổ biến tối thiểu Nếu Supp (S) ³ Minsup thì S - tập phổ biến. - Tính chất của tập phổ biến (Apriori). Tất cả các tập con của tập phổ biến đều là tập phổ biến. 2.3.2. Thuật toán Apriori 2.3.2.1. Mô tả thuật toán Đầu tiên thực hiện duyệt CSDL để tìm các mục riêng biệt trong CSDL và độ hỗ trợ tương ứng của nó. Tập thu được là C1. Duyệt tập C1 loại bỏ các mục có độ hỗ trợ < Minsup, các tập mục còn lại của C1 là các tập 1-Itemset (L1) phổ biến. Sau đó kết nối L1 với L1 để được tập các tập 2-Itemset C2. Duyệt CSDL xác định độ hỗ trợ của các tập mục trong C2. Duyệt C2 Loại bỏ các tập mục có độ hỗ trợ < Minsup, các tập mục còn lại của C2 là tập các tập 2-Itemset (L2) phổ biến. L2 lại được sử dụng để sinh ra L3 và cứ tiếp tục như vậy cho đến khi tìm được tập mục k-Itemset Lk mà Lk = Æ (tức là không có tập mục phổ biến nào được tìm thấy) thì dừng lại. Tập các tập mục phổ biến của CSDL là: Èki-1= L1. Để tăng hiệu quả của thuật toán trong quá trình sinh các tập mục ứng cử, ta sử dụng tính chất của tập mục phổ biến để làm giảm số lượng tập các tập ứng cử, không phải là tập phổ biến được sinh ra. Tính chất đó là: Tập các tập con khác rỗng của tập mục phổ biến đều là tập mục phổ biến. Bước nối: Input: Tập Lk+1 là tập (k+1)-Itemset phổ biến. Output: Tập Ck là tập các ứng cử viên cho tập mục phổ biến k-Itemset Tập các ứng cử k-Itemset được sinh ra từ việc kết nối Lk-1 với chính nó. Giả sử l1, l2 là các tập mục của Lk-1. Ta ký hiệu lj[i] là mục thứ Itemset trong tập mục lj,việc kết nối Lk-1 với Lk+1 được thực hiện như sau: Các tập mục của Lk-1 được kết nối với nhau nếu mục đầu của chúng trùng nhau và l1[k-1]<l2[k-1]. Tức là hai tập mục l1 và l2 của Lk-1 có thể kết nối được với nhau nếu thoả mãn: (L1[1] = L2[1])^(L1[2] = L2[2])^...^(L1[k-2] = L2[k-2])^(L1[k-1] = L2[k-1]) Điều kiện l1[k-1] < l2[k-1] để đảm bảo không sinh lặp lại các tập đã sinh. Kết quả tập mục thu được sau khi kết nối l1 và l2 sẽ là (l1[1], l1[2], v.v.l1[k-2], l1[k-1], l2[k-1]). Bước tỉa (Prune) Input: Ck – là tập các ứng cử k-Itemset Output: Lk – là tập các tập k-Itemset phổ biến Ta có Ck ÊLk các thành phần của Ck có thể là phổ biến hoặc không phổ biến, nhưng tất cả các tập k-Itemset đều nằm trong Ck. Bước này chúng ta thực hiện các công việc sau: Quét CSDL D một lần tính độ hỗ trợ cho mỗi tập mục trong Ck. Loại bỏ những tập mục có độ hỗ trợ nhỏ hơn hoặc bằng giá trị Minsup cho trước khỏi Ck. Tập Ck thu được chính là Lk. Tuy nhiên tập Ck có thể rất lớn và vì vậy nó làm cho công việc tính toán trở nên phức tập. Để giảm kích thước của tập Ck thì ta sử dụng tính chất Apriori: Bất kỳ một tập (k-1)-Itemset không phổ biến thì nó không thể là tập con của tập k-Itemset phổ biến, Do đó, nếu bất kỳ tập con (k-1)-Itemset của ứng cử k-Itemset không có mặt trong Lk-1 thì ứng cử đó không là phổ biến, và do vậy có thể loại bỏ tập mục này khỏi Ck. Việc kiểm tra các tập con (k-1)-Itemset có thể được thực hiện một cách nhanh chóng bằng cách duy trì một cây băm . 2.3.2.2. Ví dụ minh hoạ cho thuật toán Apriori Xét CSDL giao dịch D được cho trong bảng sau: Bảng 2.1. CSDL sử dụng minh hoạ thuật toán Apriori TID Danh sách các mục 1 I1 I2 I5 2 I2 I4 3 I2 I3 4 I1 I2 I4 5 I1 I3 6 I2 I3 7 I1 I3 8 I1 I2 I3 I5 9 I1 I2 I3 Trong lần lặp đầu tiên của thuật toán, mỗi mục là một thành viên của tập ứng cử C1. Thuật toán thực hiện quét tất cả các giao dịch của D theo đó đếm số số lần xuất hiện của mỗi mục. Giả sử độ hỗ trợ cực tiểu đếm số giao dịch là 2 (tức là Minsup = 2/9*100% = 22%). Khi đó tập mục phổ biến 1-Itemset (L1), được xác định như sau: L1 bao gồm tất cả các ứng cử 1-Itemset thoả mãn độ hỗ trợ tối thiểu. Tìm ra các tập mục phổ biến 2-Itemset (L2), thuật toán sử dụng kết nối L1 với L1 để sinh ra tập ứng cử 2-Itemset (C2). C2 bao gồm tổ hợp chập lj[i] của các phần tử có trong L1 do đó số lượng các phần tử của C2 được tính như sau: |C2| = C= C= = 10 Tiếp theo, quét các giao dịch trong D và tính độ hỗ trợ của các tập ứng cử trong C2. Tập mục phổ biến 2-Itemset L2 được xác định, bao gồm các tập mục 2-Itemset là ứng cử trong C2 có độ hỗ trợ lớn hơn hoặc bằng độ hỗ trợ tối thiểu Minsup. Sinh các tập ứng cử 3-Itemset, CL¬k-1 bằng cách, kết nối L2 với chính nó ta nhận được kết quả C3 là: C3 = {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4}, {I2, I3, I5}, {I2, I4, I5}} Sử dụng tính chất Apriori để tỉa bớt các ứng cử: Tất cả các tập con của tập phổ biến là tập phổ biến. Do đó 4 ứng cử viên của tập C3 không thể là tập phổ biến vì nó chứa các tập không phổ biến, ta thực hiện tỉa (loại) bốn tập ứng cử viên đó khỏi C3. Cụ thể như sau: + Các tập {I1, I3, I5}, {I2, I3, I5} không là phổ biến vì tập con {I3, I5} của nó không phổ biến (không có trong L2). + Tập {I2, I3, I4} không là phổ biến vì tập con {I3,I4} của nó không phổ biến (không có trong L2). + Tập {I2, I4, I5} không là phổ biến vì tập con {I4, I5} của nó không phổ biến (không có trong L2). Việc tỉa bớt các tập ứng cử này sẽ làm giảm bớt việc phải quét CSDL để tính độ hỗ trợ khi xác định L3. Lưu ý rằng, với ứng cử k-Itemset, chúng ta chỉ cần kiểm tra tập con (k-1)-Itemset có là phổ biến hay không? Vì thuật toán Apriori sử dụng chiến lược tìm kiếm theo chiều rộng. Như vậy sau khi thực hiện kết nối và tỉa ta thu được kết tập C3 là: C3 = {{I1, I2, I3}, {I1, I2, I5}} Quét các giao dịch trong CSDL để xác định L3, L3 bao gồm các ứng cử 3-Itemset trong C3 thoả mãn độ hỗ trợ tối thiểu. Ta có L3 là: L3 = {{I1, I2, I3}, {I1, I2, I5}} Sinh các tập ứng cử 3-Itemset, C3 bằng cách kết nối L3 với chính nó ta nhận được kết quả C4 là tập mục {I1, I2, I3, I5}. Sau đó thực hiện bước tỉa thì tập {I1, I2, I3, I5} bị tỉa vì nó chưa tập con {I2, I3, I5} không là tập phổ biến (không có trong L3). Như vậy ta có C4 = Æ đến đây thuật toán kết thúc. Vậy tập hợp tất cả các tập mục phổ biến đã được tìm. Các tập mục phổ biến tìm được từ CSDL giao dịch D với độ hỗ trợ tối thiểu Minsup = 22% (độ hỗ trợ tối thiểu tương đương với số giao dịch = 2). Bảng 2. 2. Kết quả thực hiện thuật toán Aprori cho CSDL D Loai tập mục phổ biến Các tập mục phổ biến 1-Itemset {I1} {I2} {I3} {I4} {I5} 2-Itemset {I1, I2} {I1, I3} {I1, I5} {I2, I3} {I2, I4} {I2, I5} 3-Itemset {I1, I2, I3} {I1, I2, I5} 2.3.2.3. Procedure-Code. Input : CSDL D, Minsup Output : L : các tập phổ biến trong D Ck : Tập ứng viên kích thước k Lk : Tập phổ biến kích thước k L1 = Tìm_tập_phổ_biến_1_hạng mục (D); for (k = 1; Lk ¹ Æ; k++ {Ck+1 = Apriori_gen (Lk); // Tạo tập ứng viên (k+1) hạng mục for mỗi