- 7 CHƯƠNG 1: TỔNG QUAN PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU. - 8 1.2 Các kỹ thuật khai phá dữ liệu. - 10 1.3 Lợi thế của khai phá dữ liệu so với các phương pháp khác. - 17 CHƯƠNG 2: KỸ THUẬT PHÂN LOẠI TRONG KHAI PHÁ DỮ LIỆU. - 59 CHƯƠNG 3: KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU. - 60 3.2 Các kiểu dữ liệu trong phép phân cụm. - 108 4.2 Chuẩn bị dữ liệu. - Họ lưu trữ các dữ liệu này vì cho rằng trong nó ẩn chứa những giá trị nhất định nào đó. - Với những lý do như vậy, các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining). - Bước quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining - DM), giúp người sử dụng thu được những tri thức hữu ích từ những CSDL hoặc các nguồn dữ liệu khổng lồ khác. - Rất nhiều doanh nghiệp và tổ chức trên thế giới đã ứng dụng kĩ thuật khai phá dữ liệu vào hoạt động sản xuất kinh doanh của mình và đã thu được những lợi ích to lớn. - Phần IV: Cài đặt thử nghiệm Phần này trình bày một số kết quả đã đạt được khi tiến hành áp dụng các giải thuật khai phá dữ liệu để khai thác thông tin dữ liệu mẫu. - Từ đó, các kĩ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay. - 1.1.1 Khái niệm khai phá dữ liệu Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối của thập kỷ 1980. - Nó là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các CSDL, kho dữ liệu. - Nhiều người coi Khai phá dữ liệu và một thuật ngữ thông dụng khác là Phát hiện tri thức trong CSDL (Knowlegde Discovery in Databases - KDD) là như nhau. - Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình Phát hiện tri thức trong CSDL. - Dữ liệu đã chuyển đổi Trích lọc dữ liệu Hình 1.1: Quá trình phát hiện tri thức Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. - (1) Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. - Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. - (3) Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. - Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logíc. - Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. - Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. - Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. - (5) Khai phá dữ liệu: Đây là bước mang tính tư duy trong khai phá dữ liệu. - Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. - (6) Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. - Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. - Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng. - Trên đây là 6 giai đoạn của quá trình phát hiện tri thức, trong đó giai đoạn 5 - khai phá dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn được quan tâm nhiều nhất. - 1.2 Các kỹ thuật khai phá dữ liệu Hình 1.2 biểu diễn một tập dữ liệu giả hai chiều bao gồm 23 case (trường hợp). - Dữ liệu được phân loại vào hai lớp: những người không có khả năng trả nợ và những người tình trạng vay nợ đang ở trạng thái tốt (tức là tại thời điểm đó có khả năng trả nợ ngân hàng). - Hai mục đích chính của khai phá dữ liệu trong thực tế là dự đoán và mô tả. - Nó sử dụng các biến hay các trường trong cơ sở dữ liệu để dự đoán các giá trị không biết hay các giá trị tương lai. - 1.2.1.1 Phân loại Mục tiêu của phương pháp phân loại dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. - Quá trình phân loại dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình để phân loại dữ liệu. - Bước 1: Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước. - Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện. - Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát. - y Bước 2: Sử dụng mô hình để phân loại dữ liệu. - Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. - Hay nói cách khác, phân loại là học một hàm ánh xạ một mục dữ liệu vào một trong số các lớp cho trước. - Hình 1.3 cho thấy sự phân loại của các dữ liệu vay nợ vào trong hai miền lớp. - Hồi quy là học một hàm ánh xạ một mục dữ liệu vào một biến dự báo giá trị thực. - 1.2.2 Khai phá dữ liệu mô tả Kỹ thuật này có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. - Phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát. - Không giống như phân loại dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. - Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân loại dữ liệu là học bằng ví dụ (learning by example). - Hình 1.4 cho thấy sự phân cụm tập dữ liệu cho vay vào trong 3 cụm: lưu ý rằng các cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn một cụm. - Hình 1.4: Phân cụm tập dữ liệu cho vay vào trong 3 cụm 1.2.2.2 Luật kết hợp Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị 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. - 1.3.1 Học máy (Machine Learning) So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ, khai phá dữ liệu có thể sử dụng với các cơ sở dữ liệu thường động, không đầy đủ, bị nhiễu và lớn hơn nhiều so với các tập dữ liệu học máy điển hình. - Trong khi đó phương pháp học máy chủ yếu được áp dụng trong các CSDL đầy đủ, ít biến động và tập dữ liệu không quá lớn. - Thật vậy, trong học máy, thuật ngữ cơ sở dữ liệu chủ yếu đề cập tới một tập các mẫu được lưu trong tệp. - Một giải thuật học sử dụng tập dữ liệu và các thông tin kèm theo tập dữ liệu đó làm đầu vào và đầu ra biểu thị kết quả của việc học. - Tuy nhiên, trong thực tế, cơ sở dữ liệu thường động, không đầy đủ và bị nhiễu, lớn hơn nhiều so với các tập dữ liệu học máy điển hình. - Phương pháp hệ chuyên gia khác với khai phá dữ liệu ở chỗ các ví dụ của chuyên gia thường ở mức chất lượng cao hơn nhiều so với các dữ liệu trong CSDL, và chúng thường chỉ bao hàm được các trường quan trọng. - Phương pháp thống kê là một trong những nền tảng lí thuyết của khai phá dữ liệu. - Sự khác nhau cơ bản giữa khai phá dữ liệu và thống kê ở chỗ khai phá dữ liệu là một phương tiện được dùng bởi người sử dụng đầu cuối chứ không phải là các nhà thống kê. - Thông tin thương mại: Phân tích dữ liệu tiếp thị và bán hàng, phân tích vốn đầu tư, chấp thuận cho vay, phát hiện gian lận. - Thêm vào đó, nó tăng thêm cơ hội cho một giải thuật khai phá dữ liệu tìm ra các mẫu không hợp lệ. - Thay đổi dữ liệu và tri thức: Thay đổi nhanh chóng dữ liệu (động) có thể làm cho các mẫu được phát hiện trước đó không còn hợp lệ. - Thêm vào đó, các biến đã đo trong một cơ sở dữ liệu ứng dụng cho trước có thể bị sửa đổi, xoá bỏ hay tăng thêm các phép đo mới. - Dữ liệu thiếu và bị nhiễu: Bài toán này đặc biệt nhạy trong các cơ sở dữ liệu thương mại. - Dữ liệu điều tra dân số U.S cho thấy tỷ lệ lỗi lên tới 20%. - Các thuộc tính quan trọng có thể bị mất nếu cơ sở dữ liệu không được thiết kế với sự khám phá bằng trí tuệ. - Về mặt lịch sử, các giải thuật khai phá dữ liệu được phát triển cho các bản ghi có giá trị thuộc tính đơn giản, mặc dầu các kỹ thuật mới bắt nguồn từ mối quan hệ giữa các biến đang được phát triển. - 1.5 Kết luận Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những hướng nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về CNTT trên thế giới. - Điều này chứng tỏ những ưu thế, lợi ích và khả năng ứng dụng thực tế to lớn của khai phá dữ liệu. - Phần này đã trình bày một số kiến thức tổng quan về khai phá dữ liệu, những kiến thức cơ bản nhất về các phương pháp phân cụm dữ liệu, phân loại dữ liệu và khai phá luật kết hợp. - -18- CHƯƠNG 2: KỸ THUẬT PHÂN LOẠI TRONG KHAI PHÁ DỮ LIỆU Các cơ sở dữ liệu với rất nhiều thông tin ẩn có thể được sử dụng để tạo nên các quyết định kinh doanh thông minh. - Phân loại là một dạng của phân tích dữ liệu, nó dùng để trích ra các mô hình mô tả các lớp dữ liệu quan trọng hay để dự đoán các khuynh hướng dữ liệu tương lai. - Hầu hết các giải thuật dùng với giả thiết kích thước dữ liệu nhỏ. - Các nghiên cứu khai phá cơ sở dữ liệu gần đây đã phát triển, xây dựng mở rộng các kỹ thuật phân loại có khả năng sử dụng dữ liệu thường trú trên đĩa lớn. - Trong chương này, ta sẽ xem xét các kỹ thuật cơ bản để phân loại dữ liệu như cây quyết định quy nạp, phân loại Bayesian, các mạng belief Bayesian, các mạng nơron và phân loại dựa trên sự kết hợp. - 2.1 Phân loại là gì? Phân loại dữ liệu là một xử lý bao gồm hai bước (Hình 2.1). - Ở bước đầu tiên, xây dựng mô hình mô tả một tập cho trước các lớp dữ liệu. - Mô hình này có được bằng cách phân tích các bộ cơ sở dữ liệu. - Các bộ dữ liệu để xây dựng mô hình gọi là tập dữ liệu huấn luyện. - Ví dụ, cho trước một cơ sở dữ liệu thông tin về độ tín nhiệm của khách hàng, các luật phân loại được học để nhận biết các khách hàng -19- có độ tín nhiệm là tốt hay khá tốt (Hình 2.1a). - Các luật được dùng để phân loại các mẫu dữ liệu tương lai cũng như cung cấp cách hiểu tốt hơn về nội dung cơ sở dữ liệu. - Lúc này, việc tìm mẫu hữu ích trong các tập con sẽ trở nên không thích hợp bởi tính không đầy đủ của dữ liệu. - Các cây nhị phân cho kết quả phân mảnh dữ liệu ít nhất. - 2.3.5 Khả năng mở rộng và cây quyết định quy nạp -29- Các giải thuật cây quyết định như ID3 và C4.5 được thiết lập cho các tập dữ liệu tương đối nhỏ. - Hiệu quả và khả năng mở rộng là các vấn đề liên quan với nhau khi các giải thuật này được áp dụng vào việc khai phá các cơ sở dữ liệu rất lớn, thế giới thực. - Lúc đầu, chiến lược cho cây quyết định quy nạp ở các cơ sở dữ liệu lớn có thể là rời rạc hoá các thuộc tính liên tục, giả định tập huấn luyện vừa đủ trong bộ nhớ. - Cả hai giải thuật đề xuất các kỹ thuật tiền sắp xếp trên đĩa - các tập dữ liệu thường trú là quá lớn để vừa trong bộ nhớ. - Cả hai đều định nghĩa ích lợi của các cấu trúc dữ liệu mới giúp cho việc xây dựng cây trở nên thuận lợi. - Các danh sách thuộc tính và các danh sách lớp được sinh ra bởi SLIQ đối với dữ liệu mẫu ở bảng 2.2 được chỉ ra trên hình 2.5. - 2.4.1 Định lý Bayes Cho X là mẫu dữ liệu chưa biết nhãn lớp, H là giả thuyết ví dụ như mẫu dữ liệu X thuộc về lớp C. - Đối với các bài toán phân loại, ta cần xác định P(H|X) là xác suất xảy ra giả thuyết H trên mẫu dữ liệu X. - Ví dụ, giả sử các mẫu dữ liệu trong tập hoa quả được mô tả bởi màu sắc và hình dạng của chúng. - Như ví dụ, đây là xác suất một mẫu dữ liệu bất kì cho trước là quả táo bất kể nó trông như thế nào. - Theo ví dụ trên, nó là xác suất để cho một mẫu dữ liệu từ tập hoa quả là đỏ và tròn. - P(X), P(H), P(X|H) được đánh giá từ dữ liệu cho trước. - Cho trước một mẫu dữ liệu chưa biết nhãn lớp X, classifier sẽ dự đoán X thuộc về lớp có xác suất hậu nghiệm cao nhất, với điều kiện trên X. - Cho trước các tập dữ liệu với nhiều thuộc tính, việc tính P(X|Ci) sẽ rất tốn kém. - Dữ liệu huấn luyện trong bảng 2.1. - Các mẫu dữ liệu được mô tả bởi các thuộc tính tuổi, thu nhập, sinh viên và độ tín nhiệm
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt