Thuật toán Apriori – T.m tập mục phổ biến

• Ý nghĩa: tìm tập mục phổ biến

• Đầu vào:

• Cơ sở dữ liệu D.

• Ngưỡng độ hỗ trợ cực tiểu của các tác vụ hay minsupp.

• Đầu ra: Tập các tập mục phổ biến.

Thuật toán Apriori- Nội dung

1. Quét cơ sở dữ liệu để tìm các tập 1 mục phổ biến L1.

2. For (k=2; Lk+1 #; k++) {

3. Ck=apriori_gen(Lk-1, minsupp); // Sinh các ứng cử từ Lk-1

4. For ( mỗi tác vụ t trong D) {// Quét D để đếm

5. Ct=subset(Ck,t);// lấy tập con của t mà là các ứng cử trong Ck

6. for ( mỗi ứng cử c khong thuoc Ct

7. c.count ++; // Tăng đếm cho c một đơn vị

8. }

9. Lk= {c khong thuoc Ck sao cho: c.count  minsupp}

10. }

11.Return L=kLk

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

- Dựa trên cây quyết định

- Dựa trên luật

- Naive Bayes

- Dựa trên thể hiện

- Mạng nơron

- SVM (support vector machine)

- Tập thô

1. CÂY QUYẾT ĐỊNH _Độ đo (En tropy)

• Độ lợi thông tin - Entropy (information gain): ID3/C4.5

• Chi tiết :

 Chọn thuộc tính có độ lợi thông tin cao nhất

 D: tập huấn luyện

 C i,D : tập các mẫu của D thuộc lớp C i với i = {1, …, m}

 |C i,D|, |D| : lực lượng của tập C i,D và D tương ứn g

 pi là xác suất để một mẫu bất kỳ của D thuộc về lớp C i

 Thông tin kỳ vọng để phân lớp một mẫu trong D là :

Thông tin cần thiết để phân chia D theo thuộc tính A :

 Độ lợi thông tin (information gain) dựa trên phân chia

theo thuộc tính A :

 Nhận xét: Độ đo Gain có xu hướng thiên vị cho các thuộc

tính có nhiều giá trị  -> Cần chuẩn hóa.

2. CÂY QUYẾT ĐỊNH_Độ đo- Information Gain Ratio: C4.5

 Giải pháp: Chọn thuộc tính có độ đo Gain Ratio lớn nhất.

GainRatio (A) = Gain (A)/SplitInfoA(D)

CÂY QUYẾT ĐỊNH - Thuật toán -Độ đo Gini index (CART, IBM IntelligentMiner

1. Tập huấn luyện D chứa các mẫu của n lớp

• Khi đó: Chỉ mục Gini của tập D, kí hiệu: gini(D)

Trong đó: pj là tần xuất của lớp Cj trong D

·        Chỉ mục Gini của phân chia D theo thuộc

tính A là

CÂY QUY Ế T Đ ỊN H - Đánh giá

 Dễ xây dựng cây

 Phân lớp mẫu mới nhanh

 Dễ d àn g d iễn g iải ch o các cây có k ích thước n h ỏ

 Độ ch ín h xác ch ấp n h ận được so với k ỹ th u ật p h ân lớp

kh ác trên n h iều tập DL đ ơn

Phương pháp dựa trên luật – Luật quy nạp ILA

Bước 1 : Chia bảng có chứa m mẫu thành n bảng con

(ứng với n giá trị của thuộc tính chia lớp)

(Bước 2 đến bước 8 sẽ được lặp lại cho mỗi bảng con)

 Bước 2 : Khởi tạo số lượng thuộc tính kết hợp j=1

 Bước 3 : Xét từng bảng con, tạo danh sách các thuộc

tính kết hợp (phần tử danh sách có j thuộc tính)

 Bước 4 : Với mỗi phần tử trong danh sách trên, đếm

số lần xuất hiện các giá trị của thuộc tính ở các d.ng

chưa đánh dấu của bảng con đang xét, nhưng giá trị

không được xuất hiện ở những bảng con khác.

Chọn phần tử kết hợp đầu tiên có số lần xuất hiện của giá trị

thuộc tính nhiều nhất và đặt tên là max-combination.

Bước 5: Nếu max-combination=0 th. j=j+1 và quay lại

bước 3

 Bước 6: Trong bảng con đang xét, đánh dấu các d.ng

có xuất hiện giá trị của max-combination

 Bước 7: tạo luật

IF AND(thuoc tính=giá trị) (thuộc max-combination)

THEN giá trị của thuộc tính lớp ứng với bảng con đang xét

 Bước 8 :

 Nếu tất cả các d.ng đều đánh dấu

 Nếu c.n bảng con th. chuyển qua bảng con tiếp theo

và lặp lại từ bước 2

 Ngược lại: chấm dứt thuật toán

 Ngược lại (c.n d.ng chưa đánh dấu) th. quay lại bước 4.

PHƯƠNG PHÁP phan lop NAIVE BAYES – Thuật toán

B1: Huấn luyện Naïve Bayes (trên tập DL huấn luyện )

 Lượng giá P(Ci)

 Lượng giá P(Xk|Ci)

B2 : Xnew được gán vào lớp cho giá trị lớn nhất

Để tránh trường hợp giá trị P(Xk|Ci)=0 do không có

mẫu nào trong DL huấn luyện thỏa m.n tử số, ta làm

trơn bằng cách thêm một số mẫu ảo.

• Làm trơn theo Laplace :

PHƯƠNG PHÁP NAIVE BAYES – Thuật toán – Đánh giá

Ưu điểm :

 Dễ dàng cài đặt

 Thời gian thi hành tương tự như cây quyết định

 Đạt kết quả tốt trong phân lớn các trường hợp

Nhược điểm :

 Giả thiết về tính độc lập điều kiện của các thuộc tính

làm giảm độ chính xác

Phân lớp DỰA TRÊN THỂ HiỆN_K_NN

1. Một mẫu mới được gán vào lớp có nhiều mẫu giống

với nó nhất trong số k mẫu gần nhất.

2. Thuật toán xác định lớp cho mẫu mới E:

 Tính khoảng cách giữa E và tất cả các mẫu trong tập

huấn luyện             

 Chọn k mẫu gần nhất với E trong tập huấn luyện

 Gán E vào lớp có nhiều mẫu nhất trong số k mẫu

láng giềng đó (hoặc E nhận giá trị trung b.nh của k mẫu)

Ưu điểm :

 Dễ sử dụng và cài đặt

 Xử l. tốt với dữ liệu nhiễu

Khuyết điểm:

 Cần lưu tất cả các mẫu

 Cần nhiều thời gian để xác định lớp cho một mẫu mới

(cần tính và so sánh khoảng cách đến tất cả các mẫu)

 Phụ thuộc vào giá trị k do người dùng lựa chọn

 Nếu k quá nhỏ th. nhạy cảm với nhiễu

 Nếu k quá lớn th. vùng lân cận có thể chứa các điểm của lớp

khác                

 Thuộc tính phi số ?

II. Gom cum

6.1. Phương pháp phân hoạch

a.Thuật toán K-means

Cho số k, mỗi cụm được biểu diễn bằng giá trị TB của DL

trong cụm

B1: Chọn ngẫu nhiên k đối tượng làm tâm của các cụm.

B2 : Gán từng đối tượng c.n lại vào cụm có tâm cụm gần

nó nhất (dựa trên độ đo khoảng cách Euclide)

B3 : Tính lại giá trị tâm của từng cụm

1. Cho cụm Ki={ti1,ti2,…,tim}, giá trị trung b.nh của cụm là

mi = (1/m)(ti1 + … + tim)

2. Di chuyển tâm cụm về giá trị TB mới của cụm

B4 : Nếu các tâm cụm không có g. thay đổi th. dừng,

ngược lại quay về B2.

Ưu điểm cua K_mean:

 Đơn giản, dễ hiểu, tương đối hiệu quả.

 Các đối tượng tự động gán vào các cụm

 Thường đạt được tối ưu cục bộ.

Hạn chế:

 Thuộc tính phi số không giải quyết được

 Cần xác định số cụm (k) trước

 Tất cả các đối tượng phải gán vào các cụm

 Phụ thuộc vào việc chọn các cụm ở lần đầu tiên

 Gặp vấn đề khi các cụm có kích thước, mật độ khác

nhau hoặc h.nh dáng không phải là h.nh cầu.

 Nhạy cảm với DL nhiễu, cá biệt

b.Thuật toán k-medoids : PAM

Cho số k, mỗi nhóm được biểu diễn bằng một

trong các đối tượng gần tâm cụm nhất.

B1: Chọn ngẫu nhiên k đối tượng gọi là những trọng tâm

của các cụm .

B2: gán từng đối tượng c.n lại vào cụm có trọng tâm cụm

gần nó nhất .

B3: Chọn một đối tượng bất kỳ. Hoán đổi nó với trọng tâm

của nhóm. Nếu chất lượng của các cụm tăng lên th.

quay lại B2. Ngược lại tiếp tục thực hiện B3 cho đến khi

không c.n có sự thay đổi.

So sanh  PAM voi K_mean

1.Thuật toán PAM hiệu quả hơn so với k-means khi có mặt

DL nhiễu, cá biệt.

2. PAM hiệu quả với tập DL nhỏ nhưng không co d.n tốt

với tập DL lớn

6.2. Phương pháp phân cấp

a.Thuật toán AGNES

AGNES (Agglomerative Nesting)

B1: Mỗi đối tượng là một cụm.

B2: Hợp nhất các cụm theo Single Link

(khoảng cách giữa những đối tượng gần nhau nhất trong các cụm là nhỏ nhất)

B3 : Nếu thu được cụm “toàn bộ” th. dừng, ngược lại

quay về B2.

b.Thuật toán DIANA

DIANA (Divisive Analysis)

B1: Tất cả các đối tượng là một cụm.

B2: Chia nhỏ các cụm có khoảng cách giữa những

đối tượng gần nhau nhất trong các cụm là lớn

nhất.

B3: Nếu mỗi nhóm chỉ chứa 1 đối tượng th. dừng,

ngược lại quay về B2.

c.Nhược điểm cua phuong phap phan cap

Tính co dãn thấp: Độ phức tạp là O(n2) với n – số

đối tượng

 Không thể quay lui về bước trước .

 Khó xác định phương pháp tích tụ hay chia nhỏ

 Nhạy cảm với nhiễu, cá biệt

 Gặp vấn đề khi các cụm có kích thước khác nhau và

có hình dáng lồi

 Có xu hướng phân chia các cụm DL lớn

 Tích hợp phương pháp phân cấp với phương pháp phân

hoạch (dựa trên khoảng cách): BIRCH, CURE,

CHAMELEON

6.3.Phương pháp dựa trên mật độ_DBSCAN

Ý. tưởng: Một cụm được xác định như tập các đối tượng có mật

độ liên thông lớn nhất .

Bài toán: Tìm các cụm hình dạng bất kỳ trong CSDL không

gian có nhiễu.

Thuật toán:

B1: Chọn ngẫu nhiên đối tượng p

B2: T.m tất cả các đối tượng có mật độ có thể đạt được từ p

theo Eps, MinPts

B3: Nếu p là đối tượng nòng cốt thì hình thành cụm.

 Nếu p là đối tượng biên (không có đối tượng nào là có mật độ đạt được từ p) th.

DBSCAN xem xét đối tượng tiếp theo trong CSDL.

B4 : Tiếp tục cho đến khi tất cả các đối tượng đều được xử lý.