Chương phân lớp web các kỹ thuật phân lớp



tải về 0.93 Mb.
Chuyển đổi dữ liệu12.11.2017
Kích0.93 Mb.
#1509

Chương 7. PHÂN LỚP WEB

Các kỹ thuật phân lớp

  • Các phương pháp cây quyết định

  • Các phương pháp dựa trên luật

  • Rule-based Methods

  • Các phương pháp Bayes «ngây thơ» và mạng tin cậy Bayes

  • Các phương pháp máy vector hỗ trợ

  • Support Vector Machines

  • Lập luận dưa trên ghi nhớ

  • Các phương pháp mạng nơron

  • Neural Networks

  • Một số phương pháp khác

Phân lớp cây quyết định

  • Mô hình phân lớp là cây quyết định

  • Cây quyết định

  • Gốc: tên thuộc tính; không có cung vào + không/một số cung ra

  • Nút trong: tên thuộc tính; có chính xác một cung vào và một số cung ra (gắn với điều kiện kiểm tra giá trị thuộc tính của nút)

  • Lá hoặc nút kết thúc: giá trị lớp; có chính xác một cung vào + không có cung ra.

  • Ví dụ: xem trang tiếp theo

  • Xây dựng cây quyết định

  • Phương châm: “chia để trị”, “chia nhỏ và chế ngự”. Mỗi nút tương ứng với một tập các ví dụ học. Gốc: toàn bộ dữ liệu học

  • Một số thuật toán phổ biến: Hunt, họ ID3+C4.5+C5.x

  • Sử dụng cây quyết định

  • Kiểm tra từ gốc theo các điều kiện

Ví dụ cây quyết định và sử dụng




Kết luận: Gán giá trị YES vào trường Cheat cho bản ghi

Ví dụ cây quyết định phân lớp văn bản

  • Phân lớp văn bản vào lớp AI : trí tuệ nhân tạo

  • Dựa vào các từ khóa có trong văn bản: System, Process, Timetable (Phân tích miền ứng dụng)



Dựng cây quyết định: thuật toán Hunt

  • Thuật toán dựng cây quyết định sớm nhất, đệ quy theo nút của cây, bắt đầu từ gốc

  • Input

  • Cho nút t trên cây quyết định đang được xem xét

  • Cho tập các ví dụ học Dt.

  • Cho tập nhãn lớp (giá trị lớp) y1, y1, … yk. (k lớp)

  • Output

  • Xác định nhãn nút t và các cung ra (nếu có) của t

  • Nội dung

  • 1: Nếu mọi ví dụ trong Dt đều thuộc vào một lớp y thì nút t là một lá và được gán nhãn y.

  • 2: Nếu Dt chứa các ví dụ thuộc nhiều lớp thì

  • 2.1. Chọn 1 thuộc tính A để phân hoạch Dt và gán nhãn nút t là A

  • 2.2. Tạo phân hoạch Dt theo tập giá trị của A thành các tập con

  • 2.3. Mỗi tập con theo phân hoạch của Dt tương ứng với một nút con u của t: cung nối t tới u là miền giá trị A theo phân hoạch, tập con nói trên được xem xét vơi u tiếp theo. Thực hiện thuật toán với từng nút con u của t.

Ví dụ: thuật toán Hunt

  • Giải thích

  • - Xuất phát từ gốc với 10 bản ghi

  • Thực hiện bước 2: chọn thuộc tính Refund có hai giá trị Yes, No. Chia thành hai tập gồm 3 bản ghi có Refund = Yes và 7 bản ghi có Refund = No

  • Xét hai nút con của gốc từ trái sang phải. Nút trái có 3 bản ghi cùng thuộc lớp Cheat=No (Bước 1) nên là lá gán No (Don’t cheat). Nút phải có 7 bản ghi có cả No và Yes nên áp dụng bước 2. Chọn thuộc tính Marital Status với phân hoạch Married và hai giá trị kia…

Thuật toán cây quyết định ID3



Rút gọn cây

  • Phân chia tập dữ liệu dựa trên việc kiểm tra các thuộc tính làm tối ưu hóa chiến lược xác định

  • Vấn đề cần giải quyết

  • Xác định cách phân chia tập dữ liệu

  • Cách xác định điều kiện kiểm tra thuộc tính

  • Cách xác định cách chia tốt nhất

  • Theo một số độ đo

  • Khi nào thì dừng phân chia (bước 2)

  • Tất cả các dữ liệu thuộc về cùng một lớp

  • Tất cả các dữ liệu có giá trị “tương tự nhau”

  • Ràng buộc dừng phân chia khác: (i) số lượng dữ liệu nhỏ thua ngưỡng cho trước, (ii) test khi-bình phương cho thấy phân bố lớp không phụ thuộc các thuộc tính hiện có; (iii) nếu phân chia không cải thiện chất lượng

Thuộc tính tốt nhất: Độ đo Gini

  • Bước 4.1. chọn thuộc tính A tốt nhất gán cho nút t.

  • Tồn tại một số độ đo: Gini, Information gain…

  • Độ đo Gini

  • Đo tính hỗn tạp của một tập ví dụ mẫu

  • Công thức tính độ đo Gini cho nút t:

  • Trong đó p(j|t) là tần suất liên quan của lớp j tại nút t

  • Gini (t) lớn nhất = 1-1/nc (với nc là số các lớp tại nút t): khi các bản ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, không có phân biệt giữa các lớp

  • Gini (t) nhỏ nhất = 0 khi tất cả các bản ghi thuộc một lớp duy nhất.

  • Ví dụ: Bốn trường hợp

Chia tập theo độ đo Gini

  • Dùng trong các thuật toán CART, SLIQ, SPRINT

  • Khi một nút t được phân hoạch thành k phần (k nút con của t) thì chất lượng của việc chia tính bằng

trong đó

  • n là số bản ghi của tập bản ghi tại nút t,

  • .ni là số lượng bản ghi tại nút con I (của nút t).

Chia tập theo độ đo Gini: Ví dụ

  • Tính toán GINI cho Refund (Yes, No), Marital Status (Single&Divorced, Married) và Taxable Income (<80K,  80K).

  • Refund: 3/10 * (0) + 7/10 * (1-(3/7)2 – (4/7)2) = 7/10*(24/49) = 24/70

  • Marital Status: 4/10 * 0 + 6/10 * (1- (3/6) 2 – (3/6) 2) = 6/10 * ½ = 3/10

  • Taxable Income: thuộc tính liên tục cần chia khoảng (tồn tại một số phương pháp theo Gini, kết quả 2 thùng và 80K là mốc)

3/10 * (0) + 7/10 * (1-(3/7)2 – (4/7)2) = 7/10*(24/49) = 24/70

Như vậy, Gini của Refund và Taxable Income bằng nhau (24/70) và lớn hơn Gini của Marital Status (3/10) nên chọn Marital Status cho gốc cây quyết định !

Chọn thuộc tính: Information Gain

  • Độ đo Information Gain

  • Thông tin thu được sau khi phân hoạch tập ví dụ

  • Dùng cho các thuật toán ID3, họ C4.5

  • Entropy

  • Công thức tính entropy nút t:

  • Trong đó p(j|t) là tần suất liên quan của lớp j tại nút t

  • độ không đồng nhất tại nút t.

  • Entropy (t) lớn nhất = log (nc) (với nc là số các lớp tại nút t): khi các bản ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, không có phân biệt giữa các lớp

  • Entropy (t) nhỏ nhất = 0 khi tất cả các bản ghi thuộc một lớp duy nhất.

  • Lấy loga cơ số 2 thay cho loga tự nhiên

  • Tính toán entropy (t) cho một nút tương tự như Gini (t)

Chọn thuộc tính: Information Gain

  • Độ đo Information Gain

  • Trong đó, n là số lượng bản ghi tại nút t, k là số tập con trong phân hoạch, ni là số lượng bản ghi trong tập con thứ i.

  • Độ đo giảm entropy sau khi phân hoạch: chọn thuộc tính làm cho Gain đạt lớn nhất.

  • C4.5 là một trong 10 thuật toán KPDL phố biến nhất.

  • Hạn chế: Xu hướng chọn phân hoạch chia thành nhiều tập con

  • Cải tiến

  • Dùng GainRatio để khắc phục xu hướng chọn phân hoạch nhiều tập con

  • Áp dụng: Tự tiến hành

Phân lớp dựa trên luật

  • Giới thiệu

  • Phân lớp các bản ghi dựa vào tập các luật “kiểu” if … then

  • Luật

  • Luật: <điều kiện>  y

Trong đó:

<điều kiện> là sự kết nối các thuộc tính (còn gọi là tiên đề/điều kiện của luật: LHS bên trái)

y là nhãn lớp (còn gọi là kết quả của luật: RHS bên phải).

  • Ví dụ

Refund = ‘Yes”  Cheat = “No”

(Refund = “No”)  (Marital Status = “Married”)  Cheat = “No”

  • Sử dụng luật

  • Một luật được gọi là “bảo đảm” thể hiện r (bản ghi) nếu các thuộc tính của r đáp ứng điều kiện của luật.

  • Khi đó, vế phải của luật cũng được áp dụng cho thể hiện.

Xây dựng luật phân lớp

  • Giới thiệu

  • Trực tiếp và gián tiếp

  • Trực tiếp

  • Trích xuất luật trực tiếp từ dữ liệu

  • Ví dụ: RIPPER, CN2, Holte’s 1R

  • Trích xuất luật trực tiếp từ dữ liệu

  • Bắt đầu từ một tập rỗng

  • Mở rộng luật bằng hàm Học_một_luật

  • Xóa mọi bản ghi “bảo đảm” bởi luật vừa được học

  • Lặp các bước 2-3 cho đến khi gặp điều kiện dừng

  • Gián tiếp

  • Trích xuất luật từ mô hình phân lớp dữ liệu khác, chẳng hạn, mô hình cây quyết định, mô hình mạng nơ ron, …

  • Ví dụ:C4.5Rule

Mở rộng luật: một số phương án

  • Sử dụng thống kê

  • Thống kê các đặc trưng cho ví dụ

  • Tìm đặc trưng điển hình cho từng lớp

  • Thuật toán CN2

  • Khởi đầu bằng liên kết rỗng: {}

  • Bổ sung các liên kết làm cực tiểu entropy: {A}, {A, B}…

  • Xác định kết quả luật theo đa số của các bản ghi đảm bảo luật

  • Thuật toán RIPPER

  • Bắt đầu từ một luật rỗng: {}  lớp

  • Bổ sung các liên kết làm cực đại lợi ích thông tin FAIL

  • R0: {} => lớp (luật khởi động)

  • R1: {A} => lớp (quy tắc sau khi thêm liên kết)

  • Gain (R0, R1) = t [log (p1 / (p1 + n1)) - log (p0 / (p0 + n0))]

  • với t: số thể hiện đúng đảm bảo cả hai R0 và R1

  • p0: số thể hiện đúng được bảo đảm bởi R0
  • n0: số thể hiện sai được đảm bảo bởi R0
  • P1: số thể hiện đúng được bảo đảm bởi R1
  • n 1: số trường hợp sai được đảm bảo bởi R1

Luật phân lớp: từ cây quyết định



Sinh luật gián tiếp: C4.5rules

  • Trích xuất luật từ cây quyết định chưa cắt tỉa

  • Với mỗi luật, r: A → y

  • Xem xét luật thay thế r’: A’ → y, trong đó A’ nhận được từ A bằng cách bỏ đi một liên kết

  • So sánh tỷ lệ lỗi r so với các r’

  • Loại bỏ các r’ có lỗi thấp hơn r

  • Lặp lại cho đến khi không cải thiện được lỗi tổng thể

  • Thay thế sắp xếp theo luật bằng sắp xếp theo tập con của luật (thứ tự lớp)

  • Mỗi tập con là một tập các luật với cùng một kết quả (lớp)

  • Tính toán độ dài mô tả của mỗi tập con

  • Độ dài mô tả = L(lỗi) + g* L(mô hình)

  • g : tham số đếm sự hiện diện của các thuộc tính dư thừa trong một tập luật (giá trị chuẩn, g=0.5)

C4.5rules: Ví dụ



Phân lớp Bayes

  • Giới thiệu

  • Khung xác suất để xây dựng bộ phân lớp

  • Xác suất có điều kiện

  • Hai biến cố A và C

  • Định lý Bayes:

  • P(c|x) = P(x|c).P(c)/P(x)

  • P(x) bằng nhau cho tất cả các lớp

  • Tìm c sao cho P(c|x) lớn nhất Tìm c sao cho P(x|c).P(c) lớn nhất

  • P(c): tần suất xuất hiện của các tài liệu thuộc lớp c

  • Vấn đề: làm thế nào để tính P(x|c)?

Định lý Bayes: Ví dụ

  • Một bác sỹ biết

  • Bệnh nhân viêm màng não có triệu chứng cứng cổ S|M: 50%

  • Xác suất một bệnh nhân bị viêm màng não M là 1/50.000

  • Xác suất một bệnh nhân bị cứng cổ S là 1/20

  • Một bệnh nhân bị cứng cổ hỏi xác suất anh/cô ta bị viêm màng não ?

Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining (Chapter 5: Classification: Alternative Techniques),  Addison Wesley, 2005, http://www.cs.uu.nl/docs/vakken/dm/dmhc13.pdf

  • Các thuộc tính (bao gồm nhãn lớp) là các biến ngẫu nhiên.

  • Cho một bản ghi với các giá trị thuộc tính (A1, A2, …, An)

  • Cần dự báo nhãn c

  • Tìm lớp c để cực đại xác suất P(C|A1, A2, …, An)

  • Có thể tính xác suất P(C|A1, A2, …, An) từ dữ liệu học?

Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining (Chapter 5: Classification: Alternative Techniques),  Addison Wesley, 2005, http://www.cs.uu.nl/docs/vakken/dm/dmhc13.pdf

Phân lớp Naïve Bayes

  • Giả thiết Naïve Bayes:

  • giả thiết độc lập: xác suất xuất hiện của thuộc tính trong đối tượng độc lập với ngữ cảnh và vị trí của nó trong đối tượng:

  • Cho

  • Tập ví dụ Dexam = Dlearn + Dtest

  • Tập từ vựng V = {f1, f2, …, f||V||}

  • Tập lớp C= {C1, C2, …, Cn} với mỗi Ci một ngưỡng i > 0

  • Tính xác suất tiên nghiệm

  • Trên tập ví dụ học Dlearn

  • p(Ci) = Mi/M, M= ||Dlearn||, Mi = ||Y  Dlearn / Y Ci||

  • Xác suất một đặc trưng fj thuộc lớp C:

  • Cho dữ liệu X mới

  • Tính xác suất hậu nghiệm



  • Nếu P(C|X) > C

thì X  C!

TF (fj| X): số lần đặc trưng fj xuất hiện trong X

Phân lớp k-NN

  • Cho trước

  • Một tập D các đối tượng dữ liệu biểu diễn bản ghi các đặc trưng

  • Một đo đo khoảng cách (Ơcơlit) hoặc tương tự (như trên)

  • Một số k > 0 (láng giềng gần nhất

  • Phân lớp đối tượng mới Xc được biểu diễn

  • Tính khoảng cách (độ tương tự) từ X tới tất cả dữ liệu thuộc D

  • Tìm k dữ liệu thuộc D gần X nhất

  • Dùng nhãn lớp của k-láng giềng gần nhất để xác định nhãn lớp của X: nhãn nhiều nhất trong k-láng giềng gần nhất



Phân lớp k-NN: Ví dụ

  • Ba trường hợp như hình vẽ

  • 1-NN: Chọn lớp “-”: láng giềng có nhãn “-” là nhiều nhất

  • 2-NN: Chọn lớp “-”: hai nhãn có số lượng như nhau, chọn nhãn có tổng khoảng cách gần nhất

  • 3-NN: Chọn lớp “+”: láng giềng có nhãn “+” là nhiều nhất



Thuật toán SVM

  • Thuật toán máy vector hỗ trợ (Support Vector Machine – SVM): được Corters và Vapnik giới thiệu vào năm 1995.

  • SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có số chiều lớn (như các vector biểu diễn văn bản).

  • Tập dữ liệu học: D= {(Xi, Ci), i=1,…n}

  • Ci Є {-1,1} xác định dữ liệu dương hay âm

  • Tìm một siêu phẳng: αSVM .d + b phân chia dữ liệu thành hai miền.

  • Phân lớp một tài liệu mới: xác định dấu của

  • f(d) = αSVM .d + b

  • Thuộc lớp dương nếu f(d) > 0

  • Thuộc lớp âm nếu f(d) < 0



  • Nếu dữ liệu học là tách rời tuyến tính:

  • Cực tiểu:

  • Thỏa mãn:

  • Nếu dữ liệu học không tách rời tuyến tính: thêm biến {ξ1… ξn}:

  • Cực tiểu:

  • Thỏa mãn:




tải về 0.93 Mb.

Chia sẻ với bạn bè của bạn:




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©tieuluan.info 2022
được sử dụng cho việc quản lý

    Quê hương