Tài liệu Khai thác dữ liệu bảo toàn tính riêng tư từ cơ sở dữ liệu ngoài

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM ------------------------ NGUYỄN HỮU THẢO KHAI THÁC DỮ LIỆU BẢO TOÀN TÍNH RIÊNG TƯ TỪ CƠ SỞ DỮ LIỆU NGOÀI LUẬN VĂN THẠC SĨ Chuyên ngành: Công Nghệ Thông Tin Mã ngành: 60340102 TP. HỒ CHÍ MINH, tháng 06 năm 2015 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM Cán bộ hướng dẫn khoa học: PGS. TS. Lê Trọng Vĩnh Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP. HCM ngày 15 tháng 08 năm 2015. Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm: TT Họ và Tên Chức danh Hội đồng 1 PGS. TSKH. Nguyễn Xuân Huy Chủ tịch 2 PGS. TS. Đỗ Phúc Phản biện 1 3 TS. Võ Đình Bảy Phản biện 2 4 PGS. TS. Lê Hoài Bắc Ủy viên 5 TS. Trần Đức Khánh Ủy viên, Thư ký Xác nhận của Chủ tịch Hội đồng đánh giá Luận văn sau khi Luận văn đã sửa chữa (nếu có). Chủ tịch Hội đồng đánh giá LV PGS. TSKH. Nguyễn Xuân Huy TRƯỜNG ĐH CÔNG NGHỆ TP. HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG QLKH – ĐTSĐH Độc lập – Tự do – Hạnh phúc TP. HCM, ngày 15 tháng 06 năm 2015 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: NGUYỄN HỮU THẢO Giới tính: Nam Ngày, tháng, năm sinh: 06/11/1972 Nơi sinh: Cần Thơ Chuyên ngành: Công nghệ thông tin MSHV: 1341860022 I- Tên đề tài: KHAI THÁC DỮ LIỆU BẢO TOÀN TÍNH RIÊNG TƯ TỪ CƠ SỞ DỮ LIỆU NGOÀI II- Nhiệm vụ và nội dung: - Tìm hiểu về bảo toàn tính riêng tư trong khai thác dữ liệu. Tìm hiểu về khả năng bảo toàn tính riêng tư từ CSDL ngoài Xây dựng ví dụ cho thuật toán đã nghiên cứu. Xây dựng chương trình Demo III- Ngày giao nhiệm vụ: 18/08/2014 IV- Ngày hoàn thành nhiệm vụ: 15/06/2015 V- Cán bộ hướng dẫn: PGS.TS. LÊ TRỌNG VĨNH CÁN BỘ HƯỚNG DẪN PGS.TS Lê Trọng Vĩnh KHOA QUẢN LÝ CHUYÊN NGÀNH LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này cũng như các trích dẫn hay tài liệu học thuật tham khảo đã được cảm ơn đến tác giả và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện Luận văn Nguyễn Hữu Thảo LỜI CÁM ƠN Trước hết, cho tôi được gửi lời cảm ơn đến sự hướng dẫn và giúp đỡ tận tình của PGS.TS Lê Trọng Vĩnh. Xin cảm ơn các Thầy/Cô, Khoa CNTT Đại Học Công Nghệ TP. HCM đã giúp đỡ và cung cấp cho tôi những kiến thức quí giá trong suốt thời gian học tập và nghiên cứu thực hiện luận văn. Tôi cũng xin gởi lời cảm ơn đến gia đình, bạn bè và những người thân đã luôn quan tâm và giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu hoàn thành luận văn này. Luận văn không thể tránh khỏi những sai sót, rất mong nhận được ý kiến đóng góp của mọi người cho luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn. TP. Hồ Chí Minh, ngày 15 tháng 6 năm 2015 NGUYỄN HỮU THẢO TÓM TẮT Khai phá tri thức tiềm ẩn trong cơ sở dữ liệu hiện nay là mục tiêu chung của ngành khoa học khai thác dữ liệu và được rất nhiều nhà nghiên cứu quan tâm. Với sự bùng nổ của dữ liệu và điện toán đám mây ngày nay, các thách thức cho ngành khoa học này ngày càng phát triển. Trong khai thác dữ liệu, khả năng khai thác và bảo toàn tính riêng tư từ cơ sở dữ liệu ngoài (do bên chủ dữ liệu cung cấp) là một hướng nghiên cứu mới. Hướng nghiên cứu này tập trung vào các thuật toán mã hóa và giải mã dữ liệu sao cho có thể bảo toàn được tính riêng tư trong cả trường hợp kẻ tấn công biết chính xác về tập hợp các mặt hàng trong cơ sở dữ liệu gốc và sự phổ biến của chúng (nghĩa là, mỗi mặt hàng được bán ra bao nhiêu lần). Thông tin này có thể lấy được từ một công ty cạnh tranh hoặc từ các báo cáo đã được công bố, nhưng vẫn không thể phát hiện ra dữ liệu thực và các luật có được trong quá trình khai thác. Nghiên cứu trong luận văn này tập trung vào nghiên cứu các thuật toán mã hóa và giải mã của một mô hình sở hữu dữ liệu bên ngoài, ví dụ như, một siêu thị, cung cấp dữ liệu cho một đơn vị làm dịch vụ gia công khai thác dữ liệu để nhận về các luật kết hợp từ đơn vị đó. Với yêu cầu phải bảo toàn tính riêng tư của dữ liệu, nghĩa là sẽ không tiết lộ dữ liệu bán hàng cũng như thông tin có được từ việc phân tích khai thác dữ liệu này. ABSTRACT The mining knowledge potential in the current database is the common goal of science data mining and it is very much interested researchers. With the explosion of data and cloud computing today, the challenge for this science growing. In data mining, the exploitation and preserve privacy from external databases (by the Whose data supply) is a new research direction. This research focuses on ciphers and decrypt data that can preserve the privacy in both cases the attacker know the exact set of items in the original database and the our common (that is, each item is sold out many times). This information can be obtained from a competing company or from the reports that have been published, but still can not detect the actual data and the rule has been in the mining data. Research in this thesis focuses on the study of algorithms of encoding and decoding a data model outside ownership, for example, a supermarket, providing data to a mining company service of data to get the association rules from that supermarket. With the request to preserve the privacy of the data, ie will not disclose sales data as well as information obtained from the analysis of this data mining. DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Ý nghĩa CSDL Cơ sở dữ liệu DB Cơ sở dữ liệu (Data base) Conf Độ đo tin cậy confidence Supp Độ đo hỗ trợ support SM Safety margin (khoảng độ đo an toàn) SMC Bảo mật tính toán đa thành phần (Secure multiparty computation) MST Minsup (ngưỡng hỗ trợ tối thiểu) MCT Minconf (ngưỡng tin cậy tối thiểu) TDB Cơ sở dữ liệu giao dịch (Transaction data base) PPDM Khai phá dữ liệu đảm bảo tính riêng tư (Privacy Preserving Data Mining) PPDP Công bố dữ liệu bảo mật tính riêng tư (Prevacy Preserving Data Publishing) PPPP Công bố mô hình bảo mật tính riêng tư (Prevacy Preserving Patern Publishing) DANH MỤC CÁC BẢNG Bảng 1.1 Cơ sở dữ liệu giao dịch ………………………………………………..07 Bảng 1.2 Dấu dữ liệu bằng phương pháp đổi chỗ…………………………………... 21 Bảng 2.1 Dữ liệu giao dịch Bảng 2.2 Tập phổ biến Bảng 2.3 Sửa giá trị của E trong các bộ chứa ADE ……………………….30 …………………………………30 ………………………………35 Bảng 2.4 Sửa giá trị của E trong các bộ chứa ABE ………………………………..36 DANH MỤC CÁC HÌNH Hình 1.1 Ví dụ về thuật toán Apriori ………………………………………………..13 Hình 2.1 Đồ thị giàn của các tập phổ biến P…..……………………………………31 Hình 2.2 Giàn giao đầy đủ của Poset(ABE)…………………………………………32 Hình 3.1 Cấu trúc của mô hình dịch vụ khai thác..…………………………………..47 Hình 3.2 Một ví dụ về CSDL giao dịch a) và độ hỗ trợ các mặt hàng b)…………….50 Hình 3.3 Phân phối hỗ trợ hạng mục của TDB thực tế được phân tích………………51 Hình 3.4 Phân phối hỗ trợ hạng mục trên TDB đã mã hóa với k=10,20,..,50 ..………54 Hình 3.5 Qui trình mã hóa CSDL giao dịch ………..………………………………..56 Hình 3.6 Phân nhóm với k=2……………………………………………………….58 Hình 3.7 Tạo độ nhiễu cho các nhóm……………………………………………….58 Hình 3.8 Bảng băm………………………………………………………………….59 Hình 3.9 Qui trình giải mã CSDL giao dịch…………………………………………63 Hình 4.1 Đọc CSDL từ file dữ liệu giao dịch & tính độ phổ biến………………….66 Hình 4.2 Dữ liệu đã được thay bằng ký hiệu mã hóa sau bước mapping ……………67 Hình 4.3 Dữ liệu D đã được biến đổi thành D*………………………..……………68 Hình 4.4 Dữ liệu sau khi được giải mã………..………………………..……………69 MỤC LỤC TÓM TẮT ............................................................................................................. iii ABSTRACT ...........................................................................................................iv DANH MỤC CÁC TỪ VIẾT TẮT ......................................................................... v DANH MỤC CÁC BẢNG .....................................................................................vi DANH MỤC CÁC HÌNH .................................................................................... vii MỤC LỤC........................................................................................................... viii PHẦN MỞ ĐẦU ..................................................................................................... 1 CHƯƠNG 1 TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU VÀ BẢO TOÀN TÍNH RIÊNG TƯ ....................................................................................................................... 4 1.1 GIỚI THIỆU ĐỀ TÀI ............................................................................................ 4 1.2 KHAI THÁC TẬP PHỔ BIẾN VÀ LUẬT KẾT HỢP. ........................................ 6 1.2.1 Một số khái niệm. ......................................................................................... 6 1.2.2 Khai thác tập phổ biến và luật kết hợp. ........................................................8 1.3 BẢO TOÀN TÍNH RIÊNG TƯ TRONG KHAI THÁC DỮ LIỆU.................... 15 1.3.1 Phân loại các phương pháp PPDM ............................................................. 17 1.3.2 Các phương pháp giấu dữ liệu nhạy cảm ................................................... 20 1.3.3 Các hướng tiếp cận khai thác dữ liệu bảo toàn tính riêng tư...................... 27 CHƯƠNG 2 MỘT SỐ THUẬT TOÁN KHAI THÁC DỮ LIỆU BẢO TOÀN TÍNH RIÊNG TƯ........................................................................................................... 29 2.1 ẨN CÁC TẬP MỤC NHẠY CẢM. .................................................................... 29 2.1.1 Ứng dụng lý thuyết giàn giao ..................................................................... 29 2.1.2 Lý Thuyết Giàn Giao.................................................................................. 30 2.1.3 Thuật toán ẩn tập mục nhạy cảm ................................................................32 2.2 THAY GIÁ TRỊ DỮ LIỆU THẬT BẰNG GIÁ TRỊ KHÔNG XÁC ĐỊNH ...... 37 2.3 CHỈNH SỬA DỮ LIỆU TRONG CSDL NHỊ PHÂN ........................................ 41 2.4 Kết chương:.......................................................................................................... 44 CHƯƠNG 3 MÃ HÓA VÀ GIẢI MÃ DỮ LIỆU ................................................. 45 3.1 CÁC NGHIÊN CỨU LIÊN QUAN..................................................................... 45 3.1.1 Đặt vấn đề ................................................................................................... 45 3.1.2 Một số nghiên cứu liên quan ...................................................................... 47 3.2 MÃ HÓA VÀ GIẢI MÃ DỮ LIỆU THUÊ NGOÀI ........................................... 49 3.2.1 Dữ liệu khai thác ........................................................................................ 49 3.2.2 Mô hình bảo mật ........................................................................................ 51 3.2.3 Mã hóa và giải mã ...................................................................................... 55 CHƯƠNG 4 THỰC NGHIỆM – ĐÁNH GIÁ THUẬT TOÁN ........................... 65 4.1 MÔ TẢ CHƯƠNG TRÌNH ................................................................................. 65 PHẦN KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN................................................. 69 Kết luận ...................................................................................................................... 70 Hướng phát triển ........................................................................................................ 70 1 PHẦN MỞ ĐẦU Lý do chọn đề tài Đề tài nghiên cứu các vấn đề về khai thác luật kết hợp từ cơ sở dữ liệu ngoài trong khuôn khổ bảo mật bí mật dữ liệu của doanh nghiệp cung cấp dữ liệu. Mục tiêu của việc khai thác luật kết hợp là phát hiện ra các nhóm sản phẩm hoặc các mặt hàng hay được khách hàng của siêu thị mua cùng nhau. Dữ liệu đầu vào là cơ sở dữ liệu bán hàng, là danh sách của tất cả các nhóm mặt hàng có khả năng, ví dụ như {sữa, bia, tã lót}, xuất hiện đồng thời trong các giỏ hàng có ý nghĩa về mặt thống kê. Sự phức tạp của nhiệm vụ này là điều hiển nhiên, do có hàng chục ngàn các sản phẩm khác nhau trong phân loại của một siêu thị, và vì vậy số lượng các nhóm ứng viên tiềm năng của các sản phẩm nhanh chóng bùng nổ về mặt quy mô nhóm. Sự phát triển của điện toán đám mây thúc đẩy sự ra đời của một mô hình sở hữu dữ liệu bên ngoài, chẳng hạn như một siêu thị, cung cấp dữ liệu cho một nhà cung cấp dịch vụ khai thác dữ liệu để nhận được các luật kết hợp từ đó. Với yêu cầu bảo đảm tính riêng tư của dữ liệu mà siêu thị đã cung cấp, nghĩa là sẽ không tiết lộ dữ liệu bán hàng cũng như thông tin từ việc phân tích khai thác dữ liệu này. Để có được sự bảo vệ dữ liệu một cách tối ưu, chúng ta cần phải thừa nhận một mô hình có kẻ tấn công, khí đó kẻ tấn công muốn có thông tin về dữ liệu bán hàng và các luật khai thác, từ khả năng họ đã có một số thông tin cơ bản từ đầu; vì mục đích này, đề tài giả định rằng kẻ tấn công biết chính xác về tập hợp các mặt hàng trong cơ sở dữ liệu giao dịch gốc và sự phổ biến của chúng (mỗi mặt hàng được bán ra bao nhiêu lần). Thông tin này có thể lấy được từ một công ty cạnh tranh hoặc từ các báo cáo đã được công bố. Qua nghiên cứu, luận văn cần tiếp cận được một phương pháp mã hóa và giải mã dữ liệu để đảm bảo tính riêng tư của đơn vị cung cấp dự liệu cho bên dịch vụ kia thác trong quá trình khai thác. Mục tiêu và phạm vi nghiên cứu 2 Thông tin luôn là một tài sản vô giá của doanh nghiệp và cần được bảo vệ bằng mọi giá. Tuy nhiên, với những đòi hỏi ngày càng gắt gao của môi trường kinh doanh yêu cầu doanh nghiệp phải năng động chia sẻ thông tin của mình cho nhiều đối tượng khác nhau qua Internet hay Intranet (mạng “Internet” trong nội bộ doanh nghiệp), việc bảo vệ thông tin trở nên ngày càng quan trọng và khó khăn hơn bao giờ hết. Hầu hết các doanh nghiệp ngày nay đều sử dụng các hệ quản trị cơ sở dữ liệu (CSDL) để lưu trữ tập trung tất cả các thông tin quý giá của mình. Hiển nhiên hệ thống sẽ là tiêu điểm tấn công của những kẻ xấu. Ở mức độ nhẹ, các cuộc tấn công sẽ làm hệ thống CSDL bị hỏng hóc, hoạt động không ổn định, mất mát dữ liệu làm cho các giao dịch hàng ngày của doanh nghiệp bị đình trệ. Nghiêm trọng hơn, các thông tin sống còn của doanh nghiệp bị tiết lộ (như chiến lược kinh doanh, các thông tin về khách hàng, nhà cung cấp, tài chánh, mức lương nhân viên,…) và được đem bán cho các doanh nghiệp đối thủ. Có thể nói là thiệt hại của việc thông tin bị rò rỉ là vô cùng kinh khủng. Đó sẽ là một đòn chí mạng đối với uy tín của doanh nghiệp đối với khách hàng và các đối tác. Từ những lý do này, Luận văn nghiên cứu một chương trình mã hóa có thể biến đổi cơ sở dữ liệu ban đầu nhằm bảo toàn tính riêng tư cho cơ sở dữ liệu của doanh nghiệp. Sự bảo vệ này có nghĩa là kẻ tấn công có một xác suất rất hạn chế trong việc dự đoán các mặt hàng thực tế có thể có trong dữ liệu bán hàng hoặc trong các kết quả khai thác dữ liệu; ngược lại, chủ sở hữu dữ liệu có thể giải mã một cách hiệu quả các kết quả khai thác bằng các tài nguyên giới hạn (bởi vì thông tin mà nó duy trì cho mục đích này là không đáng kể). Đồng thời, việc mã hóa cơ sở dữ liệu ban đầu có thể được thực hiện một cách hiệu quả. Phương pháp nghiên cứu - Tiến hành thu thập và đọc các tài liệu có liên quan đến đề tài. - Nghiên cứu tổng quan về cơ sở dữ liệu giao dịch. - Nghiên cứu thuật toán khai thác mã hóa và giải mã. 3 - Xây dựng chương trình demo và đánh giá kết quả đạt được. Bố cục luận văn Luận văn được tổ chức có 4 chương, phần mở đầu và phần kết luận. Chương 1: trình bày tổng quan về khai thác dữ liệu và bảo toàn tính riêng tư. Chương 2: trình bày lý thuyết và các thuật toán bảo toàn tính riêng tư. Chương 3: trình bày lý thuyết, thuật toán và các ví dụ minh họa thuật toán mã hóa và giải mã dữ liệu sử dụng cho dữ liệu ngoài. Chương 4: là kết quả chương trình thực nghiệm. 4 CHƯƠNG 1 TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU VÀ BẢO TOÀN TÍNH RIÊNG TƯ 1.1 GIỚI THIỆU ĐỀ TÀI Sự phát triển mạnh mẽ của mạng Internet hiện nay dẫn đến sự bùng nổ của thông tin, tri thức và với khối lượng dữ liệu ngày càng lớn đã thúc đẩy một lĩnh vực nghiên cứu đầy tiềm năng là khai phá tri thức và khai thác dữ liệu. Chúng ta đang bị ngập trong khối dữ liệu khổng lồ nhưng những dữ liệu thật sự có giá trị cho chúng ta thì rất nhỏ. Do đó, việc khai thác dữ liệu là quá trình giúp chúng ta có được những dữ liệu có giá trị từ khối dữ liệu khổng lồ đó. Ví dụ, tại một siêu thị, qua quá trình khai thác dữ liệu, người ta phát hiện ra rằng, nếu một người mua một thùng bia thì thường mua thêm một kg khô mực, hay một người mua kem đánh răng thì thường mua thêm bàn chải đánh răng và khăn mặt… Từ những khai thác dữ liệu đơn giản đó có thể giúp siêu thị đó kinh doanh tốt hơn. Một ví dụ khác về ngành y học, người ta để ý rằng, một số bệnh chỉ xảy ra ở một số vùng trên trái đất hoặc khi một nhóm người đã mắc một số bệnh thì những người này thường mắc thêm một số bệnh giống nhau nữa… Điều này giúp cho ngành y tế có thể chuẩn bị một số bệnh lạ ở các vùng có địa lý, khí hậu giống nhau hay phòng một số bệnh cho những người đã mắc những bệnh theo quy luật trước đó. Nhiều quốc gia khác nhau cũng có thể liên kết, chia sẻ dữ liệu với nhau để từ đó suy ra các quy luật của bọn tội phạm, khủng bố nhằm hỗ trợ việc truy bắt chúng và ngăn ngừa các cuộc khủng bố đẫm máu có thể sảy ra. Như vậy, khai thác dữ liệu mà cụ thể là khai thác luật kết hợp là một nhiệm vụ khai thác dữ liệu cơ bản, rất có lợi cho nhiều đơn vị, tổ chức và các quốc gia trên thế giới. Tuy 5 nhiên, việc khai thác này khó thể tiến hành ở một đơn vị hay một tổ chức khi yêu cầu chia sẻ dữ liệu xuất hiện giữa nhiều bên hay khi nhu cầu khai thác dữ liệu thuê cho nhà cung cấp dịch vụ của bên thứ ba. Ví dụ, dữ liệu về hoạt động giao dịch của các gian hàng khác nhau trong một chuỗi siêu thị có thể được gửi đến cho bên thứ ba cung cấp dịch vụ khai thác dữ liệu. Việc quản lý siêu thị không cần đến một đội ngũ các chuyên gia khai thác dữ liệu nội bộ. Bên cạnh đó, họ có thể cắt giảm các yêu cầu về quản lý dữ liệu nội bộ bởi vì các dữ liệu sẽ được định kỳ chuyển đến cho người cung cấp dịch vụ là người phụ trách việc duy trì các dịch vụ này và tiến hành khai thác nhằm đáp ứng yêu cầu từ các nhà phân tích kinh doanh của chuỗi siêu thị. Dự kiến rằng mô hình “dịch vụ khai thác và quản lý dữ liệu” sẽ phát triển với sự ra đời và phổ biến của điện toán đám mây. Trong ví dụ trên, chuỗi siêu thị, khách hàng là chủ sở hữu dữ liệu và nhà cung cấp dịch vụ được gọi là máy chủ. Một trong những vấn đề chính của mô hình này là máy chủ có quyền truy cập vào các dữ liệu có giá trị của chủ sở hữu và có thể biết hoặc tiết lộ thông tin nhạy cảm của họ. Ví dụ, khi nhìn vào các giao dịch, máy chủ (hoặc một kẻ xâm nhập có quyền truy cập vào máy chủ) có thể biết sản phẩm (mặt hàng) nào đã được mua cùng nhau, và đến lượt mình, các mô hình khai thác mô tả hành vi của khách hàng trong siêu thị. Trong trường hợp này, các giao dịch mua bán và mô hình được khai thác và tất cả các thông tin có thể lấy từ dữ liệu đều là tài sản của siêu thị và phải được giữ an toàn khỏi máy chủ và bất cứ kẻ xâm nhập nào khác. Thực sự là các thông tin lấy từ dữ liệu có thể được các siêu thị sử dụng trong các quyết định tiếp thị quan trọng nhằm cải thiện dịch vụ của họ. Vấn đề về bảo toàn thông tin cho các bên tham gia khai thác hay bên cung cấp dữ liệu cho dịch vụ khai thác là một vấn đề rất quan trọng và là đề tài nghiên cứu chính của luận văn này. 6 1.2 KHAI THÁC TẬP PHỔ BIẾN VÀ LUẬT KẾT HỢP. 1.2.1 Một số khái niệm. Khi dữ liệu được tổ chức theo một cấu trúc, được xử lý và mang đến cho con người những ý nghĩa, hiểu biết nào đó thì khi đó nó trở thành thông tin. Một số người có thể quan niệm thông tin là quan hệ giữa các dữ liệu. Các dữ liệu được sắp xếp theo một thứ tự hoặc được tập hợp lại theo một ràng buộc nào đó sẽ chứa đựng thông tin. Nếu những ràng buộc dữ liệu này được chỉ ra một cách rõ ràng, có ý nghĩa thì đó là các tri thức. a) Tri thức: Là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu. Tri thức có thể được xem như là dữ liệu trừu tượng và tổng quát ở mức độ cao. b) Khám phá tri thức: Là quá trình rút trích ra các tri thức chưa được nhận ra, tiềm ẩn trong các tập dữ liệu lớn một cách tự động. Khám phá tri thức hay phát hiện tri thức trong cơ sở dữ liệu là một quá trình gồm một loạt các bước phân tích dữ liệu nhằm rút ra được các thông tin có ích, xác định được các giá trị, quy luật tiềm ẩn trong các khuôn mẫu hay mô hình dữ liệu. c) Khai thác dữ liệu: Là một bước trong quá trình khám phá tri thức, gồm các thuật toán khai thác dữ liệu chuyên dùng với một số quy định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu, các mô hình dữ liệu hoặc các thông tin có ích. Nói cách khác, mục tiêu của khai thác dữ liệu là rút trích ra những thông tin có giá trị tồn tại trong CSDL nhưng ẩn trong khối lượng lớn dữ liệu. d) Dữ liệu giao dịch: Cho I = {i1, i2, …, in} là tập tất cả các mục dữ liệu (mặt hàng). T = {t1, t2, …, tm} là tập tất cả các giao dịch trong CSDL giao dịch D. CSDL được cho là quan hệ hai ngôi δ ⊆ I × T. Nếu mục i ∈ I xảy ra trong giao dịch t ∈ T thì ta viết là ( i, t) ∈δ, kí hiệu i δ t. 7 Ví dụ về bảng dữ liệu của một cơ sở dữ liệu giao dịch : Bảng 1.1. Cơ sở dữ liệu giao dịch Mã giao dịch Nội dung giao dịch 1 A, C, T, W 2 C, D, W 3 A, C, T, W 4 A, C, D, W 5 A, C, D, T, W 6 C, D, T e) Độ hỗ trợ: Cho CSDL giao dịch D và tập dữ liệu X ⊆ I. Độ hỗ trợ của X trong D, kí hiệu σ(X), được định nghĩa là số giao dịch mà X xuất hiện trong D. f) Tập phổ biến: X ⊆ I được gọi là phổ biến nếu σ(X) ≥ minsup (với minsup là giá trị do người dùng chỉ định). Tập phổ biến ký hiệu là FI. g) Tính chất của tập phổ biến: Mọi tập con của tập phổ biến cũng là tập phổ biến: Nghĩa là, Nếu X phổ biến thì mọi Y ⊂ X cũng phổ biến. Mọi tập cha của tập không phổ biến cũng không phổ biến: Nghĩa là, Nếu X không phổ biến thì mọi Y ( X ⊆ Y) cũng không phổ biến. h) Luật kết hợp: Một luật kết hợp có dạng A →B, với A ⊂ I, B ⊂ I và A ∩ B = Ø. Luật A→B ngầm chứa trong D với độ đo Supp s, trong đó s là tỷ lệ các giao dịch trong D chứa A ∪ B, được diễn tả bằng xác suất P(A ∪ B). Luật A→B có độ đo Conf c trong 8 tập D, thì c là tỷ lệ giữa các giao dịch trong D chứa A thì chứa luôn B, được diễn tả bằng xác suất P(B/A). 1.2.2 Khai thác tập phổ biến và luật kết hợp. Cho tập I = {I1, I2,….,Im} là một tập các mục dữ liệu. Cho D là bộ dữ liệu cần khai thác, và là một tập trong CSDL giao dịch. Mỗi giao dịch T là một tập các mục dữ liệu và T ⊆ I. Mỗi giao dịch có một định danh, được gọi là TID. Cho A là tập các mục dữ liệu. Một giao dịch T được gọi là chứa A khi và chỉ khi A ⊆ T. Một luật kết hợp có dạng A →B, với A ⊂ I, B ⊂ I và A ∩ B = Ø. Luật A→B ngầm chứa trong D với độ đo Supp s, trong đó s là tỷ lệ các giao dịch trong D chứa A ∪ B, được diễn tả bằng xác suất P(A ∪ B). Luật A→B có độ đo Conf c trong tập D, thì c là tỷ lệ giữa các giao dịch trong D chứa A thì chứa luôn B, được diễn tả bằng xác suất P(B/A). nghĩa là: Supp (A→B) = P( A ∪ B) (1.2) Conf (A→B) = P( B/A ). (1.3) Những luật thỏa mãn cả hai ngưỡng minsup và minconf được gọi là mạnh. Một tập các mục dữ liệu đơn được gọi là itemset. Một itemset chứa k items được gọi là k-itemset. Chẳng hạn tập {computer, antivirus_software} là 2-itemset. Độ phổ biến của một itemset là số lượng các giao dịch có chứa itemset. Thường được biết với các tên là support count, hay count của itemset Nếu độ đo support count của một itemset I thỏa ngưỡng min_sup cho trước thì I là một tập phổ biến. Một tập phổ biến gồm k-items được ký hiệu là ‫ܮ‬௞ . Độ đo Conf của luật A→B có thể thu được từ độ đo support count của A và của A ∪ B. Do đó, một khi độ đo support counts của A, B và A ∪ B được tìm thấy, ta có thể kiểm