SMA 2017 – Lý thuyết tập thô (P1) – Các khái niệm cơ bản

rough_set

rough_set

Đây là những ghi chú của tôi sau khoá học SMA 2017. Tôi xin chia sẻ những gì đã học được qua buổi dạy “Lý thuyết tập thô” của thầy Đặng Phước Huy từ Đại học Đà Lạt. Hơn 40 năm trong nghề và trong mười mấy năm gần đây, thầy đã tìm hiểu về lý thuyết tập thô của Pawlak rất hay, có thể áp dụng vào thống kê rất tốt nên muốn chia sẻ cho chúng ta những ứng dụng của lý thuyết này vào khai thác dữ liệu. Hy vọng những bạn quan tâm có thể áp dụng ngay vào thực tiễn.

Mới đầu thì nghe topic có vẻ hơi “thô” nhưng thật ra không hề thô tý nào. Về ứng dụng thì nó có thể dùng trong rút trích đặc trưng, tối giản hoá tập dữ liệu, rút trích hình mẫu trong dữ liệu, phát sinh luật hỗ trợ ra quyết định, … Thêm vào đó, cách diễn đạt của thầy rất có hồn và dễ hiểu không khô khan như các ký tự toán học trên giấy. Thầy sẽ đi từ ví dụ trước khi quay lại các lập luận toán học nên bạn sẽ cảm thấy dễ hiểu hơn. Các thuật ngữ tiếng Anh, tiếng Việt đều được giải nghĩa và làm rõ để có thể tiếp cận lý thuyết này nhanh nhất. Qua khoá học này, đảm bảo các bạn có thể cài đặt và áp dụng được ngay. Tôi cũng dự định sẽ cài đặt để áp dụng thử vào project hiện tại của mình.

Giới thiệu

Lý thuyết tập thô được Zdzislaw Pawlak phát triển vào những năm 1980s, hỗ trợ và áp dụng vào thống kê rất tốt. Ta nên đọc 2 tác phẩm của Pawlak để đi nhanh nhất thay vì đọc những bài báo gần đây, mặc dù có gần 40 bài nhưng chỉ có 1/4 bài chất lượng, còn lại trình bày rất râu ria và dài dòng.

  • Z. Pawlak, “Rough Sets”, International Journal of Computer and Information Sciences, Vol.11, 341-356 (1982).
  • Z. Pawlak, Rough Sets – Theoretical Aspect of Reasoning about Data, Kluwer Academic Pubilishers (1991).

Lý thuyết tập thô giải quyết được vấn đề đưa ra quyết định cứng nhắc chỉ có 2 chân trị là 0/1 bên logic học, cũng như hơn hẳn các mô hình xấp xỉ dữ liệu khác như hồi quy. Lý thuyết này còn phát hiện được những dị thường trong dữ liệu, xác định được độ mạnh yếu của thuộc tính trong hệ thông tin.

hyperplane

hyperplane

Hồi quy có thể được giải quyết bằng tập thô vì hồi quy xấp xỉ không thể tốt được. Tấm thảm đi qua các dãy núi, mỗi núi có đám mây điểm thì không xấp xỉ chính xác được.

Xuất phát từ ý tưởng triết lý người hói đầu.

Một người đàn ông hói đội tóc giả. Một hôm đang cưỡi ngựa thì một cơn gió nổi lên thổi bay mất bộ tóc giả, những người bên đường nhìn thấy ồ lên cười. Gò cương ngựa lại, anh ta nói : “tôi không giữ được cái tóc giả ở trên đầu tôi cũng chẳng có gì đáng ngạc nhiên bởi vì chủ nhân chính của nó, người mà mớ tóc này mọc cũng đã không thể giữ nó trên đầu mình”.

Ở đây ý nói, triết lý chính xác 0/1 trong logic học có nhiều lỗ hỏng trong việc ra quyết định. Trong thực tế thì mọi việc diễn ra không chính xác và rất mơ hồ. Giả sử để biểu quyết một mệnh đề ta có 1 người gật đầu đồng ý, 2 người lắc đầu không đồng ý, và có 1 người không thể hiện gì cả. Vậy ta sẽ giải quyết thế nào vấn đề này. Từ đây, trong nghiên cứu phải sinh ra các công cụ xử lý tính mơ hồ trong thông tin này trong đó có lý thuyết tập thô.

Ví dụ tập thô

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 Temp Flu
u1 Yes Normal No
u2 Yes High Yes
u3 Yes Very-high Yes
u4 No Normal No
u5 No High No
u6 No Very-high Yes
u7 No High Yes
u8 No Very-high No

Bảng quyết định

DS=(U, C \cup D), C \cap D = \emptyset, C=\{Headache, Temp\}; D=\{Flu\}

  • U: tập đang xét
  • C: tập thuộc tính điều kiện
  • D: thuộc tính quyết định

Quan sát trong bảng có điều gì dị thường không. Ta thấy \{u5,u7\} đều không nhức đầu và thân nhiệt cao nhưng lại chẩn đoán lúc có bệnh, lúc không có bệnh. Tiếp theo, ta có thể phân lớp các bệnh nhân thành những “cục gạch” như hình dưới, ta có lớp hạt tri thức cơ sở.

granular_knowledge_set

granular_knowledge_set

\forall B \subseteq C: định nghĩa một quan hệ tương đương
\forall x,y \in U, x\sim y \iff a(x) = a(y) (\forall a \in B), thuộc tính a chạy trong B

Lớp hạt tri thức cơ sở: U/C=\{\{u1\},\{u2\},\{u3\},\{u4\},\{u5,u7\},\{u6,u8\}\}. Đây chính lớp tương đương. Các phần tử bên trong gọi là hạt (granular), ta có thể xem đây là những viên gạch.

decision_classes_set

decision_classes_set

Lớp quyết định (tri thức quyết định): U/D=\{\{u1,u4,u5,u8\},\{u2,u3,u6,u7\}\}. Đường bao màu xanh là lớp quyết định Flu=No, đỏ là lớp quyết định Flu=Yes. Từ lớp hạt tri thức cơ sở và lớp quyết định, ta có thể xác định tập thô và tập chính xác.

Tập thô (tập không chính xác):

  • X1=\{u|Flu(u)=No\}=\{u1,u4,u5,u8\}
  • X2=\{u|Flu(u)=Yes\}=\{u2,u3,u6,u7\}

Tập chính xác: X=\{u3,u4,u5,u7\}. Nghĩa là biểu diễn đầy đủ thông tin mà không cần chặt các viên gạch.

Notes: Công thức toán học là như thế, cần phải chính xác và ngắn gọn nhưng lại khiến ta khó hình dung. Tinh thần trong Toán học rất có hồn, như thầy Huy có ví dụ trực quan và dẽ nhớ hơn. Giả sử chúng ta xây nhà có bức tường gồm các viên gạch rất đẹp (không bằng kích thước) gọi là tập U. Ta phân hoạch trên U tập các lớp tương đương đặt là U/C. Lúc này, có một em bé lấy sơn xịch tô lên gạch gọi là X. Khi đó, chủ nhà phải quyết định xem cần phải rút những viên gạch nào ra để vệ sinh bằng 2 bước:

  • Gỡ từng viên nằm hẳn trong X gọi là xấp xỉ dưới của X: \underline{app}_R(X) \equiv \cup \{Y \in U/R | Y \subseteq X\}
  • Gỡ những cục dính líu đến X kể cả cục nằm hẳn bên trong, gọi là xấp xỉ trên của X \overline{app}_R(X) \equiv \cup \{Y \in U/R | Y \cap X \ne \emptyset\}
related_measures

related_measures

Từ 2 điều trên, ta có thể thấy X (lớp quyết định) luôn bị chặn bởi hai tri thức xấp xỉ trên và dưới. Nếu X bằng xấp xỉ dưới hay xấp xỉ trên, ta gọi X là tập chính xác. Tập trên luôn là tập hữu hạn mặc dù trong thế giới Big Data tập này rất lớn. \forall X \subseteq U, \underline{app}_R(X) \subseteq X \subseteq \overline{app}_R(X)

Mô hình tập thô trong hệ thông tin

Với hệ thông tin là bảng bệnh nhân, ta định nghĩa thuộc tính a: U \to V_a, \forall a \in A, trong đó V_a gọi là giá trị của tập thuộc tính a. Công thức này thường dùng để lập luận chứng minh nên quan sát khó và thô, còn trong ứng dụng thì chúng ta chỉ cần nhớ hình ảnh để áp dụng.

Ta không nên nhìn quần áo thô của một người để đánh giá mà hãy nhìn vẻ đẹp bên trong của người đó.

Ví dụ: C=\{Headache, Temp\}, a=Headache: U \to V_{Headache} = \{Yes,No\}; x \mapsto Headache(x)

d \notin C là thuộc tính quyết định, có thể gồm \{d1,d2,d3\}, không nhất thiết phải là d.

\{u5, u7\} có quan hệ bất khả phân trên hệ thông tin đang xét chính là quan hệ tương đương. Đây là triết lý 2 đối tượng phải được phân cùng lớp khi có tập các giá trị thuộc tính như nhau dù cho thuộc tính quyết định có khác nhau đi nữa.

Notes: Giao hai quan hệ tương đương là quan hệ tương đương. Ta có thể tưởng tượng mảnh kính đập vỡ lần một, tiếp tục đập vỡ lần hai là những mảnh gương nhẵn nhất chính là U/C.

Mục đích của lý thuyết tập thô là làm sao tính được sự dị thường và xác định được dị thường nhiều hay ít. Độ chính xác của xấp xỉ bằng lực lượng xấp xỉ dưới chia cho lực lượng xấp xỉ trên, độ chính xác càng ít thì chỉ số càng dần về 0.

\alpha_R(X)=\frac{|\underline{app}_R(X)|}{|\overline{app}_R(X)|}

rough_membership

Hàm thành viên thô là phần giao dính liếu của [x] trong viên gạch chia cho [x] lớp tương đương của miền chứa x.

\mu_X^R(x)=\frac{|[x]_R \cap X|}{|[x]_R|}, khi đó:

  • \underline{app}_R(X)=\{x \in U | \mu_X^R(x) = 1\}
  • \overline{app}_R(X)=\{x \in U | \mu_X^R(x) > 0\}

Ta có các ký hiệu sau:

  • POS_R(X): miền dương theo X, nằm hẳn trong X, là xấp xỉ dưới.
  • NEG_R(X): miền âm theo X, những viên gạch không dính liếu vết sơn, ko dính líu đến X.
  • BND_R(X): là biên của X, nằm ở giữa POS, NEG.
basic_concepts

basic_concepts

POS, NEG là hợp của những viên gạch chính xác. Khi áp dụng vào thực tế, nó sẽ phân ra thành 3 mảnh tách biệt. Vấn đề toán học xảy ra là không biết cái biên này nên nằm trong X hay nằm ngoài hẳn X, ta sẽ đưa ra quyết định thế nào cho phù hợp.

Quay lại ví dụ tập thô ban đầu. Trong thực tế đúng nghĩa một viên gạch vì nó rất lớn, vẽ cục gạch ra cho tập \overline{app}_R(X) và \underline{app}_R(X) để dễ quan sát.

X1 = \{u|Flu(u)=No\} = \{u1,u4,u5,u8\}
X = \{u3,u4,u5,u7\}

Ta có thể thấy \{u1,u4\} là những anh trẻ chắc chắn sẽ mắc bệnh nếu có những triệu chứng được liệt kê. Tuy nhiên, \{u5,u7,u6,u8\} những anh già cũng có chung triệu chứng này nhưng có anh được chẩn đoán như thế này, có anh được chẩn đoán như thế kia.

\underline{app}_R(X1)=\{u1,u4\}
\overline{app}_R(X1)=\{u1,u4,u5,u7,u6,u8\}
\underline{app}_R(X1) \subseteq X1 \subseteq \overline{app}_R(X1)

Bên tập thô kinh điển tính độ chính xác của xấp xỉ như sau: \alpha_R(X1)=\frac{|\underline{app}_R(X1)|}{|\overline{app}_R(X1)|}=\frac{2}{6}=\frac{1}{3}

Bên phân tích toán hạt ta có\overline{app}_R(X1)=\{u1,u4,\{u5,u7\},\{u6,u8\}\}. Khi đó, \alpha_R(X1)=\frac{|\underline{app}_R(X1)|}{|\overline{app}_R(X1)|}=\frac{2}{4}=\frac{1}{2}

Biên là 2 viên gạch bự \{[u5,u7],[u6,u8]\}, 2 thằng này mơ hồ. Nhóm \{u3,u4,u5,u7\} là tập chính xác \underline{app}_R(X) = X = \overline{app}_R(X).

Ta có những tính chất cho tập xấp xỉ, dùng hình ảnh có thể hiểu được những tính chất này. Trong máy tính, các giá trị liên tục phải chuyển sang dạng rời rạc để xử lý. Các tính chất này không cần thiết phải nhớ hết, khi nào cần dùng thì lấy ra sử dụng, để cho đầu óc mình được thoáng để tư duy cái khác.

  • -X = U - X: phần bù của X
  • \underline{app}(X) \subseteq X \subseteq \overline{app}(X)
  • \underline{app}(\ne \emptyset) = \overline{app}(\ne \emptyset), \underline{app}(U) = \overline{app}(U) = U
  • \overline{app} (X \cup Y) = \overline{app}(X) \cup \overline{app}(Y)
  • \underline{app} (X \cap Y) = \underline{app}(X) \cap \underline{app}(Y)
  • X \subseteq Y implies \ \underline{app}(X) \subseteq \underline{app}(Y) and \ \overline{app}(X) \subseteq \overline{app}(Y)
  • \underline{app}(X \cup Y) \supseteq \underline{app}(X) \cup \underline{app}(Y)
  • \overline{app}(X \cap Y) \subseteq \overline{app}(X) \cap \overline{app}(Y)
  • \underline{app}(-X) = -\overline{app}(X)
  • \overline{app}(-X) = -\underline{app}(X)
  • \underline{app}(\underline{app}(X))=\overline{app}(\underline{app}(X))=\underline{app}(X)
  • \overline{app}(\overline{app}(X))=\underline{app}(\overline{app}(X))=\overline{app}(X)

Các trường hợp vùng biên

rough_classifications

rough_classifications

Những viên gạch ở vùng biên là khó chịu nhất, đây là phần ta có thể đi vào cải tiến, hình trên biểu diễn 4 trường hợp thực tiễn bị rough sets. 3 hình ảnh đầu đã được nhiều paper tuyên bố giải quyết, chỉ còn (4) thì chưa ai giải quyết triệt để.

  1. Có cục gạch nằm hẳn trong vết sơn X \underline{app}(X) \ne \emptyset \ and \ \overline{app}(X) \ne U và đứa bé không sơn hết bức tường B \subseteq C
  2. Không có đối tượng nào trong X quyết định chính xác (không có xấp xỉ dưới) \underline{app}(X) = \emptyset \ and \ \overline{app}(X) \ne U và đứa bé không sơn hết bức tường.
  3. Không có thằng nào nằm hẳn và các viên gạch đều được tô \underline{app}(X) \ne \emptyset \ and \ \overline{app}(X) = U.
  4. Để sạch sẽ bức tường này thì phải gỡ bỏ ra hết, toàn bộ viên gạch đều dính hết mà chỉ dính một ít \underline{app}(X) = \emptyset \ and \ \overline{app}(X) = U.

Bảng quyết định nhất quán

Mọi quyết định của anh đều phải nhất quán. Nếu cùng một vấn đề mà anh đưa ra nhiều hơn một quyết định thì anh không nhất quán. Nghĩa là ta cần phát hiện dị thường trong quyết định của ảnh và dị thường này là bao nhiêu?

Đặt T = (U, C \cup \{d\}) là bảng quyết định. Khi đó, bảng quyết định là nhất quán với:

  • Điều kiện 1: bảng quyết định T là nhất quán khi và chỉ khi POS_C(d) = U
  • Điều kiện 2: bảng quyết định T là nhất quán nếu $\forall x \in U$, |delta_C(x)| = 1, ngược lại đây là bảng không nhất quán. Trong đó hàm \delta_C:U \to \zeta(V_d) được định nghĩa bởi, x \in U\delta_C(x) \equiv \{d(y) | \exists y \in U, x \sim_C y\}

Ta xét bảng xếp loại học lực của những sinh viên như sau:

Student Math Literature Overall-Eval
S1 good medium good
S2 bad medium medium
S3 bad bad bad
S4 good medium good
S5 medium good good
S6 medium medium bad
S7 medium good good

Trong bảng ví dụ trên, ta thấy mặc dù sinh viên có cùng điểm nhưng chưa chắc đã được xếp hạng giống nhau. Từ đây, ta nảy sinh câu hỏi: “Thuộc tính nào thật sự có vai trò trong quyết định phân lớp của anh? Những thuộc tính không ảnh hưởng đến sự phân lớp của anh? Khi phát hiện ra dị thường thì giải quyết thế nào?” Ta xác định điều này bằng cách đi tính POS cho từng quyết định.

Giả thiết:

C=\{Math, Literature\}
U/C = \{\{S1,S4\},\{S2\},\{S3\},\{S5,S7\},\{S6\}\}
Thuộc tính quyết định: d=Overall-Eval
Các lớp quyết định: U/d = \{\{S1,S4,S5,S7\},\{S2\},\{S3,S6\}\}

Từ công thức POS_C(d) \equiv \cup_{X \in U/d} \underline{app}_C(X) ta có:

(d=good)=X1\equiv \{S1,S4,S5,S7\} \Rightarrow \underline{app}_C(X1) = X1
(d=medium)=X2\equiv \{S2\} \Rightarrow \underline{app}_C(X2) = X2
(d=bad)=X3\equiv \{S3,S6\} \Rightarrow \underline{app}_C(X3) = X3

Suy ra POS_C(d)=X1 \cup X2 \cup X3 = U

Đây là ví dụ đàng hoàng, không có dị thường. Tuy nhiên, tập dữ liệu sẽ xảy ra dị thường khi có biến động về thời gian. Ví dụ này tuân thủ nguyên lý bất khả phân, anh nằm cùng lớp thì phải xếp vào cùng lớp chứ không thể xếp vào lớp khác.

Bảng quyết định không nhất quán

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

Giả thiết:

C=\{Headache, Temp\}
U/C = \{\{u1\},\{u2\},\{u3\},\{u4\},\{u5,u7\},\{u6,u8\}\}
Thuộc tính quyết định: d=Flu
Các lớp quyết định: U/d = \{\{u1,u4,u5,u8\},\{u2,u3,u6,u7\}\}
(d=No) = X1 \equiv \{u1,u4,u5,u8\}; (d=Yes) = X2 \equiv \{u2,u3,u6,u7\}

Ta có: \delta(u5) \equiv \{d(y) | y \in U, y \sim_C u5\} = \{u5,u7\} \to \delta(u5) > 1 không thoả điều kiện 1 và 2 nên bảng quyết định này không nhất quán.

Kinh nghiệm cài đặt

Ta nên giữ tư tưởng hạt mà làm việc. Khi biểu diễn hình thức là dạng hạt, ta nên cài đặt và áp dụng hạt, đừng đem đi hội tất cả, hợp nó thành phần tử mất rồi thì không còn cục gạch nữa để dùng cho các tính toán sau.

Trên máy ta sẽ làm việc trên mấy cái khay nê không cần đọc lại CSDL. Tiếp theo, ta bắt đầu xem cái phân lớp của anh đối với cơ sở tri thức (tri thức khách quan) có bị dị thường không (do quyết định chủ quan). Nếu phát hiện được thì rất hay trong quá trình khai thác dữ liệu. Ta có thể sử dụng kĩ thuật lính canh để quyét cơ sở tri thức, khi nào quét hết bức tường rồi thì ngưng.

Demo

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

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

Run command: Rscript basics.R patients.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)

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

# choose index of features
P <- c(2,3)

####### Perform indiscernibility relation #######
IND <- BC.IND.relation.RST(decision.table, feature.set = P)

####### Perform lower and upper approximatino #####
roughset <- BC.LU.approximation.RST(decision.table, IND)

####### Determine the positive region ######
region <- BC.positive.reg.RST(decision.table, roughset)

cat("###  Indiscernibility Relation ###\n")
print(IND)

cat("\n\n\n### Lower and Upper Approximations ###\n")
print(roughset)

cat("\n\n\n### Regions ###\n")
print(region)

Output

Loading required package: Rcpp
###  Indiscernibility Relation ###
$IND.relation
$IND.relation$`No High`
[1] 5 7

$IND.relation$`No Normal`
[1] 4

$IND.relation$`No Very-high`
[1] 6 8

$IND.relation$`Yes High`
[1] 2

$IND.relation$`Yes Normal`
[1] 1

$IND.relation$`Yes Very-high`
[1] 3

$type.relation
[1] "equivalence"

$type.model
[1] "RST"

attr(,"class")
[1] "IndiscernibilityRelation" "list"

### Lower and Upper Approximations ###
$lower.approximation
$lower.approximation$No
 No Normal Yes Normal
         4          1

$lower.approximation$Yes
     Yes High Yes Very-high
            2             3

$upper.approximation
$upper.approximation$No
     No High1      No High2     No Normal No Very-high1 No Very-high2
            5             7             4             6             8
   Yes Normal
            1

$upper.approximation$Yes
     No High1      No High2 No Very-high1 No Very-high2      Yes High
            5             7             6             8             2
Yes Very-high
            3

$type.model
[1] "RST"

attr(,"class")
[1] "LowerUpperApproximation" "list"

### Regions ###
$positive.reg
[1] 1 2 3 4

$degree.dependency
[1] 0.5

$type.model
[1] "RST"

attr(,"class")
[1] "PositiveRegion" "list"
RoughSets_package

RoughSets_package

Converting the dataset into the DecisionTable format

Converting the dataset into the DecisionTable format

Generating a new decision table in the DecisionTable format

Generating a new decision table in the DecisionTable format

A scenario of data preprocessing using RoughSets

A scenario of data preprocessing using RoughSets

The learning and prediction schema in RoughSets

The learning and prediction schema in RoughSets

Kết

Đến đây, các bạn có thể đoán ra ứng dụng của lý thuyết tập thô vào rút gọn dữ liệu rồi phải không. Trong phần 1, tôi sẽ đi sơ lược các khái niệm cơ bản về lý thuyết tập thô. Ở các phần tiếp theo, tôi sẽ đi vào những ứng dụng của lý thuyết này. 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

  • Rough set theory: lý thuyết tập thô
  • Equivalent relation: quan hệ tương đương
  • Granular knowledge set: tập tri thức hạt
  • In-discernibility: bất khả phân
  • Rough membership function: hàm thành viên thô
  • Consistency of a decision table: bảng quyết định nhất quán
  • Data discretization: rời rạc hoá dữ liệu
  • Attribute significant: mức ý nghĩa thuộc tính
  • Lower approximation of X: xấp xỉ dưới của X
  • Upper approximation of X: xấp xỉ trên của X
  • Indiscernibility relation: quan hệ bất khả phân
  • Consistent/Inconsistent: nhất quán/không nhất quán

Nguồn tham khảo: https://github.com/ongxuanhong/sma_2017/blob/master/RoughSet_Models.pdf

Advertisements

2 thoughts on “SMA 2017 – Lý thuyết tập thô (P1) – Các khái niệm cơ bản

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