Một giải pháp nâng cao hiệu suất phân lớp bằng dữ liệu không gán nhãn

(1)

Một giải pháp nâng cao hiệu suất phân lớp bằng dữ liệu không gán nhãn

Quách Hải Thọ Tổ Cơ sở ngành Trường Đại học Nghệ thuật

Đại học Huế, Việt Nam e-mail: haitho37@gmail.com

Phạm Anh Phương Khoa Tin học Trường Đại học Sư phạm Đại học Đà Nẵng, Việt Nam e-mail: paphuong@yahoo.com Abstract- Học bán giám sát đã thu hút sự quan tâm

trong các nghiên cứu về mô hình học máy tiên tiến, hầu hết các nghiên cứu đã tập trung vào việc khai thác hiệu quả việc kết hợp dữ liệu không gán nhãn với dữ liệu có gán nhãn trong giai đoạn huấn luyện. Trong bài báo này chúng tôi đề xuất một cách tiếp cận cải thiện độ chính xác phân lớp của thuật toán học có giám sát với dữ liệu không gán nhãn, vấn đề này đặc biệt quan trọng khi ta cần huấn luyện một thuật toán học có giám sát với số lượng giới hạn các mẫu có gán nhãn và vô số các mẫu không có gán nhãn. Kết quả thực nghiệm cho thấy phương pháp này cải thiện hiệu suất của phương pháp học có giám sát với một số lượng lớn các dữ liệu không gán nhãn, tính toán hiệu quả các bước lặp của thuật toán boosting.

Keywords: Boosting; Semi-supervised learning; Semi- supervised improvement; Manifold; Clustering;

I.GIỚITHIỆU

Bài toán phân lớp dữ liệu là một trong những vấn đề cơ bản của khai phá dữ liệu đã có nhiều ứng dụng thực tiễn nên đã được nhiều nhà nghiên cứu quan tâm. Có nhiều hướng tiếp cận để giải quyết bài toán phân lớp, trong đó hướng giải quyết bài toán theo phương pháp học máy là một lĩnh vực đang được quan tâm nghiên cứu trong thời gian gần đây. Điểm chung của các phương pháp này đều phải trải qua giai đoạn huấn luyện trên một tập dữ liệu. Tập dữ liệu này phải đủ lớn, bao quát hết được các trạng thái của đối tượng và phương pháp này có độ chính xác cao. Tuy nhiên nó gặp phải khó khăn trong việc thu thập dữ liệu huấn luyện ban đầu, tốn thời gian và chi phí cho quá trình học máy.

Một vấn đề đặt ra: khi biết một mẫu nào đó, để phân loại mẫu đó với các mẫu khác thì nên áp dụng phương pháp học máy nào cho hiệu quả? Có 3 phương pháp học được sử dụng phổ biến: học không giám sát, học có giám sát và học bán giám sát.

Trong đó học bán giám sát (semi-supervised learning) là một phương pháp học máy mà dữ liệu huấn luyện là sự kết hợp của dữ liệu được gán nhãn và dữ liệu chưa được gán nhãn. Phương pháp này đang phát triển và áp dụng hiệu quả cho bài toán phân lớp văn bản và trang web [5, 13], bài toán phát

hiện đối tượng từ dữ liệu hình ảnh và video [9], đối với học có giám sát thì các dữ liệu huấn luyện đã được gán nhãn, do đó sẽ thu được kết quả có độ chính xác cao. Tuy nhiên, ta sẽ gặp một vấn đề khó khăn là với lượng dữ liệu lớn thì công việc gán nhãn cho dữ liệu sẽ tốn rất nhiều thời gian và công sức.

Đối với phương pháp học không có giám sát thì ngược lại, các dữ liệu huấn luyện không được gán nhãn, do đó kết quả thu được có độ chính xác không cao. Học bán giám sát đã khắc phục được các nhược điểm và phát huy được ưu điểm của học có giám sát và học không có giám sát. Học bán giám sát đã khai thác một lượng lớn các dữ liệu không gán nhãn cùng với các dữ liệu có gán nhãn giới hạn cho việc học, đã thu hút nhiều sự chú ý trong suốt những thập kỷ qua.

Các phương pháp phân lớp bán giám sát cố gắng khai thác các thông tin phân phối dữ liệu nội tại được đưa ra bởi các dữ liệu không gán nhãn. Để khai thác các dữ liệu không gán nhãn, một số giả định cần được áp dụng cho việc học, các thuật toán phân lớp bán giám sát hiện có có thể được phân thành hai loại dựa trên các giả định cơ bản của chúng, hai giả định phổ biến trong phân lớp bán giám sát là giả định cụm và các giả định đa dạng [12] - [15]. Trong đó giả định cụm là giả định trường hợp tương tự có khả năng chia sẻ các nhãn cùng lớp, do đó hướng đường biên ranh giới đi qua khu vực có mật độ thấp. Đối với giả định đa dạng là giả định dữ liệu được phân bố trên một số đa dạng có chiều thấp biểu diễn bởi đồ thị Laplacian, và các trường hợp tương tự chia sẻ kết quả phân loại theo đồ thị. Hầu hết tất cả các phương pháp phân lớp bán giám sát có sẵn áp dụng một hoặc cả hai giả định trên một cách rõ ràng hoặc ngầm [11], [21].

Các phương pháp phân lớp bán giám sát với khoảng cách lề cực đại như TSVM [18], S3VM [3]

và các biến thể của chúng [10, 19] theo giả định cụm. Các phương pháp phân lớp bán giám sát dựa trên đồ thị, chẳng hạn như lan truyền nhãn[16, 18], đồ thị cắt [14], và Laplacian SVM (LapSVM) [8] thì chấp nhận giả định đa dạng.

Trong bài báo này, chúng tôi tập trung vào đề xuất phương án phân lớp giám sát sử dụng dữ liệu không gán nhãn bằng cách xây dựng một khung

(2)

Boosting là một kết hợp tuyến tính của các bộ phân lớp yếu, các bộ phân lớp yếu này được xây dựng dựa trên đồ thị nhằm đạt hiệu quả tối ưu cho kết quả phân lớp.

Phần còn lại của bài báo này được cấu trúc như sau: Phần 2 đề xuất mô hình cho phương án phân lớp. Phần 3 trình bày kết quả thực nghiệm và đánh giá kết quả. Cuối cùng là phần kết luận và hướng phát triển.

II.MÔHÌNHPHÂNLỚP

Trong phần này chúng tôi có ý tưởng đề xuất một khung Boosting là một kết hợp giữa thuật toán học có giám sát đã cho với tập dữ liệu không gán nhãn.

Một cách tổng quát, thuật toán Boosting [20] được xây 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. Tại mỗi lần lặp, nhiều mẫu không gán nhãn sẽ được chọn và sử dụng để huấn luyện một mô hình phân lớp mới sử dụng thuật toán học có giám sát đã cho.

Tuy nhiên vấn đề khó khăn trong việc thiết kế này phải giải quyết đó là: (1) làm thế nào để lấy mẫu các mẫu không gán nhãn để huấn luyện một mô hình phân lớp mới tại mỗi lần lặp, và (2) những lớp nhãn nào nên được chỉ định đối với các mẫu không có gán nhãn được chọn. Và điểm khác của giải pháp này là không giống như các thuật toán có giám sát boosting sẽ sử dụng các mẫu có gán nhãn để xây dựng mô hình phân lớp, mà giải pháp đưa ra là sẽ lựa chọn các mẫu không gán nhãn tại mỗi lần lặp để xây dựng mô hình phân lớp.

Để giải quyết vấn đề đặt ra ở trên chúng tôi đề xuất phương án khai thác giả định cụm và các tiêu chí khoảng cách lề cực đại. Có thể cải thiện khoảng cách lề phân lớp bằng cách chọn các mẫu không gán nhãn có độ tin cậy cao để tham gia phân lớp, và gán nhãn các mẫu này bởi bộ phân lớp hiện hành (tạm gọi các nhãn được gán là plabel). Sau đó tập dữ liệu được gán nhãn sẽ kết hợp với các dữ liệu plabel được chọn sẽ được dùng cho lần lặp tiếp theo để huấn luyện bộ phân lớp mới. Đây là một chiến lược được sử dụng bởi các phương pháp như Self-training [17], Assemble [6] và Semi-supervised Margin Boost [2]. Tuy nhiên, đây mới chỉ là việc chọn các mẫu với các nhãn lớp được dự đoán và chỉ có thể giúp tăng khoảng cách lề cho bộ phân lớp, mà chưa cung cấp thông tin mới đến bộ phân lớp.

Do các mẫu không gán nhãn được chọn là những mẫu được phân lớp một cách chắc chắn, chúng thường xa đường biên quyết định. Kết quả là, phân lớp được huấn luyện bởi các mẫu không gán nhãn được chọn có khả năng chia sẽ cùng đường biên quyết định với phân lớp ban đầu mà được huấn luyện chỉ bởi các mẫu có gán nhãn, điều này là do điều chỉnh đường biên quyết định, các mẫu có độ tin

cậy phân lớp cao sẽ đạt được độ tin cậy thậm chí còn cao hơn, việc này ngụ ý rằng chúng ta có thể cần hướng dẫn bổ sung để cải thiện phân lớp cơ bản cùng với tiêu chí lề cực đại. Để khắc phục những vấn đề này, chúng tôi đề xuất sử dụng cặp các phép đo đồng dạng để lựa chọn các mẫu không gán nhãn tại mỗi lần lặp, cũng như quy định nhãn lớp cho các mẫu này.

II.1 Mô hình cải tiến

Cho tập dữ liệu D = {x1, x2, … , xn}, gồm các mẫu có gán nhãn và không có nhãn. Giả sử n_l mẫu đầu tiên được gán nhãn, được đưa ra bởi yl= (y₁^l, y₂^l, … , y_n^l_l) , trong đó mỗi lớp nhãn y_l∈ (+1, −1). Và tập yu= (y₁^u, y₂^u, … , ynu_u)là tập các mẫu không gán nhãn, trong đó nu = n − nl. Cho nhãn của toàn bộ tập dữ liệu được ký hiệu là y = y1; yn .

Cho S = Si,j n×nlà ma trận đồng dạng đối xứng, trong đó Si,j ≥ 0 tương ứng với điểm tương đồng giữa xi và xj.

Cho A là biểu thị của thuật toán học có giám sát.

Mục tiêu là đưa ra giải pháp cải thiện trình diễn của A với các bước lặp bằng cách sử dụng các mẫu không gán nhãn và cặp tương đồng S.

Mô tả tóm tắc của thuật toán cho cải tiến bán giám sát như sau:

Input: Tập dữ liệu D = {x₁, x₂, … , x_n}

Output: Một tổ hợp tuyến tính các bộ học yếu H x Method:

+ Bắt đầu bởi 1 tập rỗng tập phân lớp H x = 0.

+ Tại mỗi lần lặp

- Tính toán các plabel (và độ tin cậy của nó) cho mỗi mẫu không gán nhãn (sử dụng tập hợp hiện có và các cặp tương tự).

- Thử các mẫu có nhãn plabel có độ tin cậy cao, kết hợp chúng với các mẫu đã gán nhãn và huấn luyện một phân lớp mới bằng cách sử dụng thuật toán học có giám sát A.

- Cập nhật tập hợp bao gồm phân lớp hợp thành với 1 trọng số thích hợp.

Điều quan trọng ở đây là phải phân biệt giải pháp đưa ra với các phương pháp tiếp cận bán giám sát hiện có, bất kỳ thuật toán tập hợp nào cũng phải dựa trên plabel để tạo ra phân lớp tiếp theo trong tập hợp đó. Mặc khác, các thuật toán dựa trên đồ thị sử dụng các cặp tương đồng giữa các cặp mẫu, và gán nhãn các mẫu không có nhãn để chúng nhất quán với nhau.

Trong vấn đề cải tiến bán giám sát, chúng tôi hướng đến xây dựng một phân lớp đồng bộ sử dụng các mẫu không gán nhãn theo cách mà một phương pháp dựa trên đồ thị sử dụng.

(3)

II.2 Thuật toán phân lớp

Để cải thiện thuật toán đã cho A, chúng tôi theo ý tưởng của Boosting bằng cách vận hành thuật toán A lặp đi lặp lại. Một mô hình phân lớp mới sẽ được học tại mỗi lần lặp bằng cách sử dụng thuật toán A và các mô hình phân lớp tại những lần lặp khác nhau sẽ được kết hợp tuyến tính để tạo thành mô hình phân lớp cuối cùng.

II.2.1 Hàm mục tiêu

Các mẫu không có nhãn phải được gán nhãn theo hai tiêu chí chính sau:

a. Các điểm có độ tương đồng cao giữa các mẫu không có nhãn phải chia sẽ cùng nhãn.

b. Những mẫu không có nhãn mà rất giống với một mẫu được gán nhãn phải chia sẽ cùng nhãn.

Hàm mục tiêu F y, S là một sự kết hợp của hai điều kiện, một điều kiện là đo sự không nhất quán giữa các mẫu có gán nhãn và không có gán nhãn Fl y, S và điều kiện còn lại là đo sự không nhất quán giữa các mẫu không có nhãn Fu y_u, S .

Chúng tôi định nghĩa F_u y, S là sự không nhất quán giữa các nhãn lớp y và phép đo tương tự S, như sau:

F_u y_u, S = ⁿ_i,j=1û S_i,j exp y_iû− y_jû (1)

Nhiều hàm mục tiêu sử dụng các ma trận đồng dạng hoặc ma trận kernel, yêu cầu các kernel là tích cực nhất định để duy trì độ lồi của hàm mục tiêu (ví dụ như SVM). Tuy nhiên do exp(x) là một hàm lồi và chúng tôi giả định 𝑆𝑖,𝑗 ≥ 0 ∀𝑖, 𝑗, hàm 𝐹𝑢 𝑦_𝑢, 𝑆 lồi không phụ thuộc vào tính xác định dương của ma trận đồng dạng. Điều này cho phép các ma trận đồng dạng mà không đối xứng, không thay đổi tính lồi của hàm mục tiêu. Các ma trận đối xứng xuất hiện khi sử dụng đồ thị có hướng cho các vấn đề của mô hình phân lớp [1].

Mặc dù cách tiếp cận của chúng tôi có thể hoạt động cho các ma trận đồng dạng tổng quát. Tuy nhiên lưu ý rằng phương trình (1) có thể mở rộng như sau:

Fu y_u, S = ⁿ_i,j=1û Si,j cosh y_iû− y_jû (2) Với

cosh y_i− y_j = exp −y_i+ y_j + exp y_i− y_j /2 là hàm cosine hyperbolic, hàm cosh(x) là một hàm lồi với giá trị cực tiểu tại x = 0.

Viết lại phương trình (1) sử dụng hàm cosh(.) cho thấy mối liên hệ giữa hàm phạt bậc 2 được sử dụng trong đồ thị Laplacian dựa trên phương pháp tiếp cận và hàm phạt theo cấp số nhân được sử dụng trong các phương pháp hiện hành.

Sử dụng hàm phạt cosh(.) không chỉ là điều kiện của thuật toán boosting cơ bản mà có thể làm tăng khoảng cách lề cực đại [4].

Sự không nhất quán giữa các mẫu có nhãn và không có nhãn 𝐹_𝑙 𝑦, 𝑆 được định nghĩa như sau:

𝐹𝑙 𝑦, 𝑆 = ^𝑛_{𝑗 =1}^𝑢 𝑆𝑖,𝑗 𝑒𝑥𝑝 −2𝑦_𝑖^𝑙𝑦_𝑗^𝑢

𝑖,𝑗 𝑛_𝑙

𝑖=1 (3)

Kết hợp (1) và (3) cho ta hàm mục tiêu sau:

F y, S = Fl y, S + CFu yu, S (4)

Trong đó hằng số C là trọng số quan trọng giữa các mẫu có nhãn và không có nhãn.

Với hàm mục tiêu (4), nhãn lớp tối ưu 𝑦𝑢 được tìm thấy bằng cách giảm thiểu F.

II.2.2 Cài đặt thuật toán.

Chúng tôi sử dụng thuật toán boosting với phương pháp tối ưu các ràng buộc. Một cách khác để sử dụng thuật toán boosting với phương pháp hàm mục tiêu Gradient đã trình bày trong [7]. Phương pháp này cũng được xem như mở rộng xấp xỉ các hàm mục tiêu ban đầu của hàm tuyến tính, tuy nhiên cách tiếp cận như vậy liên quan đến đặc điểm kỹ thuật của giá trị tham số, trong dẫn xuất của chúng tôi, giá trị ở mỗi bước sẽ được tự động xác định, do đó, khắc phục được những khó khăn trong việc xác định giá trị ở mỗi bước.

Cho ℎ^𝑡 𝑥 : 𝑋 → −1, +1 biểu thị mô hình phân lớp nhị phân được học tại lần lặp thứ t bởi thuật toán A.

Cho 𝐻 𝑥 : 𝑋 → 𝑅 biểu thị mô hình phân lớp kết hợp được học sau những lần lặp T đầu tiên. Nó được tính như một sự kết hợp tuyến tính của các mô hình phân lớp T đầu tiên, tức là:

𝐻 𝑥 = 𝛼𝑡ℎ^𝑡(𝑥)

𝑇

Trong đó αt là trọng số kết hợp. 𝑡=1

Tại (T+1) bước lặp đầu tiên, mục đích là tìm một phân lớp h(x) mới và trọng số kết hợp α mà có thể giảm đến mức tối thiểu hiệu quả hàm mục tiêu F, điều này dẫn đến vấn đề tối ưu sau:

arg min_{h x ,α} ⁿ_i=1^l ⁿ_j=1^u S_i,j exp −2y_i^l H_j+ αh_j + C ⁿ_i,j=1^u S_i,jexp H_i− H_j exp α h_i− h_j (6)

Phụ thuộc vào h xi = y_i^l, i = 1, … , nl (7) ở đây H_i≡ H x_i và h_i≡ h x_i .

Biểu thức này liên quan đến tích của các biến α và hi, làm cho nó không tuyến tính vì vậy khó để tối ưu. Tuy nhiên, các ràng buộc có thể dễ dàng thỏa mãn bằng cách đưa vào tất cả các mẫu gán nhãn trong tập huấn luyện của mỗi thành phần phân lớp.

Để đơn giản việc tính toán, ta xây dựng ràng buộc trên của hàm mục tiêu như sau:

Cực tiểu (7) là tương tự như cực tiểu hàm mục tiêu

F ₁= ⁿ_i=1^u exp −2αh_i p_i+ exp⁡(2αh_i)q_i (8)

Trong đó

(4)

pi= ⁿ_j=1^l Si,je^−2Hⁱδ yj, 1 +^C₂ ⁿ_j=1^u Si,je^H^j^−Hⁱ (9) q_i= ⁿ_j=1^l S_i,je^2Hⁱδ y_j, −1 +^C₂ ⁿ_j=1^u S_i,je^Hⁱ^−H^j (10)

Và δ x, y = 1 khi x = y và 0 nếu ngược lại.

Trong biểu thức (8) khó để tối ưu khi trọng số α và phân lớp h(x) được ghép với nhau. Để cực tiểu (8) là tương đương với cực tiểu sau:

F 1≤ pi+ qi e^2α+ e^−2α− 1

n_u

i=1

− 2αhi pi− qi n_u

i=1

Chúng tôi biểu thị ràng buộc trên trong phương trình trên bằng F 2. Từ đó cực tiểu F 2, tối ưu lớp nhãn zi cho mẫu xi là zi = sign pi− qi và trọng số cho mẫu huấn luyện xilà p_i− qi . Tối ưu giá trị α để F ₁ đạt cực tiểu là:

α =¹₄ln ^{n u}ⁱ⁼¹^p_pⁱ^{δ h}ⁱ^{,1 +} ^{n u}ⁱ⁼¹^qⁱ^{δ h}ⁱ^,−1

iδ h_i,−1 +

n ui=1 ^{n u}_i=1q_iδ h_i,1 (11) Cho ϵt là lỗi trọng số tạo ra bởi bộ phân lớp, với:

ϵt= ⁿ_i=1^u p_iδ h_i, −1 + ⁿ_i=1^u q_iδ h_i, 1 pi _i+ qi

Như trong trường hợp adaboost [7], giá trị α được thực hiện như:

αt=¹₄ln ^1−ϵ_ϵ ^t

t (12)

Tương tự như hệ số trọng số của Adaboost, chỉ khác nhau bởi yếu tố không đổi là 1/2. Ngoài ra, nếu Adaboost gặp tình huống mà các phân lớp cơ sở có một giá trị lỗi ngẫu nhiêu, nghĩa là ϵt≥ 1/2 thì nó trả về phân lớp H_t hiện tại. Tình huống này có một tương ứng trực tiếp với điều kiện thuật toán dừng lại khi α ≤ 0.

Thuật toán phân lớp:

1. Tính toán cặp tương tự S_i,j giữa 2 mẫu bất kỳ.

2. Khởi tạo H x = 0.

3. Vòng lặp, For t=1, 2, ..., T

- Tính pi và qi cho mỗi mẫu bằng cách sử dụng phương trình (9) và (10).

- Tính toán các nhãn lớp zi= sign pi− qi cho mỗi mẫu.

- Gán mỗi mẫu xi bởi trọng số pi− qi

- Áp dụng thuật toán A để huấn luyện một phân lớp nhị phân h_t(x) bằng cách sử dụng các mẫu và các nhãn lớp zi

- Tính toán αt sử dụng (11).

- Cập nhật hàm phân lớp với H x ← H x + αtht(x).

Hình 1. Sơ đồ thuật toán tạo phân lớp Trong đó: H(x) là phân lớp mạnh và h(x) là phân lớp cơ sở

p, q là độ tin cậy trong việc phân x vào lớp 1 và 2

Hình 2. Kết hợp các bộ phân loại yếu thành bộ phân loại mạnh

II.3 Quá trình lấy mẫu

Quá trình lấy mẫu là bước quan trọng nhất trong phương án phân lớp đưa ra, giống như bất kỳ thuật toán boosting khác, các tiêu chuẩn để lấy mẫu thường được xét đến các vấn đề sau:

a. Có bao nhiêu mẫu phải được chọn từ tập mẫu không có nhãn có sẵn cho việc huấn luyện ?.

b. Phân phối gì và theo đó mẫu nào phải được thực hiện.

Đối với các thuật toán có giám sát Boosting giống như Adaboost có sẵn các nhãn đúng, điều này dễ dàng quyết định mẫu nào được chọn hoặc là không được chọn. Mặc khác, các nhãn được ấn định trong quá trình lặp của thuật toán đề xuất là các nhãn plabel và có thể dễ bị lỗi. Điều này cho thấy rằng nên chọn chỉ một vài điểm dữ liệu có độ tin cậy cao cho thuật toán, tuy nhiên chọn một số lượng nhỏ các

(5)

mẫu có thể làm chậm quá trình hội tụ và lựa chọn quá nhiều mẫu thì có thể chọn nhầm các mẫu không chưa thông tin hoặc thậm chí xấu cho tập huấn luyện. Việc chọn hiện nay được thực hiện dựa vào kinh nghiệm và chọn trong top 10% số mẫu hoạt động.

Để giảm F , chúng tôi lựa chọn các mẫu có giá ₁ trị p_i− q_i lớn, và sự lựa chọn này tạo ra các mẫu có gán nhãn plabel có độ tin cậy cao cho phân lớp.

Xác suất lấy mẫu được thực hiện theo phân phối:

Ps x_i = p_i− qi

pn_l _i− qi

đây là xác suất mà điểm dữ liệu xi=1 _i lấy mẫu từ bộ truyền dẫn.

II.4 Điều kiện dừng

Theo công thức tối ưu thì thuật toán dừng khi α ≤ 0, chỉ ra rằng khi bổ sung của phân lớp đó thì tăng giá trị hàm mục tiêu thay vì giảm. Tuy nhiên, giá trị α giảm rất nhanh ngay từ đầu, thậm chí tỉ lệ giảm hạ xuống, lấy một số lượng lớn các lần lặp để thực sự làm cho nó âm. Hiện nay, chúng tôi vẫn đang thực hiện theo kinh nghiệm với thiết lập giá trị T = 20.

II.5 Ma trận đồng dạng

Chúng tôi sử dụng hàm cơ bản Radial từ phương pháp tiếp cận dựa trên đồ thị. Đối với 2 mẫu x_i và x_j, có giá trị Si,j giống nhau được tính bằng:

Si,j = exp − xi− xj 2

σ²

Trong đó σ là tham số tỉ lệ kiểm soát sự lan truyền của hàm cơ bản Radial.

Biết rằng lựa chọn tham số σ sẽ tác động đến việc thực hiện của thuật toán [18], chúng tôi thực hiện việc thay đổi tham số σ với giá trị từ 10% đến 100% với bước thay đổi là 10, và μ_s là giá trị trung bình của ma trận đồng dạng S.

Trong quá trình thực nghiệm cho thấy rằng việc lựa chọn phạm vi giá trị σ có độ ổn định, đây là một mong muốn so với thực tế, vì việc lựa chọn tham số σ đúng là một vấn đề khó khăn.

III.THỰCNGHIỆM

Mục đích của giải pháp đưa ra là cải tiến phương pháp phân lớp có giám sát sử dụng dữ liệu không gán nhãn. Do đó, chúng tôi đánh giá mức độ hội tụ thuật toán của các phân lớp cơ sở, trong phần thực nghiệm đầu tiên chúng tôi sử dụng bộ dữ liệu

“Ringnorm”[23], bộ dữ liệu này có 2 lớp, mỗi lớp có 500 mẫu. Có 10 mẫu có gán nhãn trên mỗi lớp, được biểu thị bằng (■,▲).

Trong hình sau các đường liền nét cho thấy ranh giới quyết định và các vùng sáng – tối cho 2 khu vực phân lớp cùng với hiệu suất tại mỗi lần lặp, hình 4a- 4c cho thấy phân lớp thu được tại ba lần lặp đầu tiên và hình 3d cho thấy phân lớp sau cùng thu được ở lần lặp thứ 12.

Hình 4a. Hình 4b.

Lần lặp thứ 1, (65%) Lần lặp thứ 2, (75%)

Hình 4c. Hình 4d.

Lần lặp thứ 3, (85%) Lần lặp thứ 12, (95%) Thực nghiệm tiếp theo được chúng tôi tiến hành trên 9 bộ dữ liệu khác nhau được lấy từ trang UCI Machine Learning [22], trong này những tập dữ liệu đa lớp được chuyển đổi thành hai lớp bằng cách chọn 2 lớp lớn nhất.

Bảng 1. Các tập dữ liệu cho thực nghiệm STT Tập dữ liệu Số mẫu (n) Số chiều (d)

1 Iris 150 4

2 Protein 116 6

3 Soybean 47 34

4 Thyroid 215 5

5 Image 660 18

6 Isolet 600 51

7 Mfeat 400 76

8 Optdigits 1143 42

9 House 232 16

Chúng tôi chia ngẫu nhiên các tập dữ liệu thành hai phần (tập huấn luyện và tập kiểm tra), tập huấn luyện có 10 điểm gán nhãn và phần còn lại không có nhãn. Bộ phân lớp tổ hợp được học bằng phương án đưa ra trên tập huấn luyện và được đánh giá bằng việc thực hiện của nó về sự dự đoán các nhãn của tập kiểm tra. Chúng tôi tiến hành so sánh đánh giá thuật toán SVM với phương án kết hợp sử dụng SVM làm phân lớp cơ sở, trong này số lượng những phân lớp được xây dựng sẽ phụ thuộc vào số lần lặp lại T trong boosting, do đó chúng tôi thiết lập T = 10 và dừng boosting khi trọng số α_t tính từ (11) nhỏ hơn 0, và giá trị C trong hàm mục tiêu (4) được tính bằng số lượng mẫu có nhãn với số lượng mẫu không có nhãn C=n_l/n_u.

(6)

Bảng 2. So sánh SVM với phương án sử dụng SVM làm phân lớp cơ sở.

STT Tập dữ liệu SVM A-SVM

1 Iris 59.75 55.42

2 Protein 70.59 79.00

3 Soybean 52.45 52.02

4 Thyroid 78.28 72.29

5 Image 99.92 99.95

6 Isolet 89.58 95.12

7 Mfeat 98.78 99.85

8 Optdigits 90.31 96.35

9 House 91.16 90.65

Kết quả chỉ ra rằng phương án đưa ra cải thiện đáng kể hiệu suất của phân lớp cơ sở trên hầu hết các tập dữ liệu, tuy nhiên có 3 trường hợp (tập dữ liệu Iris, Thyroid, House) đã có sự suy giảm hiệu suất phân lớp, điều này cũng có thể nói rằng dữ liệu không có nhãn là không hữu ích trong những trường hợp này. Nhưng ý tưởng của chúng tôi không phải là xây dựng bộ phân lớp tốt nhất mà để có thể thấy rằng sẽ có sự cải thiện trong thực hiện phân lớp có giám sát kết hợp với dữ liệu không gán nhãn.

Cũng với một quy trình thực nghiệm như trên, chúng tôi đánh giá hiệu suất của phương án đưa ra với hiệu suất của Adaboost trên cùng một phân lớp cơ sở, cụ thể là chúng tôi so sánh đánh giá khi sử dụng thuật toán SVM, phiên bản được boost của SVM (sử dụng Adaboost) và phương án SVM - boost có sử dụng dữ liệu không gán nhãn được thêm vào cùng một tập các mẫu có nhãn.

Bảng 3. So sánh SVM, boost-SVM với phương án sử dụng SVM làm phân lớp cơ sở.

STT Tập dữ liệu SVM Boost-SVM A-SVM

1 Isolet 89.58 88.48 95.12

2 Mfeat 98.78 93.80 99.85

3 Optdigits 90.31 87.11 96.35

Qua kết quả trên có thể thấy rằng hiệu suất của phương án bổ sung thêm dữ liệu không gán nhãn tốt hơn so với các phân lớp được huấn luyện chỉ sử dụng dữ liệu có gán nhãn. Tuy nhiên khi các dữ liệu không gán nhãn được gán nhãn thì hiệu quả hoạt động phân lớp của chúng có thể sẽ tốt hơn so với phương án đưa ra.

IV.KẾTLUẬN

Qua thực nghiệm cho thấy rằng, hiệu suất của phương pháp đưa ra là có phần tốt hơn so với các phân lớp được huấn luyện chỉ sử dụng dữ liệu có gán nhãn, gồm có boost (sử dụng Adaboost) hoặc không boost. Tuy nhiên, khi tất cả các dữ liệu không có nhãn được gán nhãn, hiệu suất của các phân lớp và các phiên bản boost của chúng lại thực hiện tốt hơn phương pháp đưa ra. Trên một số tập dữ liệu với số lượng nhỏ các mẫu huấn luyện đã xuất hiện overfitting, việc bổ sung các dữ liệu không có nhãn như là một cơ chế hoạt động trong phương pháp đưa

ra nhằm tránh overfitting, từ đó chất lượng phân lớp được cải thiện.

Như vậy với phương pháp đưa ra là đề xuất phương án sử dụng một khung boosting với dữ liệu không gán nhãn để cải thiện hiệu suất của bất kỳ phân lớp cơ sở được cho nào trong sự hiện diện của các mẫu không có nhãn. Nhìn chung, hiệu suất của phương pháp đưa ra được so sánh với các thuật toán học bán giám sát tiên tiến, đã cho thấy nó khá hữu ích trong thực tế, hiện tại phương pháp đưa ra chỉ mới giải quyết bài toán 2 lớp, trong tương lai chúng tôi sẽ mở rộng cho bài toán nhiều lớp.

REFERENCES

[1] D. Zhou, J. Huang, and B. Scholkopf (2005), “Learning from labeled and unlabeled data on a directed graph” in Proc.

22nd International Conference on Machine Learning, pp. 1036–

1043.

[2] F.d’Alche Buc, Y. Grandvalet, and C. Ambroise (2002),

“Semi-supervised marginboost,” in NIPS 14, pp. 553–560.

[3] G. Fung and O. Mangasarian (2001), “Semi-supervised support vector machines for unlabeled data classification”

Optimization Methods and Software, vol. 15, pp. 29–44.

[4] J. Friedman, T. Hastie, and R. Tibshirani (2000), “Special invited paper. additive logistic regression: a statistical view of boosting” The Annals of Statistics, vol. 28, pp. 337–374.

[5]. Hồ Thị Ngọc (2012), Nghiên cứu ứng dụng bán giám sát, Luận văn thạc sĩ ngành khoa học máy tính, Đại học Đà Nẵng.

[6] K. P. Bennett, A. Demiriz, and R. Maclin (2002),

“Exploiting unlabeled data in ensemble methods,” in Proc. 8th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 289–296.

[7] L. Mason, J. Baxter, P. Bartlett, and M. Frean (1999),

“Boosting algorithms as gradient descent in function space” in NIPS 12, pp. 512–518.

[8] M. Belkin, P. Niyogi, and V. Sindhwani (2006), “Manifold regularization: A geometric framework for learning from labeled and unlabeled examples”, J.Mach.Learn.Res., vol. 7, no. 1, pp.

2399–2434.

[9] Nguyễn Đăng Bình, Lương Văn Nghĩa (2011), "Phát Hiện Các Tòa Nhà Từ Ảnh Không Gian Sử Dụng Học Nửa Giám Sát", Kỷ yếu Hội nghị quốc gia lần thứ V với chủ đề "nghiên cứu cơ bản và ứng dụng Công nghệ thông tin" - FAIR, Nhà xuất bản Khoa học kỹ thuật, trang 191-203.

[10] R. Collobert, F. Sinz, J. Weston, and L. Bottou (2006),

“Large scale transductive SVMs”, J.Mach.Learn.Res., vol. 7, pp.

1687–1712.

[11] O. Chapelle, B. Scholkopf, and A. Zien (2006), Semi- Supervised Learning. Cambridge, MA, USA: MIT Press.

[12] P. K. Mallapragada, R. Jin, A. K. Jain, and Y. Liu (2009),

“Semi-boost:Boosting for semi-supervised learning”, IEEE Trans.

Pattern Anal. Mach. Intell., vol. 31, no. 11, pp. 2000–2014.

[13]. Võ Duy Thanh (2015), “Bổ sung dữ liệu huấn luyện bằng học máy bán giám sát”, Tập san chuyên đề khoa học và giáo dục - Trường cao đẳng công nghệ thông tin hữu nghị Việt – Hàn, số 3, tr. 17-26.

[14] Wei Feng, Lei Xie and Zhi-Qiang Liu (2009), “Multicue Graph Mincut for Image Segmentation”, in ACCV'09 Proceedings of the 9th Asian conference on Computer Vision - Volume Part II, pp. 707-717.

[15] X. Zhu (2008), “Semi-supervised learning literature survey,” Ph.D. dissertation, Dept. Comput. Sci., Wisconsin- Madison, Univ., Madison, WI, USA.

[16] X. Zhu and Z. Ghahramani (2002), “Learning from labeled and unlabeled data with label propagation,” Technical Report CMU-CALD-02-107, Carnegie Mellon University.

(7)

[17] Yan Zhou, Murat Kantarcioglu, and Bhavani Thuraisingham (2012), “Self-Training with Selection-by- Rejection”, in IEEE 12th International Conference on Data Mining, pp. 586-803.

[18] Y. Bengio, O. B. Alleau, and N. Le Roux (2006), “Label propagation and quadratic criterion,” in Semi-Supervised Learning (O. Chapelle, B. Sch¨ olkopf, and A. Zien, eds.), pp. 193–216, MIT Press.

[19] Y.-F. Li, J. Kwok, and Z.-H. Zhou (2009), “Semi- supervised learning using label mean” in Proc. 26th Int. Conf.

Mach. Learn., 2009, pp. 633–640.

[20] Y. Freund and R. E. Schapire (1996), “Experiments with a new boosting algorithm” in Proc. 13th International Conference on Machine Learning, pp. 148–156, 1996.

[21] Z.-H. Zhou and M. Li (2010), “Semi-supervised learning by disagreement”, Knowl. Inf. Syst., vol. 24, no. 3, pp. 415–439.

[22] ftp://ftp.ics.uci.edu/pub/machine-learning-databases.

[23]ftp://ftp.cs.toronto.edu/pub/neuron/delve/data/tarfiles/.

(8)