Bài giảng Khai phá dữ liệu: Chương 5 - Phân lớp dữ liệu (mới nhất)

Bài giảng môn học: Khai phá Dữ liệu(7080508)

CHƯƠNG 5: PHÂN LỚP DỮ LIỆU

08/2021

Nội dung chương 5

5.1 Tổng quan về học có giám sát

5.2 Phân lớp dữ liệu

5.3 Thuật toán phân lớp dữ liệu

5.4 Ứng dụng bài toán phân lớp dữ liệu

5.1. Tổng quan về học có giám sát

•Một thuật toán học máy được gọi là học có giám sát (supervised learning) nếu việc xây dựng mô hình dự đoán mối quan hệ giữa đầu vào và đầu ra được thực hiện dựa trên các cặp (đầu vào - input, đầu ra – label) đã biết trong tập huấn luyện. Đây là nhóm thuật toán phổ biến nhất trong các thuật toán machine learning. •Tập dữ liệu học (Training data) bao gồm các quan sát (Examples, Observations), mà mỗi quan sát được gắn kèm với một giá trị đầu ra mong muốn (Label)

5.1. Tổng quan về học có giám sát

Thời gian trong ngày

Ví dụ, bạn muốn đào tạo một cỗ máy để giúp bạn dự đoán bạn sẽ mất bao lâu để lái xe về nhà từ nơi làm việc. Tại đây, bạn bắt đầu bằng cách tạo một tập hợp dữ liệu được dán nhãn. Dữ liệu này bao gồm • Điều kiện thời tiết • • Ngày lễ • Chọn đường đi

Ưu nhược điểm học có giám sát

Ưu điểm: + Học có giám sát cho phép bạn thu thập dữ liệu hoặc tạo đầu ra dữ liệu từ trải nghiệm trước đó + Giúp bạn tối ưu hóa tiêu chí hiệu suất bằng kinh nghiệm + Học máy được giám sát giúp bạn giải quyết các loại vấn đề tính toán trong thế giới thực. Nhược điểm: + Ranh giới quyết định có thể được tập trung quá mức nếu tập huấn luyện của bạn không có ví dụ mà bạn muốn có trong một lớp + Bạn cần chọn nhiều ví dụ hay từ mỗi lớp trong khi bạn đang đào tạo trình phân loại. + Phân loại dữ liệu lớn có thể là một thách thức thực sự. + Đào tạo cho việc học có giám sát cần rất nhiều thời gian tính toán.

5.2. Phân lớp dữ liệu

Phân lớp là phương pháp học có giám sát. Mục đích: dự đoán những nhãn phân lớp cho các bộ dữ liệu /mẫu mới

+ Đầu vào: Một tập các mẫu dữ liệu huấn luyện, với một nhãn phân lớp cho mỗi mẫu dữ liệu + Đầu ra: Mô hình (bộ phân lớp) dựa trên tập huấn luyện và những nhãn phân lớp

5.2. Phân lớp dữ liệu

Quá trình huấn luyện và kiểm thử với Mô hình học máy có giám sát

5.2. Phân lớp dữ liệu

Dataset sẽ bao gồm: • Các thuộc tính đầu vào (Biến độc lập) – Features (input) • Thuộc tính mục tiêu (Biến phụ thuộc) – Target (label)

5.2. Phân lớp dữ liệu

+ Tập huấn luyện (Training Set) bao gồm các điểm dữ liệu sử dụng trực tiếp trong việc xây dựng mô hình. + Tập kiểm tra (Test set) gồm các dữ liệu được dùng để đánh giá hiệu quả của mô hình. Tập kiểm tra đại diện cho dữ liệu mà mô hình chưa từng thấy, có thể xuất hiện trong quá trình vận hành mô hình trên thực tế.

+ Để đảm bảo tính phổ quát, dữ liệu kiểm tra không được sử dụng trong quá trình xây dựng mô hình. + Điều kiện cần để một mô hình hiệu quả: Kết quả đánh giá trên tập huấn luyện và tập kiểm tra đều cao.

Bài toán phân lớp

Bài toán phân loại là bài toán xác định đối tượng

quan sát thuộc về nhóm (lớp) các đối tượng đã được phân biêt, đã được nhận dạng hay có hiểu biết trước đó. Như vậy có ba đặc tính đi kèm với bài toán phân loại • Phân biệt (Differentiated) • Nhận biết (Recognized) • Hiểu biết (Understood)

Bài toán phân lớp

Mô hình phân loại Được dùng trong bài toán phân loại để thực hiện các vai trò : • Hiểu biết lớp các đối tượng thông qua tập đã được quan

sát trước đó

• Khi có đối tượng mới được quan sát, phân biệt được nó

với các đối tượng đã quan sát

• Nhận biết đối tượng thuộc một nhóm (lớp) nào đã được

quan sát trước đó

Bài toán phân lớp

Mô hình phân loại: Được dùng trong bài toán phân loại để thực hiện các vai trò : • Hiểu biết lớp các đối tượng thông qua tập đã được quan sát trước đó • Khi có đối tượng mới được quan sát, phân biệt được nó với các đối tượng đã quan sát • Nhận biết đối tượng thuộc một nhóm (lớp) nào đã được quan sát trước đó

Bài toán phân lớp

Bài toán phân lớp (Classification problem) + Học một hàm mục tiêu có giá trị rời rạc + Miền giá trị: một tập các nhãn lớp (class labels) xác địn trước + Với mỗi ví dụ cần phân loại, hệ thống xác định nhãn lớp của nó Bài toán dự đoán/hồi quy (Prediction/regression problem) + Học một hàm mục tiêu có giá trị liên tục + Miền giá trị: tập các giá trị số thực (real numbers) + Với mỗi ví dụ cần dự đoán, hệ thống xác định giá trị 14 dự đoán của nó

Bài toán phân lớp

Có rất nhiều mô hình phân loại như:  Sử dụng luật xác suất có điều kiện theo luật Trực tiếp Bay ét (NaiveBayes Classifier)

 Sử dụng cấu trúc cây

Cây quyết định Sử dụng phân loại dựa trên đối

tượng (Decision tree)

 Sử dụng phân loại dựa trên đối tượng (Instanced-Based

Classifier)

Hàng xóm gần nhất (Nearest Neigboors)

5.3. Thuật toán phân lớp dữ liệu

CÂY QUYẾT ĐỊNH

Cây quyết định (Decision tree )

+ Decision tree là một mô hình học có giám sát, có thể được áp dụng vào cả hai bài toán classification và regression. +Cây quyết định là một trong những giải thuật quan trọng được sử dụng khá phổ biến trong thực tế. Đặc biệt trong lĩnh vực Học máy, khai phá dữ liệu… + Cây quyết định là một cấu trúc phân cấp của nút và các nhánh biểu diễn dưới dạng cây + Cây quyết định là một kiểu mô hình dự báo, nghĩa là một ánh xạ từ các quan sát về một sự vật/ hiện tượng tới các kết luận về giá trị mục tiêu của sự vật hiện tượng. Mỗi nút trong tương ứng với một biến, đường nối giữa nó với nút con

Cây quyết định (Decision tree )

+ Một cây quyết định có thể được biểu diễn (diễn giải) bằng một tập các luật IF-THEN (dễ đọc và dễ hiểu) + Học cây quyết định có thể thực hiện ngay cả với các dữ liệu có chứa nhiễu/lỗi (noisy data) + Là một trong các phương pháp học quy nạp (inductive learning) được dùng phổ biến nhất + Được áp dụng thành công trong rất nhiều các bài toán ứng dụng thực tế

Cây quyết định (Decision tree )

Cây quyết định dùng trong KPDL được ứng dụng như sau + Tập dữ liệu biểu diễn các đối tượng được khởi tạo tại nút gốc + Quyết định được đưa ra thông qua phép duyệt từ gốc đến lá + Các nút trong tương ứng với quyết định ứng giá trị trường thuộc tính + Nhánh cây biểu diễn đầu ra của quyết định hay tập con dữ liệu được phân chia tương ứng quyết định nút cha + Nút lá biểu diễn các nhãn lớp

Cây quyết định (Decision tree )

Xây dựng cây: thực hiện đệ quy tập mẫu dữ liệu huấn luyện cho đến khi đối tượng ở mỗi nút lá thuộc cùng một lớp. + Các mẫu huấn luyện xuất phát nằm ở gốc + Chọn một thuộc tính để phân chia tập mẫu huấn luyện thành nhánh + Tiếp tục lặp việc xây dựng cây quyết định cho các nhánh, quá trình

dừng khi:

Tất cả các mẫu đều được phân lớp Không còn thuộc tính nào có thể dùng để chia mẫu

Có 3 loại nút: + Nút gốc(root): đỉnh trên cùng của cây (nút cao nhất) + Nút trong (internal node): biểu diễn một thuộc tính, (ứng với một phép kiểm tra trên một thuộc tính) + Nút lá (leaf node): Lớp quyết định (biểu diễn các lớp hay các phân bố

lớp

+ Nhánh (branch node): biểu diễn giá trị có thể có của thuộc tính. (Nhánh

biểu diễn kết quả phép kiểm tra)

Cây quyết định (Decision tree )

Nút trên cùng của cây

Biểu diễn kiểm tra trên một thuộc tính đơn

Nhánh biểu diễn các kết quả kiểm tra trên Nút trong

Biểu diễn lớp hay sự phân phối lớp

Cây quyết định (Decision tree )

Giải thuật ID3 • Đầu vào: Một tập hợp các tập huấn luyện. + Mỗi tập huấn luyện bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó Ví dụ: - Thuộc tính mô tả (Quang cảnh, Gió,..) - Thuộc tính phân loại (Chơi Tennis?) • Đầu ra: Cây quyết định + Có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện + Phân loại đúng cho cả các ví dụ chưa gặp trong tương lai

Giải thuật ID3

Function Induce_tree(tập_ví_dụ, tập_thuộc_tính)

if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then

return một nút lá được gán nhãn bởi lớp đó else if tập_thuộc_tính là rỗng then return nút lá được gán nhãn bởi tuyển của tất cả các lớp trong tập_ví_dụ else - chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại; - xóa P ra khỏi tập_thuộc_tính; For mỗi giá trị V của P - tạo một nhánh của cây gán nhãn V; - Đặt vào phân_vùngV các ví dụ trong tập_ví_dụ có giá trị V tại thuộc tính

P; - Gọi Induce_tree(phân_vùngV, tập_thuộc_tính), gắn kết quả vào nhánh V

End For End If End Function

Lựa chọn thuộc tính kiểm tra

 Rất quan trọng: tại mỗi nút, chọn thuộc tính kiểm tra như thế nào?

 Chọn thuộc tính quan trọng nhất cho việc phân lớp các ví dụ học

gắn với nút đó

 Làm thế nào để đánh giá khả năng của một thuộc tính đối với việc

phân tách các ví dụ học theo nhãn lớp của chúng?

 Các độ đo phân chia thuộc tính (các luật phân chia) – Xác định các

mẫu ở một node được phân chia thế nào

+ Đưa ra cách xếp hạng các thuộc tính

+ Thuộc tính với điểm cao nhất được lựa chọn

Lựa chọn thuộc tính kiểm tra

 Xác định một điểm phân chia hoặc một tập con phân chia  Các phương pháp

+ Informationgain (Entropy)

+ Gainratio

+ GiniIndex

→ Sử dụng một đánh giá thống kê – Information Gain

Ý nghĩa về độ đo thông tin thêm - information gain

• Cần xác định thuộc tính hữu ích cho việc phân loại tập các dữ liệu biểu

diễn đối tượng ?

• Độ đo thông tin thêm nói cho ta biết sự quan trọng của thuộc tính

• Ta sẽ dùng nó để sắp xếp lại các quyết định tương ứng thuộc tính cần

phân chia trên cây

Entropy  Một đánh giá thường được sử dụng trong lĩnh vực Information

Theory

 Để đánh giá mức độ hỗn tạp (impurity/inhomogeneity) của

một tập

 Ta có tập S là tập dữ liệu dèn luyện. Giả sử thuộc tính phân loại

có 2 giá trị (Y/N).

 Ta gọi: + PY: Là các vị dụ có thuộc tính Y trong tập S + PN: Là các ví dụ có thuộc tính N trong tâp S

• Tổng quát cho tập S có nhiều hơn n thuộc tính phân loại (n>=2)

Entropy

• 0

Tập ví dụ S có số lượng ví dụ thuộc

⇒

các loại khác nhau

• Entropy(S) = 0

Tập ví dụ S chỉ toàn ví dụ thuộc

⇒

cùng một loại, hay S là thuần nhất

• Entropy(S) = 1

tập ví dụ S có các ví dụ thuộc các

⇒

loại khác nhau với độ pha trộn là cao nhất.phân loại

(n>=2)

Entropy

Entropy S gồm 14 ví dụ, trong đó 9 ví dụ thuộc về lớp c1 và 5 ví dụ thuộc về lớp c2 • Entropy của tập S đối với phân lớp có 2 lớp: • Entropy(S) = -(9/14).log2(9/14)- (5/14).log2(5/14) = 0.94

 Entropy =0, nếu tất cả các ví dụ thuộc cùng một lớp (c1 hoặc c2)  Entropy =1, số lượng các ví dụ thuộc về lớp c1 bằng số lượng các ví dụ thuộc về lớp c2  Entropy = một giá trị trong khoảng (0,1), nếu như số lượng các ví dụ thuộc về lớp c1 khác với số lượng các ví dụ thuộc về lớp c2

Information Gain

Information Gain là: + Phép đo độ lợi thông tin (đo lượng thông tin thu được) + Lượng giảm entropy bị gây ra bởi việc phân chia các ví dụ theo thuộc tính này. Độ lợi thông tin Gain(S,A) của thuộc tính A trên tập S được tính theo công thức:

Ưu nhược điểm của Cây quyết định

 Cây quyết định có tốc độ học tương đối nhanh so với các phương pháp khác  Đơn giản và dễ hiểu các luật phân loại trong cây ra quyết định  Information Gain, Gain Ratio, và Gini Index là những phương pháp lựa chọn

thuộc tính thông dụng nhất

 Cắt tỉa cây là cần thiết để loại bỏ những nhánh không tin cậy

̛tƯu điểm:

- Dễ hiểu: Cây biểu diễn trực quan - Hữu ích: Xác định được các biến quan trọng - Phi tham số: không cần giả định về phân phối - Không phục thuộc vào dữ liệu: Có thể áp dụng cả dữ liệu phân loại và liên tục

Nhược điểm: - Dễ bị quá khớp (overfitting)

- Hạn chế với trường có thuộc tính số, nhiễu

Ví dụ minh họa

Xây dựng cây từ tập dữ liệu sau:

Ví dụ minh họa

Bước 2: Tính Gain cho từng thuộc tính Thuộc tính “Quang cảnh” --> Gain(S, Quang cảnh)

Ví dụ minh họa

Bước 3: Xác định thuộc tính làm nút gốc

Ví dụ minh họa

Bước 5: Tính Gain cho từng thuộc tính

Ví dụ minh họa

Bước 5: Tính Gain cho từng thuộc tính

Ví dụ minh họa

Bước 7: Tính Gain cho từng thuộc tính

Ví dụ minh họa

Bước 7: Tính Gain cho từng thuộc tính

Ví dụ minh họa

Bước 8: Xác định thuộc tính làm nút gốc

Ví dụ minh họa

Bước 9: Luật rút ra cây quyết định

Bài tập

Xây dựng cây quyết định từ tập huấn luyện sau

5.4. Ứng dung bài toán phân lớp

Bài toán ứng dụng

5.4. Ứng dung bài toán phân lớp

Ứng dụng Cây quyết định trong bài toán tuyển dụng nhân sự Với các công ty doanh nghiệp việc tuyển dụng nhân sự là việc làm mang tính chất chiến lược, đòi hỏi nhiều thời gian, công sức nhằm tuyển dụng được các ứng viên đáp ứng được yêu cầu công việc. Với các công ty về IT, việc tuyển dụng nhân sự là việc làm thường xuyên, liên tục với số lượng tuyển dụng lớn.

5.4. Ứng dung bài toán phân lớp

Ứng dụng Cây quyết định trong bài toán tuyển dụng nhân sự

• Giả sử một công ty đang cần tuyển nhân viên cho vị trí lập trình viên, vị trí này được tuyển dụng liên tục nhằm đảm bảo nguồn nhân lực cho việc hoàn thành các dự án.

• Mỗi một hồ sơ tuyển dụng được lưu trữ với 6 thuộc tính, bao gồm: Level, Job, N_Company, Top_Train, Project và Result.

• Trong đó có 5 thuộc tính quan trọng ảnh hưởng tới quyết định tuyển dụng của ứng viên và một thuộc tính cho biết kết quả UV đó có được tuyển dụng hay không?

5.4. Ứng dung bài toán phân lớp

Ứng dụng Cây quyết định trong bài toán tuyển dụng nhân sự

Bảng 1. Tập dữ liệu lịch sử tuyển dụng nhân sự (Training data)

Các thuộc tính chính của hồ sơ ứng viên

STT

ID hồ sơ

Result

N_Company

Top_Train

Project

Level

Job

Đại học Đại học Cao đẳng Đại học Đại học Đại học Cao đẳng Đại học Trung tâm tin học Cao đẳng Đại học Trung tâm tin học Đại học

Có Không Không Có Có Không Có Không Có Không Không Có Không

2 1 4 1 2 0 0 1 0 0 3 3 0

Không Có Không Có Có Có Không Có Có Không Có Có Có

Không Có Không Không Không Có Không Có Có Không Không Có Không

Không Có Không Có Có Có Không Không Không Không Có Không Không

0175 0217 0222 0310 0343 0356 0432 0477 0489 0490 0551 0563 0742 0777 0812

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Trung tâm tin học Cao đẳng

Có Không

4 5

Không Có

Không Không

Không Có 58

5.4. Ứng dung bài toán phân lớp

Ứng dụng Cây quyết định trong bài toán tuyển dụng nhân sự

 Giả sử có 3 hồ sơ ứng viên mới nộp vào công ty để đăng ký tính Level, Job,

trị các

thuộc

tuyển dụng, đã biết giá N_Company, Top_Train, Project.

 Dựa trên cơ sở dữ liệu lịch sử tuyển dụng trước đây (Training

data) để xác định giá trị cho thuộc tính Result?

Bảng 2. Dữ liệu hồ sơ ứng viên mới (Testing data)

Các thuộc tính chính của hồ sơ ứng viên

STT Result ID hồ sơ Level Job Top_Train Project N_Compa ny

1 2 3 1001 Đại học 1002 1003 Cao đẳng Trung tâm tin học Có Có Có 3 2 2 Không Có Có Không Có Không Có/không? Có/không? Có/không? 59

5.4. Ứng dung bài toán phân lớp

Thuật toán Iterative Dichotomiser 3 - ID3

• Có nhiều thuật toán để xây dựng cây quyết định: ID3, CART,

J48, C4.5, C5.0…

• Việc lựa chọn thuật toán nào để đạt hiệu quả cao, đáng tin cậy phụ thuộc vào nhiều yếu tố, đặc biệt là kiểu dữ liệu của các thuộc tính.

Bảng 3. Tập dữ liệu đã chuyển đổi về dạng số

Các thuộc tính chính của hồ sơ ứng viên

ảB ng 3. Dữ liệu hồ sơ ứng viên mới (Testing data)

STT

Result

ID hồ sơ

Level

Job

N_Company

Top_Train

Project

1 2 3 ...

0175 0217 0222 ...

2 2 1 …

1 0 0 ...

2 1 4 ...

0 1 0 ...

5.4. Ứng dung bài toán phân lớp

Thuật toán Iterative Dichotomiser 3 - ID3

Ýtưởng của ID3 như sau:  Thực hiện giải thuật tìm kiếm tham lam đối với không gian các cây quyết định có

thể.

 Xây dựng các nút từ trên xuống (Top-Down), bắt đầu từ nút gốc.  Ở mỗi nút, xác định thuộc tính kiểm tra là thuộc tính có khả năng phân loại tốt

nhất.

 Tạo mới một cây con của nút hiện tại cho mỗi giá trị có thể của thuộc tính kiểm tra, và tập dữ liệu đầu vào sẽ được tách thành các tập con tương ứng với các cây con vừa tạo.

 Mỗi thuộc tính chỉ được phép xuất hiện tối đa 1 lần đối với bất kỳ đường đi nào

trong cây.

 Quá trình phát triển cây sẽ tiếp tục cho tới khi:

 Cây quyết định phân loại hoàn toàn các dữ liệu đầu vào.  Tất cả các thuộc tính tập dữ liệu được sử dụng. 61

5.4. Ứng dung bài toán phân lớp

Thuật toán Iterative Dichotomiser 3 - ID3

 Để thuật toán ID3 thực hiện được, cần phải xác định được thứ tự chọn các thuộc tính và chọn được thuộc tính quan trọng nhất cho việc phân lớp ứng với nút đó.

 Tham số được sử dụng để xác định thuộc tính phân loại tốt nhất

cho mỗi bước là Information Gain.

 Tại mỗi nút, thuộc tính được chọn là thuộc tính có Informaiton

Gain đạt giá trị lớn nhất.



Informaiton Gain đo mức độ giảm Entropy nếu chia tập S theo các giá trị của thuộc tính đó.

5.4. Ứng dung bài toán phân lớp

Thuật toán Iterative Dichotomiser 3 - ID3

 Entropy đo mức độ hỗn tạp của một tập, Entropy của tập S đối

với việc phân lớp có n lớp được xác định như sau:

Trong đó:  pi là tỷ lệ các đối tượng trong tập S thuộc vào lớp i, và 0*log20 = 0  Entropy = 0 nếu tất các các đối tượng đều thuộc vào cùng một

lớp.

 Entropy = 1 nếu các đối tượng thuộc vào các lớp có số lượng như

nhau.

 Entropy (0,1) nếu các đối tượng thuộc vào các lớp khác nhau có

số lượng khác nhau.

5.4. Ứng dung bài toán phân lớp

Thuật toán Iterative Dichotomiser 3 - ID3



Information Gain của thuộc tính A đối với tập S được xác định như sau:

Trong đó:  Values(A) là tập giá trị có thể của thuộc tính A.  Sv = {x | x thuộc S, và xa = v}

5.4. Ứng dung bài toán phân lớp

Thuật toán Iterative Dichotomiser 3 - ID3

Các thuộc tính chính của hồ sơ ứng viên

STT

ID hồ sơ

Result

N_Company

Top_Train

Project

Level

Job

Đại học Đại học Cao đẳng Đại học Đại học Đại học Cao đẳng Đại học Trung tâm tin học Cao đẳng Đại học Trung tâm tin học Đại học

Có Không Không Có Có Không Có Không Có Không Không Có Không

2 1 4 1 2 0 0 1 0 0 3 3 0

Không Có Không Có Có Có Không Không Không Không Có Không Không

Không Có Không Không Không Có Không Có Có Không Không Có Không

Không Có Không Có Có Có Không Có Có Không Có Có Có

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0175 0217 0222 0310 0343 0356 0432 0477 0489 0490 0551 0563 0742 0777 0812

Trung tâm tin học Cao đẳng

Có Không

4 5

Không Không

Không Có

Không Có

= 0.92

5.4. Ứng dung bài toán phân lớp

Thuật toán Iterative Dichotomiser 3 - ID3

= 0.81

Các thuộc tính chính của hồ sơ ứng viên

STT

ID hồ sơ

Result

Level

= 0.54

= 0.92

= 0.23

Có Không Không Không Không Có Có Có Có Có Có Có Có Có

15 3 7 10 1 2 4 5 6 8 11 13 9 12 14

812 Cao đẳng 222 Cao đẳng 432 Cao đẳng 490 Cao đẳng 175 Đại học 217 Đại học 310 Đại học 343 Đại học 356 Đại học 477 Đại học 551 Đại học 742 Đại học 489 563 777

Trung tâm tin học Trung tâm tin học Trung tâm tin học Không