Đăng ký Đăng nhập
Trang chủ Tìm hiểu một số thuật toán khai phá tập mục lợi ích cao và ứng dụng...

Tài liệu Tìm hiểu một số thuật toán khai phá tập mục lợi ích cao và ứng dụng

.PDF
84
14
77

Mô tả:

i .. ii ĐẠI HỌC THÁI NGYÊN TRƯỜNG ĐẠI HỌC CNTT&TT TÌM HIỂU MỘT SỐ THUẬT TOÁN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO VÀ ỨNG DỤNG Vũ Anh Đức Người hướng dẫn: TS Nguyễn Huy Đức Thái Nguyên- năm 2016 iii MỤC LỤC MỤC LỤC .................................................................................................................. ii DANH MỤC HÌNH ẢNH ..........................................................................................v DANH MỤC BẢNG BIỂU ...................................................................................... vi LỜI CẢM ƠN .......................................................................................................... vii LỜI CAM ĐOAN ................................................................................................... viii LỜI MỞ ĐẦU .............................................................................................................1 Chương I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ TẬP MỤC PHỔ BIẾN ..................................................................................................................2 1.1 Khái niệm về khai phá tri thức và khai phá dữ liệu ...........................................2 1.2 Quá trình khai phá dữ liệu .................................................................................3 1.3 Một số kỹ thuật khai phá dữ liệu .......................................................................4 1.4 Một số ứng dụng của khai phá dữ liệu ..............................................................8 1.5 Khai phá tập mục phổ biến. .............................................................................10 1.5.1 CSDL giao tác ...........................................................................................10 1.5.2 Tập mục phổ biến và luật kết hợp .............................................................12 1.5.2.1. Tập mục phổ biến ..................................................................................12 1.6 Thuật toán khai phá tập mục phổ biến. ............................................................15 1.6.1 Thuật toán Apriori .....................................................................................16 1.6.2 Thuật toán FP-growth ................................................................................18 1.7 Một số hướng mở rộng của bài toán khai phá tập mục phổ biến ....................25 Chương II: MỘT SỐ THUẬT TOÁN HIỆU QUẢ KHAI PHÁ TẬP MỤC LỢI ÍCH CAO ..........................................................................................................................27 2.1 Bài toán tập mục lợi ích cao. ...........................................................................27 2.1.1 Các khái niệm liêm quan đến khai phá tập mục lợi ích cao ......................28 2.1.2 Bài toán khai phá tập mục lợi ích cao: ......................................................31 2.2 Thuật toán Hai pha ...........................................................................................32 2.2.1 Cơ sở lý thuyết ..........................................................................................32 2.2.2 Các bước thực hiện của thuật toán Hai pha ...............................................33 2.3 Thuật toán HUI - Miner ...................................................................................39 iv 2.3.1. Giới thiệu thuật toán .................................................................................39 2.3.2 Cấu trúc của utility-list ..............................................................................39 2.3.3 Khai phá tập mục lợi ích cao .....................................................................44 Chương III:CHƯƠNG TRÌNH THỰC NGHIỆM ỨNG DỤNG .............................48 3.1 Bài toán phát hiện nhóm mặt hàng mang lại lợi nhuận cao trên tập dữ liệu bán hàng của siêu thị Yên Bái. .....................................................................................49 3.2 Mô tả dữ liệu ....................................................................................................50 3.3 Xây dựng chương trình ....................................................................................53 3.4 Thực nghiệm khai phá tìm tập mục lợi ích cao. ..............................................55 3.5 Ý nghĩa của kết quả thực nghiệm ....................................................................56 KẾT LUẬN ...............................................................................................................58 TÀI LIỆU THAM KHẢO .........................................................................................60 PHỤ LỤC ..................................................................................................................62 v DANH MỤC HÌNH ẢNH Hình 1.1: Quá trình phát hiện tri thức .........................................................................3 Hình 1.2: Quá trình KPDL ..........................................................................................4 Hình 1.3: Cây quyết định ............................................................................................5 Hình 1.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu .............................................6 Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy .............................................................7 Hình 1.6: Cây FP-tree được xây dựng dần khi thêm các giao tác T1, T2, T3. ........21 Hình 1.7: Cây FP-tree của CSDL DB trong bảng 1.4 ...............................................21 Hình 2.1: không gian tìm kiếm tập mục lợi ích cao ..................................................38 Hình 2.2: utility-list ban đầu .....................................................................................42 Hình 2.3: Utility-list của 2 tập mục ...........................................................................42 Hình 2.4. Cây liệt kê các tập mục .............................................................................45 Hình 3.1: Dữ liệu đã mã hóa chuẩn bị cho khai phá .................................................53 Hình 3.2: Bảng lợi ích ...............................................................................................53 Hình 3.3: Hiển thị dạng form: ...................................................................................55 Hình 3.4: Hiển thị dạng file: .....................................................................................56 vi DANH MỤC BẢNG BIỂU Bảng 1.1. Biểu diễn ngang của CSDL giao tác .........................................................11 Bảng 1.2. Biểu diễn dọc của CSDL giao tác .............................................................11 Bảng 1.3. Ma trận giao tác của CSDL ......................................................................11 Bảng 1.4 CSDL giao tác minh hoạ cho thuật toán FP- growth.................................20 Bảng 2.1: CSDL giao tác ..........................................................................................36 Bảng 2.2: bảng lợi ích ...............................................................................................36 Bảng 2.3: Bảng giao tác ............................................................................................40 Bảng 2.4: Bảng lợi ích...............................................................................................40 Bảng 2.5 Dữ liệu sau khi duyệtCSDL .......................................................................41 Bảng 3.1: Dữ liệu đã trích chọn để khai phá .............................................................50 Bảng 3.2: Bảng lợi ích các mặt hàng ........................................................................51 Bảng 3.3 Mã hóa các mặt hàng .................................................................................52 vii LỜI CẢM ƠN Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới TS. Nguyễn Huy Đức – Trường Cao đẳng Sư phạm Trung ương, người đã chỉ bảo và hướng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu khoa học và thực hiện luận văn này. Tôi xin chân thành cảm ơn sự dạy bảo, giúp đỡ, tạo điều kiện và khuyến khích tôi trong quá trình học tập và nghiên cứu của các thầy cô giáo của Viện Công nghệ Thông tin, Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên. Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè – những người luôn ở bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyến khích tôi trong cuộc sống và trong công việc. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 10 tháng 07 năm 2016 Tác giả Vũ Anh Đức viii LỜI CAM ĐOAN Tôi xin cam đoan Luận văn "Tìm hiểu một số thuật toán khai phá tập mục lợi ích cao và ứng dụng" là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của TS. Nguyễn Huy Đức. Kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Trong toàn bộ luận văn, những điều được trình bày là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin chịu hoàn toàn trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Thái Nguyên, ngày 10 tháng 07 năm 2016 Người cam đoan Vũ Anh Đức 1 LỜI MỞ ĐẦU Khai phá tập mục phổ biến có vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục phổ biến xuất hiện như là bài toán con của nhiều lĩnh vực khai phá dữ liệu như khám phá luật kết hợp, khám phá mẫu tuần tự… Bài toán khai phá luật kết hợp do Agrawal, T.Imielinski và A. N. Swami [3] đề xuất và nghiên cứu lần đầu vào năm 1993 với mục tiêu là phát hiện các tập mục phổ biến, từ đó tạo các luật kết hợp. Trong mô hình của bài toán này, giá trị của mỗi mục dữ liệu trong một giao tác là 0 hoặc 1, tức là chỉ quan tâm mục dữ liệu có xuất hiện trong giao tác hay không. Bài toán cơ bản này có nhiều ứng dụng, tuy vậy, do tập mục phổ biến chỉ mang ngữ nghĩa thống kê nên nó chỉ đáp ứng được phần nào nhu cầu của thực tiễn. Nhằm khắc phục hạn chế của bài toán cơ bản khai phá luật kết hợp, nhiều nhà nghiên cứu đã mở rộng bài toán theo nhiều hướng khác nhau. Năm 1997, Hilderman và các cộng sự đề xuất bài toán khai phá tập mục cổ phần cao. Trong mô hình này, giá trị của mục dữ liệu trong giao tác là một số. Năm 2004, nhóm các nhà nghiên cứu H. Yao, Hamilton và Butz [9], mở rộng tiếp bài toán, đề xuất mô hình khai phá tập mục lợi ích cao. Trong mô hình khai phá tập mục lợi ích cao, giá trị của mục dữ liệu trong giao tác là một số (như số lượng đã bán của mặt hàng, gọi là giá trị khách quan), ngoài ra còn có bảng lợi ích cho biết lợi ích mang lại khi bán một đơn vị hàng đó (gọi là giá trị chủ quan). Lợi ích của tập mục là số đo lợi nhuận mà tập mục đó mang lại. Khai phá tập mục lợi ích cao là khám phá tất cả các tập mục có lợi ích không nhỏ hơn ngưỡng lợi ích tối thiểu của người sử dụng. Trong những năm gần đây, bài toán này đã và đang thu hút sự quan tâm của nhiều nhà nghiên cứu trong và ngoài nước. Với mục đích tìm hiểu bài toán tìm tập mục lợi ích cao và các thuật toán khai phá hiệu quả gần đây, em đã quyết định lựa chọn đề tài “Tìm hiểu một số thuật toán khai phá tập mục lợi ích cao và ứng dụng”. Nội dung luận văn gồm 3 chương: Chương 1: Tổng quan về khai phá dữ liệu và khai phá tập mục phổ biến Chương 2: Một số thuật toán hiệu quả khai phá tập mục lợi ích cao. Chương 3: Chương trình thực nghiệm. 2 Chương I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ TẬP MỤC PHỔ BIẾN 1.1 Khái niệm về khai phá tri thức và khai phá dữ liệu KPDL là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ liệu lớn. Tri thức đó thường ở dạng các mẫu có tính chất không tầm thường, không tường minh (ẩn), chưa được biết đến và có tiềm năng mang lại lợi ích. Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD). Ở đây chúng ta có thể coi KPDL là cốt lõi của quá trình phát hiện tri thức. Quá trình phát hiện tri thức gồm các bước [4]: Bước 1: Trích chọn dữ liệu (data selection): Là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data ware houses). Bước 2: Tiền xử lý dữ liệu (data preprocessing): Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…v.v), rút gọn dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy mẫu…v.v), rời rạc hóa dữ liệu (dựa vào histograms, entropy, phân khoảng,...v.v). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa. Bước 3: Biến đổi dữ liệu (data transformation): Là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai thác ở bước sau. Bước 4: Khai phá dữ liệu (data mining): Đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn được các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu. Bước 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin 3 (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai thác ở bước trên biểu diễn theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,…v.v. Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận được cũng có thể được lưu và sử dụng lại. Hình 1.1: Quá trình phát hiện tri thức Việc KPDL có thể được tiến hành trên một lượng lớn dữ liệu có trong CSDL, các kho dữ liệu hoặc trong các loại lưu trữ thông tin khác. Các mẫu đáng quan tâm có thể được đưa đến người dùng hoặc được lưu trữ trong một cơ sở tri thức. 1.2 Quá trình khai phá dữ liệu Các giải thuật khai phá dữ liệu thường được miêu tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó 4 có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích được. Quá trình khai phá dữ liệu được thể hiện bởi mô hình sau: Hình 1.2: Quá trình KPDL + Xác định nhiệm vụ: Xác định chính xác vấn đề cần giải quyết. + Xác định các dữ liệu liên quan dùng để xây dựng giải pháp. + Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được. Ở đây có thể gặp một số vấn đề: dữ liệu phải được sao ra nhiều bản (nếu được chiết suất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi v.v…). + 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: nhằm tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó. 1.3 Một số kỹ thuật khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát hiện được nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các đối tượng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến 5 đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được những mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau: Phân lớp dữ liệu Khái niệm phân lớp dữ liệu được Han và Kamber đưa ra năm 2000. Phân lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tượng thành những lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá trị của dữ liệu sẽ xuất hiện trong tương lai. Quá trình phân lớp dữ liệu được thực hiện qua hai bước: Bước thứ nhất: Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc trưng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám sát, học theo mẫu được cung cấp trước. Bước thứ hai: Từ những lớp dữ liệu hoặc những khái niệm đã được xác định trước, dự đoán giá trị của những đối tượng quan tâm. Một kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết định. Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương ứng. Kỹ thuật này đã được nhiều tác giả nghiên cứu và đưa ra nhiều thuật toán. Một ví dụ tiêu biểu về cây quyết định: Hình 1.3: Cây quyết định 6 Trong hình 1.3 là một cây quyết định cho lớp mua laptop, chỉ ra một khách hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh giá mua laptop là Yes hay No. Sau khi mô hình này được xây dựng, chúng ta có thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc tính khách hàng mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng rộng rãi trong nhiều hoạt động của đời sống thực. Phân nhóm dữ liệu Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu. Tuy nhiên, sự phân nhóm dữ liệu là quá trình lọc không được giám sát, là quá trình nhóm những đối tượng vào trong những lớp tương đương, đến những đối tượng trong một nhóm là tương đương nhau, chúng phải khác với những đối tượng trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc về lớp nào là phải xác định trước, trong khi phân nhóm không xác định trước. Trong phân nhóm, những đối tượng được nhóm lại cùng nhau dựa vào sự giống nhau của chúng. Sự giống nhau giữa những đối tượng được xác định bởi những chức năng giống nhau. Thông thường những sự giống về định lượng như khoảng cách hoặc độ đo khác được xác định bởi những chuyên gia trong lĩnh vực của mình. Hình 1.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu Đa số các ứng dụng phân nhóm được sử dụng trong sự phân chia thị trường. Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp có thể cung cấp những dịch vụ khác nhau tới nhóm khách hàng một 7 cách thuận lợi. Ví dụ, dựa vào chi tiêu, số tiền trong tài khoản và việc rút tiền của khách hàng, một ngân hàng có thể xếp những khách hàng vào những nhóm khác nhau. Với mỗi nhóm, ngân hàng có thể cho vay những khoản tiền tương ứng cho việc mua nhà, mua xe,… Trong trường hợp này ngân hàng có thể cung cấp những dịch vụ tốt hơn và cũng chắc chắn rằng tất cả các khoản tiền cho vay đều có thể thu hồi được. Ta có thể tham khảo một khảo sát toàn diện về kỹ thuật và thuật toán phân nhóm trong. Hồi qui (Regression): Là việc học một hàm ánh xạ từ một tập dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ hồi qui tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng hạn như hồi qui tuyến tính. Tuy nhiên, phương pháp mô hình hóa cũng được sử dụng Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lượng sinh vật phát quang hiện thời trong khu rừng bằng cách dò tìm vi sóng bằng thiết bị cảm biến từ xa; dự đoán khả năng tử vong của bệnh nhân khi biết các kết quả xét nghiệm chẩn đoán; dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng cáo… hình 1.6 chỉ ra mẫu kết quả hồi quy tuyến tính đơn giản, 8 ở đây tổng số nợ được điều chỉnh cho phù hợp giống như một hàm thu nhập tuyến tính. Việc điều chỉnh này là không đáng kể bởi vì chỉ tồn tại một tương quan yếu giữa hai biến. Tổng hợp (summarization): Là công việc liên quan đến các phương pháp tìm kiếm một mô tả cô đọng cho tập con dữ liệu. Các kỹ thuật tổng hợp thường được áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Mô hình hóa phụ thuộc (dependency modeling): Là việc tìm kiếm mô tả các phụ thuộc quan trọng giữa các biến. Mô hình phụ thuộc tồn tại hai mức: + Mức cấu trúc của mô hình (thường dưới dạng đồ thị) xác định các biến phụ thuộc cục bộ vào các biến khác; + Mức định lượng của mô hình xác định mức độ phụ thuộc của biến. Những phụ thuộc này thường được biểu thị dưới dạng luật. Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy. Đó là đồ thị có hướng không có dạng chu trình, các nút biểu diễn thuộc tính và trọng số chỉ liên kết phụ thuộc giữa các nút đó. Phát hiện sự thay đổi và độ lệch (change and deviation dectection): Nhiệm vụ này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa vào các giá trị chuẩn hay độ đo đã biết trước, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu và nội dung mong đợi. Hai mô hình độ lệch thường dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ liệu trong hai tập con dữ liệu, tính cả trường hợp tập con của đối tượng này thuộc tập con kia, nghĩa là xác định dữ liệu trong một nhóm con của đối tượng có khác nhau đáng kể so với toàn bộ đối tượng. 1.4 Một số ứng dụng của khai phá dữ liệu 9 KPDL được vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông tin. Tuỳ theo bản chất của từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác nhau. KPDL được vận dụng có hiệu quả để giải quyết các bài toán phức tạp trong những ngành đòi hỏi kỹ thuật cao như: tìm kiếm mỏ dầu từ ảnh viễn thám, xác định vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong các hệ thống sản xuất. Phân nhóm và dự đoán là những kỹ thuật rất cần thiết cho việc quy hoạch và phát triển hệ thống quản lý và sản xuất trong thực tế như: dự đoán tái sử dụng điện năng cho các công ty cung cấp điện, lưu lượng viễn thông cho các công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của sản phẩm trên thị trường cho các công ty tài chính hay phân nhóm khách hàng tiềm năng. Ngoài ra KPDL còn được áp dụng trong việc giải quyết các vấn đề xã hội như: phát hiện tội phạm hay tăng cường an ninh xã hội và mang lại những hiệu quả thiết thực cho các hoạt động trong đời sống hàng ngày. Một số ứng dụng cụ thể như sau: - KPDL được sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định. - Trong sinh học: nó dùng để tìm kiếm, so sánh các hệ gen và thông tin di truyền, tìm mối liên hệ giữa các hệ gen và chẩn đoán một số bệnh di truyền. - Trong y học: KPDL giúp tìm ra mối liên hệ giữa các triệu chứng, chẩn đoán bệnh. - Tài chính và thị trường chứng khoán: KPDL dùng để phân tích tình hình tài chính, phân tích đầu tư, phân tích cổ phiếu. - Khai thác dữ liệu web. - Trong thông tin kỹ thuật: KPDL dùng để phân tích các sai hỏng, điều khiển và lập lịch trình. 10 - Trong thông tin thương mại: dùng để phân tích dữ liệu người dùng, phân tích dữ liệu marketing, phân tích đầu tư, phát hiện các gian lận. - Trong công nghiệp viễn thông: Phân tích nhu cầu và phân tích các mẫu gian lận và xác định các mẫu khác thường. 1.5 Khai phá tập mục phổ biến. 1.5.1 CSDL giao tác Định nghĩa 1.1 Cho tập các mục (Item) I = {i1, i2, i3,..., in}. Một giao tác (transaction) T là một tập con của I, T ⊆ I. CSDL giao tác là một tập các giao tác DB ={T1, T2, T3,...,Tm}. Mỗi giao tác được gắn với một định danh TID. Một tập con X ⊆ I, gồm k mục phân biệt được gọi là một k-tập mục. Giao tác T gọi là chứa tập mục X nếu X ⊆ T. Biểu diễn CSDL giao tác: CSDL giao tác thường được biểu diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác. Biểu diễn ngang: Mỗi 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 đó. 11 Bảng 1.1. Biểu diễn ngang của CSDL giao tác Định danh giao tác Các mục dữ liệu T1 A,B,C,E T2 C,D,E T3 A,B,C,E T4 A,C,D,E T5 A,B,C,D,E T6 B,C,D Biểu diễn dọc: Trong cách 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. Bảng 1.2. Biểu diễn dọc của CSDL giao tác Mục dữ liệu Định danh các giao tác A T1 ,T3 ,T4 ,T5 B T1 ,T3 ,T5, T6 C T1 ,T2 ,T3 ,T4 ,T5 ,T6 D T2 ,T4 ,T5 ,T6 E T1 ,T2 ,T3 ,T4 ,T5 Biểu diễn bởi ma trận nhị phân: Bảng 1.3. Ma trận giao tác của CSDL TID A B C D E T1 1 1 1 0 1 T2 0 0 1 1 1 T3 1 1 1 0 1 T4 1 0 1 1 1 T5 1 1 1 1 1 T6 0 1 1 1 0 12 1.5.2 Tập mục phổ biến và luật kết hợp 1.5.2.1. Tập mục phổ biến Định nghĩa 1.2 (Độ hỗ trợ ) Cho tập mục X⊆ I. Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ liệu giao tác DB, ký hiệu supp(X), là tỷ lệ phần trăm các giao tác chứa X trên tổng số các giao tác trong DB, tức là: Supp( X )  T  DB T  X DB Ta có: 0 ≤ supp(X) ≤ 1 với mọi tập mục X ⊆ I Với CSDL cho ở bảng 1.1 ta có: Supp(A)=60%, Supp(CA)=60%, Supp(CE)=80% Định nghĩa 1.3 (Tập mục phổ biến): Cho tập mục X ⊆ I và ngưỡng hỗ trợ tối thiểu (minimum support) minsup ∈[0, 1] (được xác định trước bởi người sử dụng). X được gọi là tập mục phổ biến (frequent itemset hoặc large itemset) với độ hỗ trợ tối thiểu minsup nếu supp(X) ≥ minsup, ngược lại X gọi là tập mục không phổ biến. Với CSDL giao tác cho ở bảng 1.1 ta có: - A, B, D, CA, CB, CD, EA, EB, ED: là các tập mục phổ biến theo ngưỡng minsup = 60%. - C, E, CE: là các tập mục phổ biến theo ngưỡng minsup = 80%. Tính chất của tập mục phổ biến: Tính chất 1: Với hai tập mục X, Y với X⊆Y thì supp(X) ≥ supp(Y). Tính chất 2: Mọi tập con của một tập mục phổ biến đều là tập mục phổ biến. Nghĩa là, X là tập mục phổ biến và Y⊆X thì supp(Y)≥ supp(X)≥minSup. Tính chất 3: Mọi tập cha của một tập mục không phổ biến là tập mục không phổ biến. Nghĩa là: X là tập không phổ biến và Y ⊇ X thì supp(Y) ≤ supp(X) < minSup.
- Xem thêm -

Tài liệu liên quan