SMA 2017 – Lý thuyết tập thô (P2) – Rời rạc hoá thuộc tính

discretization

discretization

Tiếp theo phần 1, ở phần này, tôi sẽ đi tiếp làm thế nào để rời rạc hoá dữ liệu. Trong thực tế, các kiểu dữ liệu trong hệ thông tin của chúng ta không chỉ có kiểu dữ liệu số nguyên mà còn nhiều loại dữ liệu phức tạp khác như kiểu dữ liệu số thực, kiểu dữ liệu phạm trù, … Lý thuyết tập thô muốn làm việc được trên tập dữ liệu này, ta cần rời rạc hoá tập dữ liệu thành các khoảng đoạn. Ở đây, ta có hai hướng tiếp cận là kĩ thuật chia giỏ và rút gọn bảng nhị phân.

C-discretization cho bảng quyết định

Ta xét bảng quyết định sau: S=(U, A \cup \{d\})

Obj.s MACD MA5 PROC RSI Decision
1991-07-16 10.45598 0 0.46997 67.29899 0
1991-07-18 8.66146 -1 1.83377 75.16101 -1
1991-07-22 6.79574 -1 0.38667 63.90746 0
1991-07-23 6.13677 -1 0.57888 61.94267 -1
1991-07-24 5.44940 0 -0.60159 49.67291 -1

Trong đó:

  • A = {MACD: Moving Average Convergence/ Divergence, MA5: Moving Average over a 5-days period, PROC: Price Rate of Change, RSI: Wilder Relative Strength Index}
  • d = Decision \in { -1: ngày tiếp theo có giá trị thấp hơn ngày hiện tại, 1 giá trị cao hơn và 0 không thay đổi}

Để rời rạc hoá thuộc tính có kiểu dữ liệu số thực ta thực hiện như sau:

\forall a \in A, giả sử V_a = [l, r). Ta đặt a(U) \equiv \{a(x): x \in U\} \equiv \{v_1^a, ..., v_{k_a}^a\}. Tập điểm cắt cơ sở trên a, ký hiệu là B_a, được định nghĩa bởi công thức:

B_a \equiv \{(a + \frac{v_1^a + v_2^a}{2}), (\frac{v_2^a + v_3^a}{2}), ..., (\frac{v_{k-1_a}^a + v_{k_a}^a}{2})\}

Khi đó, tập các điểm cắt cơ sở trên S\bigcup_{a \in A} B_a. Tóm lại,

\forall a \in A; l_a < c_1^a < ... < c_k^a < r_a
C_a \equiv \{(a, c_1^a), ..., (a, c_k^a)\}

Với mọi điểm cắt cơ sở trên thuộc tính a. Tập các điểm cắt C \equiv \bigcup_{a \in A} C_a sẽ định nghĩa một hệ quyết định mới S^C \equiv (U, A^C, d). Hệ này gọi là C-discretization của S, trong đó

A^C \equiv \{a^C: a \in A\}

a^C(x) \equiv \{
0, a(x) < c_1^a
i, a(x) \in [c_i^a, c_{i+1}^a), i \in \{1, ..., (k+1)\}
k, a(x) > c_k^a
\}

Khi thực hiện, đầu tiên ta sẽ xác định giá trị V_{min}, V_{max} của MACD. Ta tạo điểm cắt cơ bản giữa các giá trị V_i với các điểm cắt cơ sở c_i^a. Lưu ý các giá trị V đã được sắp từ nhỏ đến lớn. Nếu ta có 4 trung điểm, ta có thể xếp vào bin và giá trị mới sẽ là thứ tự gần giá trị điểm cắt cơ sở nhất.

MACD: V_{min} = 5.44940, V_{max} = 10.45598, V = \{5.44940, 6.13677, 6.79574, 8.66146, 10.45598\}

Từ đây, ta tính được MACD(U)=\{\frac{5.44940+6.13677}{2}=5.793085; \frac{6.13677+6.79574}{2}=6.466255; \frac{6.79574+8.66146}{2}=7.7286;\frac{8.66146+10.45598}{2}=9.55872\}. Tương đương, B_{MCDA} =\{(MCDA, 5.793085),(MCDA, 6.466255), (MCDA,7.7286 ),(MCDA, 9.55872)\}

Khi đó, C-discretization cho bảng quyết định S thu được như bảng dưới:

Obj.s MACD MA5 PROC RSI Decision
1991-07-16 4 1 2 3 0
1991-07-18 3 0 4 4 -1
1991-07-22 2 0 1 2 0
1991-07-23 1 0 3 1 -1
1991-07-24 0 1 0 0 -1

Rời rạc hoá bằng cách rút gọn bảng nhị phân

Cho bảng hệ thông tin thực vật như bên dưới:

Obj. Height (cm) Concentration (%) Result
u1 0.5 1 Yes
u2 1.1 1.5 Yes
u3 1.1 2 No
u4 1.2 2 Yes
u5 1.5 1.5 No

Concentration: nồng độ kim loại ion.
Result: tăng trưởng bình thường hay không bình thường.

Ta có thể biểu diễn bảng dữ liệu trên dưới dạng đồ thị sau:

graphical_representation_of_data

graphical_representation_of_data

Ta cần rời rạc hoá bằng cách tạo điểm cắt cơ sở.

graph_of_basic_cuts

graph_of_basic_cuts

Với bảng quyết định S^P. Ta đặt a = Height, b = Concentration, d = Result. Khi đó:

a(U) = \{0.5, 1.1, 1.2, 1.5\} chia thành 3 miền, b(U) = \{1, 1.5, 2\} chia thành 2 miền, vẽ lên biểu đồ ta sẽ thấy phân hoạch theo các vùng.

p_1^a \to a \in [0.5, 1.1) (thuộc tính a sẽ bị cắt bởi đường 1)
p_2^a \to a \in [1.1, 1.2) (thuộc tính a sẽ bị cắt bởi đường 2)
p_3^a \to a \in [1.2, 1.5) (thuộc tính a sẽ bị cắt bởi đường 3)

p_1^b \to b \in [1, 1.5) (thuộc tính b sẽ bị cắt bởi đường 1)
p_1^b \to b \in [1.5, 2) (thuộc tính b sẽ bị cắt bởi đường 2)

Các điểm màu trắng nằm trên 3 vùng, màu đậm nằm trên 2 vùng. Di động các thanh cắt sao cho bảng quyết định giữ được tính chất ban đầu của dữ liệu. Ở đây (u1,u3) cách nhau 1 rào cản, ta đánh dấu bool = 1 và tương tự cho các cặp còn lại.

\phi_U = \wedge \{\psi(u_i, u_j): d(u_i) \ne d(u_j)\}

U^P p_1^a p_2^a p_3^a p_1^b p_2^b
(u1,u3) 1 0 0 1 1
(u1,u5) 1 1 1 1 0
(u2,u3) 0 0 0 0 1
(u2,u5) 0 1 1 0 0
(u4,u3) 0 1 0 0 0
(u4,u5) 0 0 1 0 1

Cuối cùng, ta quy về bài toán rút gọn bảng nhị phân sau khi rời rạc hoá. Ta chuyển thành logic mệnh đề, thằng nào mang giá trị 1 thì cộng lại hết.

\psi(u_1, u_3) = p_1^a + p_1^b + p_2^b
\psi(u_1, u_5) = p_1^a + p_2^a + p_3^a + p_1^b
\psi(u_2, u_3) = p_2^b
\psi(u_2, u_5) = p_2^a + p_3^a
\psi(u_4, u_3) = p_2^a
\psi(u_4, u_5) = p_3^a + p_2^b

Biểu thức hội và tuyển rút gọn \phi_U thành CNF form (dạng hội chuẩn)

\phi_U = (p_1^a + p_1^b + p_2^b)(p_1^a + p_2^a + p_3^a + p_1^b)p_2^b(p_2^a + p_3^a)p_2^a(p_3^a + p_2^b)

Sau khi rút gọn, ta có \phi_U = p_2^a p_2^b \Rightarrow \{p_2^a p_2^b\}. Đây chính là tập điểm cắt cơ sở tối giản.

Từ bảng C-discretization của S

U a b d
u1 0.5 1 0
u2 1.1 1.5 0
u3 1.1 2 1
u4 1.2 2 0
u5 1.5 1.5 1

Ta chuyển đổi thành bảng mới bằng tập điểm cắt cơ sở tối giản: C=\{(a;1.15),(b;1.75)\}

U a b d
u1 0 0 0
u2 0 0 0
u3 0 1 1
u4 1 1 0
u5 1 0 1

Ta có thể biểu diễn điểm cắt cơ sở như đồ thị bên dưới:

minimal_set_cuts

minimal_set_cuts

Cuối cùng, ta nhận thấy các thuộc tính đã được rời rạc hết đồng thời không phá vỡ tính dị thường và không dị thường ban đầu của tập dữ liệu. Lưu ý, quá trình tìm được tập các điểm cắt tối giản khi cho trước hệ thông tin S là NP-hard problem. 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

  • Discretization: rời rạc hoá.
  • Intervals: khoảng đoạn.
  • Set basic cuts: tập các điểm cắt cơ sở.
  • Minimal set cuts: tập các điểm cắt tối giản.
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