Phần mở đầu của luận văn giới thiệu nội dung nghiên cứu, tính cấp thiết của đề tài và những đóng góp chính của luận văn. Chƣơng 1 giới thiệu các khái niệm cơ bản về khai phá dữ liệu, Kho dữ liệu và ứng dụng. Chƣơng 2 giới thiệu về khai phá dữ liệu nói chung, các ứng dụng của khai phá dữ liệu. Chƣơng 3 giới thiệu các phƣơng pháp khai phá dữ liệu trực quan.
Chƣơng 4 giới thiệu các phƣơng pháp khai phá dữ liệu thông dụng, cách sử dụng và các trƣờng hợp nên dùng chúng. Chƣơng 5 nói về giải thuật di truyền, ứng dụng giải thuật di truyền vào bài toán lập thời khoá biểu, xây dựng bài toán lập thời khoá biểu. Phần kết luận nêu các đóng góp của luận văn và các hƣớng nghiên cứu tiếp theo. Phần phụ đƣa danh sách các modul chính trong chƣơng trình.
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU. Tổ chức và khai thác cơ sở dữ liệu truyền thống Ngay từ những năm 60, việc dùng các phƣơng tiện tin học để tổ chức khai thác các cơ sở dữ liệu (CSDL) đã đƣợc phát triển. Cho đến nay, rất nhiều CSDL đã đƣợc xây dựng, phát triển và khai thác ở khắp các lĩnh vực hoạt động của con ngƣời và xã hội. Hiện nay, lƣợng thông tin trên thế giới cứ sau 24 tháng lại tăng gấp đôi.
Ngày nay, với sự phát triển mạnh mẽ của công nghệ bán dẫn, tạo ra các hệ thống với dung lƣợng lớn, bộ xử lý tốc độ cao cùng và các công nghệ truyền hiện đại, ngƣời ta đã xây dựng các hệ thống thông tin hiện đại, trợ giúp mọi hoạt động kinh doanh, điều đó đã tạo ra khối dữ liệu khổng lồ, cần xử lý, nó bao gồm các cơ sở dữ liệu cực lớn cỡ gigabytes và thậm chí terabytes lƣu trữ các dữ liệu kinh doanh. Nhiều hệ quản trị CSDL với các công cụ mạnh ra đời trợ giúp cho con ngƣời khai thác có hiệu quả các nguồn tài nguyên dữ liệu. Mô hình CSDL quan hệ và ngôn ngữ truy vấn cấu trúc (SQL-Structure Query Language) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác các CSDL đó. Cho đến nay, không một tổ chức kinh tế nào là không sử dụng các hệ quản trị CSDL và các hệ công cụ báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các CSDL , phục vụ cho hoạt động tác nghiệp của mình.
Theo sự phát triển đi lên của các hệ thống cơ sở dữ liệu, các hệ thống thông tin cũng đƣợc chuyên môn hoá, phát triển chuyên sâu theo các lĩnh vực ứng dụng nhƣ sản xuất, kinh doanh, tài chính, thị trƣờng. Nhƣ vậy bên cạnh chức năng khai thác dữ liệu có tính chất tác nghiệp, sự ứng dụng trong kinh doanh không còn là dữ liệu đơn thuần của các hệ thống nữa mà cơ sở dữ liệu cần đem lại những "tri thức" hơn là chính những dữ liệu đó. Trong xã hội hiện nay, các hoạt động kinh doanh cần có các quyết định nhanh và chính xác dựa trên những dữ liệu sẵn có, trong khi đó khối lƣợng dữ liệu tăng nhanh làm ảnh hƣởng đến thời gian ra quyết định cũng nhƣ khả năng hiểu hết đƣợc nội dung dữ liệu. Điều này dẫn đến các mô hình CSDL truyền thống và ngôn ngữ hỏi không có khả năng đáp ứng đƣợc yêu cầu này.
Để lấy đƣợc những thông tin có tính "tri thức" trong khối dữ z 7 liệu khổng lồ này, ngƣời ta đã đi tìm những kỹ thuật có khả năng hợp nhất các dữ liệu từ các hệ thống dữ liệu khác nhau, chuyển đổi thành một tập hợp các cơ sở dữ liệu ổn định, có chất lƣợng đƣợc sử dụng chỉ riêng cho một vài mục đích nào đó. Các kỹ thuật đó đƣợc gọi chung là kỹ thuật tạo kho dữ liệu (Data Warehousing) và môi trƣờng các dữ liệu có đƣợc gọi là các kho dữ liệu. Tuy nhiên, việc sử dụng các cách khai thác dữ liệu theo khai thác truyền thống mới chỉ dừng lại ở cách khai thác dữ liệu với các kỹ thuật cao để đƣa ra các dữ liệu tinh và chính xác hơn chứ chƣa đƣa ra đƣợc dữ liệu "tri thức". Kho dữ liệu đƣợc sử dụng để hỗ trợ cho phân tích trực tuyến (OLAP) có khả năng phân tích dữ liệu, xác định xem giả thuyết đúng hay sai nhƣng không thể đƣa ra các giả thuyết.
Kỹ thuật học máy có thể đƣa ra giả thuyết, nhƣng trên các tập dữ liệu lớn trong kho dữ liệu thì chúng thể hiện khả năng rất kém. phƣơng pháp thống kê cũng không có cải tiến gì để phù hợp với sự phát triển của dữ liệu. Đây là lý do tại sao vẫn còn khối lƣợng lớn dữ liệu vẫn chƣa đƣợc khai thác và thậm chí đƣợc lƣu chủ yếu trong các kho dữ liệu không trực tuyến. Điều này đã tạo nên một lỗ hổng lớn trong việc hỗ trợ phân tích và tìm hiểu dữ liệu, tạo ra khoảng cách giữa việc tạo ra dữ liệu và việc khai thác các dữ liệu đó Trong khi đó, càng ngày ngƣời ta càng nhận thấy rằng nếu đƣợc phân tích thông minh thì dữ liệu sẽ là một nguồn tài nguyên quí giá trong cạnh tranh trên thƣơng trƣờng.
một công nghệ mới đƣợc nghiên cứu, đáp ứng cả nhu cầu trong khoa học cũng nhƣ trong hoạt động thực tiễn. Đó chính là công nghệ Khai phá dữ liệu. Khai phá dữ liệu và quá trình phát hiện tri thức. Việc sử dụng cơ sở dữ liệu vào hoạt động của một tổ chức đã đƣợc phát triển trong vòng 60 năm trở lại đây.
Với dữ liệu đƣợc thu thập trong suốt quá trình hoạt động của một tổ chức, một nhu cầu đƣợc đặt ra là tìm kiếm và khai thác tri thức từ những dữ liệu đó. Đó chính là xuất phát điểm của bài toán Phát hiện tri thức từ cơ sở dữ liệu. Ngƣời ta nhận thấy rằng có rất nhiều tri thức mà chúng ta không lƣờng trƣớc đang còn tiềm ẩn trong dữ liệu, nhiệm vụ của chúng ta là phát hiện, khám phá các tri thức đó, phục vụ cho những nhu cầu sử dụng thông tin cao hơn, ví dụ nhƣ trong các hệ chuyên gia hay hệ hỗ trợ quyết định. Khai phá dữ liệu đƣợc định nghĩa nhƣ là quá trình chắt lọc hay khai phá tri thức từ một lƣợng lớn dữ liệu.
Một ví dụ trực quan thƣờng đƣợc dùng là việc khai thác vàng từ đá và cát, một ngƣời khai thác muốn chắt lọc đƣợc vàng từ đá và cát z 8 hơn là việc tìm phải đá hoặc cát. Thuật ngữ data mining ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một lƣợng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện đƣợc dùng cũng có nghĩa tƣơng tự với từ data mining nhƣ knowledge mining (khai phá tri thức), knowledge extraction (chắt lọc tri thức), data/ patern analysis (Phân tích dữ liệu/ mẫu), data archaeology (khảo cổ dữ liệu), data dredging (nạo vét dữ liệu). Nhiều ngƣời thƣờng nhầm lẫn khái niệm khai phá dữ liệu với các thuật ngữ khác là khai phá tri thức – Knowledge Discovery in Databases (KDD).
Khai phá dữ liệu chỉ là một bƣớc trong quá trình KDD. KDD gồm có các quá trình theo thứ tự nhƣ sau [15]: 1. Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết. Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau tích hợp lại.
Lựa chọn dữ liệu: Các dữ liệu có liên quan tới quá trình phân tích đƣợc lựa chọn từ cơ sở dữ liệu. Chuyển đổi dữ liệu: Các dữ liệu đƣợc chuyển đổi sang các dạng phù hợp cho quá trình xử lý. Khai phá dữ liệu: Là một trong nhƣng bƣớc quan trọng nhất, trong đó sử dụng những phƣơng pháp thông minh để chắt lọc ra những mẫu dữ liệu. Ước lượng mẫu: Quá trình đánh giá các kết quả tìm đƣợc thông qua các độ đo nào đó.
Biểu diễn tri thức: Quá trình này sử dụng các kĩ thuật biểu diễn và thể hiện trực quan các tri thức cho ngƣời dùng. Khai phá dữ liệu là giai đoạn chủ yếu của quá trình Phát hiện tri thức từ CSDL. Công đoạn khai phá tri thức đƣợc thực hiện sau các quá trình thu thập và tinh lọc dữ liệu, có nghĩa là chỉ tìm các mẫu hình tri thức (pattern) có ý nghĩa trên tập dữ liệu có hy vọng chứ không phải là trên toàn bộ CSDL nhƣ các phƣơng pháp thống kê trƣớc đây. Vì vậy khai phá dữ liệu bao gồm việc thử tìm mô hình phù hợp với dữ liệu và tìm kiếm các mẫu hình tri thức từ dữ liệu theo mô hình đó.
Mặc dù mẫu hình z 9 có thể tìm đƣợc từ bất kỳ một CSDL nào nhƣng chỉ những mẫu phù hợp với mục đích tìm kiếm mới đƣợc gọi là tri thức. Ta sẽ có những hàm số để đánh giá các tiêu chí mẫu nhƣ mới, có lợi, đáng xem xét. Độ mới của mẫu hình phụ thuộc vào khung phạm vi quy chiếu, có thể đối với hệ thống hoặc đối với ngƣời dùng. Ví dụ với dữ liệu của một công ty, quá trình Khai phá dữ liệu tìm ra đƣợc một luật nhƣ “Lợi tức thu đƣợc giảm vào mùa thu ở vùng phía Bắc”, đối với hệ thống thì rất mới, trƣớc kia chƣa hề có nhƣng bất cứ một cán bộ lập kế hoạch nào cũng nhận ra đƣợc điều này qua các báo cáo tài chính.
Tính hữu dụng của mẫu có thể đo đƣợc qua sự liên quan đến mục đích tìm kiếm. Với một cán bộ phụ trách bảo trì máy tính ở công ty thì luật trên không có giá trị, mặc dù là mới đối với anh ta. Có thể qua công đoạn khai phá tri thức có rất nhiều mẫu đƣợc lấy ra nhƣng không phải mẫu nào cũng có giá trị, có thể là mới, hữu ích nhƣng lại tầm thƣờng, đặc biệt là khi áp dụng các kỹ thuật dựa trên thống kê. Do đó luôn phải có các tiêu chí và các hàm đánh các mẫu đáng xem xét, không tầm thƣờng.
Tóm lại, Khai phá dữ liệu thực ra có thể coi là một quá trình xác định mẫu từ các Datawarehouse, sử dụng các kỹ thuật sẵn có nhƣ học máy, nhận dạng, thống kê, phân loại. và các kỹ thuật đƣợc phát triển bởi ngành nghiên cứu trí tuệ nhân tạo nhƣ Mạng nơ-ron nhân tạo (neutral network), các thuật toán di truyền (generic algorithm), quy nạp luật (rule induction). Ta có thể xét đến một số bài toán chính đối với nghiên cứu về Khai phá dữ liệu [9]: Bài toán phân lớp (classification): Tìm một ánh xạ (phân loại) từ một mẫu dữ liệu vào một trong các lớp cho trƣớc.