Luận văn Nghiên cứu cải tiến thuật toán phân lớp sử dụng cây quyết định đệ quy

7 CHƯƠNG 1. TỔNG QUAN 1.1 GIỚI THIỆU Với sự phát triển của tin học ngày nay, càng ngày các thiết bị phần cứng càng mạnh hơn, khả năng lưu trữ nhiều dữ liệu và dễ dàng hơn. Hãy tưởng tượng chi phí cho mỗi Gigabyte dữ liệu so sánh hiện tại và cách đây vài năm, chúng ta có thể nhận thấy rằng công nghiệp phần cứng đã tiến bộ một cách vượt bậc. Song song với sự phát triển của phần cứng, các chương trình phần mềm cũng ngày càng xuất hiện nhiều, đặc biệt là các chương trình quản trị CSDL như Oracle, SQL Server … có thể lưu trữ và quản trị một lượng dữ liệu khổng lồ. Nhìn sơ lược qua thì mọi thứ dường như hoàn hảo, tuy nhiên hiện tại chúng ta lại đang trong tình trạng “thừa dữ liệu nhưng thiếu thông tin và các tri thức có giá trị”. Nhưng vấn đề là cuộc sống luôn phát triển, con người ngày càng đòi hỏi nhiều điều hơn; đối với vấn đề thông tin và tri thức cũng không nằm ngoài quy luật phát triển này. Chính vì thế mà nhu cầu đặt ra cho ngành tin học là phải tìm hiểu, khám phá được các tri thức, các thông tin quan trọng ẩn chứa trong khối dữ liệu khổng lồ được lưu trữ chứ không chỉ dừng ở mức độ lưu trữ hay thống kê dữ liệu một cách đơn thuần. Con người lúc nào cũng luôn mong muốn khám phá những tri thức tiềm ẩn bên trong các thông tin (dữ liệu) để qua đó tự hoàn thiện và phát triển khả năng tư duy của mình. Vấn đề đặt ra của ngành Công Nghệ Thông Tin là làm sao khai phá được dữ liệu với sự trợ giúp của máy tính, đây chính là nguyên nhân để khai mỏ dữ liệu (data mining) ra đời và cũng chính là lúc đánh dấu một kỷ nguyên mới của việc áp dụng tin học vào cuộc sống thực tế. Khai mỏ dữ liệu là một trong những bài toán lớn khá thú vị và cũng là một trong các vấn đề được quan tâm hàng đầu hiện nay. Việc mong muốn khám phá các tri thức tiềm ẩn bên trong các kho dữ liệu một cách nhanh chóng và chính xác đã thúc đẩy sự phát triển mạnh mẽ của các phương pháp cùng với các thuật toán khác nhau. Các phương pháp cũng như các thuật toán khai PDF created with pdfFactory Pro trial version www.pdffactory.com 8 mỏ dữ liệu khác nhau đã và đang tiếp tục được nghiên cứu phát triển để phục vụ cho nhu cầu này. Hình 1.1 Chúng ta có rất nhiều dữ liệu nhưng lại nghèo tri thức. Việc ứng dụng của khai mỏ dữ liệu vào thực tiễn thì không cần bàn cãi, các tri thức qua quá trình khai mỏ dữ liệu rất là quan trọng, thậm chí các thông tin này mang yếu tố sống còn đối với các doanh nghiệp, các tập đoàn trong quá trình hoạt động kinh doanh. Họ luôn muốn biết các tri thức tiềm ẩn bên trong quá trình hoạt động của mình thông qua các dữ liệu được lưu trữ trong quá khứ một cách nhanh chóng để có thể đưa ra các quyết định, các chính sách thích hợp nhất. Trên thị trường hiện nay có rất nhiều sản phẩm ứng dụng công nghệ khai mỏ dữ liệu điển Làm thế nào để phân tích dữ liệu, khám phá tri thức? PDF created with pdfFactory Pro trial version www.pdffactory.com 9 hình như chương trình SPSS mà tất cả các sinh viên học về kinh tế hay thống kê đều biết đến hoặc các hệ quản trị Cơ Sở Dữ Liệu như SQL Server hay Oracle đều có tích hợp chức năng khai mỏ dữ liệu. Tuy nhiên, dữ liệu thực tế thì vô cùng hỗn độn và phức tạp, các chương trình này chưa có các bước “tiền xử lý”, giúp các thuật toán hiệu quả hơn. Ngoài ra, tính chính xác của thuật toán cũng là một vấn đề quan trọng vì nếu khám phá tri thức sai thì không những không có ý nghĩa gì mà nếu tri thức khám phá được dùng để ra các quyết định thì hậu quả rất lớn. Vấn đề tốc độ khi tập dữ liệu khá lớn cũng là một khó khăn của các ứng dụng dạng này. Nội dung luận văn hướng đến việc làm sao cải tiến được tốc độ của các thuật toán phân lớp dưới hình thức cây quyết định (Decision Tree Induction). Phạm vi luận văn sẽ tập trung theo hướng trên, đưa ra một thuật toán mới giúp tăng tính khả thi, giảm chi phí thời gian cho bài toán phân lớp và đồng thời sẽ hạn chế việc truy xuất đọc/ghi trên đĩa cứng mà vẫn đảm bảo tính chính xác như các thuật toán trước đây. Ngoài ra thuật toán này cũng đảm bảo tính mở rộng trong trường hợp dữ liệu rất lớn. 1.2 TỔNG QUAN VỀ KHAI MỎ DỮ LIỆU VÀ PHÂN LỚP Phần này sẽ giới thiệu các khái niệm cơ bản cũng như tổng quan tất cả các giai đoạn trong toàn bộ quá trình khai mỏ dữ liệu, các hướng nghiên cứu trong bài toán khai mỏ dữ liệu (thực chất lĩnh vực khai mỏ dữ liệu bao gồm rất nhiều hướng nghiên cứu khác nhau). 1.2.1 Giới thiệu về khai mỏ dữ liệu Trong những thập niên gần đây, lượng dữ liệu của các tổ chức gia tăng rất nhiều. Để đáp ứng nhu cầu lưu trữ và quản trị lượng dữ liệu khổng lồ này, phần cứng máy tính cũng phát triển rất nhanh song song với việc các phần mềm chuyên về xử lý dữ liệu, các hệ quản trị Cơ sở dữ liệu ngày càng được cải tiến. Xa hơn nữa, nhu cầu của các công ty, các tập đoàn và những người sử dụng cao cấp muốn thông qua “đống dữ liệu khổng lồ trong quá khứ” này để tìm kiếm các thông tin “thật sự hữu ích còn ẩn chứa bên trong”, muốn tìm kiếm “các quy luật”, PDF created with pdfFactory Pro trial version www.pdffactory.com 10 các “hành vi” của các đối tượng nào đó hoặc thậm chí có thể dự đoán tương lai. Trong ngành công nghệ tin học có một nhánh con là công nghệ tri thức, ngành này luôn quan tâm tìm tòi và giải quyết các câu hỏi trên và vấn đề trên được gọi là khám phá tri thức từ dữ liệu (Knowledge Discovery from Data – KDD). Hình 1.2 – Quá trình “khai mỏ” để khám phá tri thức từ dữ liệu Một quá trình khám phá tri thức từ dữ liệu thông thường luôn bao gồm năm bước như sau: v Xác định vấn đề và lựa chọn nguồn dữ liệu: Đây là quá trình đầu tiên của toàn bộ quá trình. Ở giai đoạn này các chuyên gia trong lĩnh vực (domain experts) cần phải ngồi lại thảo luận với các chuyên gia tin học, chúng ta phải xác định được chúng ta mong muốn khám phá những gì hoặc chí ít thì cũng phải xác định được các thuật ngữ chuyên môn, chuyên ngành, thống nhất giải pháp cho quá trình khám phá dữ liệu (muốn có các luật hay muốn phân lớp, gom nhóm dữ liệu…). Đây là một giai đoạn hết sức quan trọng vì nếu xác định sai vấn đề thì Dữ liệu Tri thức PDF created with pdfFactory Pro trial version www.pdffactory.com 11 toàn bộ quá trình phá sản, nó trở nên vô ích; điều này cũng giống như ngành công nghệ phần mềm thất bại ở giai đoạn xác định yêu cầu người dùng. Do vậy giai đoạn này có lẽ là giai đoạn tốn nhiều thời gian nhất. v Chuẩn bị dữ liệu: Dựa trên các thông tin ở bước xác định, phải tổ chức dữ liệu, lấy dữ liệu như thế nào thì để được xem là cần thiết và đủ. Đây cũng là một giai đoạn rất quan trọng vì nếu dữ liệu đầu vào không chính xác thì hiển nhiên sẽ không thể nào có một kết quả chính xác được. Giai đoạn này sẽ bao gồm các bước nhỏ sau : § Chọn lựa dữ liệu (Data selection): chọn lựa các nguồn dữ liệu cần lấy để khám phá tri thức, giai đoạn này rất cần sự hỗ trợ của các chuyên gia trong lĩnh vực, các nhà quản trị Cơ sở dữ liệu và các chuyên gia công nghệ tin học. Các dữ liệu sẽ được lựa chọn theo tiêu chí đã thống nhất ở bước trên và nên có sự kiểm tra, giám sát và góp ý của các chuyên gia trong lĩnh vực hoặc có sự góp ý của người dùng thì càng tốt. § Tích hợp dữ liệu (Data integration): Thông thường có thể dữ liệu bao gồm nhiều nguồn khác nhau như: từ tập tin bảng tính Excel, từ Cơ sở dữ liệu Microsoft SQL Server, Oracle hoặc thậm chí từ các tập tin văn bản. Các dữ liệu này phải được tích hợp và tổ chức lại thành các bảng dữ liệu bao gồm các cột (các thuộc tính dữ liệu) và các dòng (các giá trị dữ liệu). Các dữ liệu này nên được tích hợp vào một nguồn dữ liệu duy nhất như tập tin bảng tính Excel hay tốt nhất là một hệ quản trị Cơ sở dữ liệu duy nhất để tiện quản lý và truy xuất. Lưu ý việc lưu trữ dữ liệu như thế nào cho tốt, tối ưu cùng với việc thao tác dễ dàng cũng là một trong những cách làm giảm chi phí thực thi của các thuật toán. § Làm sạch và rút gọn dữ liệu (Data cleaning and reduction): đây cũng là một giai đoạn tinh chỉnh dữ liệu. Các dữ liệu nhiễu, dữ liệu không chính xác hoặc dữ liệu thiếu (missing data – thường trong cơ sở dữ liệu gọi là dữ liệu rỗng hay null) phải được loại bỏ hoặc thay thế; thậm chí các thuộc tính phụ dư thừa (ví dụ như thuộc tính ghi chú…) có thể cũng sẽ được loại bỏ tại giai PDF created with pdfFactory Pro trial version www.pdffactory.com 12 đoạn này. Giai đoạn này cũng cần có sự tham gia chặt chẽ của các chuyên gia trong lĩnh vực và thậm chí cả người dùng. § Rời rạc hóa gom nhóm và biến đổi dữ liệu (Data discretization, reduce data by grouping and transformation): Các thuộc tính liên tục có thể được thay thế bằng các giá trị tiệm cận (gần đúng) và có thể được rời rạc hóa thành các thuộc tính có kiểu dữ liệu rời rạc (phần dưới sẽ giải thích rõ về thuộc tính liên tục và thuộc tính rời rạc). Các giá trị thuộc tính có thể được gom nhóm để làm giảm tính phức tạp (ví dụ thuộc tính địa chỉ có thể loại bỏ số nhà, loại bỏ tên đường và chỉ nhóm theo phường, quận….). Ngoài ra, cũng có thể tổng quát hóa dữ liệu (ví dụ như thuộc tính nghề nghiệp có thể tổng quát hóa vào các ngành như kỹ thuật, lao động phổ thông thuần tuý, nhân viên văn phòng, nhân viên quản trị…). v Thực hiện khai mỏ dữ liệu (data mining process): đây là bước trung tâm của toàn bộ quá trình khám phá tri thức. Quá trình này dựa trên các phương pháp và thuật toán đã chọn sẽ tiến hành khám phá tri thức từ các tập dữ liệu (hay còn gọi là tập huấn luyện – training data). Kết quả của quá trình này sẽ tìm ra các tri thức, mô hình hay các quy luật tiềm ẩn bên trong dữ liệu. Tuy nhiên chưa hẳn các kết quả này có thật sự đáng giá để sử dụng, có thật sự là các tri thức mà người dùng mong muốn tìm thấy hay không. v Đánh giá lại chất lượng của tri thức vừa khám phá (Evaluation of the discovered knowledge): Bước này được đưa ra để xem xét tri thức được tìm thấy có phải là tri thức mới, tri thức này có cần thiết hay có giá trị hay không. Lưu ý là việc đánh giá này được thực hiện thông qua các chuyên gia trong lĩnh vực và người dùng là chính chứ không phải là các chuyên gia tin học. Tuy nhiên, với một số bài toán vẫn có thể đánh giá được tính chính xác theo một cách nào đó, ví dụ như bài toán phân lớp ta có thể đánh giá được mô hình phân lớp được tạo ra có tốt không bằng cách đánh giá tỷ lệ dữ liệu thỏa mãn mô hình này dựa trên thông tin từ tập huấn luyện và dĩ nhiên tỷ lệ này càng cao thì càng tốt. PDF created with pdfFactory Pro trial version www.pdffactory.com 13 v Sử dụng các tri thức được khám phá (Using the discovered knowledge): Nếu các bước trên đều đúng, đây là bước cuối cùng. Kết quả của tri thức sẽ được mô tả sao cho dễ hiểu và dễ cập nhật khi dữ liệu thay đổi. Mô hình bên dưới giúp chúng ta có cái nhìn trực quan hơn về toàn bộ quá trình khám phá tri thức: Hình 1.3 – Các quá trình khám phá tri thức từ dữ liệu Tóm lại, khai mỏ dữ liệu là một bài toán khá phổ biến, mục tiêu chính là khám phá các tri thức, các mẫu hoặc các qui luật tiềm ẩn bên trong một tập dữ liệu. Đây là một quá trình chính trong toàn bộ quá trình khám phá tri thức từ dữ liệu, quá trình này bao gồm nhiều pha (phase) mà trong đó pha tiến hành khai mỏ dữ liệu chính là pha trung tâm để khám phá tri thức. Kho tri thức cơ sở (Knowledge base) Giao diện người dùng (User interface) Đánh giá tri thức (Discovered knowledge evaluation) Động cơ khai mỏ dữ liệu (Data mining Engine) Cơ sở dữ liệu hay kho chứa dữ liệu (Database or Data warehouse server) Kho chứa dữ liệu (Data warehouse) Cơ sở dữ liệu (Database server) World Wide Web, Email … Những nguồn dữ liệu khác Chọn lựa, tích hợp, làm sạch, biến đổi, rút gọn dữ liệu PDF created with pdfFactory Pro trial version www.pdffactory.com 14 1.2.2 Các hướng nghiên cứu trong khai mỏ dữ liệu Khai mỏ dữ liệu là một chuyên ngành rất rộng, có rất nhiều hướng nghiên cứu (bài toán) khác nhau bao gồm [5]: v Khám phá các khái niệm, các mô tả phân lớp (discover concept or data classes): dữ liệu có thể đi kèm với các khái niệm, các phân lớp. Các khái niệm hay các lớp này được dùng để mô tả tính tổng quát, tính rút gọn hoặc mô tả các mẫu. Thông qua các khái niệm hay các mô tả này có thể phát hiện các tính chất của dữ liệu (data characterization) như có thể tóm tắt dữ liệu dưới một hình thức tổng quát hơn, phân biệt các dữ liệu bằng cách so sánh với các khái niệm… Xem ví dụ như sau: § Trong một trường học với một tập dữ liệu huấn luyện, qua đó có thể phân tích rằng tất cả đối tượng con người trong trường chỉ bao gồm trong ba khái niệm: học viên, giáo viên và các nhân viên không tham gia công tác giảng dạy (hiển nhiên đôi lúc một người vừa là học viên, vừa là giáo viên). § Các hệ quản trị cơ sở dữ liệu đều hỗ trợ các chức năng phân tích cao cấp giúp nhận biết các khái niệm này thông qua các công cụ khai mỏ và phân tích và có thể tạo ra các mô hình như khối (cube), các đường mô tả (curves) như Microsoft SQL Server phiên bản 2000 trở lên có công cụ OLAP (online analytical processing). § Một hệ thống khai mỏ dữ liệu có thể so sánh cho biết sự khác biệt giữa những nhóm khách hàng trong một cửa hàng bán thiết bị tin học, ví dụ như so sánh giữa hai nhóm khách hàng thường xuyên (theo nghĩa là mua ít nhất hai lần mỗi tháng) và khách hàng vãng lai (mua khoảng vài ba lần mỗi năm). So sánh nhóm khách hàng mua trên giá trị một trăm triệu mỗi năm và dưới một trăm triệu mỗi năm. Ngoài ra, hệ thống còn có thể tìm những đặc tính chung của hai phép so sánh trên hai nhóm khách hàng trên. v Khám phá các luật kết hợp, các mối tương quan, các mẫu thường gặp (Discover association rules, correlations or frequent patterns): Các mẫu thường gặp, như là PDF created with pdfFactory Pro trial version www.pdffactory.com 15 tên gọi chính là các mẫu dữ liệu thường xuất hiện nhất. Việc khám phá các mẫu này sẽ dẫn đến việc tìm ra các luật kết hợp hay các mối tương quan giữa dữ liệu. § Ví dụ như trong một cửa hàng bán máy vi tính thông qua việc tìm các mẫu thường xuất hiện thì người ta nhận thấy rằng đối với dữ liệu về các khách hàng mua máy tính lần đầu tiên thường sẽ có kèm theo thông tin về máy chụp hình kỹ thuật số, máy in và thẻ nhớ. § Dựa vào mẫu thường xuất hiện trên, người ta rút ra được luật kết hợp sau: khi một khách hàng lần đầu mua máy tính thì họ sẽ mua kèm theo máy chụp hình, thẻ nhớ và máy in. § Cũng với cửa hàng trên, người ta nhận thấy rằng có tính tương quan như sau: trong một năm nếu khách hàng này không có trục trặc cần bảo hành hoặc nếu có thì số lần bảo hành của một thiết bị chỉ là một lần và số thiết bị cần bảo hành tối đa là hai thiết bị trong một năm. Với các khách hàng trên thì việc họ mua thêm các thiết bị trong năm hiện tại hoặc năm kế tiếp là rất nhiều, nghĩa là các khách hàng này sẽ trung thành với việc mua hàng tại cửa hàng hơn. v Phân lớp hay dự đoán (Classification or prediction): Phân lớp là quá trình xây dựng một mô hình để mô tả các dữ liệu được phân chia như thế nào. Nói cách khác phân lớp là quá trình xây dựng một mô hình bằng cách gán các đối tượng dữ liệu (như thuộc tính) vào các lớp đã được xác định. Trường hợp thuộc tính phân lớp là giá trị liên tục thì bài toán được gọi là phỏng đoán. Chi tiết về bài toán phân lớp sẽ được thảo luận chi tiết ở các phần sau. § Ví dụ trong một công ty bảo hiểm ta có thể phân lớp các khách hàng nhằm xây dựng một mô hình đánh giá mức độ rủi ro khi bán bảo hiểm cho các khách hàng. Ví dụ như các khách hàng khoảng từ 17 đến 25 tuổi có sở hữu xe phân khối cao thì sẽ dễ xảy ra bồi thường, ngược lại các khách hàng có độ tuổi từ 35 trở lên chạy xe dưới 50cc lại ít xảy ra bồi thường § Dựa trên dữ liệu của ngân hàng xây dựng một mô hình để phỏng đoán rằng với các khách hàng có tài sản, độ tuổi cao thường cần vay chỉ khoảng 100 PDF created with pdfFactory Pro trial version www.pdffactory.com 16 triệu đồng để đầu tư bất động sản hay chứng khoán; ngược lại, các khách hàng độ tuổi 20 đến 27 có tài sản lớn thường vay đến khoảng hơn 500 triệu đồng cho các khoảng đầu tư trên (ứng dụng phỏng đoán). Cũng với dữ liệu này, có thể phân tích ra được nhóm khách hàng nào có nguy cơ tiềm ẩn việc không thể trả nợ tín dụng, có thể xác định được loại hình cho vay vốn nào chịu rủi ro cao nhất (thông qua số trường hợp không thu hồi nợ được tức nợ xấu hoặc số vốn bị chiếm dụng nhiều nhưng chậm chi trả). Khác với ví dụ trên đây lại là một ứng dụng phân lớp. v Bài toán gom cụm (clustering): Không như phân lớp hay phỏng đoán, gom cụm cũng phân tích dữ liệu nhưng các thông tin về nhóm thì chưa được biết. Clustering có thể được sử dụng để tạo ra các nhãn phân lớp (class label). Một cách tổng quát các đối tượng hoặc dữ liệu được xâu (cluster) hay nhóm (group) lại với nhau dựa theo tiêu chí: các đối tượng có sự giống nhau nhất (gần nhau nhất) sẽ được nhóm thành một nhóm và khoảng cách (sự khác biệt) giữa các nhóm với nhau càng lớn (càng xa) càng tốt. § Ví dụ dựa trên thông tin về marketing của công ty bán các thiết bị tin học, tìm ra các nhóm khách hàng có cùng tiêu chí mua sắm, có thể cùng mức độ trung thành để đánh giá và có chính sách khuyến mãi thích hợp cho nhóm các khách hàng loại này. v Phân tích các hành vi (Behaviour or evolution analysis): Cũng tương tự như các phương pháp trên nhưng có kèm theo yếu tố thời gian. Luật kết hợp theo chu kỳ, theo thời gian, mô hình cây quyết định theo các quý trong năm… Với yếu tố thời gian đi kèm thì thường tri thức sẽ phức tạp hơn vì thời gian cũng là một trong những tham số làm thay đổi kết quả đạt được. § Ví dụ dễ thấy nhất là các công cụ phân tích hành vi mua/bán hay cung/cầu trên thị trường chứng khoán để tìm ra các quy luật hay thời điểm mua bán thích hợp trong năm. v Vai trò của ngành khai mỏ dữ liệu : PDF created with pdfFactory Pro trial version www.pdffactory.com 17 § Khám phá được nhiều dạng tri thức khác nhau như luật kết hợp, phân lớp, gom nhóm dữ liệu… § Kết hợp với việc tương tác với người dùng trong quá trình khám phá tri thức để hiểu sâu hơn về các mức độ trừu tượng cao hơn của dữ liệu. Ví dụ kiểm chứng một quy luật, xác định các dữ liệu ngoại lệ (nhiễu)… § Kết hợp với các tri thức có sẵn để tăng tính chính xác và đạt được các kết quả rất cao: kết hợp với các kiến thức, các quy luật cơ bản trong lĩnh vực đang khảo sát hay kết hợp với các ràng buộc của cơ sở dữ liệu có thể làm tăng tốc và đưa ra các kết quả bất ngờ. § Phát triển các công cụ truy vấn cao cấp chứ không đơn thuần chỉ là các câu truy vấn SQL thông thường, người dùng có thể tìm kiếm các thông tin như: cho tôi biết mối liên hệ giữa phụ nữ và những loại sữa tắm trong cơ sở dữ liệu của siêu thị. § Và còn rất nhiều ứng dụng khác của khai mỏ dữ liệu như tích hợp vào các hệ chuyên gia, các hệ hỗ trợ ra quyết định … 1.2.3 Tổng quan về bài toán phân lớp Phân lớp là một trong những bài toán phổ biến trong khai mỏ dữ liệu, như tên gọi của bài toán có nghĩa là phân chia các dữ liệu vào các lớp thích hợp. Kết quả của quá trình phân lớp là những mô hình sẽ được xây dựng dựa trên thông tin phân lớp đã có sẵn, nghĩa là ta sẽ tìm kiếm một mô hình liên hệ giữa các thuộc tính còn lại và thuộc tính phân lớp. Phân lớp là một dạng học có giám sát (Supervised Learning) bởi chính người dùng sẽ phải xác định trước các giá trị nhãn của lớp (class label): (C = {c1,c2, ….cn} ) Î kiểu số nguyên Cho tập dữ liệu T bao gồm các cột là các thuộc tính và các dòng là các bộ dữ liệu tương ứng như sau: PDF created with pdfFactory Pro trial version www.pdffactory.com 18 T = {A1 A2 A3 ……An C} a11 a21 a31 ……an1 c1 a1j a2j a3j ……anj c2 a1j a2j a3j ……anj c3 a1j a2j a3j ……anj c4 ………………………… a1j a2j a3j ……anj cn Trong đó aij Î MiềnGiáTrị(Ai) và ci là giá trị thuộc tính phân lớp tại bộ dữ liệu thứ i tương ứng, hiển nhiên ci Î MiềnGiáTrị(C). Phân lớp là xây dựng một mô hình hay nói cách khác là một hàm ánh xạ f từ mỗi thuộc tính của tập dữ liệu tới các nhãn lớp đã xác định sẵn như sau: y = f(X) với yÎ C và X Î T Xét một tập dữ liệu bao gồm nhiều dòng dữ liệu, mỗi dòng chứa nhiều cột gọi là các thuộc tính. Một thuộc tính có thể là thuộc tính kiểu phân loại (hay kiểu rời rạc - categorical or unordered attributes) như kiểu chuỗi, kiểu ngày tháng, luận lý hoặc thậm chí kiểu số nguyên. Thuộc tính kiểu số thực còn được gọi là thuộc tính liên tục hay có thứ tự (continuous or ordered attributes). Phân lớp như tên gọi nghĩa là phân chia các dữ liệu, các đối tượng vào những lớp cụ thể, muốn vậy phải xác định trước các lớp này. Việc xác định các lớp để phân chia dữ liệu vào thường do các chuyên gia trong lĩnh vực đề nghị. Thuộc tính được chọn sẽ được gọi là thuộc tính phân lớp hay nhãn lớp (gọi tắt là nhãn – class label), thường thuộc tính này là thuộc tính rời rạc và miền giá trị của chúng tương đối nhỏ. Mục tiêu chính của phân lớp là xây dựng mô hình nhằm phân chia các thuộc tính khác vào các thuộc tính phân lớp để thấy được mối liên hệ của chúng [5]. Xét ví dụ một công ty bảo hiểm có các thông tin sau đây: PDF created with pdfFactory Pro trial version www.pdffactory.com 19 Bảng 1.1: Tập huấn luyện về cơ sở dữ liệu bảo hiểm nhân thọ. Mã KH Tuổi Nghề nghiệp Thu nhập Tình trạng gia đình Tình trạng sức khoẻ Rủi ro Nguyễn Văn A 19 Sinh Viên 0 Độc thân Tốt Không Nguyễn Văn B 25 Công nhân xây dựng 1000000 Độc thân Tốt Có Nguyễn Thị C 45 Lao động phổ thông 500000 Có gia đình Bệnh tim Có Dựa vào tập dữ liệu trên, công ty bảo hiểm muốn xác định xem các tính chất nào được xem là quan trọng của một khách hàng sẽ quyết định đến độ rủi ro khi bán bảo hiểm để từ đó có chính sách kinh doanh thích hợp hơn. Như vậy, thuộc tính “Rủi ro” sẽ là thuộc tính phân lớp, các thuộc tính khác sẽ được phân vào nhóm có hay không có rủi ro khi bán bảo hiểm. Một cách tổng quát: Cho một tập huấn luyện X={X1, X2, X3…. Xn}, trong đó X1, X2… Xn là miền giá của thuộc tính tương ứng. Mỗi dòng dữ liệu sẽ là một bộ x = (x1,x2,x3 ….xn) với xi Î Xi . Mỗi một dòng dữ liệu này sẽ chỉ có một giá trị thuộc tính phân lớp duy nhất là ci . Như vậy, bước kế tiếp ta sẽ xây dựng một hàm ánh xạ y = f(X), hàm này sẽ làm nhiệm vụ với một bộ dữ liệu x, nó sẽ ánh xạ bộ dữ liệu này vào đúng giá trị phân lớp. Hàm f được gọi là hàm phân lớp, hàm này có thể xuất hiện dưới các dạng như sau: luật kết hợp, cây quyết định hoặc các công thức toán học…. 1.2.4 Các phương pháp phân lớp § Phân lớp dựa trên phương pháp thống kê Bayes: Phương pháp này dựa trên lý thuyết thống kê, tính toán xác suất của các lớp thành viên và đưa ra xác suất để một bộ dữ liệu thuộc về một lớp xác định. Phương pháp này dựa trên cơ sở lý PDF created with pdfFactory Pro trial version www.pdffactory.com 20 thuyết Bayes do một nhà lý thuyết vào thế kỷ 18 và còn được gọi là phương pháp phân lớp ngây thơ theo Bayes (naive Bayesian classifier) hay có thể gọi là phân lớp Bayes đơn giản. Phân lớp Bayes dựa trên một giả định là các lớp độc lập với nhau nhưng trong thực tế thì không phải lúc nào cũng thỏa mãn. Để biểu diễn sự phụ thuộc này, người ta đưa ra một mô hình liên hệ giữa các yếu tố xác suất, mô hình này tạo thành một sơ đồ như là một sơ đồ mạng và được gọi là mạng niềm tin Bayes (Bayesian belief network). Mạng này sẽ được “huấn luyện” để học và tuỳ theo phương pháp cũng như dữ liệu học sẽ quyết định độ chính xác của mạng [5], [19]. § Phân lớp dựa trên cây quyết định (Classifiers using Decision Tree Induction): Cây quyết định là một mô hình có cấu trúc cây, trong đó các nút lá tương ứng với các giá trị của thuộc tính phân lớp hay còn gọi là nhãn lớp; mỗi nút con tức các nút bên trong mà không phải nút lá sẽ tương ứng với các thuộc tính khác thuộc tính phân lớp trong tập dữ liệu. Nút đầu tiên gọi là nút gốc của cây. Trong những thập niên 70-80, Ross Quinlan, một nhà nghiên cứu về lĩnh vực máy học đã phát triển một thuật toán gọi là ID3 để xây dựng cây quyết định [8]. Bên dưới là ví dụ về một mô hình cây quyết định: Hình 1.4 – Một ví dụ về cây quyết định. Nghề nghiệp Tin học Học sinh Công nhân Không có máy vi tính Có máy vi tính Tuổi Có máy vi tính 10 Không có máy vi tính PDF created with pdfFactory Pro trial version www.pdffactory.com 21 Các nút con (các nút con hình chữ nhật, các nút lá (nhãn) là các giá trị của thuộc tính phân lớp là các nút hình bầu dục, các hình chữ nhật đứt nét tượng trưng cho các giá trị được chọn để phân lớp của thuộc tính. Mục đích ví dụ trên muốn phân lớp cho các đối tượng theo hai nhãn: có/không sở hữu máy vi tính, dựa trên các tiêu chí (thuộc tính) là nghề nghiệp và độ tuổi. § Phân lớp dựa trên luật kết hợp: luật kết hợp là các luật ở dạng: Nếu … thì … (If …. Then…). Lưu ý là luật kết hợp cũng là một trong những phương pháp biểu diễn tri thức dễ hiểu và dễ sử dụng nhất. Để xây dựng nên các luật này, có thể dùng các phương pháp như khám phá luật kết hợp, sau đó chọn lọc lại các luật này với điều kiện vế phải chứa các giá trị phân lớp, hoặc có thể xây dựng cây quyết định rồi từ đó suy ra các luật này. Ngoài ra, còn có thể sử dụng một thuật toán gọi là thuật toán bao tuần tự (Sequential Covering Algorithm) để khám phá ra các luật này như AQ, CN2, Ripper [5]. Trong phương pháp này có hai khái niệm quan trọng phải lưu ý đó là độ chính xác của luật (accuracy of rule) và độ bao phủ của luật (coverage of rule). Cho một luật R, gọi D là tập huấn luyện, X là bộ dữ liệu đã được đánh nhãn trong D; Ncovers là số bộ dữ liệu thỏa mãn vế trái của luật R; Naccuracy là số bộ dữ liệu thỏa mãn luật Rvà |D| là số bộ dữ liệu trong tập huấn luyện. Hai tham số này được định nghĩa như sau: coverage(R) = |D| N erscov accuracy(R) = erscov accuracy N N Xét ví dụ về một bảng dữ liệu khách hàng của một công ty tin học như sau: PDF created with pdfFactory Pro trial version www.pdffactory.com 22 Bảng 1.2: Một ví dụ về dữ liệu khách hàng. Age Income Student Credit_rating Buy_computer (Class) Youth High No Fair No Youth High No Excellent No Middle_Age High No Fair Yes Senior Medium No Fair Yes Senior Low Yes Fair Yes Senior Low Yes Excellent No Middle_Age Low Yes Excellent Yes Youth Medium No Fair No Youth Low Yes Fair Yes Senior Medium Yes Fair Yes Youth Medium Yes Excellent Yes Middle_Age Medium No Excellent Yes Middle_Age High Yes Fair Yes Senior Medium No Excellent No Trong bảng dữ liệu trên, hãy xét luật sau: R: Nếu “age” = Youth và “student” = yes thì “buy_computer” = yes. Nhận thấy rằng với luật R, có hai bộ thỏa mãn vế trái (tức vừa có “age” = Youth vừa có “student” = yes) trong tổng số mười bốn bộ. Vậy coverage(R) = 2 / 14 ≈ 14.28 % . Cả hai bộ này đêu thỏa mãn vế phải (phân lớp - tức “buy_computer” = yes). Như vậy, độ đo accuracy(R) = 2 / 2 = 100%. § Phương pháp phân lớp sử dụng mạng nơron lan truyền ngược: Lĩnh vực nghiên cứu của phương pháp mạng nơron dựa trên ý tưởng chính là bộ não con người. Phương pháp này hơi có vẻ không trực quan và quá trình học phải lặp đi lặp lại nhiều lần [5]. PDF created with pdfFactory Pro trial version www.pdffactory.com 23 Hình 1.5: Một mô hình mạng nơron nhiều lớp. § Phương pháp phân lớp sử dụng SVM (Support Vector Machine): đây là một phương pháp tương đối mới trong thời gian gần đây. Ý tưởng chính của phương pháp này là dùng một đường phân chia (còn gọi là biên quyết định) để phân chia tập dữ liệu. Ta có thể tưởng tượng một đường thẳng cắt ngang không gian của tập dữ liệu (các dữ liệu là các điểm) như hình minh họa dưới đây: Hình 1.6 – Một mô hình SVM, các đường đứt nét là các đường phân chia có thể được chọn để phân chia tập dữ liệu thành hai lớp riêng biệt. 2 1 3 4 5 6 x1 x2 x3 w14 w15 w24 w25 w34 w35 w46 w56 A2 A1 Class 1, y= +1 (có_máy_tính=yes) Class 1, y= -1 (có_máy_tính =no) PDF created with pdfFactory Pro trial version www.pdffactory.com 24 § Phương pháp phân lớp dựa trên thuật giải di truyền (Classification using Genetic Algorithm): Thuật giải di truyền thể hiện tự nhiên theo cách rất sinh động, các luật (bất kỳ) được tạo ra theo kiểu luật nếu …. thì …. và được mã hóa thành các chuỗi bit. Tập dữ liệu ban đầu trong quần thể, thông qua hai phương pháp cơ bản của tự nhiên là lai ghép và đột biến để tạo một quần thể mới dựa trên một độ đo gọi là độ đo thích nghi (fitness) và quá trình tạo quần thể mới cứ tiếp diễn đến khi nào có một quần thể được tạo ra mà trong đó mỗi cá thể (luật) thỏa mãn ngưỡng của độ đo thích nghi này. Phương pháp thuật giải di truyền có thể dễ dàng song song hóa và tối ưu nên thường được sử dụng để đánh giá tính phù hợp cũng như độ chính xác của các phương pháp phân lớp khác. § Hướng tiếp cận dựa trên tập thô: Phương pháp này dựa trên một lý thuyết gọi là lý thuyết tập thô, chỉ áp dụng cho các dữ liệu rời rạc, các giá trị liên tục như giá trị số khi muốn áp dụng phương pháp này thì trước hết phải “rời rạc hóa”. Lý thuyết tập thô dựa trên cơ sở đưa ra các lớp tương đương bên trong tập dữ liệu, tất cả dữ liệu tồn tại dưới hình thức lớp tương đương sẽ không thể phân biệt được. Xem thêm về lý thuyết tập thô trong [2]. Hình 1.7: tập thô xấp xỉ tập các bộ của lớp C dùng các tập biên trên và biên dưới gần đúng của C, các hình chữ nhật đại diện cho các lớp tương đương. § Hướng tiếp cận dùng tập mờ (Fuzzy Set Approaches): Dùng lý thuyết mờ và tập mờ để giải quyết bài toán phân lớp [1]. Biên trên xấp xỉ của C Biên dưới xấp xỉ của C PDF created with pdfFactory Pro trial version www.pdffactory.com 25 § Phương pháp sử dụng sinh ngẫu nhiên tập dữ liệu: Mục đích chính của phương pháp này là từ một tập dữ liệu ban đầu sẽ sinh ra một tập dữ liệu con bằng nhiều cách như lựa chọn ngẫu nhiên hay thay thế một phần dữ liệu. Việc sinh tập dữ liệu mới sẽ được lặp lại nhiều lần và sẽ dùng các tập dữ liệu mới này để phân lớp. Mục đích của phương pháp phân lớp này là hướng đến một mô hình chính xác hơn. v Mỗi phương pháp phân lớp có những ưu và khuyết điểm khác nhau, tuy nhiên xét về góc độ trực quan đối với người dùng thì tạm thời có thể phân cấp các phương pháp phân lớp từ thấp đến cao (theo nghĩa dễ hiểu, dễ sử dụng đối với người dùng) như sau: Hình 1.8 – Phân chia theo mức độ cảm quan của người sử dụng. 1.3 NỘI DUNG LUẬN VĂN Nội dung luận văn này được chia ra làm năm phần như sau: Ø Phần một: Mô tả tổng quan về khai mỏ dữ liệu và phân lớp, mô tả các bài toán con trong khai mỏ dữ liệu cũng như các phương pháp phân lớp. Cây quyết định Luật kết hợp Phương pháp sinh ngẫu nhiên tập dữ liệu Phương pháp tập mờ Phương pháp SVM Phương pháp dùng thuật giải di truyền Phương pháp Bayes Phương pháp mạng nơ ron Dễ hiểu Khó hiểu PDF created with pdfFactory Pro trial version www.pdffactory.com 26 Ø Phần hai: Mô tả bài toán phân lớp dữ liệu dựa trên cây quyết định, sơ lược về các thuật toán hiện tại cũng như các ưu và khuyết điểm của chúng. Dựa trên việc phân tích các ưu khuyết điểm này để đưa ra một thuật toán mới nhằm tránh được các khuyết điểm nhưng vẫn giữ lại các ưu điểm của các thuật toán trên. Ø Phần ba: Mô tả thuật toán Hybrid Data sử dụng Hybrid list cho bài toán phân lớp nhằm làm giảm tối thiểu việc truy xuất đọc/ghi dữ liệu mà vẫn đảm bảo được đầy đủ thông tin và khả năng mở rộng của bài toán. Lưu ý luận văn chỉ tập trung vào pha phân lớp là chính, chủ yếu nhằm giảm chi phí về thời gian cũng như khả năng mở rộng khi dữ liệu tăng lên chứ không tập trung nhiều vào các pha khác. Bản chất thuật toán Hybrid Data không làm thay đổi kết quả trong quá trình tạo cây phân lớp so với các thuật toán trước đây mà cụ thể là không thay đổi các bước xử lý cơ bản trong thuật toán gốc. Chương này cũng chứng minh ưu điểm của Hybrid Data so với các thuật toán khác, mô tả các bước song song hóa thuật toán nhằm mở rộng thuật toán này trong trường hợp tập dữ liệu là rất lớn. Ngoài ra, luận văn cũng xin được đề cập đến một số vấn đề cần cải tiến trong thuật toán tổng quát, tìm hiểu nguyên nhân và đưa ra các giải pháp khắc phục để bổ sung cho các vấn đề này. Ø Phần bốn: Mô tả chương trình ứng dụng đã xây dựng để minh họa cho thuật toán Hybrid Data. Ø Phần năm: Nêu các đánh giá cũng như kiến nghị về phương pháp đã sử dụng. Nêu các kết luận cũng như các hướng phát triển của đề tài. Ø Phụ lục I: Ghi chú các thuật ngữ thường sử dụng trong các tài liệu liên quan. Ø Phụ lục II: Mô tả các thuật toán chính trong luận văn. PDF created with pdfFactory Pro trial version www.pdffactory.com