SMA 2017 – Lý thuyết tập thô (P4) – Rút trích luật quyết định

rules_extraction

rules_extraction

Trong thực tế, mặc dù đã có trong tay nhiều thông tin nhưng sự nhập nhằng và mơ hồ luôn tồn tại trong quá trình đưa ra quyết định. Trong quyết định, có quyết định an toàn và chắc chắn như bỏ vốn tiết kiệm vào ngân hàng và biết trước lãi suất hằng năm là bao nhiêu. Cũng có quyết định mang tính rủi ro như đầu tư chứng khoán, ta chỉ biết một vài thông tin về công ty hay lịch sử giao dịch quá khứ, cũng có thể đây là công ty mới lên sàn và không hề có bất kỳ thông tin gì. Ngoài ra, còn có những quyết định mang tính đánh đổi như quyết định giữa việc tiếp tục đi làm hay tự startup công ty để tăng nguồn thu nhập cho bản thân, …

Các thuật toán Machine learning bạn từng biết như Decision tree, Association rules, … cũng hỗ trợ ra quyết định. Trong bài viết này, ta hãy thử tìm hiểu lý thuyết tập thô có giúp cho chúng ta tìm ra quyết định chính xác và phù hợp hay không.

Ví dụ rút trích luật từ bảng quyết định

Ta sẽ đi từ ví dụ rồi mới quay lại ký hiệu toán học. Lấy ví dụ sự sụt giảm thân nhiệt sau khi gây mê (Grzymala-Busse, 1992).

(Obj.s) Temperature Hemoglobin Blood-Pressure Oxygen-Saturation Comfort
1 low fair low fair low
2 low fair normal poor low
3 normal good low good low
4 normal good low good medium
5 low good normal good medium
6 low good normal fair medium
7 normal fair normal good medium
8 normal poor high good very-low
9 high good high fair very-low

Từ bảng trên ta có:

U = \{1,2,3,4,5,6,7,8,9\}: tập đang xét.
C = \{Temperature,Hemoglobin,Blood-Pressure,Oxygen-Saturation\}: tập thuộc tính điều kiện.
d = Comfort: thuộc tính quyết định.
U/C = \{1, 2, \{3,4\}, 5, 6, 7, 8, 9\}: tập hạt cơ sở.

Lớp quyết định:

  • Y1 = (d = low) = \{1,2,3\}
  • Y2 = (d = medium) = \{4,5,6,7\}
  • Y3 = (d = high) = \{8,9\}

Ta có công thức tổng quát cho xấp xỉ dưới (miền dương POS), xấp xỉ trên (miền âm NEG), và miền biên BND:

\underline{C} \equiv \bigcup \{Y \in U/C | Y \subseteq X\}
\overline{C} \equiv \bigcup \{Y \in U/C | Y \cap X \ne \phi\}
BND_C(X) \equiv \overline{C} - \underline{C}

Ta lập thành bảng tương ứng:

Lớp quyết định Xấp xỉ dưới Xấp xỉ trên
(d = low) \{1,2\} \{1,2,3,4\}
(d = medium) \{5,6,7\} \{3,4,5,6,7\}
(d = very-low) \{8,9\} \{8,9\}

Luật quyết định r sẽ có dạng giá trị ghi nhận (trái), kết luận nhận được (phải). Dưới đây là một trong các luật có thể rút trích ra được từ hệ thông tin cho trước.

r: if (Hemoglobin=good) \wedge (Oxygen-Saturation=good) then (Comfort = low) \vee (Comfort = medium)

Quay lại các ký hiệu Toán học

Đặt T = (U, C \cup D) là bảng quyết định (D = \{d\}) và K là một khái niệm quyết định nằm trong U/C.

Khái niệm quyết định này sẽ phủ toàn bộ tập L cặp thuộc tính – giá trị, được định nghĩa như sau:

[L] \equiv \bigcap_{c \in L} [c]. Trong đó:

  • c = (a = v), a \in A \cup D
  • v \in V_a
  • [c] = \{x \in U: x(a) = v\}
  • [L]_K^{+} = [L] \cap K
  • [L]_K^{-} = [L] \cap (U \setminus K)

(a \in C = v \in V_a): biểu diễn cơ sở của cặp thuộc tính – giá trị. Ví dụ:
a = Temp \in C; (Temp = low) \to L = \{u1,u2,u5,u6\}
a =Blood-Pressure \in C; (Blood-Pressure =normal) \to L = \{u2,u5,u6,u7\}
L = [(Temp = low) \wedge (Blood-Pressure = normal)]

Luật quyết định r (mô tả một phần K) có dạng:

  • if L then (d = \alpha) (luật chắc chắn)
  • if L then (d = \alpha_1 \vee \alpha_2 \vee ... \vee \alpha_k) (luật xấp xỉ, không chắc chắn)
  • L = c_1 \wedge ... \wedge c_m; \alpha, \alpha_1, ..., \alpha_k \in V_d

Luật r discriminant (biệt thức) trong K phải biểu diễn chính xác (xấp xỉ dưới =xấp xỉ trên). Thứ tự tìm cái luật lớn nhất, xong tìm cái nhỏ hơn, cho đến khi phủ hết thì cái luật cuối cùng nó sẽ ngắn. Luật ở đây là các mẫu dữ liệu có quyết định độc lập. Tìm khi nào phủ đủ cả viên gạch theo nguyên lý tự nhiên luật hấp dẫn.

(1) r \in R là biệt thức
(2) \bigcup_{r \in R}[L] = K,
(3) \not \exists r \in R: R - r thoả (1) và (2).

Ví dụ:

decision_concept_k

decision_concept_k

K = \{2,3,4,5\}, R=\{r1,r2\}
r1: if (Hemoglobin=good) \wedge (Oxygen-Saturation=good) then (Comfort = low) \vee (Comfort = medium)
r2: if (Oxygen-Saturation = poor) then (Comfort = low)

Các trường hợp:

  • [L] \equiv \{3,4,5\} \subseteq K (consistent)
  • [Hemoglobin = good] = \{3,4,5,6,9\} \not \subset K (minimal)
  • [Oxygen-Saturation = good] = \{3,4,5,7,8\} \not \subset K (minimal)

Đánh giá luật

Sức mạnh của luật: số đối tượng thoả điều kiện bên trái.

Strength(r) = |[L]_K^{+}|

Độ dài của luật: lực lượng cặp thuộc tính-giá trị, trong luật vế trái

Length(r) = |L|; L = c_1 \wedge ... \wedge c_m \Rightarrow |L| = m

Độ chính xác của luật: tỉ lệ giữa số mẫu dữ liệu phân lớp đúng so với mẫu dữ liệu đem ra test.

Accuracy = \frac{n_C}{n}
POS/NEG: luật chắc chắn.
BND: luật xấp xỉ không chắc chắn.

Hướng tiếp cận của các nhóm

Grzymala bị vướng mắc ở chỗ: luật xấp xỉ tìm được lại chứa luôn luật chính xác nên dẫn đến nhập nhằng và trùng lặp quá nhiều. Từ đây khó có thể đưa ra quyết định chính xác, ta cần phải triệt tiêu hiện tượng này triệt để. Nếu 3 lớp thì sinh luật dễ, lỡ m lớp quyết định thì ở mặt tổng quát sẽ như thế nào?

Stefanowski: đưa ra hướng tiếp cận trên vùng biên sẽ phân thành lớp tương đương, dùng công thức bù trừ. Vì các luật đã rời nhau thì luật không bị trùng.

Rút trích luật bằng thuật toán LEM2

Input: a set B

Output: a single local covering T of set B

begin

  1. G := B;
  2. T := \phi;
  3. while G \ne \phi
    1. T := \phi;
    2. T(G) := \{t | [t] \cap G \ne \phi\};
    3. while T = \phi or [T] \not \subseteq B
      1. Select a pair t \in T(G) with the highest attribute priority, if a tie occurs, select a pair t \in T(G) such that |[t] \cap G| is maximum; if another tie occurs, select a pair t \in T(G) with the smallest cardinality of [t]; if a further tie occurs, select first pair;
      2. T := T \cup \{t\};
      3. G := [t] \cap G;
      4. T(G) := \{t | [t] \cap G \ne \phi\};
      5. T(G) := T(G) - T;
    4. for each t \in T do
      1. if [T - \{t\}] \subseteq B then T := T - \{t\};
    5. T := T \cup \{T\};
    6. G := B - \cup_{T \in T}[T];
  4. for each T \in T do
    1. if \cup_{S \in T - \{T\}}[S] = B then T := T - \{T\};

end

Review Bayes

Nhắc lại hàm thành viên thô: \mu_X(x) = \frac{|X \cap [x]_R|}{|[x]_R|} \equiv P(X|[x]_R), X \subseteq U, x \in U

Ví dụ: U = \{1,2,3,4,5,6\}, R,X=\{2,3\}

example_rough_membership_function

example_rough_membership_function

Ta có:

\underline{R}(X) = \{x \in U: \mu_X(x) = 1\} = \{2\}
\overline{R}(X) = \{x \in U: \mu_X(x) > 0\} = \{2\} \cup \{1,3\}
BND_{R}(X) = \{x \in U: 0 < \mu_X(x) < 1\} = \{1,3\}

Suy ra:

\mu_X(x) =

  • \frac{1}{2}, x \in X_1 = \{1,3\}
  • 1, x \in X_2 = \{2\}
  • 0, x \in X_3 = \{4,5,6\}

Nhắc lại Bayesian:

Đặt \Omega là tập các trạng thái.
A là tập các hành động có thể xảy ra.
P(\omega | x) là xác suất có điều kiện trạng thái \omega khi cho trước đối tượng x.
\lambda(a|\omega) là hàm mất mát thực hiện hành động a khi cho trước trạng thái \omega .

Hàm mất mát trung bình sẽ là:

Giãn nở vùng biên nghĩa là bỏ bớt đi dấu \vee. Tổn thất trung bình này giảm

R(a | x) = \sum_{\omega \in \Omega}\lambda(a|\omega)P(\omega|x)

Ứng dụng vào tập thô:

bayesian_rough_set_example

bayesian_rough_set_example

K = (U, R) gọi là không gian xấp xỉ, R là quan hệ tương đương và X \subseteq U.
\Omega = \{X, X^C\}
A = \{a_1,a_2,a_3\}. Trong đó, a_1: \to POS_R(X), a_2: \to NEG_R(X), a_3: \to BND_R(X)
\lambda(a_k|X) \equiv \lambda_{kX},\lambda(a_k|X^C) \equiv \lambda_{kX^C}
P(X|[x]_R) = \mu_X(x)
P(X^C|[x]_R) = \mu_{X^C}(x)
x = [x]_R: cục gạch của đối tượng x

Ứng dụng hàm mất mát trung bình:

R(a_1|[x]_R) = \lambda_{1X}P(X|[x]_R)+\lambda_{1A^C}P(X^C|[x]_R)=\lambda_{1A^C} + (\lambda_{1A} - \lambda_{1A^C})\mu_X(x)
R(a_2|[x]_R) = \lambda_{2X}P(X|[x]_R)+\lambda_{2A^C}P(X^C|[x]_R)=\lambda_{2A^C} + (\lambda_{2A} - \lambda_{2A^C})\mu_X(x)
R(a_3|[x]_R) = \lambda_{3X}P(X|[x]_R)+\lambda_{3A^C}P(X^C|[x]_R)=\lambda_{3A^C} + (\lambda_{3A} - \lambda_{3A^C})\mu_X(x)

Quyết định Bayesian sẽ chọn ra luật quyết định có hàm mất mát nhỏ nhất:

(P) if R(a_1|[x]_R) \le min_{j=2,3}R(a_j|[x]_R) \to POS_R(X)
(N) if R(a_2|[x]_R) \le min_{j=1,3}R(a_j|[x]_R) \to NEG_R(X)
(B) if R(a_3|[x]_R) \le min_{j=1,2}R(a_j|[x]_R) \to BND_R(X)

conditional_part_of_p

conditional_part_of_p

Ta có:

  • \lambda_{1X} \le \lambda_{3X} < \lambda_{2X}
  • \lambda_{2X^C} \le \lambda_{3X^C} < \lambda_{1X^C}

Ta có thể viết lại hệ quyết định Bayesian như sau:

(P) if P(X|[x]_R) \ge max\{\gamma, \alpha\} \to POS_R(X)
(N) if P(X|[x]_R) \le min\{\beta, \gamma\} \to NEG_R(X)
(B) if \beta \le P(X|[x]_R) \le \alpha \to BND_R(X)

Trong đó:

\alpha = \frac{\lambda_{1X^C} - \lambda_{3X^C}}{(\lambda_{3X} - \lambda_{3X^C})-(\lambda_{1X} - \lambda_{1X^C})}; \alpha \in (0;1]
\beta = \frac{\lambda_{3X^C} - \lambda_{2X^C}}{(\lambda_{2X} - \lambda_{2X^C})-(\lambda_{3X} - \lambda_{3X^C})}; \beta \in [0;1)
\gamma = \frac{\lambda_{1X^C} - \lambda_{2X^C}}{(\lambda_{2X} - \lambda_{2X^C})-(\lambda_{1X} - \lambda_{1X^C})}; \gamma \in (0;1)

Ta có thể đặt \alpha \ge \beta \to \underline{R}(X) \subseteq \overline{R}(X). Khi \alpha > \beta, ta có \alpha > \gamma > \beta, lúc này luật quyết định sẽ là:

(P) if \mu_X(x) \ge \alpha \to POS_R(X)
(N) if \mu_X(x) \le \beta \to NEG_R(X)
(B) if \beta < \mu_X(x) < \alpha \to BND_R(X) Khi \alpha = \beta, ta có \alpha = \gamma = \beta: (P) if \mu_X(x) > \alpha \to POS_R(X)
(N) if \mu_X(x) < \beta \to NEG_R(X)
(B) if \mu_X(x) = \alpha \to BND_R(X)

Chứng minh:

R(a_1|[x]_R) \le R(a_2|[x]_R)
R(a_1|[x]_R) \le R(a_3|[x]_R)

\lambda_{1X^C} + (\lambda_{1X} - \lambda_{1X^C})\Sigma_X(x) \le \lambda_{2X^C} + (\lambda_{2X} - \lambda_{2X^C}) \Sigma_X(x)
\lambda_{1X^C} + (\lambda_{1X} - \lambda_{1X^C})\Sigma_X(x) \le \lambda_{3X^C} + (\lambda_3X - \lambda_{3X^C}) \Sigma_X(x)

Chú ý:

\lambda_1X^C - \lambda_2X^C \le [(\lambda_2X - \lambda_2X^C) - (\lambda_1X -  \lambda_1X^C)] \Sigma_X(x)
\lambda_1X^C - \lambda_3X^C \le [(\lambda_3X - \lambda_3X^C) - (\lambda_1X - \lambda_1X^C)] \Sigma_X(x)
(\lambda_2X - \lambda_2X^C) - (\lambda_1X - \lambda_1X^C) = (\lambda_2X - \lambda_1X) > 0 + (\lambda_1X^C - \lambda_2X^C) > 0

Cách của Wiziark: thằng nào quá bán thì kéo hẳn vào trong, ngược lại loại ra khỏi X (luật hấp dẫn, biểu quyết số đông): mô hình tập thô độ chính xác thay đổi (\alpha thay đổi) VPRS (Variable Precision Rough Set Model).

(P) \ if \ \Sigma_X(x) \ge 1 - \alpha \to POS(X)
(N) \ if \ \Sigma_X(x) \ge \alpha \to NEG(X)
(B) \ if \ \alpha < \Sigma_X(x) < 1 - \alpha \to BND(X)

Demo

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

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

Run command: Rscript rules_induction.R patients2.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)]
loaded_data <-SF.asDecisionTable(loaded_data, decision.attr = 5, indx.nominal = c(1:5))

rules <- RI.LEM2Rules.RST(loaded_data)
rules

test <- SF.asDecisionTable(loaded_data[3:4, -ncol(loaded_data)])
predict(rules, test)

Output

Loading required package: Rcpp
A set consisting of  4  rules:
1. IF Hemoglobin is fair and Temperature is low THEN  is low;
		(supportSize=2; laplace=0.6)
2. IF Blood.Pressure is normal and Hemoglobin is good THEN  is medium;
		(supportSize=2; laplace=0.6)
3. IF Hemoglobin is fair and Oxygen.Saturation is good THEN  is medium;
		(supportSize=1; laplace=0.5)
4. IF Blood.Pressure is high THEN  is very-low;
		(supportSize=2; laplace=0.6)
  predictions
1      medium
2      medium

Kết

  • Nên cài LEM2 để hiểu thuật toán, thử nghiệm trên cơ sở dữ liệu mới có dữ liệu đẹp. Thường phải cài trước vì tính tay không nổi. Hệ tư vấn cũng sử dụng luật như vậy.
  • Miền biên thì mới xảy ra tranh cãi cho luật xấp xỉ. Luật quyết định sinh ra hoặc cái này hoặc cái kia. Vậy muốn phát triển thêm phải đưa tư tưởng Bayes vào để quyết định.
  • Không như xác suất thống kê phải giả sử, lý thuyết tập thô sử dụng luôn tri thức từ quá khứ.
  • Đưa ra được các luật chính tắc so với tự nhiên còn rất xa vời thực tiễn. Rút trích luật là bài toán NP hard có độ phức tạp quá lớn. Ta chỉ có thể dùng xấp xỉ để giải quyết, tìm thuật toán ngẫu nhiên để lấy ra 1 trong những giải pháp. Cũng giống như khi đi trên mặt biển thì phải cho tôi la bàn nho nhỏ để đi trong một vùng nào đó (Markov chain chẳng hạn). Do Big Data như là vũ trụ bao la, làm sao ta biết được đã khám phá hết một vùng. Do đó, đừng định kiến một phương pháp nào là số 1, phải học hỏi và thử mọi phương pháp hiện có.

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.

Tham khảo thêm:

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