Apriori và FP-Growth với tập dữ liệu plants

Trong bài viết này, ta sẽ khai thác các tập phổ biến (frequent itemset) trên tập dữ liệu Plants (sự phân bố của một số loài thực vật ở khu vực Mỹ và Canada). Các công đoạn tiền xử lý được thực hiện bởi Python. Để dễ tiếp cận, các bước khai thác dữ liệu được thực hiện với Weka.

Plant
Plant

Tập dữ liệu: plants
Địa chỉ: http://archive.ics.uci.edu/ml/machine-learning-databases/plants/plants.data
Mô tả: http://archive.ics.uci.edu/ml/machine-learning-databases/plants/stateabbr.txt
Github: https://github.com/ongxuanhong/Apriori-and-FP-growth-with-plant-dataset

Chuyển đổi định dạng file

Tập dữ liệu ban đầu là danh sách phân bố của từng loài cây ở các khu vực.

abelia,fl,nc
abelia x grandiflora,fl,nc
abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi
abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi
abelmoschus moschatus,hi,pr
abies,ak,az,ca,co,ct,ga,id,in,ia,me,md,ma,mi,mn,mt,nv,nh,nm,ny,nc,oh,or,pe,ri,tn,ut,vt,va,wa,wv,wi,wy,ab,bc,lb,mb,nb,nf,nt,ns,nu,on,pe,qc,sk,yt,fraspm
abies alba,nc
abies amabilis,ak,ca,or,wa,bc
abies balsamea,ct,in,ia,me,md,ma,mi,mn,nh,ny,oh,pe,ri,vt,va,wv,wi,ab,lb,mb,nb,nf,ns,nu,on,pe,qc,sk,fraspm
abies balsamea var. balsamea,ct,in,ia,me,md,ma,mi,mn,nh,ny,oh,pe,ri,vt,va,wv,wi,ab,lb,mb,nb,nf,ns,nu,on,pe,qc,sk,fraspm

Ta cần chuyển sang dạng nhị phân để có thể thao tác trên Weka. Ta sử dụng file convert_data2binary.py để chuyển đổi tập dữ liệu ban đầu thành dạng nhị phân. Dựa vào danh sách tên các vùng được viết tắt nằm trong file stateabbr.txt, ta được file ở dạng nhị phân lưu thành file plants_for_weka.csv

  • Mỗi dòng là một loài cây.
  • Cột đầu tiên là tên loài cây, các cột tiếp theo là các vùng phân bố.
  • Giá trị nhị phân gồm y và ?. y đại diện cho sự xuất hiện của cây trong vùng phân bố và ? là không xuất hiện.
name,co,dengl,ca,ga,ct,pr,lb,tx,la,tn,pa,pe,mn,de,dc,hi,yt,me,md,ma,mb,ut,mo,fraspm,mi,nu,mt,qc,ms,va,ab,vi,ak,al,ar,vt,il,in,ia,az,id,nh,ks,nj,nm,nb,nc,nd,ne,nf,ny,ns,nt,ri,nv,wa,bc,wi,wv,fl,wy,on,ok,oh,sk,sc,ky,or,sd
abelia,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?
abelia x grandiflora,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?
abelmoschus,?,?,?,?,y,y,?,?,y,?,?,?,?,?,y,y,?,?,y,?,?,?,?,?,y,?,?,?,y,y,?,y,?,?,?,?,y,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,y,y,?,?
abelmoschus esculentus,?,?,?,?,y,y,?,?,y,?,?,?,?,?,y,?,?,?,y,?,?,?,?,?,y,?,?,?,y,y,?,y,?,?,?,?,y,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,y,y,?,?
abelmoschus moschatus,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?
abies,y,?,y,y,y,?,y,?,?,y,?,y,y,?,?,?,y,y,y,y,y,y,?,y,y,y,y,y,?,y,y,?,y,?,?,y,?,y,y,y,y,y,?,?,y,y,y,?,?,y,y,y,y,y,y,y,y,y,y,?,y,y,?,y,y,?,?,y,?
abies alba,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?
abies amabilis,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,y,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,y,y,?,?,?,?,?,?,?,?,?,?,y,?
abies balsamea,?,?,?,?,y,?,y,?,?,?,?,y,y,?,?,?,?,y,y,y,y,?,?,y,y,y,?,y,?,y,y,?,?,?,?,y,?,y,y,?,?,y,?,?,?,y,?,?,?,y,y,y,?,y,?,?,?,y,y,?,?,y,?,y,y,?,?,?,?
abies balsamea var. balsamea,?,?,?,?,y,?,y,?,?,?,?,y,y,?,?,?,?,y,y,y,y,?,?,y,y,y,?,y,?,y,y,?,?,?,?,y,?,y,y,?,?,y,?,?,?,y,?,?,?,y,y,y,?,y,?,?,?,y,y,?,?,y,?,y,y,?,?,?,?

Quan sát tập dữ liệu

Đầu tiên, ta dùng Weka để nạp dữ liệu plants_for_weka.csv vào chương trình như hình dưới. Ở tab Preprocessing, ta click vào nút Open files. Sau đó, tìm đến nơi lưu fileplants_for_weka.csv ban nãy và click Open (lưu ý: Files of Type ta chọn CSV data file (*.csv)).

Load plant to Weka
Load plant to Weka

Quan sát tập dữ liệu plants_for_weka.csv ta có những thông tin cơ bản sau:

  • Tổng số các loài cây: 34781
  • Số lượng vùng phân bố: 69

Thực thi file find_min_max_plants_of_states.py ta có kết quả sau

{'percent_min': 0.5203990684569161, 'state_min': 'pa', 'state_max': 'ca', 'num_min': 181, 'num_max': 11676, 'percent_max': 33.570052614933445}
  • Vùng phân bố có ít loài cây nhất: pa (Pennsylvania) 181 (0.52%).
  • Vùng phân bố có nhiều loài cây nhất: ca (California) 11676 (33.57%).

Thực thi file find_avg_plants_each_state.py ta có kết quả sau

Average plants each state:  4346
  • Số loài cây trung bình phân bố trên từng vùng: 4346

Tiến hành khai thác tập phổ biến (frequent itemset)

Chúng ta chuẩn bị áp dụng giải thuật Apriori trên dữ liệu này, giả sử khi khai thác tập phổ biến và luật kết hợp ta chỉ quan tâm đến các vùng mà một loài cây có xuất hiện ở đó (các giá trị ‘y’) dữ liệu được xem như dữ liệu giao dịch. Giải thuật Apriori trong Weka khi thực hiện sẽ bỏ qua các giá trị thiếu. Thuộc tính đầu tiên (tên loài cây) không cần thiết trong bài toán khai thác tập phổ biến, ta có thể xóa nó đi.

Apriori

Trong tab Associate ta chọn Associator là phương pháp Apriori. Ta sử dụng thuật toán Apriori trong Weka để khai thác tất cả tập hạng mục có độ phổ biến (thông số lowerBoundMinSupport) từ 0.1 trở lên.

Apriori parameter
Apriori parameter
Association Rules
Association Rules

Nhấn nút Start để bắt đầu chạy thuật toán Apriori. Sau khi hoàn tất, ta được kết quả như bên dưới:

Apriori
Apriori

Kết quả phát sinh được các tập phổ biến

Generated sets of large itemsets:

Size of set of large itemsets L(1): 49
Size of set of large itemsets L(2): 167
Size of set of large itemsets L(3): 120
Size of set of large itemsets L(4): 25
Size of set of large itemsets L(5): 2

Ta có thể tổng hợp thành bảng sau

Kích thước Số lượng
1 hạng mục 49
2 hạng mục 167
3 hạng mục 120
4 hạng mục 25
5 hạng mục 2

Ngoài ra, ta còn thu được top 10 tập luật phổ biến

Best rules found:

 1. ct=y ma=y nj=y 3562 ==> ny=y 3524    conf:(0.99)
 2. tn=y md=y nc=y 3531 ==> va=y 3489    conf:(0.99)
 3. ct=y pe=y nj=y 3618 ==> ny=y 3571    conf:(0.99)
 4. ga=y va=y al=y sc=y 3579 ==> nc=y 3529    conf:(0.99)
 5. ga=y va=y sc=y 3882 ==> nc=y 3825    conf:(0.99)
 6. ms=y al=y nc=y sc=y 3572 ==> ga=y 3519    conf:(0.99)
 7. nj=y ny=y oh=y 3556 ==> pe=y 3502    conf:(0.98)
 8. ct=y pe=y ma=y 3784 ==> ny=y 3726    conf:(0.98)
 9. pe=y ma=y nj=y 3699 ==> ny=y 3640    conf:(0.98)
10. ga=y md=y nc=y 3551 ==> va=y 3484    conf:(0.98)

FP-Growth

Tương tự, ta có thể sử dụng thuật toán FP-Growth trong Weka để khai thác tất cả các luật kết hợp. Với độ tin cậy (Confidence từ menu sổ xuống metricType) từ 0.95 (thông số minMetric) trở lên.

FP-Growth parameter
FP-Growth parameter

Nhấn nút Start để bắt đầu chạy thuật toán FP-Growth. Sau khi hoàn tất, ta được kết quả như bên dưới:

FPGrowth
FPGrowth

Ta có thể tổng hợp thành bảng sau

Tập hạng mục phổ biến Số lượng luật
ma=y, nj=y, ct=y 3562
nc=y, md=y, tn=y 3531
pe=y, nj=y, ct=y 3618
ga=y, al=y, va=y, sc=y 3579
ga=y, va=y, sc=y 3882
nc=y, al=y, sc=y, ms=y 3572
ny=y, nj=y, oh=y 3556
pe=y, ma=y, ct=y 3784
pe=y, ma=y, nj=y 3699
ga=y, nc=y, md=y 3551

Kết luận

Qua bài viết này, ta mượn cấu trúc tập dữ liệu Plant để minh họa phương pháp khai thác các tập phổ biến trong thực tế. Tương tự, đối với các tập dữ liệu giao dịch trong siêu thị (chứa danh sách mã sản phẩm trong từng giao dịch), ta có thể áp dụng một trong hai phương pháp này để giúp triển khai các chính sách kinh doanh sản phẩm được tốt hơn.

Advertisements

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s