SMA 2017 – Lý thuyết tập thô (P3) – Rút gọn thuộc tính

rough_set_attribute_reduction

rough_set_attribute_reduction

Rút gọn thuộc tính hay lựa chọn thuộc tính là bước quan trọng trong xây dựng mô hình dự đoán. Khi thu thập dữ liệu, ta sẽ tiến hành lấy tất cả thông tin liên quan đến đối tượng cần xét càng nhiều càng tốt. Điều này dẫn đến dữ liệu sẽ bị dư thừa và không phải thuộc tính thông tin nào cũng cần thiết trong mô hình dự đoán. Do đó, việc xác định và loại bỏ được các thuộc tính dư thừa trong tập dữ liệu là điều cần thiết trước khi xây dựng mô hình ML cho hệ thống.

Việc rút gọn hay loại bỏ được các thuộc tính dư thừa giúp cải thiện độ chính xác của mô hình, giảm bớt overfitting, đẩy nhanh quá trình tính toán giúp tiết kiệm tài nguyên và chi phí. Tiếp theo phần 2, bài viết này tập trung vào đánh giá và rút gọn thuộc tính để trích chọn ra những đặc trưng mang mức độ ý nghĩa cao cho hệ thông tin của chúng ta.

Sự phụ thuộc giữa các thuộc tính

Đặt T=(U, C \cup D) là bảng quyết định. Ta nói rằng D phụ thuộc vào C với mức độ k (0 \le k \le 1), ký hiệu là C \Rightarrow_k D

k \equiv \gamma (C,D) = \frac{|POS_C(D)|}{|U|} = \sum_{X \in U/D}\frac{|\underline{C}(X)|}{|U|}

Trong đó, POS_C(D) = \bigcup_{X \in U/D} \underline{C}(X) gọi là miền dương C trên quyết định D. Ở đây, ta ký hiệu \underline{C}(.) để viết tắt cho \underline{app}_C(.)

Từ công thức trên, ta có các tính chất sau:

  • Nếu k = 1 thì ta nói rằng D phụ thuộc hoàn toàn vào C.
  • Nếu k < 1 thì ta nói rằng D phụ thuộc một phần (cấp độ k) vào C.

Ta đặt tất cả các thuộc tính điều kiện không thể loại bỏ trong TCORE(C)

CORE(C) = \cap RED(C)

trong đó, RED(C) là tập tất cả các rút gọn trên C.

Notes: Ta thử loại thuộc tính a ra khỏi bảng, nếu POS_C(D) = POS_{C- a} (D) thì a có thể loại bỏ để rút gọn. CORE cái nhân thuộc tính này là giao hết tất cả các rút gọn mà vẫn không thay thế được thì thuộc tính đó đặc biệt có ý nghĩa trong dữ liệu. Rút gọn phải thoả 2 điều kiện: (1) phải bằng thằng mẹ U, (2) không tồn tại tập con nào bằng U. Tính được CORE sau đó sắp xếp các thuộc tính có ý nghĩa giảm dần để khảo sát.

Rút gọn thuộc tính

Cho hệ thông tin/bảng bệnh nhân như bên dưới (ví dụ trong HongLi Chen, ShanGuo Lv., 2010)

U Headache Muscle-pain Temp Flu
u1 Yes Yes Normal No
u2 Yes Yes High Yes
u3 Yes Yes Very-high Yes
u4 No Yes Normal No
u5 No No High No
u6 No Yes Very-high Yes

Ta có:

D = {d}
\underline{C}(Flu = Yes) = \{u1, u4, u5\}
\underline{C}(Flu = No) = \{u2, u3, u6\}
|POS_C(d)| = |\cup \{Y \in U|d\} \le (Y)| = \sum_{Y \in U|d}|\underline{C}(Y)| = 6 \Rightarrow POS_C(d) = U

C1 = \{Muscle-pain, Temp\}
U/C1=\{\{u1,u4\},\{u2\},\{u3,u6\},\{u5\}\}
POS_C(d)=POS_{C1}(d) = U
RED1 = \{Muscle-pain, Temp\}

C2 = \{Headache, Temp\}
U/C2=\{u1,u2,u3,u4,u5,u6\}
POS_C(d)=POS_{C2}(d) = U
RED2 = \{Headache, Temp\}

Như vậy, ta có CORE = \{\{Headache, Temp\} \cup \{Muscle-pain, Temp\}\} = \{Temp\}. Temp là thuộc tính có ý nghĩa trong bảng quyết định này.

Ma trận phân biệt

Ta dùng ma trận phân biệt để tính toán rút gọn, ký hiệu là M(T)

m(x,y) = \{a \in C: a(x) \ne a(y)\} \ if \ \exists d \in D \ [d(x) \ne d(y)]. \ Otherwise = \Omega \ if \ \forall d \in D \ [d(x) = d(y)].

Trong đó, x, y \in U | x \ or \ y \in POS_C(D). m(x, y) là tập tất cả các thuộc tính điều kiện có thể phân lớp đối tượng xy thành hai lớp khác nhau.

Cho bảng tuần hoàn các nguyên tố hoá học (nhóm Balan)

U a b c e d1 d2
1 (H) s 0 3 1s 1 1A
2 (He) s 8 3 1s 1 8A
3 (Li) s 1 1 2s 2 1A
4 (Sc) d 3 1 3d 4 3B
5 (Fe) d 3 1 3d 4 8B
6 (Zn) d 3 1 3d 4 2B
7 (Y) d 3 1 4d 5 3B
8 (Cd) d 3 1 4d 5 2B
9 (Th) f 5 1 5f 7 3B
10 (Pa) f 5 1 5f 7 3B
  • b: kim loại
  • c: vật chất
  • e: lớp quỹ đạo (orbitan)

Ta tiến hành tính toán bảng rút gọn dựa trên ma trận phân biệt. Vì ma trận đối xứng nên hàng ngang ta sẽ xét từ 1 đến 9, hàng dọc sẽ xét từ 2 đến 10 và chỉ xét ma trận dưới. Giá trị trong ma trận là dãy các thuộc tính khác nhau. C là toàn bộ thuộc tính.

1 2 3 4 5 6 7 8 9
2 b
3 bce bce
4 C C abe
5 C C abe \phi
6 C C abe \phi \phi
7 C C abe e e e
8 C C abe e e e \phi
9 C C abe abe abe abe abe abe
10 C C abe abe abe abe abe abe \Omega

Chung hàng dùng phép hội kí hiệu bằng dấu +, chung dòng dùng phép giao. Hàm bool a1 \vee a2 \vee ... ak ký hiệu là \sum m(x,y); m(x,y) = \phi, khi đó hàm phân biệt được định nghĩa như sau:

f(C) = \prod_{(x,y) \in U x U} \sum m(x,y)

Quay lại bảng phân biệt ta áp dụng hàm phân biệt như bên dưới:

F(C) = b(b+c+e)C(a+b+e)e
= be(b+c+e)(a+b+e)
= be[(b+e)(a+b+e)+c(a+b+e)]
= be(b+e+ac) = be

Như vậy sau khi rút gọn thuộc tính ta được \{b, e\} chính là nguyên nhân/nguyên tố của biểu thức.

U b e d1 d2
1 (H) 0 1s 1 1A
2 (He) 8 1s 1 8A
3 (Li) 1 2s 2 1A
4 (Sc) 3 3d 4 3B
5 (Fe) 3 3d 4 8B
6 (Zn) 3 3d 4 2B
7 (Y) 3 4d 5 3B
8 (Cd) 3 4d 5 2B
9 (Th) 5 5f 7 3B
10 (Pa) 5 5f 7 3B

Demo

Link: https://github.com/ongxuanhong/sma_2017/tree/master/roughset_demo

Libraries: https://github.com/janusza/RoughSets

Run command: Rscript feature_selection.R chemicals.csv

library(RoughSets)

# get data file name argument
args <- commandArgs(TRUE)
data_name <- as.character(args[1])

# loading data to data frame
loaded_data <- read.csv(data_name)
loaded_data <- loaded_data[-c(1)]

# convert to decision table
decision.table <- SF.asDecisionTable(dataset = loaded_data, decision.attr = c(5, 6), indx.nominal = c(1:6))

## build the decision-relation discernibility matrix
res.2 <- BC.discernibility.mat.RST(decision.table, range.object = NULL)

## generate all reducts
reduct <- FS.all.reducts.computation(res.2)

## generate new decision table
new.decTable <- SF.applyDecTable(decision.table, reduct)
new.decTable

Output

Loading required package: Rcpp
Warning message:
In if (decision.attr != ncol(objects)) { :
  the condition has length > 1 and only the first element will be used
   b  e d1 d2
1  0 1s  1 1A
2  8 1s  1 8A
3  1 2s  2 1A
4  3 3d  4 3B
5  3 3d  4 8B
6  3 3d  4 2B
7  3 4d  5 3B
8  3 4d  5 2B
9  5 5f  7 3B
10 5 5f  7 3B

Mức ý nghĩa của thuộc tính

Đặt T = (U, C \cup D) là bảng quyết định và B \subseteq C. Chất lượng phân lớp của B đối với D ký hiệu là r_B(D) (chất lượng của xấp xỉ)

r_B(D) = \frac{|POS_B(D)|}{|U|}

Đặt T = (U, C \cup D) là bảng quyết định và B' \subseteq B \subseteq C. Mức ý nghĩa của B' trong B ký hiệu là s_{D,B} (B')

s_{D,B} (B') = r_B(D) - r_{B - B'}(D)

Ví dụ r_B(D) là thông tin khi có thu nhập người cha, r_{B - B'}(D) là thông tin khi không có thu nhập người cha. Có thu nhập người cha hay không thì không ảnh hưởng đến thu nhập của gia đình thì vai trò của người cha mất đi. Cuối cùng ta có thể sắp xếp theo tầm quan trọng của thuộc tính bằng s. Nếu có diễn giải, hình ảnh minh hoạ hay các ký hiệu toán học nào bất hợp lý các bạn có thể xem slide của thầy để đối chiếu lại.

Phụ lục từ ngữ chuyên ngành

  • Discernibility Matrix: ma trận phân biệt.
  • Reduct: rút gọn.
  • Classification quality: chất lượng phân lớp.
  • Attribute significance: mức ý nghĩa thuộc tính.
Advertisements

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s