CHƯƠNG 1 KHAI PHÁ DỮ LIỆU VÀ CẤU TRÚC CÂY DỮ LIỆU Nội dung chương sẽ giới thiệu khái niệm về khai phá dữ liệu, tiến trình khai phá dữ liệu, các kĩ thuật khai phá dữ liệu, các phương pháp khai phá dữ liệu thông dụng, những thách thức gặp phải trong quá trình khai phá dữ liệu và giới thiệu một số công cụ hỗ trợ trong khai phá dữ liệu.1 Khai phá dữ liệu 1.1 Tại sao lại cần khai phá dữliệu Theo [1] khoảng hơn một thập kỷtrởlại đây, lượng thông tin được lưu trữtrên các thiết bị điện tử(đĩa cứng, CD-ROM, băng từ, .) không ngừng tăng lên. Người ta ước đoán rằng lượng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó sốlượng cũng nhưkích cỡcủa các cơsởdữliệu (CSDL) cũng tăng lên một cách nhanh chóng. Khai phá dữ liệu ra đời nhưmột hướng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên. Khá nhiều định nghĩa vềkhai phá dữ liệu, tuy nhiên có thểhiểu đơn giản rằng khai phá dữ liệu nhưlà một công nghệtri thứcgiúp khai thác những thông tin hữu ích từnhững kho dữliệu được tích trữtrong suốt quá trình hoạt động của một công ty, tổchức nào đó.2 Khai phá dữliệu là gì? Thuật ngữkhai phá dữ liệu ám chỉviệc tìm kiếm một tập hợp nhỏcó giá trịtừmột số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ớiKhai phá dữ liệu (Data Mining) nhưKhai phá tri thức (Knowledge Mining), Chắt lọc tri thức (knowledge extraction), Phân tích dữliệu/mẫu (data/patern analysis), Khảo cổ dữ liệu (data archaeoloogy), Nạo vét dữ liệu (datadredging),.1Khai phá dữ liệu là một tập hợp các kỹthuật được sửdụng đểtựđộng khai thác và tìm ra các mối quan hệlẫn nhau của dữ liệu trong một tập hợp dữliệu 6 khổng lồvà phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó.[2] Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD (Knowleadge Discovery in Database) và KDD được xem như7 quá trình khác nhau theo thứtự sau: 1. Làm sạch dữ liệu (data cleaning & preprocessing)s: Loại bỏnhiễu và các dữliệu không cần thiết. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền xửlý (data cleaning & preprocessing). Trích chọn dữ liệu (data selection): trích chọn dữ liệu từnhững kho dữ liệu và sau đó chuyển đổi vềdạng thích hợp cho quá trình khai thác tri thức.
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ý 5. Khai phá dữ liệu (khai phá dữ liệu): Là một trong các 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 (knowledge evaluation): 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 (knowledge presentation): Quá trình này sửdụng các kỹthuật đểbiểu diễn và thểhiện trực quan cho người dùng.
7 Hình 1-1Các bước trong Khai phá dữ liệu& KDD[6] 1.3 Các chức năng chính của khai phá dữ liệu Khai phá dữ liệu được chia nhỏthành một sốhướng chính nhưsau: Mô tảkhái niệm (concept description): thiên vềmô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ởdạng khá đơn giản. Ví dụ: “60 % nam giới vào siêu thịnếu mua bia thì có tới 80% trong sốhọsẽmua thêm thịt bò khô”.
Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính & thịtrường chứng khoán,. Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một sốkỹthuật của machine learningnhưcây quyết định (decision tree), mạng nơron nhân tạo (neural network),.
Người ta còn gọi phân lớplà học có giám sát (học có thầy). Phân cụm (clustering): xếp các đối tượng theo từng cụm (sốlượng cũng nhưtên của cụm chưa được biết trước. Người ta còn gọi phân cụmlà học không giám sát (học không thầy). 8 Khai phá chuỗi (sequential/temporal patterns): tương tựnhưkhai phá luật kết hợp nhưng có thêm tính thứtựvà tính thời gian.
Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thịtrường chứng khoán vì nócó tính dựbáo cao.4 Các công cụ khai phá dữ liệu Khai phá dữ liệu không phải là tất cả về các công cụ hay phần mềm cơ sở dữ liệu đang sử dụng. Có thể thực hiện khai phá dữ liệu bằng các hệ thống cơ sở dữ liệu bình thường và các công cụ đơn giản, bao gồm việc tạo và viết phần mềm riêng hoặc sử dụng các gói phần mềm thương mại. Khai phá dữ liệu phức tạp được hưởng lợi từ kinh nghiệm trong quá khứ và các thuật toán đã định nghĩa với phần mềm và các gói phần mềm hiện có, với các công cụ nhất định để thu được một mối quan hệ hoặc uy tín lớn hơn bằng các kỹ thuật khác nhau. [3] Gần đây các tập hợp dữ liệu rất lớn và việc xử lý dữ liệu theo cụm và quy mô lớn có thể cho phép khai phá dữ liệu để sắp xếp và lập báo cáo về các nhóm và các mối tương quan của dữ liệu phức tạp hơn.
Bây giờ đã có sẵn rất nhiều công cụ và hệ thống hoàn toàn mới, gồm các hệ thống lưu trữ và xử lý dữ liệu kết hợp.5 Các kỹ thuật khai phá dữ liệu Một số kỹ thuật cốt lõi, được sử dụng trong khai phá dữ liệu, mô tả kiểu hoạt động khai phá và hoạt động phục hồi dữ liệu [6].1Khai phá luật kết hợp Khai phá luật kết hợp (mối quan hệ) là kỹ thuật khai phá dữ liệu được biết đến nhiều hơn vì tính quen thuộc và đơn giản. Ở đây, thực hiện một sự tương quan đơn giản giữa hai hoặc nhiều mục, thường cùng kiểu để nhận biết các mẫu.Việc xây dựng các công cụ khai phá dữ liệu dựa trên sự kết hợp hay mối quan hệ có thể thực hiện đơn giản bằng các công cụ khác nhau. Ví dụ 1-1: Hình 1-2 cho thấy của cơ sở dữ liệu ví dụ mẫu [9] 9 Hình 1-2 Luồng thông tin được sử dụng theo cách kết hợp[1] 1.2Phân lớp Kỹ thuật phân lớpdùng để xây dựng một ý tưởng về kiểu khách hàng, kiểu mặt hàng hoặc kiểu đối tượng bằng cách mô tả nhiều thuộc tính để nhận biết một lớp cụ thể. Ví dụ, bạn có thể dễ dàng phân loại các xe ô tô thành các kiểu xe khác nhau (xe mui kín, 4x4, xe có thể bỏ mui) bằng cách xác định các thuộc tính khác nhau (số chỗ ngồi, hình dạng xe, các bánh xe điều khiển).
Với một chiếc xe mới, bạn có thể đặt nó vào một lớp cụ thể bằng cách so sánh các thuộc tính với định nghĩa đã biết của chúng tôi. Bạn có thể áp dụng các nguyên tắc tương tự ấy cho các khách hàng, ví dụ bằng cách phân loại khách hàng theo độ tuổi và nhóm xã hội. Hơn nữa, bạn có thể sử dụng việc phân loại như một nguồn cấp, hoặc như là kết quả của các kỹ thuật khác. Ví dụ, bạn có thể sử dụng các cây quyết định để xác định một cách phân loại.
Việc phân cụm sẽ cho phép bạn sử dụng các thuộc tính chung theo các cách phân loại khác nhau để nhận biết các cụm.3Phân cụm Bằng cách xem xét một hay nhiều thuộc tính hoặc các lớp, có thể nhóm các phần dữ liệu riêng lẻ với nhau để tạo thành một quan điểm cấu trúc. Ở mức đơn giản, việc phân cụm đang sử dụng một hoặc nhiều thuộc tính làm cơ sở cho bạn để nhận ra một nhóm các kết quả tương quan. Việc phân cụm giúp để nhận biết các thông tin khác nhau vì nó tương quan với các ví dụ khác, nên có thể thấy ở đâu có những điểm tương đồng và các phạm vi phù hợp. Việc phân cụm có thể làm theo hai cách.
Có thể giả sử rằng có một cụm ở một điểm nhất định và sau đó sử dụng các tiêu chí nhận dạng để xem liệu có đúng không. Đồ thị trong Hình 1-3 là một ví dụ. Một ví dụ mẫu về dữ liệu kinh doanh so sánh tuổi của khách hàng với quy mô bán hàng. Hợp lý khi thấy rằng những người ở độ tuổi hai mươi (trước khi kết hôn và còn nhỏ), ở độ tuổi năm mươi và sáu mươi (khi không còn con cái ở nhà), có nhiều tiền tiêu hơn.
Hình 1-3Phân cụm [6] Trong ví dụ này, chúng ta có thể nhận ra hai cụm, một cụm xung quanh nhóm 2.000 Đô la Mỹ/ 20-30 tuổi và một cụm ở nhóm 7.000 Đô la Mỹ/ 50-65 tuổi. Trong trường hợp này, giả thuyết hai cụm và đã chứng minh giả thuyết bằng một đồ 11 thị đơn giản mà ta có thể tạo ra bằng cách sử dụng bất kỳ phần mềm đồ họa thích hợp nào để có được cái nhìn nhanh chóng. Các quyết định phức tạp hơn cần phải có một gói phần mềm phân tích đầy đủ, đặc biệt là nếu muốn các quyết định tự động dựa vào thông tin lân cận gần nhất. Việc vẽ đồ thị phân cụm theo cách này là một ví dụ đơn giản về cái gọi là nhận ra sự lân cận gần nhất.
Có thể nhận ra các khách hàng riêng lẻ bằng sự gần gũi theo nghĩa đen của họ với nhau trên đồ thị. Có nhiều khả năng là các khách hàng trong cùng một cụm cũng dùng chung các thuộc tính khác và bạn có thể sử dụng sự mong đợi đó để giúp hướng dẫn, phân loại và nếu không thì phân tích những người khác trong tập hợp dữ liệu của bạn. Cũng có thể áp dụng việc phân cụm theo quan điểm ngược lại; dựa vào một số thuộc tính đầu vào, có thể nhận ra các tạo phẩm khác nhau. Ví dụ, một nghiên cứu gần đây về các số PIN 4-chữ số đã tìm ra các cụm giữa các chữ số trong phạm vi 1- 12 và 1-31 cho các cặp đầu tiên và thứ hai.
Bằng cách vẽ các cặp này, bạn có thể nhận ra và xác định các cụm liên quan đến ngày tháng (các ngày sinh nhật, các ngày kỷ niệm).4Dự báo Dự báo là một chủ đề rộng và đi từ dự báo về lỗi của các thành phần hay máy móc đến việc nhận ra sự gian lận và thậm chí là cả dự báo về lợi nhuận của công ty nữa. Được sử dụng kết hợp với các kỹ thuật khai phá dữ liệu khác, dự báo gồm có việc phân tích các xu hướng, phân loại, so khớp mẫu và mối quan hệ. Bằng cách phân tích các sự kiện hoặc các cá thể trong quá khứ, bạn có thể đưa ra một dự báo về một sự kiện.