Đồ án Khai phá và làm sạch dữ liệu

Lời cám ơn Cám ơn các thày cô giáo trường Đại học Dân lập Hải Phòng, đã dạy dỗ chúng em trong nhiều năm qua. Cám ơn thày Trần Hữu Nghị đã cho em một mái trường để cho chúng em có cơ hội học được những kiến thức bổ ích để có thể trở thành một công dân có ích cho xã hội. Xin chân thành cám ơn thày cô bộ môn Tin học đã truyền đạt kiến thức về công nghệ thông tin, một môn học bổ ích, là hành trang vững chắc để em tự tin trong những công việc được giao phó trong thời gian tới. Cám ơn thày Đỗ Trung Tuấn, trường đại học tự nhiên; cám ơn thày Vương Đạo Vy, trường đại học công nghệ, Đại học Quốc gia Hà nội đã giúp đỡ em trong quá trình thực tập, viết luận văn cũng như quá trình học tập trên ghế nhà trường. Đặc biệt là thày Đỗ Trung Tuấn đã tận tình giúp đỡ em trong quá trình thực tập, đã tạo điều kiện cho em được thực tập tại ban công nghệ trường Đại học quốc gia Hà Nội để em có thể đem kiến thức mình đã học được trên ghế nhà trường áp dung vào thực tiễn để em có thể nhận thấy mình đã trang bị được những gì còn thiếu những gì trong hành trang của mình. Cám ơn các anh chị trong ban công nghệ trường Đại học quốc gia Hà Nội đã tận tình chỉ bảo em trong quá trình thực tập tại ban. Cám ơn gia đình và người thân, đã tận tình giúp đỡ, chu cấp tài chính, động viên em trong suốt thời gian học tập tại trường. Xin cám ơn các bạn bè trong lớp và các bạn trong khoa cũng như sinh viên cả trường đã giúp đỡ tôi trong thời gian học tập cũng như trong thời gian làm thực tập tốt nghiệp. MỤC LỤC Mở đầu Nhu cầu về xử lí dữ liệu trong cuộc sống số ngày nay là hiện thực và cấp bách. Công nghệ thông tin cho phép người ta xây dựng xã hội tri thức, biến thông tin thành tiền bạc và quyền lực. Từ vài thập niên gần đây, với sự phát triển mạnh mẽ của công nghệ thông tin và hệ thống truyền thông thế giới đã có những bước tiến triến mới mà ở đó thông tin và tri thức đóng vai trò rất quan trọng trong mọi mặt đời sống. Việc lưu trữ, tổ chức thông tin làm sao cho hiệu quả nhất là một vấn đề được đặt ra. Việc xử lí dữ liệu cần đến kiến thức về cơ sở dữ liệu (CSDL). Nghiên cứu CSDL yêu cầu nghiên cứu về (i) hệ thống thông tin; (ii) hệ quản trị file và hệ quản trị CSDL; (iii) mô hình dữ liệu; (iv) quản trị bên trong hệ quản trị CSDL… Trong CSDL, người ta dùng nhiều loại dữ liệu, với mục đích khác nhau. có dữ liệu về (i) số; (ii) văn bản; (iii) đồ hoạ; (iv) video; (iv) dữ liệu meta… Dữ liệu meta có vai trò quan trọng, cho biết mối quan hệ giữa các dữ liệu và tri thức về CSDL. Việc chỉ ra các dữ liệu meta có thể thực hiện thông qua tri thức người dùng khi mô tả các điều kiện toàn vẹn dữ liệu; qua mô hình dữ liệu về thế giới thực; qua việc khai phá dữ liệu. Luận văn này trình bày về một khía cạnh trong các khía cạnh nghiên cứu trên. Đó chính là khai phá dữ liệu. Luận văn được chia thành các chương : Chương 1. Mở đầu. Chương 2. CSDL và nhu cầu về dữ liệu meta. Chương 3. Khai phá dữ liệu. Chương 4. Luật kết hợp và các tiếp cận. Chương 5. Thử nghiệm việc khai phá dữ liệu. Chương 6. Kết luận CSDL và nhu cầu dữ liệu Meta Mô hình dữ liệu quan hệ Hiện nay mô hình dữ liệu được sử dụng rộng rãi nhất là mô hình dữ liệu quan hệ gọi tắt là mô hình quan hệ được E.F.Codd đề xuất năm 1970 và ngày càng có nhiều hệ quản trị CSDL cho mô hình này gọi là các hệ quản trị CSDL quan hệ. Mô hình được xây dựng dựa trên lý thuyết tập hợp nên dễ hiểu và dễ biểu diễn bằng toán học. Mô hình này bao gồm: Một hệ thống các ký hiệu để mô tả dữ liệu dưới dạng dòng và cột như quan hệ, bộ, thuộc tính, khoá chính, khoá ngoài,… Một tập hợp các phép toán thao tác trên dữ liệu như phép toán tập hợp, phép toán quan hệ. Ràng buộc toàn vẹn quan hệ. Nhu cầu về dữ liệu meta Trong vài thập niên với những tác động mạnh mẽ của các tiến bộ trong công nghệ công nghệ thông tin và truyền thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế xã hội đã phát triển, nhu cầu về dữ liệu ngày càng nhiều. Sự phong phú về dữ liệu, thông tin cùng với khả năng khai thác kịp thời chúng đã mang đến những năng xuất và chất lượng mới cho các công tác quản lý, hoạt động kinh doanh. Yêu cầu về các thông tin trong các lĩnh vực hoạt động đó đòi hỏi cao hơn, người quyết định không những cần dữ liệu mà còn cần có thêm nhiều hiểu biết, nhiều tri thức để hỗ trợ cho việc ra quyết định của mình. Những năm 90 của thế kỷ trước, nhu cầu khám phá tri thức mới là thực sự, với các nghiên cứu về tổ chức các kho dữ liệu và kho thông tin, các hệ trợ giúp ra quyết định, các thuật toán nhận dạng mẫu, phân lớp,...và đặc biệt là khai phá dữ liệu. Khai phá dữ liệu trở thành một trong những hướng nghiên cứu thu hút sự quan tâm của nhiều người nghiên cứu trong lĩnh vực khác nhau như hệ thống CSDL, thống kê, trí tuệ nhân tạo,... Kho dữ liệu có thể giúp khai thác thông tin bằng các công cụ truy vấn, chiết xuất thông tin và báo cáo cũng như được sử dụng để hỗ trợ việc phân tích trực tuyến, kiểm định các giả thuyết. Tuy nhiên chỉ có kho dữ liệu thì chưa thể có được tri thức, nếu dữ liệu được phân tích một cách thông minh thì chúng sẽ là nguồn tài nguyên vô cùng quý giá. Từ những khối lượng khổng lồ dữ liệu có sẵn, tìm ra những thông tin tiềm ẩn có giá trị, chưa được phát hiện, những xu hướng phát triển và những yếu tố tác động lên chúng là một điều hết sức cần thiết. Tiến hành như vậy chính là thực hiện quá trình phát hiện tri thức trong CSDL. Quá trình phát hiện tri thức gồm nhiều giai đoạn, trong đó giai đoạn khai phá dữ liệu là giai đoạn chủ yếu. Giai đoạn khai phá dữ liệu được thực hiện sau các khâu tinhlọc và tiền xử lý dữ liệu, nhằm tìm ra các mẫu, các xu hướng có ý nghĩa từ các tập dữ liệu. Chỉ có các mẫu, các xu hướng được xem là đáng quan tâm, theo một phương diện nào đó, mới được coi là tri thức. Tri thức là có ích khi nó có thể giúp đạt được mục đích của hệ thống hoặc người dùng. Các kỹ thuật khai phá dữ liệu được chia làm ba mảng cơ bản (i) phân lớp / phân cụm dữ liệu; (ii) các luật kết hợp; và (iii) khai phá chuỗi. Khai phá luật kết hợp trong những CSDL lớn lần đầu tiên xuất hiện vào năm 1993 và hiện tại đã và đang được nghiên cứu, phát triển rất mạnh, trở thành một khuynh hướng quan trọng của khai phá dữ liệu. Ở Việt Nam, trong những năm trở lại đây, nhu cầu về tự động khám phá tri thức từ các dữ liệu có sẵn nhằm tăng năng lực cạnh tranh của các ngành kinh tế đang phát triển nhanh.  Khai phá dữ liệu Giới thiệu về khai phá dữ liệu Giới thiệu chung Những năm 60 của thế kỷ trước, người ta bắt đầu sử dụng các công cụ tin học để tổ chức và khai thác các CSDL. Cùng với sự phát triển vượt bậc của các công nghệ điện tử và truyền thông, khả năng thu thập, lưu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng được nâng cao, theo đó, lượng thông tin được lưu trữ trên các thiết bị như đĩa từ, băng từ, đĩa CD-ROM,... không ngừng tăng lên. Theo thống kê sơ bộ, lượng thông tin trên các hệ thống tin học cứ sau 20 tháng lại tăng lên gấp đôi. Cuối thập kỷ 80 của thế kỷ 20, sự phát triển rộng khắp của các CSDL ở mọi quy mô đã tạo ra sự bùng nổ thông tin trên toàn cầu, vào thời gian này, người ta bắt đầu đề cập đến khái niệm khủng hoảng phân tích dữ liệu tác nghiệp để cung cấp thông tin với yêu cầu chất lượng ngày càng cao cho người làm quyết định trong các tổ chức tài chính, thương mại, khoa học. Người ta nói “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”. Lượng dữ liệu khổng lồ này thực sự là một nguồn “tài nguyên” có nhiều giá trị bởi thông tin là yếu tố then chốt trong mọi hoạt động quản lý, kinh doanh, phát triển sản xuất và dịch vụ,... Nó giúp những người điều hành và quản lý có hiểu biết về môi trường và tiến trình hoạt động của các tổ chức trước khi ra quyết định để tác động đến quá trình hoạt động nhằm đạt được mục tiêu một cách hiệu quả và bền vững. Khai phá dữ liệu là một lĩnh vực mới, nhằm tự động khai thác những thông tin, những tri thức có tính tiềm ẩn, hữu ích từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp,... làm thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức. Các kết quả khoa học cùng những ứng dụng thành công trong khám phá tri thức, cho thấy khai phá dữ liệu có thể phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng, đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện nay, khai phá dữ liệu đã ứng dụng ngày càng rộng rãi trong các lĩnh vực, như thương mại, tài chính, điều trị y học, viễn thông tin – sinh,... Về khai phá dữ liệu Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong CSDL, để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn; trong đó khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu hay các mô hình từ dữ liệu. Ở một mức độ trừu tượng nhất định có thể định nghĩa về khai phá dữ liệu : Data Mining là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. Khám phá tri thức (KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm đó được xem như hai lĩnh vực tương đương nhau. Nhưng, nếu phân chia một cách tách bạch thì khai phá dữ liệu là một bước chính trong quá trình KDD. Quá trình phát hiện tri thức trong CSDL Khám phá tri thức trong CSDL (KDD) là lĩnh vực liên quan đến các ngành như: thống kê, học máy, CSDL, thuật toán, trực quan hoá dữ liệu, tính toán song song và hiệu năng cao,… Mục đích của quá trình phát hiện tri thức là rút ra tri thức từ dữ liệu trong CSDL lớn. Quá trình KDD là quá trình gồm nhiều giai đoạn và lặp lại, mà trong đó sự lặp lại có thể xuất hiện ở bất cứ bước nào. Quá trình đó có thể được mô tả theo hình sau: Các bước thực hiện trong quá trình phát hiện tri thức Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước thứ hai là thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. Bước thứ ba là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu. Bước thứ tư là hiển thị tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. Nhiệm vụ chính trong khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất các tri thức từ dữ liệu. Do đó có thể coi mục đích chính của khai phá dữ liệu sẽ là mô tả và dự đoán. Các mẫu mà khai phá dữ liệu phát hiện được nhằm vào các 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 trường trong CSDL để chiết xuất ra các mẫu là các dự đoán những giá trị chưa biết hoặc những giá trị trong tương lai của các biến đá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. Nhiệm vụ chính của khai phá dữ liệu : Phân lớp, phân loại. Phân loại là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã được biết trước đó. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp. Như thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Các kiến thức được phát hiện biểu diễn dưới dạng các luật theo cách sau: “Nếu các thuộc tính dự báo của một mục thoả mãn điều kiện của các tiền đề thì mục đó nằm trong lớp chỉ ra trong kết luận”. Thí dụ một mục biểu diễn thông tin về nhân viên có các thuộc tính dự báo là: họ tên, tuổi, giới tính, trình độ học vấn, … và thuộc tính phân loại là trình độ lãnh đạo của nhân viên. Hồi quy. Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Có rất nhiều ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, ví dụ như dự đoán số lượng biomass xuất hiện trong rừng biết các phép đo vi sóng từ xa, đánh giá khả năng tử vong của bệnh nhân 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 chỉ tiêu quảng cáo, dự đoán theo thời gian với các biến đầu vào là các giá trị của mẫu dự đoán trong quá khứ, v.v… Phân nhóm là việc mô tả chung để tìm ra các tập xác định các nhóm hay các loại để mô tả dữ liệu. Các nhóm có thể tách riêng nhau hoặc phân cấp hoặc gối lên nhau. Có nghĩa là một dữ liệu có thể vừa thuộc nhóm này, vừa thuộc nhóm kia. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm như: phát hiện tập các khách hàng có phản ứng giống nhau trong CSDL tiếp thị, xác định các loại quang phổ từ các phương pháp đo tia hồng ngoại. Tóm tắt liên quan đến các phướng pháp tìm kiếm một mô tả tóm tắt cho một tập con dữ liệu. Ví dụ như việc lập bảng các độ lệch chuẩn và trung bình cho tất cả các trường. Các phương pháp phức tạp hơn liên quan đến nguồn gốc của các luật tóm tắt, khai thác mối liên hệ hàm giữa các biên. Các kỹ thuật tóm tắt thường được áp dụng cho các phân tích dữ liệu tương tác có tính thăm dò và tạo báo cáo tự động. Mô hình hóa phụ thuộc bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến. Các mô hình phụ thuộc tồn tại dưới hai mức: Mức cấu trúc của mô hình xác định (thường ở dạng đồ họa) các biến nào là phụ thuộc cục bộ với nhau Mức định lượng của một mô hình xác định độ mạnh của sự phụ thuộc theo một thước đo nào đó. Ví dụ như các mạng phụ thuộc xác suất sử dụng độc lập có điều kiện để xác định khía cạnh có cấu trúc của một mô hình và các xác suất hoặc tương quan để xác định độ mạnh của sự phụ thuộc. Các mạng phụ thuộc xác suất đang ngày càng tìm thấy nhiều ứng dụng trong các lĩnh vực khác nhau như phát triển các hệ chuyên gia y tế áp dụng tính xác suất từ các CSDL, thu thập thông tin, mô hình hóa gen di truyền của người. Phát hiện sự thay đổi và chuyển hướng. Tiếp cận tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các giá trị chuẩn hoặc được đo trước đó. Các kĩ thuật khai phá dữ liệu Các kĩ thuật tiếp cận Khám phá tri thức trong CSDL là một lĩnh vực liên ngành, bao gồm: Tổ chức dữ liệu, học máy, trí tuệ nhân tạo và các khoa học khác, sự kết hợp này có thể được diễn tả như trong hình dưới Các lĩnh vực liên quan đến khám phá tri thức trong CSDL Trên quan điểm của học máy, các kỹ thuật trong Data Mining gồm: Học có giám sát: Là quá trình gán nhãn lớp cho các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết Học không có giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) dữ liệu tương tự nhau mà chưa biết trước các thông tin về lớp hay tập các ví dụ huấn luyện Học nửa giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trước. Căn cứ vào lớp các bài toán cần giải quyết, khai phá dữ liệu có các kỹ thuật áp dụng sau : Phân lớp và dự đoán: xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp các bệnh nhân dữ liệu trong hồ sơ bệnh án. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định, mạng nơ ron nhân tạo. Phân lớp và dự đoán còn được gọi là học có giám sát. Luật kết hợp: Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Có thể lấy một ví dụ đơn giản về luật kết hợp như sau: phân tích CSDL bán hàng nhận được thông tin về những khách hàng mua máy tính cũng có khuynh hướng mua phần mềm quản lý tài chính trong cùng lần mua được miêu tả trong luật kết hợp sau: “Mua máy tính ® Mua phần mềm quản lý tài chính” [Độ hỗ trợ: 4%, độ tin cậy: 70%]. Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật. Chúng tương ứng phản ánh sự hữu ích và sự chắc chắn của luật đã khám phá. Độ hỗ trợ 4% có nghĩa là: 4% của tất cả các tác vụ đã phân tích chỉ ra rằng máy tính và phần mềm quản lý tài chính là đã được mua cùng nhau. Còn độ tin cậy 70% có nghĩa là 70% các khách hàng mua máy tính cũng mua phân mềm quản lý tài chính. Phân tích chuỗi theo thời gian: Tượng tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. Phân cụm: xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân cụm còn được gọi là học không có giám sát. Mô tả khái niệm: thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. Dạng dữ liệu có thể khai phá Do Data Mining được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều kiểu dữ liệu khác nhau. Sau đây là một số dạng dữ liệu điển hình: CSDL quan hệ, CSDL đa chiều, CSDL dạng giao dịch, CSDL quan hệ-hướng đối tượng, dữ liệu không gian và thời gian, Dữ liệu chuỗi thời gian, CSDL đa phương tiện, dữ liệu Text và Web,..,. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu ứng dụng vào rất nhiều lĩnh vực. Sau đây là một số lĩnh vực khá điển hình: Kinh doanh Ngân hàng Bảo hiểm sức khỏe Y tế Khai phá luật kết hợp và ứng dụng Luật kết hợp là một biểu thức có dạng: , trong đó và là tập các trường gọi là item. Ý nghĩa của các luật kết hợp khá dễ nhận thấy: Cho trước một CSDL có là tập các giao tác - trong đó mỗi giao tác là tập các item - khi đódiễn đạt ý nghĩa rằng bất cứ khi nào giao tác có chứa thì chắc chắn có chứa . Độ tin cậy của luật (rule confidence) có thể được hiểu như xác suất điều kiện. Ý tưởng của việc khai thác các luật kết hợp có nguồn gốc từ việc phân tích dữ liệu mua hàng của khách và nhận ra rằng “Một khách hàng mua mặt hàng X1 và X2 thì sẽ mua mặt hàng Y với xác suất là c%”. Ứng dụng trực tiếp của các luật này trong các bài toán kinh doanh cùng với tính dễ hiểu vốn có của chúng – ngay cả đối với những người không phải là chuyên gia khai thác dữ liệu – làm cho luật kết hợp trở thành một phương pháp khai thác phổ biến. Hơn nữa, luật kết hợp không chỉ bị giới hạn trong phân tích sự phụ thuộc lẫn nhau trong phạm vi các ứng dụng bán lẻ mà chúng còn được áp dụng thành công trong rất nhiều bài toán kinh doanh. Như vậy, khai phá luật kết hợp là một phương pháp xử lý thông tin quan trọng và phổ biến, nó nhằm khám phá mối liên hệ giữa các mẫu dữ liệu. Một thuật toán về khai phá dữ liệu Ý tưởng thuật toán Apriori Apriori là một thuật giải được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993. Thuật toán tìm giao dịch t có độ hỗ trợ và độ tin cậy thoả mãn lớn hơn một giá trị ngưỡng nào đó. Thuật toán được tỉa bớt những tập ứng cử viên có tập con không phổ biến trước khi tính độ hỗ trợ. Thuật toán Apriori tính tất cả các tập ứng cử của tập k trong một lần duyệt CSDL. Apriori dựa vào cấu trúc cây băm. Tìm kiếm đi xuống trên cấu trúc cây mỗi khi ta chạm lá, ta tìm được một tập ứng cử viên có tiền tố chung được bao gồm trong giao dịch. Sau đó các tập ứng cử này được tìm trong giao dịch đã được ánh xạ trước đó. Trong trường hợp tìm thấy biến đếm được tăng lên 1. Thuật toán Apriori Gồm 2 bước: Tạo tập item phổ biến: tạo tất cả các tập item dự kiến, tính toán độ hỗ trợ, loại bỏ các tập dự kiến không đạt minsupp. Kiểm tra tập 1 item có là phổ biến không. Lần duyệt thứ k: Sử dụng các tập Lk-1 của tập k-1 item phổ biến để tạo tập dự kiến Ck (dùng hàm apriori_gen). Duyệt CSDL và tính support cho Ck. Lk: là tập hợp của các tập k_item phổ biến, mỗi phần tử là một tập có 2 trường itemset, support. Ck: tập hợp của tập k_item dự kiến. Tỉa bớt Thấy tập không phổ biến Trực quan về thuật toán Apriori Tạo luật kết hợp: Từ các tập con của tập phổ biến xây dựng luật kết hợp và tính độ tin cậy của luật. Từ tập item phổ biến L, tìm tất cả các tập con không rỗng f Ì L rồi tạo ra luật f ® L – f thoả mãn minconf. VD: Nếu {A,B,C,D} là tập item phổ biến thì có các luật dự kiến: ABC ®D, ABD ®C, ACD ®B, BCD ®A, A ®BCD, B ®ACD, C ®ABD, D ®ABCAB ®CD, AC ® BD, AD ® BC, BC ®AD, BD ®AC, CD ®AB, Nếu L có k item thì có thể tạo ra 2k-2 luật kết hợp dự kiến(bỏ qua luật L ® Æ và Æ ® L) Dựa vào tính chất của độ tin cậy để tạo ra luật có conf >= minconf. Độ tin cậy không có tính chất c(ABC ®D) có thể lớn hơn hay nhỏ hơn c(AB ®D) Nhưng nếu luật được sinh ra từ cùng một tập item phổ biến thì có thuộc tính đó: VD: L = {A,B,C,D} c(ABC ® D) ³ c(AB ® CD) ³ c(A ® BCD) Loại bỏ các luật Luật có confidence thấp Sinh luật 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% 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, C}} 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. Ví dụ thuật toán Apriori Luật kết hợp và các tiếp cận Khai phá luật kết hợp Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong đó sự xuất hiện của tập các thuộc tính S nào đó trong các bản ghi của D sẽ kéo theo sự xuất hiện của một tập những thuộc tính khác U cũng trong những bản ghi đó. Mỗi luật kết hợp được đặc trưng bởi một cặp tỉ lệ. Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ % những bản ghi trong D chứa cả S và U. Vấn đề khám phá luật kết hợp được phát biểu như sau : Cho trước tỉ lệ hỗ trợ q và độ tin cậy b. Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn q và b tương ứng. Giả thiết D là CSDL mua bán và với q = 40%, b = 90%. Vấn đề phát hiện luật kết hợp được thực hiện như sau: Liệt kê, đếm tất cả những qui luật chỉ ra sự xuất hiện một số các mục sẽ kéo theo một số mục khác. Chỉ xét những qui luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn 90%. Hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách hàng được yêu cầu điền vào các mẫu bán hàng để công ty có được một CSDL về các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan hệ "tuổi, giới tính, nghề nghiệp và sản phẩm". Khi đó có thể có rất nhiều câu hỏi tương ứng với luật trên. Ví dụ trong lứa tuổi nào thì những khách hàng nữ là công nhân đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là nhiều nhất, thoả mãn một ngưỡng nào đó ? Lý thuyết về luật kết hợp Cho một tập I = {I1, I2, ..., Im} các tập m mục, một giao dịch T được định nghĩa như một tập con của các khoản mục trong I (TÍI). Tương tự như khái niệm tập hợp, các giao dịch không được trùng lặp, nhưng có thể nới rộng tính chất này của tập hợp và trong các thuật toán sau này, người ta đều giả thiết rằng các khoản mục trong một giao dịch và trong tất cả các tập mục khác, có thể coi chúng đã được sắp xếp theo thứ tự từ điển của các mục. Gọi D là CSDL của n giao dịch và mỗi giao dịch được đánh nhãn với một định danh duy nhất. Nói rằng, một giao dịch T Î D hỗ trợ một tập X Í I nếu nó chứa tất cả các item của X. Điều này nghĩa là X Í T, trong một số trường hợp người ta dùng ký hiệu T(X) để chỉ tập các giao dịch hỗ trợ cho X. Kí hiệu support(X) (hoặc sup(X), s(X)) là tỷ lệ phần trăm của các giao dịch hỗ trợ X trên tổng các giao dịch trong D, nghĩa là: sup(X) = Độ hỗ trợ tối thiểu minsup là một giá trị cho trước bởi người sử dụng. Nếu tập mục X có sup(X) ³ minsup thì ta nói X là một tập các mục phổ biến. Một tập phổ biến được sử dụng như một tập đáng quan tâm trong các thuật toán, ngược lại, những tập không phải tập phổ biến là những tập không đáng quan tâm. Các phần sau sẽ sử dụng những cụm từ khác như “X có độ hỗ trợ tối thiểu”, hay “X không có độ hỗ trợ tối thiểu” cũng để nói lên rằng X thỏa mãn hay không thỏa mãn support(X) ³ minsup. ®Một khoản mục X được gọi là k-itemset nếu lực lượng của X bằng k, tức là . Một luật kết hợp có dạng R: X -> Y, trong đó X, Y là tập các mục, X, Y Í I và X ÇY = Æ. X được gọi là tiên đề và Y được gọi là hệ quả của luật. Luật X => Y tồn tại một độ tin cậy c . Độ tin cậy c được định nghĩa là khả năng giao dịch T hỗ trợ X thì cũng hỗ trợ Y. Ta có công thức tính độ tin cậy c như sau: conf(X =>Y) = p(Y Í I | X Í I ) = Một số hướng tiếp cận trong khai phá luật kết hợp Lĩnh vực khai thác 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. Có những đề xuất nhằm cải tiến tốc độ thuật toán, có những đề xuất nhằm tìm kiếm luật có ý nghĩa hơn… và có một số hướng chính như sau. Luật kết hợp nhị phân là hướng nghiên cứu đầu tiên của luật kết hợp. Luật kết hợp có thuộc tính số và thuộc tính hạng mục. Luật kết hợp tiếp cận theo hướng tập thô. Luật kết nhiều mức. Luật kết hợp mờ. Luật kết hợp với thuộc tính được đánh trọng số. Luật kết hợp song song. Bên cạnh những nghiên cứu về các 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ừ CSDL. Thử nghiệm Phân tích, thiết kế ứng dụng Bài toán văn hoá Bài toán khai thác thông tin từ cơ sở dữ liệu về âm nhạc. Cơ sở dữ liệu này lưu trữ thông tin của các nghệ sĩ, các tác phẩm. Thông tin về nghệ sĩ bao gồm: Mã nghệ sĩ, họ tên, ngày sinh, giới tính, nơi sinh, địa chỉ, điện thoại và dòng nhạc chính của nghệ sĩ đó. Một nghệ sĩ có thể là một nhạc sĩ, một ca sĩ hay là người sáng tác lời cho một bài hát nào đó. Vì vậy một nghệ sĩ có thể sáng tác một hay nhiều bài hát, có thể biểu diễn một hay nhiều bài hát và một bài hát cũng có thể do một hay nhóm nghệ sĩ sáng tác hoặc biểu diễn. Thông tin về bài hát bao gồm: Mã tác phẩm, tên tác phẩm, thể loại và tóm tắt nội dung của bài hát đó. Khi nghệ sĩ sáng tác một bài hát thì thông tin của bài hát đó sẽ được lưu vào trong cơ sở dữ liệu cùng với thông tin về nghệ sĩ và năm sáng tác. Mỗi bài hát khi được một nghệ sĩ thể hiện thì các thông tin mà nghệ sĩ đó biểu diễn sẽ được lưu trong cơ sở dữ liệu, bao gồm thông tin về nơi biểu diễn và thời lượng mà nghệ sĩ đó thể hiện bài hát. Khi cần thông tin nào đó người dùng truy cập vào hệ thống thư viện lưu trữ CSDL truy xuất ra thông tin mình cần. Mô tả dữ liệu Sơ đồ quan hệ giữa các bảng dữ liệu Bảng hồ sơ nghệ sĩ Bảng tác giả tác phẩm Bảng danh sách tác phẩm Bảng tác phẩm ca sĩ Áp dụng thuật toán khai phá dữ liệu. Muốn có được các thông tin trên, nhưng do dung lượng quá lớn, nên dùng các phương pháp thống kê cổ điển thì sẽ không thể kết xuất ra được. Do vậy cần dùng các kỹ thuật khai phá dữ liệu. Để cho đơn giản chương trình, em thực hiện bước tiền xử lí dữ liệu đưa dữ liệu về dạng. Bảng dữ liệu sau khi qua bước tiền xử lí Trong đó: Trong ListItemID theo thứ tự là: mã nghệ sĩ sáng tác, mã nghệ sĩ thể hiện, thể loại ca khúc. Mã nghệ sĩ sáng tác, mã ng hệ sĩ thể hiện đã lưu trữ trong CSDL ban đầu. Thể loại ca khúc gồm: TL1: Nhạc trữ tình TL2: Nhạc truyền thống TL3: Nhạc nhẹ TL4: Nhạc Rock TL5: Nhạc cách mạng, tiền chiến Sau khi thực hiện bước tiền xử lí dữ liệu ta áp dụng thuật toán Apriori thực hiện khai phá dữ liệu Thực hiện khai phá dữ liệu Giới thiệu chương trình Giao diện chính của chương trình Giao diện chính của chương trình Chương trình sau khi khởi động có giao diện như hình 5.5. M ôt số nút chính như sau: đây là bước cần làm đầu tiên sau khi khởi động chương trình. Dữ liệu sẽ được cập nhật.Mỗi khi thay đổi dữ liệu hay thực hiện lại thuật toán thì sẽ thao tác lại bước này. Parameter: Số phần tử trong tập phổ biến mà thuật toán sinh ra Min support: Độ hỗ trợ tối thiểu do người dùng tuỳ theo mục đích sử dụng của mình mà nhập vào. Min Confidence: Độ tin cậy tối thiểu do người dùng tuỳ theo mục đích sử dụng của mình mà nhập vào. để tạo ra 1 list các item đưa ra các tập mục phổ biến với số k đã nhập ban đầu đưa ra các tập luật đóng chương trình Kết quả chương trình Thực hiện chương trình để khai phá tìm luật kết hợp, quá trình khai phá gồm 3 bước: Load CSDL Nhập Min Support, Min Confidence. Thực hiện thuật toán: Nhấn các nút để hiển thị các tâp mục phổ biến, để hiển thị các luật\ Ví dụ: Khi thực hiện trên tệp DBItem.db, với k=2, độ hỗ trợ cực tiểu Min Support=0.2 và minconf =0.5 tìm ra 3 tập mục phổ biến, 6 luật Danh sách tập mục Các tập mục Các tập mục phổ biến tìm được khi áp dụng thuật toán Apriori Các luật kết hợp tìm được Các luật xác định bởi phần tiền đề và phần kết luận cùng độ hỗ trợ và độ tin cậy của nó. Ví dụ, trong các luật trên có luật: “NS06®NS54” với độ hỗ trợ Support=0,2357724 và độ tin cậy Confidence=1,0. Luật này có ý nghĩa là: Nghệ sĩ Trần Lập sáng tác bài hát nào thì ban nhạc Bức tường sẽ thể hiện ca khúc đó với độ hỗ trợ Support=0,2357724 và độ tin cậy là Confidence=1,0. Kết luận Kết quả đạt dược của luận văn Luận văn đã trình bày tổng quan và các nét đặc trưng nhất trong lĩnh vực Data Mining bao gồm các vấn đề cần khám phá tri thức, các hướng tiếp cận và nghiên cứu tiểu biểu, trong đó phát hiện luật kết hợp là một phương pháp khám phá tri thức quan trọng trong Data Mining có nhiều ý nghĩa trong khoa học cũng như trong thực tiễn. Đây là chủ đề trọng tâm cho nội dung của luận văn. Về mặt lý thuyết, khai phá tri thức bao gồm các bước: Hình thành, xác định và định nghĩa bài toán; thu thập và tiền xử lý dữ liệu; khai phá dữ liệu, rút ra các tri thức; sử dụng các tri thức phát hiện được. Về thuật toán khai phá tri thức, luận văn trình bày thuật toán Apriori Về mặt cài đặt thử nghiệm, luận văn giới thiệu kỹ thuật khai phá dữ liệu theo thuật toán Apriori áp dụng vào bài toán văn hoá Trong quá trình thực hiện luận văn, em đã cố gắng tập trung tìm hiểu và tham khảo các tài liệu liên quan. Tuy nhiên, với thời gian và trình độ có hạn nên không tránh khỏi những hạn chế và thiếu sót. Em rất mong được sự nhận xét và góp ý của các thầy cô giáo và bạn bè và những người cùng quan tâm để hoàn thiện hơn các kết quả nghiên cứu của mình. Phát triển luận văn - Nghiên cứu thêm các thuật toán khai phá dữ liệu khác, tìm cách minh hoạ thuật toán tốt hơn nữa và áp dụng vào một số bài toán khai phá dữ liệu phù hợp với giai đoạn hiện nay: dự báo dân số, bệnh dịch, thời tiết, định hướng trong kinh doanh … - Tiếp tục hoàn thiện và mở rộng chương trình trong luận văn này để có thể áp dụng vào thực tế một cách triệt để. Chương trình thực hiện theo đúng các bước trong quá trình khai phá dữ liệu như: 1-chọn lọc dữ liệu (chọn lọc rút trích từ CSDL đưa vào CSDL riêng, chỉ chọn các dữ liệu thực sự quan tâm cần thiết cho sau này), 2 - làm sạch dữ liệu (chống trùng lặp và giới hạn vùng giá trị), 3 - làm giàu dữ liệu, 4 - khai thác tri thức từ dữ liệu (tìm tác vụ phát hiện luật kết hợp, trình chiếu báo cáo), 5 - chọn dữ liệu có ích áp dụng vào trong hoạt động thực tế. - Cho đến nay hầu hết các thuật toán xác định các tập phổ biến đều được xây dựng dựa trên thừa nhận độ hỗ trợ cực tiểu (Min Support) là thống nhất, tức là các tập mục được chấp nhận đều có độ hỗ trợ lớn hơn cùng một độ hỗ trợ tối thiểu. Điều này không thực tế vì có nhiều ngoại lệ khác được chấp nhận thường có độ hỗ trợ thấp hơn nhiều so với khuynh hướng chung (các tiêu chí phân loại, ưu tiên là khác nhau). Ví dụ: Trong các mặt hàng bán ở siêu thị thì yêu cầu về các mặt hàng khác nhau cũng khác nhau, chẳng hạn: luật chứa các mặt hàng như gạo, trứng, sữa, thịt, rau, bánh kẹo, giấy ăn, bột giặt, ... thường có độ hỗ trợ cao hơn rất nhiều so với các luật chứa mặt hàng như: tủ lạnh, máy giặt, lò vi sóng, ti vi, máy tập thể thao, ... Như vậy, độ hỗ trợ cần đòi hỏi khác nhau theo các mức khái niệm (thông tin của các mặt hàng) khác nhau của tập mục dữ liệu như theo giá trị bán của các mặt hàng trong siêu thị. Vì vậy, hướng nghiên cứu tiếp theo của em là phát hiện luật kết hợp với độ hỗ trợ không giống nhau (điều này cũng đang được nhiền người quan tâm). Có thể ta căn cứ vào đơn giá của mặt hàng để tính toán trên giá trị tiền mua. Xác định trên tập dữ liệu mờ (giá trị của hàng hoá là khác nhau). Từ đó có thể đưa ra các độ hỗ trợ và độ tin cậy tối tiểu (Min Support và Min Confidence) linh hoạt cho từng chủng loại mặt hàng.