Tiếp cận tập thô xây dựng cây quyết định đa trị trong khai phá dữ liệu

- NGUYỄN THỊ MINH TÂM TIẾP CẬN TẬP THÔ XÂY DỰNG CÂY QUYẾT ĐỊNH ĐA TRỊ TRONG KHAI PHÁ DỮ LIỆU LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH.
- Tôi làm luận văn tốt nghiệp cao học với đề tài “Tiếp cận tập thô xây dựng cây quyết định đa trị trong khai phá dữ liệu”, do PGS.
- 6 Chương 1 Tổng quan về phát hiện tri thức trong cơ sở dữ liệu.
- Tiến trình phát hiện tri thức trong cơ sở dữ liệu.
- Các nhiệm vụ chính của khai phá dữ liệu.
- Cây quyết định.
- Sự phụ thuộc của các thuộc tính.
- Rút gọn các thuộc tính.
- Cây quyết định đa trị.
- Các vấn đề trong việc khai phá dữ liệu với cây quyết định .
- 51 3.2.2 Những khó khăn trong việc quản lý dữ liệu đa trị bằng các phương pháp phân lớp truyền thống.
- Các kỹ thuật khai phá dữ liệu (tháng .
- Tập dữ liệu huấn luyện đa trị.
- Dữ liệu được thu thập trong các cơ sở dữ liệu vì thế trở thành dữ liệu "bị chôn vùi.
- Các quyết định thường được thực hiện dựa vào trực giác của người tạo quyết định mà không dựa vào dữ liệu giàu thông tin có sẵn trong cơ sở dữ liệu.
- Tình huống lúc này được mô tả như "Giàu dữ liệu nhưng nghèo thông tin" [11].
- Các công cụ phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) ra đời thực hiện việc phân tích dữ liệu để phát hiện các tri thức có ích như các dạng hay các mô hình.
- Phương pháp dùng cây quyết định là phương pháp khai phá dữ liệu để tìm ra sự phân lớp tri thức trong các tập dữ liệu huấn luyện bằng cách xây dựng cây quyết định.
- Lý thuyết tập thô được Pawlak đề xuất vào đầu những năm 1980 được xem như một cách tiếp cận mới để phát hiện tri thức và nó "tạo thành một cơ sở vững chắc cho các ứng dụng khai phá dữ liệu" [8].
- Lý thuyết tập thô đưa ra các công cụ toán học để phát hiện các dạng ẩn trong dữ liệu: nhận biết một phần hoặc toàn bộ sự phụ thuộc (ví dụ, các quan hệ nguyên nhân-kết quả) trong các cơ sở dữ liệu, loại ra các dữ liệu thừa, đưa ra cách tiếp cận đối với vấn đề dữ liệu không đầy đủ (dữ liệu không có giá trị, thiếu dữ liệu, dữ liệu động.
- Dữ liệu không đầy đủ ở đây có nhiều dạng, trong đó có nhiều trường hợp dữ liệu lưu trữ là không chắc chắn được thể hiện qua các hệ thông tin với các thuộc tính đa trị.
- Cách tiếp cận lý thuyết tập thô của Pawlak không xem xét trường hợp này, do đó làm hạn chế các ứng dụng của nó trong xử lý dữ liệu.
- Chương 1 Tổng quan về phát hiện tri thức trong cơ sở dữ liệu.
- Chương này trình bày các khái niệm cơ bản của lĩnh vực nghiên cứu KDD, quy trình KDD, các nhiệm vụ chủ yếu của khai phá dữ liệu (Data Mining - DM), các phương pháp DM, các ứng dụng của KDD và các thách thức của lĩnh vực nghiên cứu này.
- Từ đó ta thấy được những khó khăn trong việc quản lý dữ liệu đa trị bằng các phương pháp phân lớp truyền thống như cây quyết định đơn trị.
- Chương này giới thiệu về mô hình tập thô có độ chính xác thay đổi và đưa ra giải thuật xây dựng cây quyết định dựa trên tập thô có độ chính xác thay đổi nhằm khai phá dữ liệu.
- 9 Chương 1 Tổng quan về phát hiện tri thức trong cơ sở dữ liệu Knowledge Discovery and Data mining (KDD) là lĩnh vực nghiên cứu đang phát triển mạnh mẽ.
- KDD là sự kết hợp giữa cơ sở dữ liệu (CSDL) với các kỹ thuật thống kê, học máy và các lĩnh vực liên quan để trích rút tri thức và thông tin có giá trị từ số lượng dữ liệu rất lớn.
- KDD được xem là một trong các lĩnh vực nghiên cứu có triển vọng nhất từ những năm 1990 bởi các nhà nghiên cứu về học máy và cơ sở dữ liệu.
- Nói cách khác, tri thức có thể được xem như dữ liệu ở mức cao của sự trừu tượng hoá và tổng quát hoá.
- Khai phá tri thức (Data mining) là quá trình phát hiện tri thức bao gồm các giải thuật khai phá dữ liệu để tìm ra các mẫu hay các mô hình trong dữ liệu dưới khả năng có thể chấp nhận được của máy tính điện tử.
- Nói cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu là để tìm ra các mẫu hay các mô hình quan tâm tồn tại trong CSDL nhưng lại ẩn trong lượng dữ liệu lớn.
- Tiến trình phát hiện tri thức trong cơ sở dữ liệu Tiến trình KDD bao gồm nhiều bước được chỉ ra trong hình 1.1.
- Hình 1.1 - Tiến trình KDD Bước thứ ba là DM để trích rút ra các dạng và các mô hình ẩn trong dữ liệu.
- Một mô hình có thể được xem như "một sự mô tả toàn bộ một cấu trúc để tổng kết các thành phần cơ bản của dữ liệu một cách có hệ thống hay mô tả dữ liệu có thể được xuẩt hiện như thế nào".
- Các kinh nghiệm cho thấy rằng các mô hình hay các dạng được phát hiện từ dữ liệu ngay từ đầu không phải luôn đúng.
- Một cách thức chuẩn để đánh giá các luật được đưa ra là chia dữ liệu thành hai tập, huấn luyện trên tập đầu tiên và kiểm thử trên tập thứ hai.
- Các nhiệm vụ chính của khai phá dữ liệu Trong thực tế, DM có hai mục đích chính là dự báo và mô tả.
- Mục đích thứ nhất đòi hỏi phải sử dụng một số biến hoặc trường trong cơ sở dữ liệu để dự báo các giá trị chưa biết hoặc sẽ có của các biến quan tâm khác.
- Mục đích thứ hai tập trung vào việc tìm các dạng mô tả dữ liệu có thể hiểu được.
- Mối quan hệ của hai mục đích này đối với các ứng dụng khai phá dữ liệu có thể thay đổi một cách đáng kể.
- Mô tả lớp cung cấp một sự tổng kết ngắn gọn và súc tích của một sự thu thập dữ liệu.
- Sự tổng kết của một sự thu thập dữ liệu được gọi là đặc tả lớp.
- ngược lại, sự so sánh giữa hai hoặc nhiều hơn các thu thập dữ liệu được gọi là so sánh hoặc phân biệt lớp.
- Chúng thường được biểu diễn ở dạng luật chỉ ra các điều kiện giá trị-thuộc tính xuất hiện thường xuyên cùng với nhau trong một tập dữ liệu đã cho.
- Một luật kết hợp ở dạng X⇒Y được hiểu như "các bộ dữ liệu mà thoả mãn X thì có khả năng thoả mãn Y".
- Các phân tích kết hợp được sử dụng một cách rộng rãi trong các cơ sở dữ liệu giao dịch đối với xu hướng tiếp thị, các sản phẩm có quan hệ với nhau, thiết kế catalog và các quy trình tạo quyết định thương mại khác.
- Sự phân lớp phân tích một tập dữ liệu huấn luyện (ví dụ, một tập các đối tượng mà nhãn lớp được biết) và xây dựng một mô hình cho mỗi lớp dựa vào các đặc trưng trong dữ liệu.
- Một cây quyết định hoặc một tập các luật phân lớp được tạo bởi một quy trình phân lớp như thế có thể sau đó được dùng cho một sự hiểu biết tốt hơn của mỗi lớp trong cơ sở dữ liệu và cho sự phân lớp của dữ liệu trong tương lai.
- Chức năng khai phá này dự báo các giá trị có thể của một số dữ liệu bị thiếu hoặc sự phân bố giá trị của các thuộc tính nào đó trong một tập đối tượng.
- Nó bao gồm việc tìm tập thuộc tính liên quan với thuộc tính quan tâm (ví dụ, một số phân tích thống kê) và dự báo phân bố giá trị dựa trên tập dữ liệu tương tự với các đối tượng đã chọn.
- Các phân tích phân cụm phân vùng dữ liệu thành các cụm.
- Nghiên cứu DM tập trung vào tính chất lượng và các phương pháp phân cụm scalable (khả năng sử dụng cùng một giải thuật cho một số lượng lớn các đầu vào) đối với cơ sở dữ liệu lớn và nhiều chiều.
- Việc nhận biết các nhiệm vụ DM mới để có được cách sử dụng dữ liệu tốt hơn là vấn đề nghiên cứu thú vị.
- Ý tưởng của tập thô dựa vào các quan hệ tương đương, cho phép phân chia một tập dữ liệu thành các lớp tương đương và bao gồm các tập được định nghĩa như một cặp của các tập, được gọi là các xấp xỉ trên và xấp xỉ dưới.
- Bảng bao gồm các đối tượng (còn gọi là các trường hợp) và các thuộc tính.
- Vì vậy, cây quyết định được nhiều nhà nghiên cứu tập trung trong khai phá dữ liệu.
- Tập dữ liệu được chia thành các tập huấn luyện và các tập kiểm thử.
- Sự kết hợp dữ liệu: tương tự với phân lớp nhưng nó nhận biết dữ liệu chứa lỗi.
- Lọc dữ liệu: làm trơn một tín hiệu đầu vào.
- Các giải thuật học máy mô hình hoá môi trường dựa vào dữ liệu đã cho, sản xuất các luật hiện (explicit) hay các cây quyết định trong quy trình.
- Phân cụm Phân cụm hay nhóm là việc tìm ra các nhóm trong dữ liệu.
- Phân cụm có thứ bậc: mỗi điểm trong dữ liệu được xem như một cụm riêng biệt và được kết hợp một cách liên tiếp dựa vào các quan hệ của nó với các dạng khác.
- Các phương pháp tối ưu hoá dựa trên hàm đối tượng: các phương pháp này sử dụng một chỉ số hiệu năng để giúp cho việc phát triển các phân chia tốt của các điểm dữ liệu.
- 19 Các giải thuật phân cụm thực tế đòi hỏi các kiểm tra dữ liệu một cách cẩn thận để đạt được sự hội tụ.
- Với một cơ sở dữ liệu lớn, các kiểm tra này trở thành chi phí rất đắt đỏ.
- Hình học fractal cung cấp lợi thế duy nhất để nén dữ liệu mà không bị mất mát.
- Các kỹ thuật khai phá dữ liệu hiện nay đang được sử dụng được minh hoạ trong hình 1.2.
- Các kỹ thuật khai phá dữ liệu [16] 1.5.
- Thông tin thương mại : o Phân tích dữ liệu bán hàng và tiếp thị.
- o Các cơ sở dữ liệu chuỗi sinh học.
- Các thách thức của KDD - Các cơ sở dữ liệu lớn.
- Dữ liệu nhiều chiều.
- Không chỉ có các cơ sở dữ liệu có số bản ghi lớn mà còn có các cơ sở dữ liệu có số các trường (các thuộc tính, các biến) rất lớn.
- Một tập dữ liệu nhiều chiều tạo ra các vấn đề dưới dạng tăng kích thước của không gian tìm kiếm cho sự quy nạp mô hình trong một cách thức bùng nổ tổ hợp.
- Thay đổi dữ liệu và tri thức.
- Việc thay đổi dữ liệu với một tốc độ nhanh có thể làm cho các dạng được phát hiện trước đó không còn giá trị.
- Hơn nữa, các biến được đo trong một ứng dụng cơ sở dữ liệu đã cho có thể bị thay đổi.
- Dữ liệu thiếu và nhiễu.
- Vấn đề này đặc biệt nghiêm trọng trong các cơ sở dữ liệu giao dịch.
- Dữ liệu điều tra dân số Mỹ có tỷ lệ lỗi lên tới 20%.
- Các thuộc tính hoặc các giá trị được xây dựng có thứ tự, các quan hệ giữa các thuộc tính, và các ý nghĩa tinh vi hơn đối với việc mô tả tri thức về các nội dung của một cơ sở dữ liệu sẽ đòi hỏi các giải thuật phức tạp.
- Ông nghiên cứu tri thức từ một quan điểm mới và kết hợp tri thức với sự phân lớp, cung cấp công cụ toán học có thể chia sẻ cho sự nhận dạng của con người để đối phó với vấn đề phân lớp dữ liệu không đầy đủ và không chính xác.
- trong đó d∉AT là thuộc tính quyết định.
- Rút gọn các thuộc tính Một vấn đề quan trọng khác trong cách tiếp cận tập thô là rút gọn dữ liệu.
- Ví dụ, dễ dàng thấy rằng nếu trong T1 chúng ta loại bỏ hoặc là thuộc tính Cân nặng hoặc là thuộc tính Kem dưỡng da chúng ta cũng sẽ thu được tập dữ liệu tương đương với tập dữ liệu gốc, đối với các xấp xỉ và các phụ thuộc.
- Am } là tập các thuộc tính.
- Việc rút gọn số lớp tương đương trong một hệ thông tin sẽ làm đơn giản hoá hệ thông tin đó trong tiến trình khai phá dữ liệu.
- Xây dựng mô hình phân lớp bằng cách phân tích tập dữ liệu huấn luyện.
- Dùng mô hình trên để phân loại hay để dự đoán dữ liệu mới.
- Ví dụ như ngân hàng có thể dùng mô hình phân lớp đã được học từ dữ liệu của các khách hàng đang tồn tại để dự đoán độ tín nhiệm của một khách hàng mới.
- Điều kiện cần thiết để khai phá dữ liệu với cây quyết định là.
- Xác định trước các lớp : các phân loại mà các trược hợp được gán vào phải được biết trước (dữ liệu có giám sát.
- Có đủ dữ liệu : thông thường có hàng trăm, thậm chí hàng nghìn các trường hợp huấn luyện.
- Các vấn đề trong việc khai phá dữ liệu với cây quyết định Các vấn đề thực tế trong việc học cây quyết định bao gồm việc xác định độ sâu để phát triển cây quyết định, quản lý các thuộc tính có giá trị liên 46 tục, độ đo để lựa chọn thuộc tính thích hợp, quản lý dữ liệu huấn luyện có các giá trị thuộc tính lỗi và cải tiến hiệu năng tính toán.
- Tránh sự trùng khớp dữ liệu (over-fitting) Trong thực tế, over-fitting là khó khăn đáng kể đối với cây quyết định và nhiều phương pháp học khác.
- Có nhiều phương pháp để tránh trùng khớp dữ liệu trong cây quyết định, chúng được chia thành hai loại.
- Phương pháp dừng phát triển cây sớm hơn, trước khi nó đạt đến điểm mà nó đạt đến sự phân lớp hoàn toàn dữ liệu huấn luyện.
- Phương pháp lược bớt dữ liệu bổ sung cho cây.
- Suy diễn cây quyết định từ tập huấn luyện, phát triển cây cho đến khi tập dữ liệu huấn luyện thích hợp đến mức có thể và cho phép xuất hiện over-fitting

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt