MỞ ĐẦU Công nghệ thông tin đã và đang trở thành lĩnh vực nghiên cứu, ứng dụng và triển khai có hiệu quả trong đời sống kinh tế, xã hội. Việc ứng dụng công nghệ thông tin trong các ngành khoa học, kinh tế, xã hội đã mang lại những hiệu quả to lớn không thể phủ nhận. Với các ngành khoa học, kinh tế - xã hội nơi có những kho dữ liệu khổng lồ thì việc tìm kiếm, truy xuất và đưa ra những thông tin cần thiết phù hợp với thời gian và yêu cầu là không dễ dàng và chính vì thế một thế hệ mới các phương pháp tiếp cận, phương pháp nghiên cứu, và các kỹ thuật, công cụ cho phép phân tích, tổng hợp, khai phá tri thức từ dữ liệu một cách thông minh và hiệu quả đã được các nhà khoa học quan tâm và nghiên cứu. Một trong những lĩnh vực nghiên cứu các phương pháp ứng dụng khai phá dữ liệu, tìm kiếm tri thức, kết xuất tri thức … từ dữ liệu là cây quyết định (decision tree) cũng được nghiên cứu từ nhiều năm trước đây và đã có những kết quả khả quan và mang lại hướng ứng dụng có hiệu quả cao.
Ngày nay, kỹ thuật khai phá dữ liệu dựa trên cây quyết định đã được áp dụng và mạng lại hiệu quả cho nhiều ngành, nhiều lĩnh vực như: kinh tế, tài chính, khoa học - kỹ thuật, ngân hàng, thương mại, giáo dục, y tế,… Các kỹ thuật khai phá dữ liệu bằng cây quyết định rất đa dạng và phong phú như các kỹ thuật dựa trên các thuật toán Hunt, ID3, C4.5, … và kỹ thuật xây dựng cây quyết đinh dựa trên các phụ thuộc hàm trong cơ sở dữ liệu quan hệ. Với mong muốn làm rõ hơn các kỹ thuật khai phá tri thức từ dữ liệu sử dụng cây quyết định nhằm phục vụ công tác nghiên cứu chuyên môn cũng như mong muốn đưa các kỹ thuật khai phá dữ liệu sử dụng cây quyết định vào thực tế nên tôi lựa chọn thực hiện luận văn tốt nghiệp sau đại học là “Một số phƣơng pháp xây dựng cây quyết định trong khai phá dữ liệu”. Mục đích khi thực hiện luận văn này là tổng hợp các kiến thức về kỹ thuật khai phá dữ liệu bằng các kỹ thuật xây dựng cây quyết định dựa trên các thuật toán và phương pháp xây dựng cây quyết định dựa trên phụ thuộc hàm của cơ sở dữ liệu quan hệ. Nội dung chính của luận văn bao gồm 5 chương, trong đó: 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1.
Tổng quan, chương này trình bày khái quát về các vấn đề về khai phá dữ liệu, các thách thức gặp phải khi sử dụng các kỹ thuật khai phá dữ liệu và các ứng dụng của khai phá dữ liệu và tình hình nghiên cứu về khai phá dữ liệu nói chung và kỹ thuật khai phá dữ liệu sử dụng cây quyết định nói riêng ở thế giới và nước ta. Các khái niệm cơ bản, bao gồm các khái niệm cơ bản về khai phá dữ liệu, cây quyết định, các khái niệm trong cơ sở dữ liệu quan hệ. Một số phƣơng pháp xây dựng cây quyết định, chương này là trọng tâm của luận văn đề cập đến phương pháp xây dựng cây quyết định dựa trên các thuật toán khai phá dữ liệu bằng cây quyết định bao gồm các thuật toán CLS, ID3, C4.5 và phương pháp xây dựng cây quyết định dựa trên phụ thuộc hàm xấp xỉ trong cơ sở dữ liệu quan hệ. Ứng dụng thử nghiệm, chương này so sánh các kỹ thuật xây dựng cây quyết định và đưa ra bài toán ứng dụng thử nghiệm để từ đó áp dụng một phương pháp khai phá dữ liệu cho bài toán đã nêu ra, từ đó thiết kế các modul cho triển khai bài toán.
Đánh giá, kết luận, chương này đưa ra các đánh giá, kết luận và các phân tích sau khi thực hiện luận văn. Trong luận văn, các trích dẫn của các tác giả khác liên quan đến lĩnh vực nghiên cứu đặt trong dấu ngoặc vuông [ ]. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1. SƠ LƢỢC VỀ KHAI PHÁ TRI THỨC 1.
Dữ liệu và tri thức Trong những năm gần đây, dưới sự tác động mạnh mẽ của khoa học và công nghệ đặc biệt là công nghệ thông tin và truyền thông thì các dữ liệu cần được lưu trữ ngày càng lớn do đặc trưng của dữ liệu là thông tin, có thông tin là có dữ liệu. Chúng ta có thể có nhiều dạng dữ liệu khác nhau cho nhiều lĩnh vực khác nhau nhưng cũng có thể các dữ liệu lại có một sự quan hệ tương đối mật thiết và chặt chẽ với nhau và không phải dữ liệu nào thu được cũng hoàn toàn chính xác hoặc phù hợp với yêu cầu của con người. Từ dữ liệu, con người phải tiến một bước dài trước khi xác định được tri thức trong khi con người luôn luôn mong muốn có được một tri thức đúng về một vấn đề cụ thể nào đó. Tri thức chính là động lực quan trọng trong quá trình phát triển và tiến bộ của con người nói riêng và văn minh nhân loại nói chung dù rằng những khái niệm chính xác về tri thức, bản chất của tri thức, quá trình hình thành của tri thức, mối quan hệ của các đối tượng trong thế giới với tri thức,… vẫn đang được tranh luận và chưa có câu trả lời thỏa đáng nhưng trong mọi lĩnh vực từ khoa học, công nghệ, kỹ thuật,… đến kinh tế, văn hóa, xã hội tri thức luôn luôn được tìm kiếm, phát hiện và tác động ngày càng lớn đến sự phát triển của loài người.
Sự phong phú về thông tin, dữ liệu cùng với khả năng kịp thời khai thác chúng đã mang lại những năng suất và chất lượng cao trong công tác quản lý, hoạt động kinh tế, phát triển sản xuất và dịch vụ,… tuy nhiên, các yêu cầu về thông tin, tri thức trong các dữ liệu đó đặc biệt là công tác quyết định ngày càng đòi hỏi chất lượng cao hơn, kịp thời hơn và nhều tri thức hơn nhằm hỗ trợ việc ra quyết định của mình. Không phải ngẫu nhiên mà John Naisbett đã cảnh báo “Chúng ta đang ngập chìm trong dữ liệu mà vẫn đói tri thức” [1], điều đó cũng báo trước việc ứng dụng công nghệ thông tin đang chuyển sang một thời kỳ mới mà mục đích chủ yếu của công nghệ thông tin là giúp con người nhiều hơn trong 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com quá trình tìm kiếm, khai phá tri thức từ dữ liệu, biến đổi từ sự giàu có về thông tin thành sự giàu có về tri thức. Các khái niệm thông tin, dữ liệu và tri thức luôn có quan hệ chặt chẽ, mật thiết với nhau và khó phân biệt được bằng các định nghĩa rõ ràng. Ta có thể hiểu thông tin như là khái niệm chung nhất bao gồm mọi sự hiểu biết về các sự vật, hiện tượng, quan hệ,… mà con người thu nhận được qua các giác quan, giao tiếp, khảo sát, thực nghiệm, nghiên cứu, lý giải,… Dữ liệu có thể được mô tả bởi các giá trị cho các sự kiện, hiện tượng cụ thể còn tri thức có thể được xem như là những hiểu biết có mức độ khái quát, về các mối quan hệ có quy luật giữa các thuộc tính của đối tượng, các sự vật, hiện tượng mà con người thu được sau khi “chân lý hóa” bằng kinh nghiệm, phân tích dữ liệu hay qua nghiên cứu, lý giải, suy luận.
Hoạt động nhận thức của con người bao gồm việc tìm kiếm tri thức để tăng cường sự hiểu biết về xã hội và cuộc sống, từ đó có thể tạo nên các kỹ thuật, công nghệ và giải pháp nhằm cải thiện đời sống của mình. Dưới sự trợ giúp của công nghệ thông tin, các phương pháp khai phá tri thức từ dữ liệu đã được từng bước nghiên cứu và các công cụ, giải pháp nhằm tổ chức các kho thông tin và dữ liệu có khả năng linh hoạt hơn trong việc trợ giúp quyết định trên nền kiến trúc khách hàng, phục vụ thích hợp, với việc sử dụng các phương pháp khai phá dữ liệu và phát hiện tri thức hiện đang được nghiên cứu rộng rãi trên thế giới cũng như ở Việt Nam. Từ nhiều thế kỷ qua, nếu như khoa học luôn hướng đến việc phát hiện các tri thức có giá trị phổ biến dưới dạng các nguyên lý, quy luật, định lý,… thì ngày nay chúng ta càng thấy rõ rằng ngay trong cuộc sống hàng ngày, trong việc quản lý, kinh doanh,… cũng cần những tri thức có thể có ý nghĩa hẹp hơn, ít phổ biến hơn, có độ chính xác thấp hơn, có đời sống ngắn hơn,… nhưng lại đáp ứng và phù hợp với nhu cầu trực tiếp của con người. Tuy nhiên, để có thể nhận biết được các tri thức này lại là điều không đơn giản.
Một trong những nguồn dữ liệu quan trọng để từ đó có thể khai phá, phân tích, tổng hợp là các kho thông tin, các cơ sở dữ liệu phong phú mà con người đã và đang tích lũy được. Khai phá dữ 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com liệu và phát hiện tri thức là một hướng nghiên cứu quan trọng, đang phát triển mạnh và phù hợp với các công việc quan trọng đó. Khai phá tri thức Với khối lượng thông tin do con người khám phá và được lưu trữ ngày càng nhiều đặc biệt là trong những thập niên gần đây. Dữ liệu được tích lũy ngày càng nhiều và tốc độ phát triển của dữ liệu tích lũy ngày càng cao.
Một số báo cáo cũng đã nhận định rằng lượng thông tin trên toàn cầu tăng khoảng gấp đôi sau hai năm, theo đó số lượng cũng như kích cỡ các cơ sở dữ liệu cũng tăng lên nhanh chóng. Và trong rất nhiều ngành từ kinh tế, xã hội đến khoa học công nghệ, các nhà nghiên cứu, quản lý, ứng dụng và triển khai đang phải đối mặt với một thách thức to lớn là trong tay có một khối lượng tài nguyên thông tin khổng lồ nhưng trong nhiều trường hợp lại thấy thiếu tri thức. Lượng thông tin và dữ liệu khổng lồ này thực sự đã trở thành nguồn tài nguyên có giá trị bởi thông tin và dữ liệu là yếu tố then chốt trong quá trình xử lý, điều hành, nghiên cứu,… Việc khai thác những thông tin, tri thức tiềm ẩn mang tính dự đoán từ các cơ sở dữ liệu lớn, khổng lồ đã và đang ngày càng trở thành lĩnh vực thiết yếu trong cuộc sống con người Những năm năm mươi của thế kỷ trước, cha đẻ của ngành khoa học máy tính là A.Von Neumann đã phân tích, so sánh, đánh giá và đưa ra nhiều nhận xét lạc quan về khả năng tư duy của máy tính trong tương lai.