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ý.
Bạn đang đọc truyện trên: Truyen2U.Pro