chương I Khai phá dữ liệu là sự vận dụng học thuật vào các vấn đề thiết thực đang diễn ra. Khai phá dữ liệu là tiến trình khái quát các sự kiện rời rạc trong đữ liệu thành các tri thức mang tính khái quát, tính quy luật, hỗ trợ tích cực cho việc ra quyết định. Nghiên cứu nhằm xây dựng và cải thiện các kỹ thuật trong khai phá đữ liệu là một lĩnh vực hứa hẹn và phù hợp với điều kiện nghiên cứu ở Việt Nam. Khai phá dữ liệu là một ngành khá non trẻ, các kỹ thuật của ngành còn chưa có khả năng giải quyết hiệu quả tốt các bài toán thực tế.
Việc nghiên cứu cải thiện các giải thuật nhằm đưa ra các kỹ thuật mới là một khả năng có thể thực hiện trong môi trường làm việc còn thiếu thốn ở Việt Nam. Một số hướng nghiên cứu về lý thuyết trong khai phá dữ liệu đang được nghiên cứu hiện nay: Áp dụng các chiến lược để cải thiện hiệu quả các giải thuật. Phát triển các phiên bản mới của các giải thuật có khả năng giải quyết các tập dữ liệu lớn bằng kỹ thuật sử đụng bộ đệm. Song song và phân bố các giải thuật trong khai phá đữ liệu đề tận dụng khả năng tính toán mạnh của tính toán lưới,.
12 CHUONG 2 KHAI PHA CAC LUAT KET HOP SONG SONG 2. Luật kết hợp trong khai phá dữ liệu Luật kết hợp là một hướng quan trọng trong khai phá dữ liệu. Luật kết hợp giúp chúng ta tìm được các mối liên hệ giữa các mục dữ liệu (items) của cơ sở dữ liệu. Luật kết hợp là đạng khá đơn giản nhưng lại mang khá nhiều ý nghĩa.
Thông tin mà dạng luật này đem lại là rất đáng kế và hỗ trợ không nhỏ trong quá trình ra quyết định. Tìm các luật kết hợp mang nhiều thông tin từ cơ sở dữ liệu tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực khai phá dữ liệu [12]. Một số hướng tiếp cận trong khai phá luật kết hợp Lĩnh vực khai phá 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. Luật kết hợp nhị phân Luật kết hợp nhị phân (binary association rules hoặc boolean association rules) là hướng nghiên cứu đầu tiên của luật kết hợp.
Hầu hết các nghiên cứu ở thời kỳ đầu về luật kết hợp đều liên quan đến luật kết hợp nhị phân. Trong dạng luật kết hợp này, các thuộc tính chỉ được quan tâm là có hay không xuất hiện trong giao tác của cơ sở Àx dữ liệu chứ không quan tâm về “mức độ” xuất hiện. Ví đụ như khách hang A mua 10 sản phẩm B hay | san pham B được xem là như nhau. Thuật toán tiêu biéu nhất khai phá dạng luật này là thuật toan Apriori và các thuật toán thuộc họ Aprlori [16].
Đây là dạng luật đơn giản và các luật khác cũng có thể chuyển về dạng luật này nhờ một số phương pháp như rời rạc hoá, mo hoa,. Vi du vé dạng luật này: “Nếu khách hàng mua sản phẩm A thì sẽ mua sản phẩm B với độ hỗ trợ 20% và độ tin cậy 80%”. Luật kết hợp có thuộc tính số và thuộc tính danh mục Các thuộc tính của cơ sở dữ liệu thực tế có kiểu rất đa dạng: nhị phân, số, danh mục,. Để phát hiện luật kết hợp có thuộc tính số và thuộc tính danh mục (quantitative and categorial association rules), cdc nha nghién ctru đã để xuất một số phương pháp rời rạc hoá 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ó [I6].
Ví đụ về dạng luật này “Nếu là nữ và tuôi từ [30.50] thì mua thực phẩm”, với độ hỗ trợ là 20%, và độ tin cậy là 80%. Luật kết nhiều mức Luật kết nhiều mức (multi-level association rules), với cách tiếp cận theo luật AOD này sẽ tìm kiếm thêm những luật có dạng tông quát hóa. Ví dụ ta điễn tả “áo măng tô là một loại “áo mặc bên ngoài”, “áo len” là một loại “áo mặc bên ngoài”. Từ thực tế “người mua áo măng tô thì mua giày ống” và “người mua áo len thì mua giày ống”.
Ta có thê phỏng đoán một luật tổng quát hơn: “Người mua áo mặc bên ngoài thì mua giày ống”. Như vậy dạng luật này là dạng luật tổng quát hoá của 2 luật trước. Luật “Người 13 mua áo mặc bên ngoài thì mua giày ông” là một luật có giá trị đối với nhu cầu của người sử dụng hiện thời, còn luật “người mua áo măng tô thì mua giày ống” và “người mua áo len thì mua giày ống” thì không có giá trị bằng luật tông quát. Thêm vảo đó, luật tong quát có thê ở nhiều mức khác nhau.
Luật kết hợp mờ Với những hạn chế còn gặp phải trong quá trình rời rạc hoá các thuộc tính số (quantitative attributes), các nhà nghiên cứu đã để xuất luật kết hợp mờ (fuzzy association rules) [I6] nhằm khắc phục các hạn chế trên và chuyền luật kết hợp về một dạng tự nhiên hơn, gần gũi hơn với người sử dụng. Luật kết với thuộc tính được đánh trọng số Trong thực tế, các thuộc tính trong cơ sở đữ liệu không phải lúc nào cũng có vai trò như nhau. Có một số thuộc tính được chú trọng hơn và có mức độ quan trọng cao hơn các thuộc tính khác. Khi đó, trong quá trình tìm kiếm luật, chúng ta có thế gán thuộc tính này có trọng số lớn hơn thuộc tính kia.
Đây là hướng nghiên cứu rất thú vị và đã được một số nhà nghiên cứu đề xuất cách giải quyết bài toán này. Với luật kết hợp có thuộc tính được đánh trọng số, chúng ta sẽ khai thác được những luật “hiếm” (tức là có độ hỗ trợ thấp, nhưng có ý nghĩa đặc biệt hoặc mang rất nhiều ý nghĩa). Luật kết hợp song song Bên cạnh khai phá luật kết hợp tuần tự, các nhà làm tin học cũng tập trung vào nghiên cứu các thuật giải song song đề phát hiện luật kết hop, đó là Luật kết hợp song song (parallel mining of association rules) [16]. Nhu cầu song song hoá và xử lý phân tán là cần thiết bởi kích thước đữ liệu ngày càng lớn hơn nên đòi hỏi tốc độ xử lý cũng như đung lượng bộ nhớ của hệ thống phải được đảm bảo.
Có rất nhiều thuật toán song song khác nhau đã đề xuất đề có thê không phụ thuộc vào phần cứng. Bên cạnh những nghiên cứu về những biến thế của luật kết hợp, các nhà nghiên cứu còn chú trọng đề xuất những thuật toán nhằm tăng tốc quá trình tìm kiếm tập phô biến từ cơ sở dữ liệu. Ngoài ra, còn có một số hướng nghiên cứu khác về khai phá luật kết hợp như: Khai phá luật kết hợp trực tuyến, khai phá luật kết hợp được kết nối trực tuyến đến các kho dir ligu da chiéu (Multidimensional data, data warehouse) théng qua công nghệ OLAP (On-Line Analysis Processing), MOLAP (multidimensional OLAP), ROLAP (Relational OLAP),. Các tính chất của luật kết hợp Cho D là cơ sở dữ liệu giao dịch I ={ii, ia„.ia} là tập bao gồm n mục phân biệt (Item - còn gọi là các thuộc tinh - attribute).
X = I được gọi lả tập mục (itemset). tạ} là tập gồm m giao địch (Transaction - còn gọi là bản ghi - record), mỗi giao dịch có một định danh duy nhất được ký hiệu là TID (Transaction 14 Identification). Mỗi giao dịch được định nghĩa như một tập con (subset) các mục trong I(T]) và có dạng <TTD, 1, la,. 14> Một giao dịch T e D hỗ trợ (support) cho một tập mục X; X C I nếu nó có chứa tat cả các mục của X, nghĩa là X c T.
Trong một số trường hợp, người ta dùng ký hiệu TCX) dé chi tap cac giao dich hỗ trợ cho X. Ký hiệu support(X) (Viết gọn là sup(X)) - Độ hỗ trợ (support) của một tập mục X - là ty lệ phần trăm số giao dịch trong cơ sở dữ liệu D chứa X trên tổng số các giao dịch trong cơ sở dữ liệu D. Tập mục X được gọi là một tập phô biến (hay Frequent Itemset hoặc Large Itemset) theo ngưỡng minsup nếu và chỉ nếu độ hỗ trợ của nó lớn hơn hoặc băng ngưỡng minsup: sup(X)2 minsup. Một tập mục phố biến được sử dụng như là một tập đáng quan tâm trong các thuật toán, các tập mục không phải là tập mục phổ biến là những tập không đáng quan tâm.
Người ta dùng cụm từ “X có độ hỗ trợ tối thiểu” hoặc “X không có độ hỗ trợ tối thiêu” để nói lên X thoả mãn hay không thỏa mãn sup(X)> minsup. Một tập mục X được gọi là k-Itemset nếu lực lượng của X bằng k (|X| =k). Tính chất liên quan đến tập mục phố biến Tính chất 1: Độ hỗ trợ cho các tập con (Support for Subsets) Giả sử A, B là các tập mục, nếu A C B thi sup(A) = sup(B) vi tat cả các giao dịch của D hỗ trợ B thì cũng hỗ trợ A. Tính chất 2: Nếu một tập mục là tập mục không phổ biến thì mọi tập chứa nó không là tập mục phô biến (Supersets of Infrequent Sets are Infrequent).
Nếu một tập mục B không có độ hỗ trợ tối thiểu trên D, tức là sup(B) < minsup thì mọi tập cha A của B cũng không phải là tập mục phổ biến vì sup(A) < sup(B) < minsup. Tính chất này được áp dụng rất hiệu quả trong các thuật toán khai phá luật kết hợp ví dụ như Aprlorl. 15 AB 1a tap muc không phô biển tu. sơ J]—— “Am” AB bị tia Nhà ` ~~~.
Tập chúa tập mục không phô biến là không phô biến Tính chất 3: Tập con của tập mục phổ biến cũng là tập mục phố biến (Subsets of Frequent Sets are Frequent). Nếu một tập mục B là một tập mục phô biến trên D nghĩa là sup(B) > minsup thỉ mọi tập con A của B đều là tập phô biến trên D vì sup(A) > sup(B) > minsup. Định nghĩa 2: Một luật kết hợp là một quan hệ có dạng X => Y; trong đó X, Y C I là các tập mục hay còn gọi là Itemset và X ¬ Y = @. Trong do X la tiền đề, Y là hệ quả của luật.
Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy. Định nghĩa 3: Độ hỗ trợ (support) của luật kết hợp X => Y là tỷ lệ phần trăm giữa các giao dịch chứa X t2 Y và tổng số các giao dịch có trong cơ sở dữ liệu, được ký hiệu và tính theo công thức: sup(X > Y)= P(X U Y)= le px Idtr c7ỉÌ (2) Khi nói độ hỗ trợ của luật bằng 6% nghĩa là có 6% tông số giao dịch có chứa XU Y.