Kĩ thuật phân lớp dữ liệu trong Khai Phá Dữ Liệu là một trong những vấn đề nguyên cứu mở rộng hiện nay ; tập trung chủ yếu vào thống kê, máy học và mạng nơtrôn .

Kĩ thuật phân lớp được đánh giá là một kĩ thuật khai phá dữ liệu được sử dụng rộng rãi nhất với nhiều mở rộng .

Sự kết hợp của kỹ thuật phân lớp và cơ sở dữ liệu là một lĩnh vực hứa hẹn bởi vì đáp ứng được một vấn đề hết sức quan trọng của ứng dụng cơ sở dữ liệu đó là tính uyển chuyển cao .

Với những ý nghĩa và vai trò hết sức quan trọng của kĩ thuật phân lớp đã nêu ở trên , bài thu hoạch này tập trung nguyên cứu sâu những kĩ thuật phân lớp ,những cách tiếp cận khác nhau đối với kỹ thuật phân lớp cùng với những tìm hiểu và đánh giá những cải tiến của kĩ thuật phân lớp trong thời gian gẩn đây từ những kết quả được đăng tải trên một số báo cáo khoa học tại những hội nghị khoa học quốc tế về Khai Phá Dữ Liệu cũng như việc tìm hiểu và sử dụng kĩ thuật phân lớp trong sản phẩm thương mại Microsoft SQL Server 2000 .

Bùi Thanh Hiếu

Cao học Khóa 1

1. Giới thiệu về phân lớp :

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 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 . Phân lớp cũng là tiên đoán loại lớp của nhãn . Bên cạnh kĩ thuật phân lớp có một hình thức tương tự là kĩ thuật tiên đoán , kĩ thuật tiên đoán khác với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kĩ thuật tiên đoán mô hình những hàm đánh giá liên tục .

Kĩ thuật phân lớp được tiến hành bao gồm 2 bước : Xây dựng mô hình và sử dụng mô hình .

Xây dựng mô hình : là mô tả một tập những lớp được định nghĩa trước trong đó : mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước như là được xát định bởi thuộc tính nhãn lớp , tập hợp của những bộ được sử dụng trong việc sử dụng mô hình được gọi là tập huấn luyện . Mô hình được biểu diễn là những luật phân lớp , cây quyết định và những công thức toán học .

Sử dụng mô hình : Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến . Trước khi sử dụng mô hình người ta thường phải đánh giá tính chính xát của mô hình trong đó : nhãn được biết của mẫu kiểm tra được so sánh với kết quả phân lớp của mô hình , độ chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại đúng bởi mô hình , tập kiểm tra là độc lập với tập huấn luyện .

Phân lớp là một hình thức học được giám sát tức là : tập dữ liệu huấn luyện ( quan sát , thẩm định .) đi đôi với những nhãn chỉ định lớp quan sát , những dữ liệu mới được phân lớp dựa trên tập huấn luyện .

Ngược lại với hình thức học được giám sát là hình thức học không được giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không được biết đến

.

2. Phân lớp bằng phương pháp qui nạp cây quyết định :

2.1. Khái niệm cây quyết định :

Cây quyết định là một flow-chart giống cấu trúc cây , nút bên trong biểu thị một kiểm tra trên một thuộc tính , nhánh biểu diễn đầu ra của kiểm tra , nút lá biểu diễn nhãn lớp hoặc sự phân bố của lớp .

Việc tạo cây quyết định bao gồm 2 giai đoạn : Tạo cây và tỉa cây .

Để tạo cây ở thời điểm bắt đầu tất cả những ví dụ huấn luyện là ở gốc sau đó phân chia ví dụ huấn luyện theo cách đệ qui dựa trên thuộc tính được chọn .

Việc tỉa cây là xát định và xóa những nhánh mà có phần tử hỗn loạn hoặc những phần tử nằm ngoài (những phần tử không thể phân vào một lớp nào đó) .

Việc sử dụng cây quyết định như sau : Kiểm tra những giá trị thuộc tính của mẫu đối với cây quyết định .

2.2. Thuật toán qui nạp cây quyết định :

Giải thuật cơ bản (giải thuật tham lam) được chia thành các bước như sau:

1. Cây được xây dựng đệ qui từ trên xuống dưới (top-down) và theo cách thức chia để trị (divide-conquer).

2. Ở thời điểm bắt đầu , tất cả những ví dụ huấn luyện ở gốc .

3. Thuộc tính được phân loại ( nếu là giá trị liên tục chúng được rời rạc hóa)

4. Những ví dụ huấn luyện được phân chia đệ qui dựa trên thuộc tính mà nó chọn lựa .

5. Kiểm tra những thuộc tính được chọn dựa trên nền tảng của heristic hoặc của một định lượng thống kê .

Điều kiện để dừng việc phân chia :

1.Tất cả những mẫu huấn luyện đối với một node cho trước thuộc về cùng một lớp.

2.Không còn thuộc tính còn lại nào để phân chia tiếp .

3.Không còn mẫu nào còn lại