Chương 1. Giới thiệu về Khai phá dữ liệu 1. Tổng quan về Khai phá dữ liệu Khai phá dữ liệu là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Một số phương pháp Khai phá dữ liệu tiêu biểu: Phân lớp (Classification): Khai thác một hàm đã được huấn luyện trước để phân loại một đối tượng dữ liệu vào một trong các lớp được định nghĩa trước.
Hồi qui (Regression): Khai thác một hàm đã được huấn luyện trước để ánh xạ một đối tượng dữ liệu thành một giá trị thực là kết quả dự báo. Phân cụm (Clustering): Giải quyết vấn đề tìm kiếm, phát hiện số lượng hữu hạn các cụm mô tả một tập hợp dữ liệu ban đầu không có nhãn. Đó là quá trình tìm cách nhóm các đối tượng đã cho vào các cụm, sao cho các đối tượng trong cùng một cụm tương tự (similar) nhau, và các đối tượng khác cụm thì không tương tự (dissimilar) nhau. Tổng hợp (Summarization): Quá trình bao gồm các phương pháp để tìm một mô tả súc tích cho một tập (hoặc một tập con) dữ liệu.
Mô hình hóa ràng buộc (Dependency Modeling): Tìm một mô hình cục bộ mô tả các ràng buộc quan trọng giữa các biến hoặc giữa các giá trị của một đặc trưng trong một tập dữ liệu hoặc trong một phần của tập dữ liệu Phát hiện biến đổi và độ lệch (Change and Deviation Detection): Khai phá những biến đổi quan trọng nhất trong tập dữ liệu. Khai phá dữ liệu có nhiều ứng dụng quan trọng trong thực tế, lĩnh vực cũng rất phong phú: Trong lĩnh vực Bảo hiểm, Tài chính, và Thị trường chứng khoán: phân tích tình hình tài chính của một công ty dựa trên báo cáo tài chính. Hay dự đoán giá cổ phiếu dựa vào phân tích dữ liệu về Thị trường chứng khoán,… Trong Thống kê, Phân tích dữ liệu và Hỗ trợ ra quyết định. Trong Y học: chẩn đoán bệnh và gợi ý phác đồ điều trị dựa vào mối liên hệ giữa các triệu chứng của bệnh nhân.
Quảng cáo, Thương mại điện tử, Phát triển ứng dụng hướng người dùng: phân tích thói quen sử dụng/mua bán sản phẩm của người dùng để đưa ra các gợi ý mua sắm hoặc cách sắp xếp, cách đầu tư các sản phẩm tối ưu. Dự đoán hành vi người dùng nhằm nâng cao chất lượng dịch vụ. … TIEU LUAN MOI download : skknchat@gmail.com 3 Các phần tiếp theo tôi sẽ trình bày một số kỹ thuật Khai phá dữ liệu tôi đã tìm hiểu để phục vụ cho đề tài nghiên cứu của mình. Thuật toán k láng giềng gần nhất (kNN) 1.
Phương pháp Láng giềng gần nhất (Nearest Neighbor) Phương pháp Láng giềng gần nhất [5, 8] được đề xuất bởi Fix và Hodges năm 1951, là một trong những kỹ thuật cơ bản, đơn giản và trực giác nhất trong lĩnh vực Phân tích thống kê. Nó được xây dựng từ nhu cầu thực hiện phân tích biệt số khi không biết hoặc khó xác định các tham số tin cậy ước lượng các hàm mật độ xác suất. Trong phương pháp này, một quan sát (observation) mới x sẽ được gán nhãn lớp của đối tượng quan sát trong tập tham chiếu có nét tương đồng nhất với x. Độ tương tự giữa các đối tượng dữ liệu được quyết định dựa vào một hàm đo khoảng cách.
Đặt: L = {(yi, xi), i = 1,…, nL } là tập tham chiếu gồm các dữ liệu được quan sát, trong đó yi {1,…, c} biểu diễn nhãn lớp và xi = (xi1,…, xip) là vectơ biểu diễn một đối tượng dữ liệu trong không gian đặc trưng. Việc xác định các láng giềng gần nhất dựa trên một hàm khoảng cách d(. Theo đó, với một quan sát mới (y, x) thì láng giềng gần nhất của nó (y(1), x(1)) trong tập tham chiếu được xác định bởi: d(x, x(1)) = ( ( )) (1.1) và nhãn lớp ̂ = y(1) của láng giềng gần nhất được lựa chọn để gán cho y. Ở đây các ký hiệu x(j) và y(j) biểu diễn láng giềng gần nhất thứ j của x và nhãn lớp tương ứng của nó.
Hàm khoảng cách d(.) thường là hàm khoảng cách Euclidean: ( ) .2) hoặc hàm khoảng cách tuyệt đối: ( ) ∑ | | (1.3) Phương pháp Láng giềng gần nhất được giải thích dựa vào sự phân bố ngẫu nhiên của tập tham chiếu, được mô tả bởi Fahrmeir và các cộng sự vào năm 1996 [5]. Nhãn lớp y(1) của láng giềng gần nhất x(1) của đối tượng quan sát mới x là một biến ngẫu nhiên. Xác suất để x được phân vào lớp y(1) là P(y(1)|x(1)). Với tập tham chiếu có kích thước lớn, có thể coi x và x(1) gần như trùng khớp với nhau, dẫn đến P(y(1)|x(1)) ≈ P(y|x).
Do đó x được phán đoán thuộc về lớp đúng y với xác suất xấp xỉ P(y|x). TIEU LUAN MOI download : skknchat@gmail. Thuật toán kNN Thuật toán k láng giếng gần nhất [5, 6, 8] là một mở rộng đầu tiên của phương pháp trên, và thường được sử dụng rộng rãi trong thực tế. Ở đây không chỉ tham chiếu đến một mà xét đến k láng giềng gần nhất trong tập tham chiếu của đối tượng cần phán đoán x.
Điều này giúp tránh trường hợp một đối tượng quan sát kỳ dị (nhiễu) trong tập tham chiếu quyết định nhãn lớp. Tham số k do người dùng lựa chọn. Nhãn lớp được gán cho x là lớp chiếm đại đa số trong tập k láng giềng vừa xác định. Đặt kr là số quan sát thuộc về lớp r nằm trong tập k láng giềng gần nhất của x.4) Khi đó x sẽ được gán nhãn lớp l thỏa mãn: ( ) (1.5) Mức độ cục bộ của phương pháp này phụ thuộc vào tham số k.
Với k = 1, ứng với phương pháp Láng giềng gần nhất cơ bản, cho mức độ cục bộ tối đa. Với k = nL, kéo theo một kết quả phán đoán duy nhất cho mọi đối tượng quan sát mới, nhãn lớp xuất hiện nhiều nhất trong tập tham chiếu sẽ luôn được chọn. Bộ phân lớp dựa trên thuật toán k láng giếng gần nhất là một bộ học lười (lazy learner), không cần thực hiện quá trình học cho mô hình. Nó cần sử dụng tất cả các đối tượng dữ liệu trong tập tham chiếu để ra quyết định gán nhãn lớp cho một quan sát mới.
Một ví dụ về thuật toán kNN: Hình 1.1: Ví dụ về thuật toán kNN TIEU LUAN MOI download : skknchat@gmail.com 5 Với k = 5, trong 5 láng giếng gần nhất của đối tượng cần phân lớp x có 3 đối tượng quan sát thuộc lớp âm (-), và 2 đối tượng quan sát thuộc lớp dương (+). Như vậy x sẽ được gán nhãn là lớp âm. Thuật toán Weighted k-Nearest-Neighbors (WkNN) Thuật toán WkNN [5] cải tiến thuật toán kNN theo ý tưởng: các láng giềng ở gần đối tượng quan sát mới x phải có vai trò quan trọng hơn so với các láng giềng ở xa trong việc quyết định nhãn lớp của x. Trong thuật toán kNN thì cả k láng giềng gần nhất của x đều có vai trò ảnh hưởng như nhau, dù độ tương tự giữa từng thành viên trong chúng so với x có thể khác xa nhau.
Để phản ánh độ quan trọng khác nhau của các láng giềng gần nhất của x, các giá trị khoảng cách từ chúng đến x cần được biến đổi thành các trọng số. Theo đó, mỗi láng giềng của x sẽ được gán cho một giá trị trọng số, giá trị này sẽ được dùng trực tiếp để quyết định nhãn lớp cho x. Chiến lược đánh trọng số cho các láng giềng Việc biến đổi từ giá trị khoảng cách sang giá trị trọng số được thực hiện thông qua một hàm trọng số f(.) là hàm của biến khoảng cách d, nhận đầu vào là giá trị khoảng cách d, đầu ra là giá trị trọng số w = f(d). f(d) đạt giá trị cực đại khi d = 0.
f(d) là hàm giảm nghiêm ngặt với d → ±∞. Tức f(d1) ≤ f(d2) Một số hàm trọng số tiêu biểu được mô tả trong bảng 1.1 dưới đây: TIEU LUAN MOI download : skknchat@gmail.1: Các hàm trọng số tiêu biểu Tên hàm Công thức tương ứng Biweight ( ) ( ) (| | ) Cosine ( ). / (| | ) Epanechnikov ( ) ( ) (| | ) Gauss ( ) ( ) √ Inversion ( ) | | Rectangular ( ) Triangular ( ) | | (| | ) Triweight ( ) ( ) (| | ) Trong ngữ cảnh sử dụng các giá trị khoảng cách làm tham số đầu vào, đương nhiên chỉ miền xác định dương của hàm f(.) được sử dụng. Việc lựa chọn dùng hàm trọng số nào là tham số đầu vào thứ ba của thuật toán này.
Ta thấy hầu hết các hàm trọng số trong bảng 1.1 đều có tập xác định là [0, 1]. Và để tránh trường hợp giá trị trọng số của một láng giềng nào đó bằng 0 (khi d = 1), tức láng giềng đó hoàn toàn không có vai trò gì trong việc quyết định nhãn lớp của đối tượng quan sát x, thì giá trị của d cần được chuẩn hóa để xác định trong khoảng [0, 1). WkNN thực hiện điều này bằng cách sử dụng giá trị khoảng cách của láng giềng gần nhất thứ (k+1) khi chuẩn hóa các khoảng cách của k láng giềng đã chọn. Ta dùng công thức sau để chuẩn hóa khoảng cách của k láng giềng gần nhất: ( ( )) ( ( )) (1.6) ( ( )) trong đó: ( ( ) ) là khoảng cách từ láng giềng thứ i đến x.
TIEU LUAN MOI download : skknchat@gmail.com 7 ( ( ) ) là khoảng cách từ láng giềng thứ k+1 đến x. > 0 là một hằng số có giá trị rất nhỏ được dùng để đảm bảo ( ( )). Nếu không dùng thì trong trường hợp một trong số k láng giềng gần nhất của x có khoảng cách đến x bằng với láng giềng gần nhất thứ (k+1) thì khoảng cách sau khi chuẩn hóa của nó sẽ bằng 1. Dẫn đến trọng số của nó sẽ bằng 0 nếu dùng với một số hàm trọng số trong bảng 1.
Với cách chuẩn hóa như trên thì ta sẽ đảm bảo ( ( ) ) , ). Và như vậy ta có thể sử dụng được bất kỳ hàm trọng số nào trong bảng 1. Lược đồ hoạt động Sau khi xác định các độ đo tương tự cho các quan sát trong tập tham chiếu, mỗi đối tượng quan sát mới x sẽ được phân vào lớp r có tổng các trọng số lớn nhất: (∑ ( .7) Trong đó: ( ) { Có thể coi hai thuật toán kNN và NN là các trường hợp đặc biệt của thuật toán WkNN. Ta có kết quả của kNN nếu chọn sử dụng hàm trọng số Rectangular.