PHÂN LỚP HÌNH ẢNH DỰA TRÊN CẤU TRÚC KD-TREE

Nguyễn Thị Định và CS. Tập 131, Số 2A, 2022 110 tại mỗi mức có tối đa k phép so sánh để chọn nút tốt nhất. Trong mỗi lần so sánh, thuật toán 1 duyệt qua n phần tử của vector fi. Vì vậy, tại mỗi mức, số phép toán tối đa là k × n. Cây có chiều cao h, nên số phép toán tối đa để duyệt từ gốc đến lá theo một hướng được chọn là k × n × h. Vì h và k là hằng số nhỏ, nên độ độ phức tạp của thuật toán phụ thuộc vào n. Mặc khác, số chiều vector fi là cố định ban đầu nên n cũng là hằng số. Gọi C là giá trị hằng số và C > k × h × n nên k × h × n ≤ C × 1. Vì vậy, độ phức tạp của thuật toán 1 là O(1). 3.3 Huấn luyện tập véc-tơ phân lớp trên cấu trúc KD-Tree Sau khi xây dựng cấu trúc KD-Tree phân lớp, mỗi nút lá là một phân lớp hình ảnh. Ban đầu, tập véc-tơ phân lớp cho mỗi nút lá được khởi tạo ngẫu nhiên nên hiệu suất phân lớp trên KD-Tree chưa cao. Do đó, cần phải thực hiện quá trình điều chỉnh các véc-tơ phân lớp lưu trữ tại các Nodei. Quá trình điều chỉnh véc-tơ phân lớp này được gọi là quá trình huấn luyện tập véc-tơ phân lớp trên cấu trúc KD-Tree. Quá trình huấn luyện để tìm ra tập véc-tơ phân lớp tốt nhất cho mô hình phân lớp dựa vào cấu trúc KD-Tree được thực hiện theo sơ đồ trên Hình 2. Để giảm chi phí cho quá trình xây dựng KD-Tree và huấn luyện tập véc-tơ phân lớp, tập dữ liệu ảnh ban đầu gồm n phần tử được chia thành nhiều Epoch dữ liệu ngẫu nhiên. Mỗi Epochi, chứa m phần tử (m < n), thực hiện xây dựng cây KD-Tree và huấn luyện tìm tập véc-tơ phân lớp tốt nhất Fmaxi. Sau đó, từ tập Fmaxi, tiếp tục xây

dựng cây KD-Tree cho Epoch(i+1) và huấn luyện tìm tập Fmax(i+1). Quá trình này lặp lại cho đến khi hết các Epoch dữ liệu và quá trình xây dựng cây KD-Tree và huấn luyện tìm tập véc-tơ phân lớp dừng lại. Kết quả của quá trình này là cấu trúc KD-Tree cho kết quả phân lớp tốt nhất ứng với bộ Hình 2. Sơ đồ xây dựng và huấn luyện KD-Tree theo các Epochi dữ liệu