CHƯƠNG 1: TỔNG QUAN TÌNH HÌNH NGHIÊN CỨU, CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN VỀ VIỆC ĐÁNH GIÁ HIỆU QUẢ LÀM VIỆC CỦA CÁN BỘ CÔNG CHỨC 1.1 Tổng quan về khai phá dữ liệu 1.1 Khái niệm của khai phá dữ liệu Khai phái 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, KPDL 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 (regularities) trong tập dữ liệu[4]. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database-KDD) để 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 đó, KPDL là một bước đặc biệt trong toàn bộ tiến trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu (pattern) (hay các mô hình) từ dữ liệu[5]. Khai phá dữ liệu là một tiến trình sử dụng các công cụ phân tích dữ liệu khác nhau để khám phá ra các mẫu dưới nhiều góc độ khác nhau nhằm phát hiện ra các mối quan hệ giữa các dữ kiện, đối tượng bên trong CSDL, kết quả của việc khai phá là xác định các mẫu hay các mô hình đang tồn tại bên trong, nhưng chúng nằm ẩn khuất ở các CSDL. Để từ đó rút trích ra được các mẫu, các mô hình hay các thông tin và tri thức từ các CSDL. Các giải thuật KPDL thường được mô tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu.
Với các phương pháp học máy và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích được. Quá trình xử lý KPDL bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết.
Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chú́ ng thành dạng sao cho giải thuật LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 KPDL có thể hiểu được. Về lý thuyết thì có vẻ rất đơn giản nhưng khi thực hiện thì đây thực sự là một quá trình rất khó khăn, gặp phải rất nhiều vướng mắc như: các dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi). Bước tiếp theo là chọn thuật toán KPDL thích hợp và thực hiện việc KPDL để tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó (thường được biểu diễn dưới dạng các luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy).
Đặc điểm của mẫu phải là mới (ít nhất là đối với hệ thống đó). Độ mới có thể đuợc đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện tại với các giá trị trước đó hoặc các giá trị mong muốn) hoặc bằng tri thức (mối liên hệ giữa phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới của mẫu được đánh giá bằng một hàm logic hoặc một hàm đo độ mới, độ bất ngờ của mẫu.1: Sơ đồ quá trình KPDL Kỹ thuật KPDL thực chất là phương pháp không hoàn toàn mới. Nó là sự kế thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như máy học, nhận dạng, thống kê (hồi quy, xếp loại, phân cụm), các mô hình đồ thị, các mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia, v.v… Tuy nhiên, với sự kết hợp tài tình của KPDL, kỹ thuật này có ưu thế hơn hẳn các phương pháp trước đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa học.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Các thuật toán và công cụ 1) Khái thác tập phổ biến và luật kết hợp Khai phá tập mục thường xuyên là bài toán có vai trò quan trọng nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục thường xuyên được biết đến ban đầu là một trong những bài toàn quan trọng của khai phá luật kết hợp được giới thiệu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị, phân tích sở thích mua của khách hàng bằng các tìm ra những mặt hàng khác nhau được khách hàng mua cùng trong một lần mua. Những thông tin như vậy sẽ giúp người quản lý kinh doanh tiếp thị chọn lọc và thu xếp không gian bày hàng hợp lí hơn, giúp cho kinh doanh hiệu quả hơn. Đây là tiến trình khám phá các tập giá trị thuộc tính xuất hiện phổ biến trong các đối tượng dữ liệu.
Từ tập phổ biến có thể tạo ra các luật kết hợp giữa các giá trị thuộc tính nhằm phản ánh khả năng xuất hiện đồng thời các giá trị thuộc tính trong tập các đối tượng. Một luật kết hợp X → Y phản ánh sự xuất hiện của tập X dẫn đến sự xuất hiện đồng thời của tập Y. Chẳng hạn 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ó khuynh hướng mua phần mềm quản lý nhân sự trong cùng lần mua được miêu tả bằng luật kết hợp như: “Máy tính Þ Phần mềm quản lý nhân sự” Luật kết hợp giúp các nhà hoạch định hiểu rõ xu thế bán hàng, tâm lý khách hàng từ đó đưa ra chiến lược bố trí mặt hàng, kinh doanh, tiếp thị. Việc sinh luật kết hợp có 2 bước: bước thứ nhất là tìm các tập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ tối thiểu minsup cho trước; bước thứ hai là từ các tập mục thường xuyên tìm được sinh ra các luật kết hợp thỏa mãn ngưỡng độ tin cây minconf cho trước.
Mộ khó khăn của bài toán này là tập trung ở bước thú nhất, đó là khai phá tất cả các tập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ cho trước. 2) Phân lớp dữ liệu Phân lớp (Classification): Là tiến trình khám phá các luật phân loại hay đặc trưng cho các tập dữ liệu đã được xếp lớp. Tập dữ liệu học bao gồm tập đối tượng đã được xác định lớp sẽ được dùng để tạo mô hình phân lớp dựa trên đặc trưng của đối tượng trong tập dữ liệu học. Các luật phân lớp được sử dụng để xây dựng các bộ phân lớp dữ liệu.
Phân lớp dữ liệu có vai trò quan trọng trong tiến trình dự báo các khuynh hướng quy luật phát triển. Áp dụng vào tiến trình phân lớp dữ liệu khách hàng trong CSDL LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 có thể xây dựng các luật phân lớp khách hàng. Một số kỹ thuật thường được sử dụng trong phân lớp: - Cây quyết định (Decision tree): Cấu trúc dạng hình cây là biểu thị cho các quyết định. Các quyết định này sinh ra các quy tắc để phân lớp và dự đoán (dự báo) tập dữ liệu mới chưa được phân lớp.
Tri thức được rút ra trong kỹ thuật này thường được mô tả dưới dạng tường minh, đơn giản, trực quan, dễ hiểu đối với người sử dụng. Tuy vậy, nó cũng đòi hỏi một không gian nhất định để mô tả tri thức trong phạm vi mà con người có thể hiểu được. - Mạng Nơron (Neural Network): Đây là một trong những kỹ thuật được ứng dụng rất phổ biến hiện nay vì kỹ thuật này bắt chước khả năng tìm kiếm mẫu của bộ não con người. Việc huấn luyện theo phương pháp này được bắt đầu bằng việc cho vào một tập dữ liệu (gọi là tập dữ liệu huấn luyện) mạng sẽ tự động điều chỉnh (học) qua từng lớp trong mạng và cho ra kết quả, quá trình huấn luyện được lặp đi lặp lại nhiều lần.
Sau khi mạng học thành công thì nó được xem là một chuyên gia trong lĩnh vực đó. 3) Gom cụm Gom cụm (clustering): Là tiến trình nhận diện các cụm tiềm ẩn trong tập các đối tượng chưa được xếp lớp. Tiến trình phân cụm dựa trên mức độ tương tự giữa các đối tượng. Các đối tượng được gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng một cụm là cực đại và mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là cực tiểu.
Các cụm được đặc trưng bằng các tính chất chung của tất cả các đối tượng trong cụm. Do vậy, khảo sát các cụm sẽ giúp khái quát, tổng kết nhanh chóng nội dung của khối dữ liệu lớn. Một số kỹ thuật dùng trong gom cụm: phương pháp phân cấp và thuật giải k-means. Trong phương pháp phân cấp gồm hai giai đoạn: ở giai đoạn gộp mỗi đối tượng thuộc về một lớp, dưới một ngưỡng nào đó chúng được gom lại và tiếp tục như vậy cho đến khi tất cả các đối tượng thuộc về cùng một cụm; còn ở giai đoạn tách sẽ tiến hành ngược lại so với giai đoạn gộp.
Trong phương pháp này, để đưa ra được ngưỡng người ta dựa vào liên kết đơn (khoảng cách gần nhất) và liên kết đôi (khoảng cách xa nhất) giữa hai cụm. Trong thuật giải k-means: khi tiến hành gom cụm ta cần phải biết trước số cụm. Với mỗi cụm như vậy ta chọn phần tử trọng tâm, tiếp đến tính khoảng cách từ mỗi đối LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 tượng đến phần tử trọng tâm ở tất cả các cụm và gán nó vào cụm có khoảng cách nhỏ nhất. Quá trình này tiếp tục như vậy cho đến khi các cụm không còn biến đổi hoặc thoả điều kiện đặt ra [5].3 Ứng dụng của khai phá dữ liệu KPDL được vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông tin.
Tùy theo bản chất của từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác nhau. KPDL cũng được vận dụng hiệu quả để giải quyết các bài toán phức tạp trong các ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu từ ảnh viễn thám, xác định các vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong các hệ thống sản xuất.