Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Nghiên cứu ứng dụng kỹ thuật boostmetric nhằm tăng hiệu quả phân lớp dữ liệu lớn...

Tài liệu Nghiên cứu ứng dụng kỹ thuật boostmetric nhằm tăng hiệu quả phân lớp dữ liệu lớn

.PDF
58
189
128

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌCGIA CÔNG NGHỆ ĐẠI HỌC QUỐC HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THANH TỊNH NGUYỄN THANH TỊNH NGHIÊN NGHIÊN CỨU CỨU ỨNG ỨNG DỤNG DỤNG KỸ KỸ THUẬT THUẬT BOOSTMETRIC BOOSTMETRIC NHẰM NHẰM TĂNG TĂNG HIỆU HIỆU QUẢ QUẢ PHÂN PHÂN LỚP LỚP DỮ DỮ LIỆU LIỆU LỚN LỚN Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin LUẬN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN Mã VĂN Số: 60480104 LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN HÀ NAM HÀ NỘI - 2014 HÀ NỘI - 2014 Lời cam đoan Tôi xin cam đoan luận văn “Nghiên cứu ứng dụng kỹ thuật BoostMetric nhằm tăng hiệu quả phân lớp dữ liệu lớn” là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả được trình bày trong luận văn là hoàn toàn trung thực. Tôi đã trích dẫn đầy đủ các tài liệu tham khảo, công trình nghiên cứu liên quan. Ngoại trừ các tài liệu tham khảo này, luận văn hoàn toàn là công việc của riêng tôi. Luận văn được hoàn thành trong thời gian tôi là học viên tại Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội. Hà Nội, ngày 30 tháng 10 năm 2014 Học viên Nguyễn Thanh Tịnh Lời cảm ơn Lời đầu tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới PGS.TS. Nguyễn Hà Nam đã tận tình hướng dẫn tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Tôi chân thành cảm ơn các thầy, cô đã tạo cho tôi những điều kiện thuận lợi để tôi học tập và nghiên cứu tại trường Đại học Công Nghệ. Tôi xin gửi lời cảm ơn tới các bạn trong lớp cao học K18 đã ủng hộ, khuy ến khích tôi trong suốt quá trình học tập tại trường. Tôi cũng thầm biết ơn tới công lao to lớn của gia đình - những người luôn luôn động viên và nuôi dưỡng tôi trong cuộc đời. Cám ơn những người bạn đồng nghiệp của tôi, luôn bên cạnh tôi để chia sẻ những kinh nghiệm trong học tập cũng như trong cuộc sống. Tôi xin chân thành cảm ơn! Hà Nội, ngày 30 tháng 10 năm 2014 Học viên Nguyễn Thanh Tịnh Mục lục Danh mục hình vẽ Danh mục bảng biểu Danh mục viết tắt STT Thuật ngữ Từ viết tắt 1 k-Nearest Neighbors kNN 2 Weighted k-Nearest Neighbors WkNN 3 Support Vector Machine SVM 4 Số thứ tự STT 8 9 Mở đầu Ngày nay, cuộc cách mạng về khoa học và công nghệ đã có những bước phát triển vượt bậc, đánh dấu những mốc son đáng tự hào trong nền văn minh của thế giới đương đại. Cùng với sự phát triển này, một lượng dữ liệu ngày càng lớn và vô cùng phong phú đã được tạo ra. Lượng dữ liệu rất lớn, nhưng thông tin chứa trong nó thì rất ít, nên đòi hỏi phải có các kỹ thuật mới để khai thác thông tin, khai phá dữ liệu ra đời nhằm đáp ứng các yêu cầu đó. Phân lớp dữ liệu là một trong các hướng nghiên cứu của khai phá dữ liệu. Phân lớp dữ liệu là kỹ thuật dựa trên tập huấn luyện và những giá trị hay là nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới. Thuật toán k láng giềng gần nhất (kNN) 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ê. Bộ phân lớp dựa trên thuật toán kNN 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ặc dù rất đơn giản, nhưng thuật toán kNN đã cho kết quả tốt trong nhiều ứng dụng thực tế. BoostMetric là phương pháp đo khoảng cách giữa các điểm dữ liệu dựa vào việc huấn luyện ma trận tham số X của hàm khoảng cách Mahalanobis. Trong luận văn này, chúng tôi đề xuất mô hình kết hợp sử dụng BoostMetric và Weighted kNN, một cải tiến của thuật toán kNN, nhằm làm tăng hiệu quả phân lớp dữ liệu. Nội dung của luận văn được chia thành các chương như sau: Chương 1: Luận văn giới thiệu khái quát về Khai phá dữ liệu và một số kỹ thuật Học máy cơ bản, bao gồm hai thuật toán BoostMetric và WkNN. Chương 2: Luận văn đề xuất mô hình kết hợp hai thuật toán BoostMetric và WkNN để làm tăng hiệu quả phân lớp dữ liệu. Chương 3: Thực nghiệm, kết quả, và đánh giá. Tiến hành thực nghiệm theo mô hình đã đề xuất trong chương 2. Phần kết luận: Tóm lược kết quả đạt được của luận văn. 10 Chương 1. Giới thiệu về Khai phá dữ liệu 1.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ụ.  … 11 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. 1.2. Thuật toán k láng giềng gần nhất (kNN) 1.2.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: (1.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). 1.2.2. 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 12 đế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. Ta có: (1.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: ? k=5 Hình 1.1: Ví dụ về thuật toán kNN 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. 13 1.3. 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. 1.3.1. 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(.). Hàm 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). Hàm f(d) phải thỏa mãn các tính chất sau: • f(d) ≥ 0 . • 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: Bảng 1.1: Các hàm trọng số tiêu biểu Tên hàm Công thức tương ứng 14 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. 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.1 ở trên. 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.1. 15 1.3.2. 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: (1.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. Và có kết quả của NN nếu chọn k = 1, với mọi lựa chọn của hàm trọng số. Mục đích chính của phương pháp này là xây dựng được một kỹ thuật trong đó đạt tới một cấp độ tương đối độc lập với việc lựa chọn giá trị tham số k, với kNN thì việc chọn sai giá trị của k sẽ dẫn đến tỉ lệ phân lớp sai lớn. Số lượng các láng giềng gần nhất hoàn toàn được ẩn đi với việc sử dụng các trọng số: nếu k có giá trị quá lớn, nó sẽ tự động được điều chỉnh xuống một giá trị thấp hơn. Trong trường hợp này, một số nhỏ các láng giềng có trọng số lớn sẽ lấn át các láng giềng khác. Thuật toán WkNN được mô tả tổng quan ở dưới đây: Bước 1: Đặt L = {(yi, xi), i = 1,…, nL } là tập tham chiếu chứa các đối tượng quan sát xi với nhãn lớp tương ứng yi. Giả sử ta cần phán đoán nhãn lớp y của một đối tượng quan sát mới x. Bước 2: Tìm k+1 láng giềng gần nhất của x dựa vào một hàm khoảng cách d(x, xi). Ở đây dùng hàm khoảng cách Minkowski: (1.8) Bước 3: Sử dụng công thức (1.6) để chuẩn hóa khoảng cách từ x đến k láng giềng gần nhất của nó. Bước 4: Sử dụng một trong số các hàm trọng số để biến đổi các khoảng cách chuẩn thành các giá trị trọng số: (1.9) Bước 5: Chọn lớp có tổng các trọng số lớn nhất để gán nhãn cho x: (1.10) Nhìn chung có thể coi các phương pháp WkNN và kNN là các phương pháp bầu cử nhóm: một số bộ phân lớp tiềm năng (các láng giềng gần nhất) được kết hợp lại và thực hiện một cuộc bầu cử đa số thắng, và kết quả này được dùng để thực hiện phán đoán. Hình 1.2 dưới đây minh họa một ví dụ về thuật toán WkNN với k = 5: 16 0.33 0.34 0.73 ? 0.35 0.71 k=5 Hình 1.2: Ví dụ về thuật toán WkNN Trong hình 1.2 trên ta thấy các láng giềng gần nhất của đối tượng quan sát cần phán đoán lớp x thuộc về hai lớp: lớp dương (+), và lớp âm (-). Giả sử sau khi tính toán khoảng cách ta tìm được 5 láng giềng gần nhất của x như trên, trong đó có 3 đối tượng thuộc về lớp âm và 2 đối tượng thuộc về lớp dương. Giả sử các trọng số của từng láng giềng có giá trị tính được như trên hình vẽ. Ta có: Tổng trọng số của lớp dương là: 0.73 + 0.71 = 1.44 Tổng trọng số của lớp âm là: 0.33 + 0.34 + 0.35 = 1.02 Như vậy x sẽ được phán đoán thuộc về lớp dương vì lớp này có tổng trọng số lớn nhất. Qua ví dụ này ta thấy có sự khác biệt rõ ràng trong kết quả phán đoán của WkNN và kNN. Nếu sử dụng bộ phân lớp kNN thì x sẽ được phán đoán thuộc về lớp âm vì đây là lớp chiếm đại đa số trong 5 láng giềng gần nhất của x. Từ mô hình hoạt động của bộ phân lớp WkNN ta nhận thấy bộ phân lớp này có một vấn đề, đó là nó sử dụng một hàm khoảng cách duy nhất (cách tính luôn cố định trước) cho mọi tập dữ liệu đầu vào – hàm khoảng cách Minkowski. Hàm khoảng cách này có thể cho kết quả tốt (lựa chọn chính xác các láng giềng gần nhất) với một số bộ dữ liệu nhất định nhưng không đảm bảo cho được kết quả tương tự với rất nhiều bộ dữ liệu khác. Và quan trọng hơn, với việc dùng hàm khoảng cách Minkowski, bộ phân lớp WkNN vẫn chưa vượt qua được vấn đề không gian phi tuyến, nơi các đối tượng dữ liệu phân bố tương đối tự do và mức độ phân tán theo các chiều là khác xa nhau. 17 Mục tiêu luận văn của tôi là tìm một phương pháp đo khoảng cách khác có khả năng thích ứng với mọi bộ dữ liệu đầu vào, và hoạt động tốt trên không gian phi tuyến. Ở đây, khả năng thích ứng với mọi bộ dữ liệu đầu vào có nghĩa là kỹ thuật đó cho phép huấn luyện hàm đo khoảng cách dựa vào tập huấn luyện. Phương pháp BoostMetric được trình bày ở mục 1.7 đáp ứng đầy đủ các tiêu chí trên. 1.4. Phương pháp Kernel kNN 1.4.1. Tổng quan Thuật toán kNN đã cho kết quả tốt trong nhiều bài toán thực tế. Tuy nhiên, với các bài toán phi tuyến phức tạp, nơi dữ liệu phân bố tương đối tùy ý, nó thường cho kết quả khá tồi. Từ thực trạng đó, năm 2002, nhóm tác giả Kai Yu, Liang Ji, và Xuegong Zhang, tiếp cận theo hướng sử dụng hàm nhân (Kernel) để cải tiến độ chính xác của thuật toán kNN trên không gian phi tuyến [7]. Về bản chất, Kernel kNN dùng một hàm phi tuyến ánh xạ các mẫu dữ liệu trong không gian ban đầu sang một không gian đặc trưng mới, rồi thực hiện thuật toán kNN trên không gian đặc trưng mới đó. Điểm mấu chốt của phương pháp này là dựa vào việc sử dụng một hàm nhân để tính phép nhân trong (inner product) của các vectơ là ảnh của các mẫu dữ liệu ban đầu qua phép ánh xạ. Nếu chọn được một hàm nhân phù hợp thì hiệu quả của thuật toán kNN có thể được cải thiện đáng kể. Ta xét trường hợp ánh xạ một không gian n-chiều sang một không gian đặc trưng m-chiều như sau: trong đó là không gian n-chiều ban đầu và là không gian đặc trưng mới có mchiều. là một vectơ tùy ý trong , là vectơ tương ứng trong . là một ánh xạ phi tuyến tùy ý từ không gian ban đầu sang không gian , và (i = 1…m) là các hàm ánh xạ đặc trưng. Ta định nghĩa một hàm nhân K sao cho với mọi ta có: (1.11) trong đó biểu diễn phép nhân trong của và , là một hàm của x và y. Việc định nghĩa một hàm nhân như công thức (1.11) ở trên dẫn đến phép nhân trong trong không gian đặc trưng mới có thể được tính mà không cần thực sự thực hiện phép ánh xạ . Ba hàm nhân được mô tả trong bảng 1.2 dưới đây thường được sử dụng rộng rãi: Bảng 1.2: Một số hàm nhân hay được dùng Tên hàm Công thức tương ứng 18 Polynomial Radial Basis Sigmoid Trong đó là các tham số có thể điều chỉnh được. 1.4.2. Nguyên lý hoạt động Trong thuật toán kNN truyền thống, một hàm đo khoảng cách chuẩn như khoảng cách Euclidean thường được sử dụng. Bằng cách định nghĩa lại hàm đo, ta có thể sử dụng phương pháp hàm nhân để áp dụng vào thuật toán kNN. Phương pháp sử dụng hàm nhân dựa trên một thực tế là ta cần phải tính phép nhân trong giữa các vectơ là ảnh của các mẫu dữ liệu ban đầu qua phép ánh xạ. Do phép nhân trong chỉ tính được trong không gian Hilbert, nên ta chỉ quan tâm đến các hàm đo khoảng cách chuẩn trong không gian Hilbert. Khoảng cách chuẩn giữa 2 vectơ x và y là: (1.12) Để sử dụng thuật toán kNN trong không gian đặc trưng mới, ta cần tính khoảng cách chuẩn trong không gian đó. Sử dụng (1.11) và (1.12) ta có: (1.13) Như vậy khoảng cách chuẩn trong không gian đặc trưng mới có thể được tính bằng cách sử dụng một hàm nhân và các vectơ dữ liệu trong không gian mẫu ban đầu mà không cần xác định và thực hiện phép ánh xạ . Sau khi xác định được hàm đo khoảng cách ở công thức (1.13), ta có thể dễ dàng thực hiện thuật toán kNN trên không gian đặc trưng mới. 1.5. Khoảng cách Mahalanobis Khoảng cách Mahalanobis [9] giữa một đối tượng quan sát thuộc một nhóm các quan sát với trung bình của nhóm đó là: (1.14) trong đó S là ma trận hiệp phương sai của nhóm. Nếu ma trận hiệp phương sai S là ma trận đơn vị, khoảng cách Mahalanobis trở thành khoảng cách Euclidean. Dùng khoảng cách Mahalanobis ta có thể biết được một 19 điểm ở cách trung bình của nhóm bao nhiêu độ lệch chuẩn. Khoảng cách xa gần không đơn giản như những gì mắt ta nhìn thấy. Ta xét ví dụ một phân bố dữ liệu như hình 1.3 dưới đây: Hình 1.3: Ví dụ về độ biến thiên theo các chiều khác nhau của dữ liệu Theo đó, dữ liệu được phân bố theo các hình e-líp đồng tâm tại gốc tọa độ (trung bình của nhóm). Ta gọi các đường e-líp này lần lượt là các đường e-líp 10%, 20%,…, 90% tính từ gốc tọa độ. Mật độ dữ liệu ở các đường e-líp càng gần tâm thì càng lớn. Ta xét 2 điểm có tọa độ lần lượt là A(0; 2) và B(4; 0). Nếu dùng khoảng cách Euclidean, rõ ràng điểm A(0; 2) ở gần tâm hơn so với điểm B(4; 0). Nhưng như ta thấy điểm A(0; 2) nằm trên đường e-líp 90% (ngoài cùng), còn điểm B(4; 0) nằm trên đường e-líp 70%, nên B(4; 0) phải ở gần tâm hơn so với A(0; 2). Ở đây phương sai theo chiều Y nhỏ hơn so với phương sai theo chiều X. Dùng khoảng cách Mahalanobis ta sẽ phản ánh được hiện tượng trên. Khoảng cách Mahalanobis có những ưu điểm sau:  Tính đến phương sai theo các chiều khác nhau là khác nhau.  Tính đến hiệp phương sai giữa các biến. 1.6. Kỹ thuật Boosting Để trả lời cho câu hỏi của Michael Kearns năm 1988: “Liệu có thể tạo ra một bộ phân loại mạnh từ một tập các bộ phân loại yếu?”, Robert Schapire đã giới thiệu thuật toán Boosting vào năm 1990. Boosting [3] là một thuật toán thuộc lớp các phương pháp học tổ hợp (ensemble learning), nơi nhiều bộ học được huấn luyện để giải quyết cùng một bài toán. Một thuật toán Boosting điển hình tạo một bộ học mạnh duy nhất bằng cách từng bước thêm các bộ học cơ sở (yếu) vào bộ học mạnh cuối cùng. Các bộ học cơ sở có vai trò quan trọng trong bộ học mạnh, chúng là các bộ học đơn giản, chỉ cần có độ chính xác trên 50%. Một cách tổng quát, một thuật toán Boosting được xây 20 dựng trên một thủ tục huấn luyện cơ bản do người dùng định rõ và chạy lặp đi lặp lại với dữ liệu được sửa đổi là đầu ra từ những vòng lặp trước. Dạng tổng quát của thuật toán Boosting được mô tả trong hình 1.4 bên dưới. Đầu vào của thuật toán là một tập các mẫu huấn luyện x và nhãn lớp y tương ứng của nó. Kết quả cuối cùng là một bộ phân lớp mạnh có dạng: (1.15) trong đó là một bộ học cơ sở. Input: Tập dữ liệu huấn luyện. Begin • Khởi tạo một tập trọng số trên các mẫu huấn luyện; for j = 1,2,…, do  Thu được một bộ học yếu ;  Tính ;  Cập nhật ; end; End; Output: Một tổ hợp tuyến tính của các bộ học yếu: . Hình 1.4: Dạng tổng quát của thuật toán Boosting Ví dụ trong hình 1.5 dưới đây minh họa việc xây dựng một bộ học mạnh từ các bộ học yếu :
- Xem thêm -

Tài liệu liên quan