Tài liệu Khai phá luật kết hợp cho cơ sở dữ liệu gia tăng

  • Số trang: 36 |
  • Loại file: PDF |
  • Lượt xem: 122 |
  • Lượt tải: 0
nganguyen

Đã đăng 34345 tài liệu

Mô tả:

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- PHÙNG QUANG TIẾN KHAI PHÁ LUẬT KẾT HỢP CHO CƠ SỞ DỮ LIỆU GIA TĂNG CHUYÊN NGÀNH : KHOA HỌC MÁY TÍNH MÃ SỐ 60.48.01 : TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: GS.TS VŨ ĐỨCTHI Phản biện 1: ………………………………………………………………………… Phản biện 2: ………………………………………………………………………… Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng lên một cách nhanh chóng. Bên cạnh đó, việc tin học hóa một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực khác đã tạo ra cho chúng ta một lượng dữ liệu cần lưu trữ khổng lồ. Hàng triệu cơ sở dữ liệu được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý,..., trong đó có nhiều cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí Terabyte. Trong các lĩnh vực kinh doanh và đời sống như: marketing, tài chính, ngân hàng, bảo hiểm, khoa học, y tế, giáo dục, an ninh, internet... các tập dữ liệu luôn luôn được bổ sung và gia tăng theo thời gian, do vậy các tập thường xuyên và các luật kết hợp đã được tính toán không còn giá trị trên tập dữ liệu mới. Ngoài ra, với một cơ sở dữ liệu ổn định, khi cần tìm các tập dữ liệu thường xuyên với độ hỗ trợ khác, công việc phải tính lại từ đầu do vậy rất mật thơi gian và tốn kém. Để cố gắng tìm ra được những phương pháp để làm giảm đi độ phực tạp và đỡ tốn kém thời gian, chi phí cho quá trình khai phá dữ liệu đối với những hệ cơ sở dữ liệu lơn, thường xuyên thay đổi nên tôi chọn đề tài “Khai phá luật kết hợp cho cơ sở dữ liệu gia tăng”. Luận văn gồm 3 chương, với các nội dung: Chương 1: Trình bày tổng quan về khám phá tri thức và khai phá dữ liệu, trong đó có đề cập đến khái niệm tri thức, dữ liệu, quá trình khám phá tri thức, nhiệm vụ và các kỹ thuật khám phá tri thức. Chương 2: Trình bày về luật kết hợp, trong đó trình bày về các khái niệm, định nghĩa, tính chất của luật kết hợp, một số kỹ thuật khai thác luật kết hợp. Chương 3: Khai phá luật kết hợp trên cơ sở dữ liệu gia tăng Luật văn này đã được hoàn thành trong khoảng thời gian không dài. Tuy nhiên, đã đạt được một số kết quả tốt, tôi đang nghiên cứu để hoàn thiện và đưa chương trình trong luận văn vào ứng dụng thực tế. Tôi xin bày tỏ sự biết ơn sâu sắc của mình tới GS.TS Vũ Đức Thi người đã trực tiếp hướng dẫn, chỉ bảo tận tình, cung cấp tài liệu và phương pháp luận nghiên cứu khoa học để tôi hoàn thành bản luận văn này. Tôi xin gửi lời cảm ơn tới các thầy cô giáo đã dạy dỗ trong quá trình tôi theo học tại Học viện. Trong suốt quá trình nghiên cứu, mặc dù đã hết sức cố gắng nhưng chắc chắn luận văn không tránh khỏi những thiếu sót, rất mong nhận được sự góp ý của quý thầy cô, đống nghiệp và bạn bè để luận văn được hoàn chỉnh hơn. 2 CHƯƠNG 1 TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 1.1. Giơi thiệu khám phá tri thức và khai phá dữ liệu Trong thời đại bùng nổ thông tin, các công nghệ lưu trữ dữ liệu hiện nay càng được phát triển tạo điều kiện cho các đơn vị thu thập thông tin dữ liệu được tốt hơn. Đặc biệt là trong các lĩnh vực kinh doanh, giáo dục, y tế, ngân hàng,… khối lượng lưu trữ thông tin dữ liệu lên tới hàng Gigabyte thập chí hàng Terabayte. Với khối lượng thông tin dữ liệu lớn như vậy và ngày cang tăng thì các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống không còn đáp ứng được với nhu cầu của tình hình mới là nhanh, chính xác được nữa; do vậy một khuynh hướng kỹ thuật mới đã ra đời đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD- knowledge Discovery and Data Mining). Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được hiểu ra, có thể được phát hiện, hoặc có thể được học. Nói cách khác, tri thức có thể được coi là dữ liệu có độ trừu tượng và tổ chức cao. Phát hiện tri thức trong các cơ sở dữ liệu một qui trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được. Còn khai thác dữ liệu là một bước trong qui trình phát hiện tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra các mẫu hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi hàng “núi” dữ liệu. Nhiều người coi khai phá dữ liệu và khai phá tri thức trong cơ sở dữ liệu là như nhau. Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình phát hiện tri thức trong cơ sở dữ liệu. 1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu Quá trình khai phá dữ liệu sẽ tiến hành qua 6 giai đoạn như sau: Envalution of Rule Data Mining Transformat ion Cleansing Preprocessing Knowledg e Preparation Selection Transforme d Data Gatherin g Internet, ... Target Data Data Cleansed Preprocesse d Preparated Pattern Discover y 3 Hình 1.1 Quá trình khám phá tri thức từ cơ sở dữ liệu - Gom dữ liệu ( Gathering) - Trích lọc dữ liệu ( Selection) - Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu ( cleansing, Pre-processing and Preparation) - Chuyển đổi dữ liệu (Transformation) - Phát hiện và trích mẫu dữ liệu ( Pattern Extraction and Discovery) - Đánh giá kết quả mẫu (Evaluation of Result) 1.2.1. Xác định vấn đề 1.2.2. Thu thập và tiền xử lý dữ liệu 1.2.3. Khai thác dữ liệu 1.2.4. Minh họa và đánh giá 1.2.5. Đưa kết quả vào thực tế 1.3. Khai phá dữ liệu 1.3.1 Các quan niệm về khai phá dữ liệu Sau đây là một số quan niệm về khai phá dữ liệu: Khai phá dữ liệu là tập hợp các thuật toán nhằm chiết xuất những thông tin có ích từ kho dữ liệu khổng lồ. Khai phá dữ liệu giống như quá trình tìm ra và mô tả mẫu dữ liệu. Dữ liệu như là một tập hợp của các vật hay sự kiện, còn đầu ra của quá trình khai phá dữ liệu như là những dự báo của các vật hay sự kiện mới. Như vậy, mục đích của khám phá tri thức và khai phá dữ liệu là tìm ra các mẫu hoặc mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị khuất bởi một số lượng dữ liệu khổng lồ. 1.3.2. Nhiệm vụ của khai phá dữ liệu - Phân cụm, phân loại, phân nhóm, phân lớp - Khai phá dữ liệu kết hợp - Lập mô hình dự báo, bao gồm hai nhiệm vụ - Phân tích đối tượng ngoài cuộc - Phân tích sự tiến hóa 1.3.3. Triển khai việc khai phá dữ liệu Nhóm các tác giả CABENA ET AL đề nghị triển khai quá trình khai phá dữ liệu theo 5 bước : Bước 1: Xác định rõ mục tiêu thương mại cần khai phá Bước 2: Chuẩn bị dữ liệu (Thu thập, tiền xử lý, chuyển đổi khuôn dạng dữ liệu nếu thấy cần thiết) 4 Bước 3: Khai phá dữ liệu (Chọn thuật toán thích hợp) Bước 4: Phân tích kết quả thu được (Xem có gì thú vị không?) Bước 5: Tiêu hóa các tri thức thu lượm được (Nhằm đề ra kế hoạch khai thác các thông tin mới) 1.3.4. Một số ứng dụng khai phá dữ liệu Hiện nay, kỹ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như (thương mại, thông tin sản xuất, thông tin khoa học, Giáo dục, y tế, marketing, ngân hàng, viễn thông, du lịch, internet… Và những gì thu được thật đáng giá. Điều đó được chứng minh bằng thực tế: Chẩn đoán bệnh trong y tế dựa trên kết quả xét nghiệm đã giúp cho bảo hiểm y tế phát hiện ra nhiều trường hợp xét nghiệm không hợp lý, tiết kiệm được nhiều kinh phí mỗi năm; Trong dịch vụ viễn thông đã phát hiện ra những nhóm người thường xuyên gọi cho nhau bằng mobile và thu lợi hàng triệu USD; IBM Suft-Aid đã áp dụng khai phá dữ liệu vào phân tích các lần đăng nhập Web vào các trang liên quan đến thị trường để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện hoạt động của các Website; Trang Web mua bán qua mạng Amazon cũng tăng doanh thu nhờ áp dụng khai phá dữ liệu trong việc phân tích sở thích mua bán của khách hàng. 1.3.5. Các kỹ thuật khai phá dữ liệu Thường được chia thành hai nhóm chính: - Kỹ thuật khai phá dữ liệu mô tả: gồm có Phân cụm (clustering), tóm tắt (summarization), trực quan hóa (visualiztation), phân tích sự phát triển và độ lệch (evolution and deviation analyst), phân tích luật kết hợp (association rules)… - Kỹ thuật khai phá dữ liệu dự đoán: gồm có Phân lớp (classification), hồi quy (regession)… Tuy nhiên, chỉ có một số phương pháp thông dụng nhất là: Phân cụm dữ liệu, phân lớp dữ liệu, phương pháp hồi quy và khai phá luật kết hợp. 1.3.6. Kiến thức của hệ thống khai phá dữ liệu Như đã trình bày ở trên, khai phá dữ liệu là một giai đoạn trong quá trình phát hiện tri thức từ số lượng lớn dữ liệu lưu trữ trong các cơ sở dữ liệu, kho dữ liệu hoặc các nơi lưu trữ khác. Bước này có thể tương tác lẫn nhau giữa người sử dụng hoặc cơ sở tri thức, những mẫu đáng quan tâm được đưa cho người dùng hoặc lưu trữ như là một tri thức mới trong cơ sở tri thức. 5 Giao diện người dùng Đánh giá mẫu Cơ sở tri thức 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 Hình 1.2 kiến trúc của hệ thống khai phá dữ liệu Kiến trúc của hệ thống khai phá dữ liệu (hình 1.2) có các thành phần như sau: - Cơ sở dữ liệu, kho dữ liệu: Đó là một hoặc tuyển tập các cơ sở dữ liệu, kho dữ liệu… Các kỹ thuật làm sạch dữ liệu, tích hợp, lọc dữ liệu có thể thực hiện trên dữ liệu. - Cơ sở dữ liệu hoặc kho dữ liệu phục vụ: Là kết quả lấy dữ liệu có liên quan trên cơ sở khai phá dữ liệu của người dùng. - Cơ sở tri thức: Đó là lĩnh vực tri thức được sử dụng để hướng dẫn việc tìm hoặc đánh giá các mẫu kết quả thu được. - Mô tả khai phá dữ liệu: Bao gồm tập các modul chức năng để thực hiện các nhiệm vụ mô tả đặc điểm, kết hợp, phân lớp, 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: Đâ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 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 đề 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. 6 Xác định nhiệm vụ Xác đinh 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 Hình 1.3. Quá trình khai phá dữ liệu Sau đó 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. 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 - Dữ liệu lớn: - Kích thước lớn: - Dữ liệu động: - Các trường dữ liệu không phù hợp - Các giá trị bị thiếu - Các trường hợp dữ liệu bị thiếu - Quá phù hợp - Khả năng biểu đạt mẫu - Sự tương tác với người sử dụng các tri thức sẵn có 7 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 mua hàng ở 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 các 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ách hàng đỡ 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 văn bản có nhiều câu giống nhau 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, những “website đúp” (mirror website). 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 2 là tìm luật. 2.2. Các khái niệm cơ bản 2.2.1. Cơ sở dữ liệu giao tác Cho I={x1,x2,...,xn} là tập hợp các mục dữ liệu. Một tập con t={ xi1,xi2,…,xik} i gọi là một giao tác trên I. Một bảng gồm m giao tác T={ t1,t2,…,tm} gọi là một cơ sở dữ liệu giao tác trên I. Mỗi tập con của X ⊆ I gọi là tập mục dữ liệu ( itemset), mỗi tập con S⊆T gọi là tập giao tác ( tidset). Để thuận tiện trong ký hiệu, ta viết X= ABC thay cho X={ A, B, C}, viết S=123 thay cho S={1,2,3}. 2.2.2. Biểu diễn cơ sở dữ liệu giao tác Có hai cách biểu diễn tập cơ sở dữ liệu giao tác sau: - Biểu diễn ngang Một csdl là một danh sách các giao tác. Mỗi giao tác có một định danh giao tác (tid) và một danh sách những mục dữ liệu trong giao tác đó. Ví dụ 1.2: Giao tác t1 t2 t3 t4 t5 t6 t7 t8 Mục dữ liệu A,B,C B,D B,C A,B,D A,C B,C A,C A,B,C,E 8 t9 t10 A,B,C A,B,E,G Bảng: 2.1 Biểu diễn ngang của cơ sở dữ liệu giao tác - Biểu diễn dọc: Một cơ sở dữ liệu là một danh sách những mục dữ liệu, với mỗi mục dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu này. Định danh giao tác Mục dữ liệu A B C D E G t1,t4,t5,t7,t8,t9,t10 t1,t2,t3,t4,t6,t8,t9,t10 t3,t5,t6,t7,t8,t9 t2,t4 t1,t8,t10 t10 Bảng 2.2: Biểu diễn dọc của cơ sở dữ liệu giao tác Ma trận giao tác: cho một cơ sở dữ liệu giao tác T={t1,t2,…,tm} trên I={ x1,x2,…,xn}. Ma trận giao tác của T là ma trận m=(mij) m*n được định nghĩa  1 khi xj  ti  mij   0 khi xj  ti  ví dụ: 1.3: với cơ sở dữ liệu giao tác 1.1 ta có ma trận giao tác là: t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 A 1 0 0 1 1 0 1 1 1 1 B 1 1 1 1 0 1 0 1 1 1 C 1 0 1 0 1 1 1 1 1 0 D 0 1 0 1 0 0 0 0 0 0 E 0 0 0 0 0 0 0 1 0 1 G 0 0 0 0 0 0 0 0 0 1 2.2.3. Định nghĩa về luật kết hợp - Định nghĩa luật kết hợp: 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ố 9 riêng. Một luật kết hợp là một mệnh đề kéo theo cá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ó hai độ đo quan trọng với luật kết hợp: Độ hỗ trợ (support) và độ tin cậy (confidence), được định nghĩa như sau: - Đĩ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 : Y  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à có 50 bản ghi chứa X  Y. Như vậy, độ hỗ trợ mang ý nghĩa thống kê của luật. - Đị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 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) giữ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 đến nguyên 10 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ý. 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 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à minconf. 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ư: 80% 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 đề “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. Định nghĩa 2.5: Tập hợp X được gọi là tập hợp thường xuyên (Frenquent intemset) nếu có supp(X) ≥ minsup, với minsup là những 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 ⊆I, nếu B là tập hợp thường xuyên và A⊆ B thì A cũng là tậ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 và 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. Đị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à 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ớn nhất là MFI. Dễ thấy MFI ⊆ FCI ⊆ FI. Kết nối Galois: Cho cơ sở dữ liệu giao tác T trên I, ký hiệu Supset(A) là tập tất cả các tập con của A.Ta định nghĩa hai ánh xạ: tran: Subset(I) →Subset(T): X⊆I: tran(X)={t∈ T | X ⊆ t} tran (X) là tập hợp tất cả các giao tác của T chứa tất cả các thuộc tính trong X. item: Subset(T) → Subset(I): S ⊆T: item(S)={ X∈I | ∀t ∈S, x ∈t} 11 item(S) là tập hợp tất cả các thuộc tính của I xuất hiện ở tất cả các giao tác trong S. Cặp ánh xạ ( tran,item) được gọi là kết nối Galois trên T x I. 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(ABCD)/supp(AB)) Nếu conf ≥ miniconf thì luật được giữ lại ( và thỏa mãn độ hỗ trợ tối thiểu vì ABCD là phổ biến). 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ế hợp thỏa mãn ngưỡng độ hỗ trợ δ, ngưỡng độ tin cận α. * Thuật toán: 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 của 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 T1 T2 T3 T4 Mua hàng gì? Bánh mì, Bơ, Trứng Bơ, Trứng, Sữa Bơ Bánh mì, Bơ Bảng 2.3. Giao dịch mua hàng 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 như sau: Tập hợp Bánh mì Các tập {1,4} Tỷ lệ Độ hỗ trợ 2/4 50% Vượt ngưỡng độ Đúng 12 Bơ Trứng Sữa Bánh mì, Bơ Bánh mì, Trứng Bánh mì, Sữa Bơ, Trứng Bơ, Sữa Trứng, sữa Bánh mì, Bơ, trứng Bánh mì, Bơ, Sữa Bánh mì, Trứng, Sữa Bơ, Trứng, Sữa Bánh mì, Bơ, Trứng, Sữa {1,2,3,4} {1,2} {2} {1,4} {1} {} {1,2} {2} {2} {1} {} {} {2} {} 4/4 2/4 1/4 2/4 1/4 0/4 2/4 1/4 1/4 1/4 0/4 0/4 1/4 0/4 100% 50% 25% 50% 25% 0% 50% 25% 25% 25% 0% 0% 25% 0% Đúng Đúng Sai Đúng Sai Sai Đúng Sai Sai Sai Sai Sai Sai Sai Bảng 2.4: 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 Bánh mì → Bơ Bơ → Bánh mì Bơ → Trứng Trứng → Bơ Tỷ lệ 2/4 2/2 2/2 2/4 Độ tin cậy 50% 100% 100% 50% Vượt ngưỡng độ tin cậy 60% Sai Đúng Đúng Sai Bảng 2.5: Các luật kết hợp và độ tin cậy của chúng 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 tính bằng 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 khai phá luật kế hợp đỡ tốn thời gian hơn. Agrawal đề nghị một thuật toán 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 α * Thuật toán: 1) Lây ra một tập xuất hiện δ – thường xuyên s ∈ S, và 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 – X. Các thuật toán xoay quanh khai phá luật kết hợp chủ yếu nêu các giải pháp để đẩy nhanh việc thực hiện mực 1 của thuật toán 1 như đã nêu ở trên. 2.3. Một số hướng tiếp cận trong khai phá luật kết hợp - Luật kết hợp nhị phân ( Binary association rule): 13 - 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): - Luật kết hợp tiếp cận theo hướng tập thô ( mining association rule base on rough set): - Luật kết hợp nhiều mức ( multi-level association rules): - Luật kết hợp mờ ( fuzzy association rule): - Luật kết hợp với thuộc tính được đánh trọng số ( association rules with weighted items): 2.4. Khai thác luật kết hợp song song ( parallel mining of association rule): Một số thuật toán khai phá luật kết hợp 2.4.1- Thuật toán AIS 2.4.2- Thuật toán SETM 2.4.3- Thuật toán Apriori * Thuật toán Apriori Input: CSDL D, minsup. Output: Tập các tập mục phổ biến. 1. L1 = {Các 1 - itemset phổ biến}; 2. k=2; 3. While( Lk-1! = ) 4. { Ck = apriori_gen(Lk-1, minsup);// các ứng cử mới theo chương trình con ở dưới đây. 5. for(  giao dịch t D) 6. { Ct=Subset (Ck,t);// ứng cử viên được chứa trong t 7. for ( ứng cử c  Ct) 8. c.count ++; 10. } 11. Lk={ c  Ck c.count  minsup} 12. K++; 13. } 14. Return L= kLk' ; // sinh ứng cử viên mới (**) Void apriori_gen(Lk-1, minsup ) 1. { 2. for ( itemset l1 Lk-1) for ( itemset l2 Lk-1) 3. if((L1(1)== L2(1)&&L1(2) == L2(2)&&...&& L1(k-2) == L2(k-2)) &&L1(k-1) == L2(k-1)) 14 4. c= L1 kết nối L2; { 5. if( hasinrequent_subset(c, Lk-1)) delete c; 6. else add c to Ck; 7. 8. } return Ck 9.} Void has_infrequent_subset(c,Lk-1) 1.{ for ( (k-1)-subset s c) 2. if(s  Lk-1) return TRUE; 3. else return FALSE ; 4.} * Ví dụ minh hoạ thuật toán Apriori Cho CSDL dưới đây, tìm các tập phổ biến có độ hỗ trợ tối thiểu là 60%. D (CSDL) TID Các mục T100 {F, A, D, B} T200 {D, A, C, E, B} T300 {C, A, B, E} T400 {B, A, D} C2 2 - itemset {A, B} {A, D} {B, D} Tỉa C1 Quét toàn bộ D C2 2 - itemset {A, B} {A, D} {B, D} 1 - itemset {A} {B} {C} {D} {E} {F} support 100% 100% 50% 75% 50% 25% Xóa bỏ mục có support < minsup L1 1 - itemset {A} {B} Kết nối {D} L1 & L1 support 100% 100% 75% 15 C2 2 - itemset {A, B} {A, D} {B, D} Quét toàn bộ D L2 2 - itemset support {A, B} 100% {A, D} 75% {B, D} 75% Tỉa 3 - itemset {A, B, D} 3 - itemset {A, B, D} Kết nối L2 & L 2 Quét toàn bộ D L3 3 - itemset support {A, B, D} 75% Như vậy, tập các tập mục phổ biến mà ví dụ trên thu được là: L = L1 L2 L3 = { {A},{B},{D},{A, B},{A, D},{B, D},{A, B, D}} Nhận xét: Thuật toán Apriori với n là độ dài lớn nhất của tập được sinh ra. Vậy thì thuật toán sẽ thực hiện duyệt toàn bộ các giao tác n+1 lần. Như vậy, nếu bỏ qua thời gian so sánh tìm sự xuất hiện của một mẫu trong một giao tác thì độ phức tạp của thuật toán Apriori là O(A) > O(n*L) trong đó L là kích thước CSDL còn n là độ dài cần đạt được của các mẫu. Ngoài ra, nếu độ hỗ trợ tối thiểu minsup bị thay đổi thì thuật toán sẽ phải thực hiện lại từ đầu, điều này sẽ rất mất thời gian. Thuật toán Apriori được xây dựng nhằm phát hiện các luật kết hợp giữa các đối tượng với độ hỗ trợ và độ tin cậy tối thiểu. 2.4.4 - Thuật toán CHARM 2.4.5- Thuật toán PARTITION_P_TREE ( Thuật toán phân hoạch ) 16 CHƯƠNG 3 THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG 3.1. Mở đầu Chương này giới thiệu và nghiên cứu về hai thuật toán khai phá các luật kết hợp trong cơ sở dữ liệu gia tăng. [4] Thuật toán xử lý dữ liệu tăng trưởng theo chiều dọc, và chiều ngang dựa trên kỹ thuật xây dựng cây. 1) Thoạt đầu, chưa có dữ liệu, ta xây dựng cây rỗng. Khi một giao tác t  {x i , x i ,..., x i } trên I = {x1, x2, …, xn} xuất hiện, ta chèn dữ liệu vào cây. Với t vừa xuất 1 k 2 hiện, nếu x i  I thì ta đặt x i = xn+1 và tăng trưởng I = {x1, x2, …, xn, xn+1}. j j 2) Với cây đã được xây dựng, ta duyệt cây để tính độ hỗ trợ của mọi tập mục dữ liệu đã xuất hiện trong các giao tác và từ đó tìm ra mọi tập thường xuyên với ngưỡng hỗ trợ tùy ý. 3) Khi việc khai thác dữ liệu gián đoạn, có thể lưu trữ cây ra bộ nhớ ngoài và rồi đưa vào bộ nhớ trong để xử lý khi cần thiết. Với các giao tác đã xử lý, có thể hủy bỏ, không ảnh hưởng đến công việc xử lý dữ liệu tăng trưởng tiếp theo. Dựa trên lý thuyết giải thuật của hai bài toán xử lý dữ liệu gia tăng theo chiều dọc và xử lý dữ liệu gia tăng theo chiều ngang trong [4]. Tác giả xây dựng chương trình ứng dụng minh họa cho thuật toán xử lý dữ liệu gia tăng theo chiều ngang, chương trình xử lý được về mặt kỹ thuật của thuật toán một cách trực quan thông qua ngôn ngữ lập trình Visual Studio 2008 và sử dụng cấu trúc lập trình ngôn ngữ lập trình C#. Xây dựng một ứng dụng vào hệ cơ sở dữ liệu thống kê dân số để mô tả và minh họa cho thuật toán gia tăng theo chiều ngang. 3.2. Cơ sở lý thuyết 3.3. Thuật toán xử lý dữ liệu gia tăng theo chiều dọc 3.3.1. Ý tưởng thuật toán Thuật toán gia tăng 1 khai phá luật kết hợp trên cơ sở dữ liệu gia tăng theo chiều dọc. 2) Khi đi tìm tập mục dữ liệu thường xuyên theo một ngưỡng S0 nào đó, ta cần tính độ hỗ trợ của tất cả các tập ứng viên và lưu lại. SC={(X,Sup)| X là tập ứng viên và Sup=Supp(X)}. 3) Khi dữ liệu chưa gia tăng, cần tìm các mục dữ liệu thường xuyên có độ hỗ trợ S1 ≥ S0, công việc đơn giản là lọc từ SC để tạo ra tập: FS1={X| (X,Sup) ∈ SC và Sup ≥ S1} 4) Theo thời gian, số lượng các giao tác tăng dần, thuật toán tính toán lại độ hỗ trợ của các tập ứng viên trong SC chỉ dựa vào dữ liệu tăng thêm, không cần tính toán lại từ đầu. 3.3.2. Phân lớp dữ liệu * Thủ tục Vertical chuyển đổi cơ sở dữ liệu giao tác T thành biểu diễn dọc. 17 Thủ tục Vertical(T,P) Input: T={t1,t2,…,tm}: cơ sở dữ liệu giao tác trên I={x1,x2,…,xn}; Output: P={P1,P2,…,Pn} với Pi = (ti1,ti2,…,tik); Method: 1. For ( i= 1; i>= n; i++) 2. { 3. Pi=Ø; 4. } 5. For (j=1 ; j>= m ; j++) 6. For (i= 1; i>= n ; i++) 7. { 8. If (xi ∈ tj ) 9. { 10. Pi=Pj ∪ {j}; 11. } 12. } 3.3.3. Các thủ tục phụ trợ * Thủ tục Sort_List Trên I={x1,x2,…,xn} ta định nghĩa một quan hệ thứ tự như sau: ∀xi, yj ∈ I: xi < xj ⇔ Supp (xi) ≤ Supp (xj) Trong mục này, khi mô tả một tập mục dữ liệu X thì các thành phần của nó đã được sắp xếp theo thứ tự trên: X= {x1,xi2,…,xik} ⇒ Supp(xi1) ≤ Supp(xik)⇒ i1 < …< ik Cho Si là một số nguyên, gọi là ngưỡng cho trước, đặt Fsi= {X | X ⊆ I và Supp (X) ≥ Si} Từ định nghĩa, ta có: Nếu S1 ≥ S2 thì Fs1 ≥ Fs2. Trên Fsi ta định nghĩa một quan hệ thứ tự πF như sau: ∀ Z,Y ∈ Fsi, Z={z1,…,zk}, Y = {y1,…,yh}: ZπF Y ⇔ ∃i : 0 ≤ i < Min {k,h}, zj=yj với mọi j ≤ i và zi+1 π yi+1. Gọi Gj={X∈ Fsi | ||X||=j}. Thủ tục Group_List(Fsi,G); Input: Fsi= {X|X ⊆I, Supp (X)≥Si} Output: G= {G1,G2,…,Gk} với Gj={X∈Fsi | ||X|| =j}; Method: 1. K:=Max (||X||) với X ∈ Fsi; 2. For (j=1; j ≤ k;j++) 3. { 4. Gj=Ø; 5. } 6. Foreach ( X in Fsi ) 7. { 8. J=||X||; 9. Gj=Gj ∪ {X}; 18 10. } *Thủ tục Sort_List Sau đây sắp xếp các phần tử của Gk thành một tập theo thứ tự πF *Thủ tục Sort_List(Gk) Input: Gk={X|X ∈ Fsi và ||X||=k}; Output: Gk={X∝1,…,X∝h } thỏa X ∝vπF X ∝v+1, v ∈ {1,…,h-1}; Method 1. For (i=1; i ≤ h-1, i++) 2. For (j=i+1; j ≤ h, j++) 3.{ 4. If (X ∝j πF X∝i ) 5. { 6. Tam=X ∝i; 7. X ∝i = X ∝j; 8. X ∝j=Tam; 9. } 10. } * Thủ tục Split-Class Gọi Gk = {X ⊆ I | ||X|| =k và Supp(X) ≥ S0=} là tập các thường xuyên theo ngưỡng S0 có k phần tử. Ta có Gk= {X1,X2,…,Xn} với Xi ={Xi1,Xi2,…,Xik}, i∈ {1,2,…,h}. Trên Gk ta định nghĩa quan hệ tương đương Rk như sau: Với Xi ={xi1,xi2,…,xik}, Y={yi1,yi2,…,yik} ∈ Gk: X Rk Y ⇔ xi1=yi1,…,xik-1=yjk-1 Hai phần tử trong Gk là tương đương nhau nếu chúng có k-1 thành phần đầu giống nhau, thành phân thứ k khác nhau. Đặt Px là lớp tương đương chứa X: Px:={Y∈ Gk|XRxY}. Như vậy, những phần tử trong một lớp tương đương có k-1 thành phần đầu tiên giống nhau. Phần giống nhau này gọi là tiền tố của Px. Gọi Z={xi1,…,xik-1} là tiền tố của Px , đặt L[Z]={xik | {xi1,…,xik}∈ Px} với tập Gk đã được sắp xếp theo thứ tự πF ở phần trên thì việc phân hoạch Gk thành các lớp tương đương là nhanh chóng. Thủ tục Slip_Class phân Gk thành các lớp tương đương. * Thủ tục Slip_Class(Gk, L) Input: Gk={X ⊆ I | ||X|| = k, Supp(X) ≥ S0} Output: L={L(Z) Z là tiền tố của Px và X ∈ Gk} Method: 1. H={Z={xi1,…,xik-1}| {xi1,xi2,…,xik}∈ Gk}; 2. L=Ø; 3. Foreach (Z= {zi1,…,zik-1}∈ H ) 4. { 5. L[Z]=Ø; 6. } 7. Foreach (X={xi1,xi2,…,xik}∈ Gk) 8. { 9. If ({zi1,…,zik-1}=={xi1,…,xik-1}) 10. { 11. L[Z]=L ∪ {xjk}; 12. }
- Xem thêm -