Chương 1: Giới thiệu nội dung và mục tiêu của đề tài Chương 2: Cơ sở lý thuyết, các giải thuật KPDL cản bản, công cụ KPDL Weka, Các giải thuật bảo mật trong KPDL bằng phương pháp Luật liên kết, Tìm hiểu cơ sở dữ liệu điểm của sinh viên trường Đại học Bách Khoa Chương 3: Đề xuất 1 số bài toán tiềm năng, áp dụng các phương pháp KPDL để giải quyết các bài toán đặt ra Chương 4: Bảo mật trong KPDL Chương 5: Tổng kết, đánh giá và hướng phát triển Tài liệu tham khảo Nguyễn Minh Ý 7/81 Privacy Preserving Data Mining Ts.Đặng Trần Khánh-Ts.Nguyễn Đức Cường 2 Chương II - Cơ sở lý thuyết 2.1 Khai phá dữ liệu Trong thời đại ngày nay, với sự phát triển vượt bậc của ngành Công Nghệ Thông Tin, các hệ thống thông tin lưu trữ dữ liệu cũng tăng lên rất nhanh. Từ khối dữ liệu này, áp dụng các kỹ thuật KPDL và máy học để phân tích và trích xuất những thông tin hữu ích ẩn chứa trong dữ liệu. Các tri thức này có thể được đưa vào để cải thiện quá trình hoạt động của hệ thống. Một số định nghĩa về KPDL: KPDL là khoa học rút trích các thông tin hữu ích từ dữ liệu quá khứ với mục đích giúp cải tiến các quyết định trong tương lai.[19] Một định nghĩa khác, KPDL là một quá trình truy xuất các thông tin ngầm, thông tin quá khứ chưa được biết đến, thông tin hữu ích tiềm ẩn như các qui luật(rules), quy tắc, các ràng buộc chứa trong cơ sở dữ liệu.
[15] Tóm lại KPDL là quá trình học tri thức mới từ những liệu đã thu thập được.[19] Một số ứng dụng của KPDL: Hiện nay kỹ thuật KPDL đ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ư:y tế, marketing, ngân hàng, viễn thông, internet… .Không ai có thể phủ định được những lợi ích to lớn mà nhờ áp dụng kỹ thuật khai phá đem lại. Điều đó được minh chứng 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ế Australia 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 1 triệu $/năm; British Telecom đã 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 được hàng triệu USD; IBM Surf – Aid đã áp dụng KPDL vào phân tích các lần đăng nhập Web vào các trang có 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 KPDL trong việc phân tích sở thích mua bán của khách hàng…. Các kỹ thuật KPDL (Data mining) được chia làm 2 nhóm chính : • Nhóm mô tả dữ liệu:có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có gồm các kỹ thuật:phân cụm (clustering), tóm tắt (Sumerization), trực quan hoá (Visualization), phân tích Luật liên kết (Association rules)… • Nhóm dự đoán:Đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm có phân lớp (Classification), hồi quy (Regesssion).
Nguyễn Minh Ý 8/81 Privacy Preserving Data Mining Ts.Đặng Trần Khánh-Ts.Nguyễn Đức Cường 2.2 Quá trình KPDL KPDL là một quá trình của khám phá những mô hình khác nhau, tổng hợp, đưa ra giá trị từ tập dữ liệu cho trước. Thông thường quá trình KPDL là quá trình lặp bao gồm các bước sau: 9 Tìm hiểu nghiệp vụ và dữ liệu 9 Chuẩn bị dữ liệu 9 Mô hình hoá dữ liệu 9 Hậu xử lý và đánh giá mô hình 9 Triển khai tri thức 2.1 Tìm hiểu nghiệp vụ và dữ liệu Đây là công việc đầu tiên cũng là công việc quan trọng nhất trong quá trình KPDL. Ở bước này người KPDL phải nắm rõ được các nguồn dữ liệu, cấu trúc của hệ thông cũng như mối quan hệ, ý nghĩa của từng bảng, từng trường tồn tại trong CSDL. Để hiểu rõ hơn về dữ liệu chúng ta phải hiểu được 1 số nghiệp vụ liên quan.
Việc hiểu rõ dữ liệu và nghiệp vụ giúp người KPDL đề xuất, định hình được 1 số bài toán tiềm năng, đặc tả, phân vùng, xác định những dữ liệu liên quan đến bài toán.2 Chuẩn bị dữ liệu Dữ liệu được thu thập thông tin từ rất nhiều nguồn khác nhau: từ những chuyên gia hoặc từ cơ sở dữ liệu có sẵn như database, data warehouses, data marts. Vì vậy công việc đầu tiên phải làm đó là kết hợp và chuẩn hoá các nguồn dữ liệu trên. Một số công việc liên quan đến bước chuẩn bị dữ liệu gồm có: • Xử lý dữ liệu bị thiếu • Khử sự trùng lắp • Loại bỏ các giá trị bất thường • Giảm nhiễu • Xây dựng các thang định danh • Chuẩn hóa, rời rạc hóa • Rút trích và xây dựng đặc trưng từ dữ liệu đã có • Giảm chiều • Chuyển dữ liệu sang dạng đơn phẳng • … 2.3 Mô hình hoá dữ liệu Có nhiều phương pháp, giải thuật Khai phá dữ liệu, tuy nhiên ứng với mỗi bài toán thường chỉ có 1 hoặc 2 phương pháp là cho kết quả tối ưu. Vì vậy để chọn được phương pháp hợp lý và chính xác thì công việc tìm hiểu dữ liệu, đặc tả chi tiết bài toán chính là cơ sở để chọn phương pháp thích hợp.
Một số phương pháp khai phá dữ liệu tiêu biểu: Nguyễn Minh Ý 9/81 Privacy Preserving Data Mining Ts.Đặng Trần Khánh-Ts.Nguyễn Đức Cường • Thống kê • Cây quyết định & luật quyết định • Luật liên kết • Phân cụm • Mạng Neural…[1,3] Sau khi chọn được phương pháp KPDL thích hợp sẽ là quá trình kiểm thử trên các tập dữ liệu. Quá trình này sẽ được thực hiện lặp đi lặp lại nhiều lần để có thể tìm được kết quả như mong muốn.4 Hậu xử lý và đánh giá mô hình Kết quả KPDL sẽ được kiểm thử trên 1 số mẫu thử để đánh giá được tính hiệu quả của giải thuật. Thông thường kết quả KPDL phải được kết hợp, tinh chỉnh để phù hợp nhu cầu của người sử dụng. Các kết quả ở dạng học máy sẽ được chuyển sang dạng nghiệp vụ để phù hợp với ngưới sử dụng.5 Triển khai tri thức Các kết quả đã được kiểm thử, tinh chỉnh, chuyển đổi để phù hợp với nhu cầu của người sử dụng.
Nếu đáp ứng được các yêu cầu đặt ra của bài toán, các kết quả này sẽ được triển khai (thường ở dạng module) để hỗ trợ quá trình ra quyết định. Thông thường kết quả này được triển khai ở dạng web để hỗ trợ ra quyết định của nhiều người sử dụng. Trên thực tế quá trình KPDL là một quá trình lặp nhằm hoàn thiện và rút ra được những thông tin hữu ích nhất, những mẫu và qui luật chính xác nhất. Tìm hiểu nghiệp vụ và dữ liệu Chuẩn bị dữ liệu Mô hình hóa dữ liệu Hậu xử lý và đánh giá mô hình Triển khai tri thức Hình 1 Qui trình phát triển tri thức Nguyễn Minh Ý 10/81 Privacy Preserving Data Mining Ts.Đặng Trần Khánh-Ts.Nguyễn Đức Cường 2.3 Phương pháp KPDL KPDL được ứng dụng trong rất nhiều các lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú nằm ẩn trong dữ liệu.
Tùy vào lĩnh vực và tính chất của bài toán, việc vận dụng KPDL có những phương pháp khác nhau.1 Phương pháp thống kê (Statiscal Methods) Thống kê là khoa học của thu thập và tổ chức dữ liệu để đưa ra kết quả từ tập dữ liệu. Phân tích dữ liệu thống kê là một trong số những phương pháp tốt nhất để KPDL. Phương pháp đánh giá Giá trị trung bình Mean = 1 / n∑ xi Median = x(n+1)/2 nếu n là lẻ Median = x(n)/2 nếu n là chẳn n Phương sai σ2 = (1/(n)) ∑ ( xi − mean) 2 i =1 Độ lệch chuẩn σ Công thức Bayes:P(H/X)=[P(X/H).P(H)]/P(X) Theo lý thuyết xác suất Bayes thì xác suất của một sự cố có thể được tính từ các xác suất xảy ra của các sự cố trước (đó gọi là tiền xác suất) Ví dụ: Cho tập dữ liệu huấn luyện trong bảng 1, bạn phải phân loại cho một mẫu dữ liệu sau X = {1, 2, 2, class= ?} Ví dụ Attribute 1 Attribute 2 Attribute 3 Class C A1 A2 A3 1 1 2 1 1 2 0 0 1 1 3 2 1 2 2 4 1 2 1 2 Nguyễn Minh Ý 11/81 Privacy Preserving Data Mining Ts.Đặng Trần Khánh-Ts.Nguyễn Đức Cường 5 0 1 2 1 6 2 2 2 2 7 1 0 1 1 Theo lý thuyết Bayes thì chúng ta phải tìm ra Max của P(X/Ci).0616 Vậy chúng ta có thể dự đoán X thuộc vào lớp C2(C=2) Phương pháp phân loại bằng Bayes là phương pháp có tỉ lệ lỗi thấp nhất so với các phương pháp phân loại khác trong KPDL. Tuy nhiên, trong thực tế các thuộc tính không độc lập với nhau vì vậy độ phức tạp của phương pháp này sẽ tăng lên rất nhiều.
Trong trường hợp các giá trị là liên tục và đặc tính bài toán có tính nhân quả thì kỹ thuật thống kê được sử dụng là hồi qui (Regression). Mục tiêu của bài toán này là tìm ra một số hàm biểu diễn sự phụ thuộc của đầu ra với các biến đầu vào ví dụ như:Y= C1+ aX Hàm biểu diễn có thể là hàm tuyến tính Y= C1+ a1x1 + a2x2 + a3x3 + a4x4 +. + anxn Hàm đa thức Y= C1+ a1x + a2x2 + a3x3 + a4xn +. + anxn Hàm mũ Y= C1+ ex 2.2 Phân cụm (Cluster Analysis) Là một tập các phương pháp tự động phân loại tập ví dụ vào một số nhóm với tiêu chí các phần tử giống nhau thì thuộc cùng một tập, 2 phần tử thuộc 2 tập khác nhau sẽ không giống nhau.
Nguyễn Minh Ý 12/81 Privacy Preserving Data Mining Ts.Đặng Trần Khánh-Ts.Nguyễn Đức Cường Phân cụm theo nội dụng (Clustering concepts) Ví dụ: bạn có thể phân loại các hóa đơn mua hàng theo giá trị của đơn hàng, chủng loại mặt hàng … Thông thường con người có thể phân loại theo 1,2,3. Tuy nhiên bài toán đặt ra trong thực tế số chiều là rất lớn và độ phức tạp cao vì vậy con người không thể làm bằng tay.