CHƯƠNG I.Tổng quan về khai phá dữ liệu 1. Nhu cầu phát hiện tri thức từ dữ liệu Tốc độ vượt bậc về dung lượng dữ liệu do con người khởi tạo, lưu giữ và truyền dẫn ngày càng tăng cùng với nhu cầu hoạt động về mọi mặt của đời sống xã hội và sự phát triển của công nghệ chế tạo các thiết bị xử lý, lưu trữ và truyền dẫn dữ liệu đã dẫn đến “Hiện tượng bùng nổ thông tin”. Các kết quả của sự phát triển công nghệ phần cứng máy tính đã tạo điều kiện thuận lợi cho sự phát triển công nghệ CSDL (liên quan tới tổ chức và quản lý CSDL) và công nghệ mạng (liên quan tới hoạt động truyền dẫn dữ liệu). Công nghệ CSDL đã và đang phát triển không ngừng nhằm đáp ứng nhu cầu quản lý dữ liệu của con người nói chung và trong hoạt động quản lý nói riêng.
Trong quá trình tiến hóa của công nghệ CSDL, nhiều hệ quản trị cơ sở dữ liệu được phát triển và năng lực của hệ quản trị cũng ngày càng được nâng cao. Một ví dụ về sự tăng trưởng nổi bật về kích thước CSDL quản lý đó chính là sự xuất hiện nhiều CSDL có kích thước hàng trăm TB (1TB = 1000 GB). Ngoài ra sự phát triển về công nghệ mạng cả về quy mô và tốc độ đã tạo ra sự tăng trưởng mạnh về năng lực truyền dẫn thông tin. Thích ứng với hoàn cảnh đó, các phương pháp xử lý dữ liệu và các bộ công cụ tiện ích thi hành các phương pháp này ra đời.
Xây dựng phát triển phương pháp và công cụ xử lý dữ liệu lớn nhằm mục đích phát hiện tri thức tiềm ẩn là nội dung của lĩnh vực phát hiện tri thức trong cơ sở dữ liệu. 1: Tiến hóa của công nghệ cơ sở dữ liệu theo quan điểm của J.Kamber Nguồn: Nguyễn Hà Nam, Nguyễn Trí Thành, Hà Quang Huy (2016) 1. Khai phá dữ liệu Khai phá dữ liệu (Data mining) [1] là quá trình phân loại, sắp xếp và tính toán các tập dữ liệu lớn để xác định các mẫu và thiết lập các mối liên hệ nhằm giải quyết các vấn đề từ việc phân tích dữ liệu từ đó chuyển bộ dữ liệu thành một cấu trúc dễ hiểu để sử dụng tiếp. Quy trình khai phá dữ liệu Nguồn: https://bienuit.com/khaiphadulieu Quá trình khai phá dữ liệu bao gồm: - Bước 1: Xác định vấn đề, lĩnh vực cần nghiên cứu và dữ liệu liên quan để giải quyết vấn đề (Problem understanding and data understanding).
- Bước 2: Chuẩn bị dữ liệu (Data preparation), bao gồm các quá trình làm sạch dữ liệu (Data cleaning), tích hợp dữ liệu (Data integration), chọn dữ liệu (Data selection), biến đổi dữ liệu (Data transformation). - Bước 3: Khai phá dữ liệu (Data mining): xác định nhiệm vụ khai thác dữ liệu và lựa chọn kỹ thuật khai thác dữ liệu. Kết quả của bước này cho ta một nguồn tri thức thô. - Bước 4: Đánh giá (Evaluation): dựa trên một số tiêu chí tiến hành kiểm tra và lọc nguồn tri thức thu được.
- Bước 5: Triển khai (Deployment): dựa vào kết quả của quá trình đánh giá và chọn lọc nguồn tri thức, tiến hành triển khai vào thực thế những ứng dụng, công cụ để thu được lời ích. Các lĩnh vực ứng dụng Khai phá dữ liệu có thể áp dụng cho nhiều lĩnh vực khác nhau. Trong thiên văn học, nó dùng để nhận dạng, đặc tính hóa và phân loại nhanh chóng các sự kiện bầu trời thời gian thực. Đối với tin sinh học, nó dùng để phân tích các hệ thống để tìm ra nguồn hiểu biết tinh sinh học mới.
Đối với thương mại điện tử, khai phá dữ liệu dùng để phân khúc thị trường, phân tích giỏ hàng và dự báo khách hàng. Tỉ lệ người dụng sử dụng internet ngày càng gia tăng, do đó việc phát hiện ra những kẻ lừa đảo qua mạng là một vấn đề cần phải đặt ra, đây cũng chính là một trong những ứng dụng của khai phá dữ liệu. Đối với quảng cáo, khai phá dữ liệu có thể thu thập các thông tin của người dùng từ đó đề xuất ra những quảng cáo phù hợp với sở thích của họ. Ngoài các ứng dụng trên, một số lĩnh vực có thể ứng dụng khai phá dữ liệu như: bào chế thuốc, viễn thông, thể thao giải trí, đầu tư và chăm sóc sức khỏe.
Các phương pháp khai phá dữ liệu 1. Khai phá luật kết hợp 1. Giới thiệu về Luật kết hợp Khai phá luật kết hợp [2] là tìm ra các mẫu có tần suất cao, các mẫu kết hợp, liên quan hoặc các cấu trúc tồn tại giữa các tập hợp đối tượng trong cơ sở dữ liệu các giao dịch, cơ sở dữ liệu quan hệ hoặc các kho chứa thông tin khác. Nói các khác là chúng ta tìm tất cả các tập phổ biến từ trong dữ liệu.
Bài toán của Luật kết hợp được diễn giải như sau. Cho biết = { , ,…, } là tập các giao dịch với là số các giao dịch có trong. Tập = { , , … , } là một tập gồm n tập mục khác nhau xuất hiện trong. Mỗi giao dịch là một tập các mục xuất hiện đồng thời.
Với và là các tập mục. Một luật kết hợp được biểu diễn bời công thức: => (1) Trong đó ⊆ , ⊆ và ∩ = ∅ Một giao dịch thuộc chứa một tập mục nếu là tập con của .Độ hỗ trợ của trong là số giao dịch chứa trong (viết tắt là .Để đo độ mạnh của một luật kết hợp, ta sử dụng hai độ do sau: Độ hỗ trợ và độ tin cậy. Độ hỗ trợ của một luật => là tỉ lệ phần trăm (%) các giao dịch trong mà chứa cả và. Nó giúp xác định mức độ phổ biến của các giao dịch chứa tập mục ( ∪ ) trong tổng số tất cả các giao dịch.
Công thức tính độ hỗ trợ (Support): 6 ∪. ( => ) = = ( ∪ ) (2) Độ tin cậy của luật => là tỉ lệ % các giao dịch trong chứa cả và trên tổng số các giao dịch trong chỉ chứa. Công thức tính độ tin cậy (confidence): ∪. = ( ∪ | ) (3) Những luật kết hợp thỏa mãn điều kiện độ hỗ trợ tối thiểu ( _ ) và độ tin cậy tối thiểu ( _ ) được gọi là các luật mạnh.
Nhìn chung, khai phá luật kết hợp là một quá trình gồm 2 bước sau: - Bước 1: Tìm tất cả các tập mục thường xuyên. Tập mục thường xuyên là tập mục mà độ hỗ trợ của nó lớn hơn hoặc bằng _. - Bước 2: Tạo các luật kết hợp mạnh từ tập mục thường xuyên. Luật kết hợp mạnh là những luật có độ hỗ trợ và độ tin cậy lớn hơn _ và _ tương ứng.
Thuật toán Apriori Apriori [2] là một thuật toán được giới thiệu lần đầu vào năm 1994 bởi R.Srikant, nhằm khai phá tập mục phổ biến nhị phân. Thuật toán này thực hiện lặp lại việc tìm kiếm theo mức, sử dụng thông tin ở mức để duyệt mức + 1. Thuật toán này được tiến hành như sau: - Đầu tiên, các tập mục thường xuyên có độ dài là 1 được xây dựng bằng việc duyệt qua toàn bộ dữ liệu để đếm sự xuất hiện của từng phần tử và giá trị này phải lớn hơn hoặc bằng _. Kết quả của việc đếm này được ký hiệu là L.
- Tiếp theo L được sử dụng để tìm kiếm tập mục thường xuyên L có độ dài là 2. Việc này được thực hiện lặp đi lặp lại đến khi không tìm được tập mục thường xuyên có độ dài là k thỏa mãn điều kiện _. Thuật toán FP-Growth Thuật toán FP-Growth [2] được giới thiệu năm 2000 bời Jiawei Hai Jian Pei và Yiwen Yin nhằm khắc phục hai nhược điểm của Thuật toán Apriori đó là: - Chi phí lớn cho một số lượng lớn các tập ứng cử. - Đòi hỏi lặp lại nhiều lần duyệt CSDL, để kiểm tra tất cả các tập ứng cử.
Thuật toán này được tiến hành như sau: 7 - Duyệt CSDL lần thứ nhất để tính độ hỗ trợ của tất cả 1-itemset và loại bỏ những mục có độ hỗ trợ bé hơn min_sup. Các mục còn lại được sắp xếp theo thứ tự giảm dần độ hỗ trợ (cũng tức là giảm dần theo số lần xuất hiện trong CSDL), sau đó ta nhận được danh sách L đã sắp xếp. - Duyệt CSDL lần hai, với mỗi tác vụ t, loại bỏ các mục không đủ độ hỗ trợ, các mục còn lại theo thứ tự giảm dần độ hỗ trợ được đưa vào cây FP-tree. - Tìm các tập mục phổ biến trên cây FP-tree đã xây dựng mà không duyện lại CSDL nữa.
Ứng dụng Khai phá luật kết hợp Khai phá luật kết hợp có một số ứng dụng như: phân tích luật kết hợp để hỗ trợ kinh doanh, tìm hiểu thói quen mua sắm của khách hàng, khả năng tìm ra những dấu hiệu để tìm vi phạm bản quyền tài liệu, gợi ý và hỗ trợ chuẩn đoán bệnh tật và hỗ trợ ra quyết định trong chứng khoáng. Một số kĩ thuật mới như luật kết hợp hiếm và luật kết hợp âm đã được phát triển nhằm tăng khả năng và mở rộng phạm vị ứng dụng của khai phá luật kết hợp. Phân cụm Phân cụm (Clustering) là [2] việc thực hiện nhóm dữ liệu thành các “cụm” để có thể phát hiện được các mẫu phân bố dữ liệu trong miền ứng dụng. Phân cụm là một phương pháp học máy không giám sát, cố gắng khám phá các nhóm tự nhiên và phân phối thống kê dữ liệu.
Phân cụm phẳng Giải thuật k-means thuộc lớp phân cụm phẳng, đầu vào cho thuật toán k-means là tập dữ liệu D gồm n phần tử dữ liệu, số lượng các cụm đầu ra k. Đầu ra của giải thuật là k cụm dữ liệu. Giải thuật k-means được trình bày như sau: 1. Chọn ngẫu nhiên k phần tử trong tập làm trọng tâm ban đầu cho các cụm.
Phân các phần tử dữ liệu trong vào các cụm dựa vào độ tương đồng của nó với trọng tâm của các cụm. Phần tử dữ liệu sẽ được phân vào cụm có độ tương đồng lớn nhất. Tính lại trọng tâm của các cụm. Nhảy đến bước 2 cho đến khi quá trình hội tụ (không có sự gán lại các phần tử dữ liệu giữa các cụm, hay trọng tâm của các cụm là không đổi).
Phân cụm phân cấp Khác với các giải thuật phân cụm phẳng, các thuật toán phân cụm phân cấp sẽ tạo ra một cây phân cấp các cụm dữ liệu. Các thuật toán phân cụm phân cấp bao gồm: Thuật toán phân cụm gộp, thuật toán phân cấp Birch, thuật toán phân cụm Diana và thuật toán phân cụm Rock.