Biểu diễn phụ thuốc hàm xấp xỉ theo phân hoạch, ma trận phân biệt được và luật kết hợp

hi và chỉ khi
∑
U∈piX
|U |2 = ∑
V ∈piXY
|V |2
Chứng minh. Giả sử phân hoạch piX gồm các lớp tương đương Ui, i = 1, ..., |piX | và phân
hoạch piXY gồm các lớp tương đương Vj , j = 1, ..., |piXY |. Gọi E(piX) là kỳ vọng của tổng số bộ
ứng với các lớp tương đương Ui, i = 1, ..., |piX |. Gọi E(piXY ) là kỳ vọng của tổng số bộ ứng với các
lớp tương đương Vj , j = 1, ..., |piXY |.
Khi đó
E(piX) =
|piX |∑
i=1
|Ui|.P (Ui) , với P (Ui): khả năng phân bố các bộ của r vào Ui
=
|piX |∑
i=1
|Ui|. |Ui||r| =
1
|r|
∑
U∈piX
|U |2,
E(piXY ) =
|piXY |∑
j=1
|Vj |.P (Vj), với P (Vj): khả năng phân bố các bộ của r vào Vj
=
|piXY |∑
j=1
|Vj |. |Vj ||r| =
1
|r|
∑
V ∈piXY
|V |2.
Ta có E(piX) = E(piXY ) khi và chỉ khi có sự phân bố các bộ vào các U ∈ piX giống sự
phân bố các bộ vào các V ∈ piXY . Do vậy X → Y là một phụ thuộc hàm khi và chỉ khi∑
U∈piX
|U |2 = ∑
V ∈piXY
|V |2 
Nhận xét 4.1. Ta có thể đặt δ(X,Y ) =
∑
V ∈piXY
|V |2∑
U∈piX
|U |2 . Khi đó, 0 < δ(X,Y ) ≤ 1 và δ(X,Y ) tăng
thì khả năng xảy ra lỗi của phụ thuộc hàm càng ít.
BIỂU DIỄN PHỤ THUỘC HÀM XẤP XỈ 167
Ví dụ 4.1. Cho quan hệ r(R) sau:
Bảng 1. Một quan hệ trên tập thuộc tính R = {A1, ..., A4}
A1 A2 A3 A4
0 1 0 0
1 0 1 1
0 1 1 2
2 1 0 0
0 1 0 1
1 0 2 2
Khi đó, ta có: δ(A1, A2) = 1, δ(A1, A3) = 4/7, δ(A1, A4) = 3/7.
Từ Tính chất 4.2 và Nhận xét 4.1, ta có Định nghĩa 4.3 như sau:
Định nghĩa 4.3. (Độ đo lỗi g4 theo phân hoạch) Cho quan hệ r(R). Khi đó, độ đo lỗi
g4(X → Y, r) từ các phân hoạch được tính như sau:
g4(X → Y, r) = 1− δ(X,Y ) = 1−
∑
V ∈piXY
|V |2∑
U∈piX
|U |2 ·
Với Bảng 1, ta có g4(A1 → A2, r) = 0, g4(A1 → A3, r) = 3/7, g4(A1 → A4, r) = 4/7.
Nhận xét 4.2. Từ Tính chất 4.2, Nhận xét 4.1 và Định nghĩa 4.3, ta thấy rằng g4(X → Y, r) có
quan hệ mật thiết với sự phân bố của các bộ dữ liệu vào các V ∈ piXY ứng với các U ∈ piX . Tuy
nhiên g2(X → Y, r) và g3(X → Y, r) không biểu diễn được cho sự phân bố này.
Ví dụ 4.2. Cho quan hệ r(R) sau:
Bảng 2. Một quan hệ trên tập thuộc tính {Hoten, Trieuchung, Benh}
Hoten Trieuchung Benh
P1 2 4
P2 1 1
P3 1 2
P4 2 2
P5 1 4
P6 2 3
P7 1 1
P8 2 2
P9 2 2
P10 1 3
P11 2 1
168 TRẦN DUY ANH
Với quan hệ ở Bảng 2, ta có g2(Trieuchung → Benh, r) = 0, g3(Trieuchung → Benh, r) =
6
11 . Nếu chúng ta thay đổi sự phân bố của các bộ dữ liệu, chẳng hạn ở người có Hoten là P6, ta
thay thế giá trị 3 thành giá trị 1 ứng với thuộc tính Benh thì g2(Trieuchung → Benh, r) và
g3(Trieuchung → Benh, r) vẫn không thay đổi.
Nhận xét 4.3. Bây giờ, ta thu hẹp tập dữ liệu của quan hệ r ứng với phép chọn, khi đó g4(X →
Y, σX=xi(r)) với xi ∈ dom(X) đo được mức độ tập trung của các bộ dữ liệu trong σX=xi(r) vào
các lớp tương đương V ∈ piXY .
Thật vậy, ta có g4(X → Y, σX=xi(r)) = 1 −
∑
V ∈piXY
|V |2
|σX=xi(r)|2
. Do đó g4(X → Y, σX=xi(r)) càng
nhỏ khi chỉ khi
∑
V ∈piXY
|V |2
|σX=xi (r)|2
càng lớn. Hay g4(X → Y, σX=xi(r)) càng nhỏ khi chỉ khi mức độ tập
trung các bộ σX=xi(r) vào một hay một số lớp tương đương V ∈ piXY là càng lớn.
Với quan hệ ở Bảng 2, ta có: g4(Trieuchung → Benh, σTrieuchung=1(r)) = 1825 ,
g4(Trieuchung → Benh, σTrieuchung=2(r)) = 23 . Nếu ở người có Hoten là P6, ta thay đổi giá trị
3 thành giá trị 1 ứng với thuộc tính Benh thì g4(Trieuchung → Benh, σTrieuchung=2(r)) = 118 .
Như vậy nếu g4(Trieuchung → Benh, σTrieuchung=xi(r)) càng nhỏ ứng với triệu chứng xi thì
mức độ phân bố tập trung bệnh nhân trong σTrieuchung=xi(r) vào một hoặc một số bệnh nào đó
càng lớn và ngược lại. Điều này góp một phần trong việc dự đoán được bệnh của bệnh nhân thông
qua các triệu chứng.
Nhận xét 4.4. Ta thấy rằng g4(X → Y, r) ≥ g1(X → Y, r), nghĩa là g4(X → Y, r) nghiêm ngặt
hơn g1(X → Y, r). Tuy nhiên g1(X → Y, r) là không tốt cho việc đo lỗi của X → Y và mức độ
tập trung của các bộ dữ liệu trong r vào các lớp tương đương V ∈ piXY . Thật vậy, ta có
g4(X → Y, r) =1−
∑
V ∈piXY
|V |2∑
U∈piX
|U |2 =
|r|2∑
U∈piX
|U |2 ·
∑
U∈piX
(
|U |2 − ∑
V ∈piXY
V⊆U
|V |2
)
|r|2
=
|r|2∑
U∈piX
|U |2 ·
∣∣{(ti, tj)∣∣ti, tj ∈ r, ti[X] = tj [X], ti[Y ] 6= tj [Y ]}∣∣
|r|2
=
|r|2∑
U∈piX
|U |2 · g1(X → Y, r)·
Suy ra g4(X → Y, r) ≥ g1(X → Y, r).
Bây giờ ta xét một quan hệ ở Ví dụ 4.3 dưới đây.
Ví dụ 4.3. Cho quan hệ r(R) sau:
Bảng 3. Một quan hệ trên tập thuộc tính {A,B,C}
A 0 2 1 1 0 1 3 3 2 3 0 2 2 3 2
B 1 5 1 2 3 4 3 4 3 2 2 2 1 1 4
C 1 3 2 2 2 1 2 1 2 1 1 3 1 1 3
BIỂU DIỄN PHỤ THUỘC HÀM XẤP XỈ 169
g4(A→ B, r) = 4459 ' 0.756, g3(A→ B, r) = 1115 ' 0.733, g1(A→ B, r) = 44225 ' 0.196.
Ta thấy rằng độ đo lỗi g1(A→ B, r) là quá nhỏ so với g4(A→ B, r), trong khi đó lỗi của
phụ thuộc hàm A→ B là tương đối lớn và mức độ phân bố tập trung các bộ dữ liệu vào các
lớp tương đương V ∈ piAB ứng với U ∈ piA là nhỏ.
Tính chất 4.3. (Độ đo g4 trên phân hoạch thu gọn) Cho quan hệ r(R). Khi đó, độ đo lỗi
g4(X → Y ) từ các phân hoạch thu gọn được xác định như sau:
g4(X → Y, r) =
∑
U∈pˆiX
|U |2 − ∑
V ∈pˆiXY
|V |2 − ∑
U∈pˆiX
|U | + ∑
U∈pˆiXY
|V |∑
U∈pˆiX
|U |2 + |r| − ∑
U∈pˆiX
|U | ·
Chứng minh. Ta có |r| − ∑
U∈pˆiX
|U |: là số lớp tương đương một phần tử bị loại khỏi piX để có
pˆiX . Suy ra ∑
U∈piX
|U |2 =
∑
U∈pˆiX
|U |2 + |r| −
∑
U∈pˆiX
|U |
Tương tự ta có
∑
V ∈piXY
|V |2 = ∑
V ∈pˆiXY
|V |2 + |r| − ∑
V ∈pˆiXY
|V |. Do đó:
g4(X → Y, r) =1−
∑
V ∈pˆiXY
|V |2 + |r| − ∑
V ∈pˆiXY
|V |∑
U∈pˆiX
|U |2 + |r| − ∑
U∈pˆiX
|U |
=
∑
U∈pˆiX
|U |2− ∑
V ∈pˆiXY
|V |2− ∑
U∈pˆiX
|U |+ ∑
U∈pˆiXY
|V |∑
U∈pˆiX
|U |2+|r|− ∑
U∈pˆiX
|U | 
Ví dụ 4.4. Với Bảng 1, ta có:
pˆiA1 = {{t1, t2, t3}, {t4, t5}}, pˆiA1A3 = {{t1, t2}}
Độ đo lỗi g4(A1 → A3, r) được tính từ các phân hoạch thu gọn và g4(A1 → A3, r) = 3
7
.
5. BIỂU DIỄN PHỤ THUỘC HÀM XẤP XỈ THEO MA TRẬN
PHÂN BIỆT ĐƯỢC
Trong phần này chúng tôi xây dựng ma trận phân biệt được M(S) theo 1 cách khác và đề xuất
cách biểu diễn độ đo lỗi g1, g2, độ phụ thuộc γ và ý nghĩa thuộc tính σ thông qua M(S).
Định nghĩa 5.1. (Ma trận phân biệt được) Cho r = t1, t2, . . . , tn. Ma trận phân biệt được
của S = (r,R), ký hiệu M(S) = (mij)|r|×|r| là ma trận đối xứng mà mỗi phần tử của nó là
một tập hợp các thuộc tính, được xác định như sau:
mij =

{Ak ∈ C|ti(Ak) 6= tj(Ak)} ti(D) 6= tj(D)
∅
{β |6 ∃Ak ∈ C : ti(Ak) 6= tj(Ak)}
ti(D) = tj(D)
ti(D) 6= tj(D), β /∈ C
với i, j = 1, |r|.
170 TRẦN DUY ANH
Định nghĩa 5.2. Cho ma trận phân biệt được M(S) = (mij)|r|×|r|. Khi đó số lần X xuất
hiện trong M(S) ký hiệu là SL(X) và được định nghĩa như sau:
SL (X) =
∣∣∣{mij ∣∣∣(X ∩mij) 6= ∅, X ⊆ C,∀i, j = 1, |r|} ∣∣∣
Nếu X = ∅ thì SL(∅) =
∣∣∣{mij ∣∣∣mij = ∅ , ∀i, j = 1, |r|} ∣∣∣ .
Tính chất 5.1. Cho ma trân phân biệt được M(S) = (mij)|r|×|r|. Khi đó, X → D với
X ⊆ C là một phụ thuộc hàm khi và chỉ khi SL(X) = |r|2 − SL(∅).
Chứng minh. Ta có với mỗi mij = ∅ thì ti[D] = tj [D]. Do đó SL(∅) là số cặp bộ (ti, tj),
i, j = 1, |r| không vi phạm phụ thuộc hàm X → D.
Mặt khác, với mỗi mij sao cho (X ∩ mij) 6= ∅, X ⊆ C thì ti[X ∩ mij ] 6= tj [X ∩ mij ]
và ti[D] 6= tj [D] suy ra ti[X] 6= tj [X] và ti[D] 6= tj [D]. Do đó SL(X) là số cặp bộ (ti, tj),
i, j = 1, |r| không vi phạm phụ thuộc hàm X → D.
Vậy SL(X) + SL(∅) = |r|2 với X ⊆ C ⇔6 ∃ti, tj ∈ r : ti[D] 6= tj [D] và ti[X] = tj [X] ⇔
X → D là một phụ thuộc hàm. 
Tính chất 5.2. Độ đo lỗi g1 của một phụ thuộc hàm X → D, với X ⊆ C trên r được xác
định như sau:
g1(X → D, r) = 1− SL(∅) + SL(X)|r|2
Chứng minh. Theo Tính chất 5.1, ta có SL(X) + SL(∅) là số cặp bộ (ti, tj), i, j = 1, |r| không
vi phạm phụ thuộc hàm X → D. Do đó: g1(X → D, r) = |r|
2−SL(∅)−SL(X)
|r|2 = 1 −
SL(∅)+SL(X)
|r|2

Hệ quả 5.1. Độ đo lỗi g1 của một phụ thuộc hàm X → D, với X ⊆ C trên r được xác định
như sau:
g1(X → D, r) =
∣∣∣{mij | ((X ∩mij) = ∅) ∧ (mij 6= ∅) , i, j = 1, |r| } ∣∣∣
|r|2
Chứng minh. - Ta có ((X ∩mij) = ∅) ∧ (mij 6= ∅) ⇔6 ∃A ∈ X : ti[A] 6= tj [A] và ti[D] 6=
tj [D] ⇔ ti[X] = tj [X] và ti[D] 6= tj [D]⇔ cặp (ti, tj) vi phạm phụ thuộc X → D.
- Trường hợp mij = β suy ra ((X ∩mij) = ∅)∧ (mij 6= ∅) (vì β 6∈ X)⇔ cặp (ti, tj) vi phạm
phụ thuộc X → D
Vậy
∣∣∣{mij | ((X ∩mij) = ∅) ∧ (mij 6= ∅) , i, j = 1, |r| } ∣∣∣ = số cặp (ti, tj) vi phạm phụ thuộc
X → D. Do đó: g1(X → D, r) = |{mij |((X∩mij)=∅)∧(mij 6=∅) , i,j=1,|r| } ||r|2 · 
Tính chất 5.3. Độ đo lỗi g2 của một phụ thuộc hàm X → D, với X ⊆ C trên r được xác
định như sau:
g2(X → D, r) = 1−
|r|∑
i=1
hangi(X)
|r|
Trong đó: hangi(X) =
{
1 (X ∩mij) 6= ∅ ∀mij 6= ∅, j = 1, |r|
0 ∃j : (mij 6= ∅) ∧ ((X ∩mij) = ∅) ·
BIỂU DIỄN PHỤ THUỘC HÀM XẤP XỈ 171
Chứng minh. Ta có:
g2(X → D, r) = |{ ti |ti ∈ r, ∃tj ∈ r : ti [X] = tj [X] , ti [D] 6= tj [D] } ||r| ·
Gọi q là số bộ vi phạm phụ thuộc hàm X → D trên r. Khi đó:
q = |{ ti |ti ∈ r, ∃tj ∈ r : ti [X] = tj [X] , ti [D] 6= tj [D] } |
Ta có với mỗi bộ ti ∈ r:
- Xét trường hợp, nếu (X ∩mij) 6= ∅ ∀mij 6= ∅, j = 1, |r|
Ta có (X ∩mij) 6= ∅ ∀mij 6= ∅, j = 1, |r| ⇔6 ∃tj ∈ r : ti[X] = tj [X] và ti[D] 6= tj [D] (vì
nếu ∃tj : ti[X] = tj [X] và ti[D] 6= tj [D] thì (X ∩mij) = ∅. Điều này mâu thuẫn với giả thiết)
⇔ ti là bộ thỏa phụ thuộc X → D ⇔ hangi(X) = 1.
- Xét trường hợp, nếu ∃j : (mij 6= ∅) ∧ ((X ∩mij) = ∅):
Ta có ∃j : (mij 6= ∅) ∧ ((X ∩mij) = ∅) ⇔ ti[X] = tj [X] và ti[D] 6= tj [D] ⇔ ti là bộ vi phạm
phụ thuộc X → D ⇔ hangi(X) = 0.
- Xét trường hợp mij = β
Ta có mij = β suy ra (mij 6= ∅) ∧ ((X ∩mij) = ∅) ⇔ ti là bộ vi phạm phụ thuộc X → D ⇔
hangi(X) = 0. Do đó
|r|∑
i=1
hangi(X) = số bộ thỏa phụ thuộc hàm X → D nên q = |r| −
|r|∑
i=1
hangi(X). Suy ra g2(X → D, r) = 1−
|r|∑
i=1
hangi(X)
|r| . 
Nhận xét 5.1.
- Độ phụ thuộc γ(X,D) được tính thông qua công thức γ(X,D) = 1− g2(X → D, r) [7], với
X ⊆ C và g2(X → D, r) = 1−
|r|∑
i=1
hangi(X)
|r| (Tính chất 5.3) như sau: γ(X,D) =
|r|∑
i=1
hangi(X)
|r| ·
- Ý nghĩa thuộc tính được tính dựa trên ma trận phân biệt được thông qua công thức:
σC∪D(Ai) = 1− γ(C−{Ai},D)γ(C,D) [9], với γ(X,D) =
|r|∑
i=1
hangi(X)
|r| và X ⊆ C.
6. LUẬT KẾT HỢP
Định nghĩa 6.1. [2] (CSDL giao dịch) Cho I(items) = {i1, i2, ..., im} là tập mục, một
CSDL giao dịch, được ký hiệu là TD gồm các giao dịch T ∈ TD, với mỗi giao dịch (Trans-
action) T được định nghĩa là tập con của tập mục I(T ⊆ I) và có một định danh duy nhất
〈TID, i1, i2, ..., ik〉.
Định nghĩa 6.2. [2] (Luật kết hợp) Cho cơ sở dữ liệu TD gồm các giao dịch T ứng với tập
mục I = {i1, i2, . . . , im}. Khi đó, một luật kết hợp giữa IX và IY có dạng là IX ⇒ IY , với
IX , IY ⊂ I và IX ∩ IY = ∅.
Định nghĩa 6.3. [2] (Độ hỗ trợ của một tập mục) Cho tập mục IX ⊆ I, độ hỗ trợ của tập
mục IX được ký hiệu là Support(IX ,TD) và được định nghĩa như sau: Support(IX ,TD) =
|{T∈TD|IX⊆T }|
|TD| hay Support(IX ,TD) là tỷ lệ phần trăm giữa các giao dịch chứa IX trên tổng
các giao dịch có trong cơ sở dữ liệu TD.
172 TRẦN DUY ANH
Định nghĩa 6.4. [2] (Độ hỗ trợ của luật kết hợp) Độ hỗ trợ của luật kết hợp IX ⇒ IY ,
(ký hiệu là Support(IX ⇒ IY ,TD)) bằng tỷ lệ phần trăm giữa các giao dịch chứa IX ∪ IY
trên tổng số các giao dịch trong cơ sở dữ liệu TD:
Support(IX ⇒ IY ,TD) = Support(IX ∪ IY ,TD) = |{T ∈ TD |IX ∪ IY ⊆ T }||TD| .
Định nghĩa 6.5. [2] (Độ tin cậy của luật kết hợp) Độ tin cậy của luật kết hợp IX ⇒ IY ,
(ký hiệu là Confidence(IX ⇒ IY ,TD)) bằng tỷ lệ phần trăm giữa các giao dịch chứa IX ∪ IY
trên số giao dịch có chứa IX :
Confidence(IX ⇒ IY ,TD) = Support(IX ∪ IY ,TD)Support(IX ,TD)
7. MỐI QUAN HỆ GIỮA PHỤ THUỘC HÀM XẤP XỈ
VÀ LUẬT KẾT HỢP
7.1. Một số ký hiệu [7]
- r(R): một quan hệ trên lược đồ R, với R = {A1, A2, ..., Am}
- Miền trị của X ⊂ R, ký hiệu là dom(X) = {x1, x2, ..., xk}
- Miền trị của Y ⊂ R, ký hiệu là dom(Y ) = {y1, y2, ..., yl}
- n = |r| và nxi = |{t ∈ r|t [X] = xi}| , nyj = |{ t ∈ r|t [Y ] = yj} |,
nxiyj =
∣∣{ t ∈ r|t [X] = xi và t [Y ] = yj} ∣∣
- Cho R = {A1, A2, ..., Am}. Khi đó, với Ak ∈ R thì iAk là một mục (item) trong luật kết hợp.
- Cho X ⊆ R. Khi đó, tập mục của X ký hiệu là IX = {iAk |Ak ∈ X}
7.2. Định nghĩa mới của phụ thuộc hàm xấp xỉ
Định nghĩa 7.1. [7] Cho quan hệ r(R) với R = {A1, A2, ..., Am} . Một cơ sở dữ liệu giao
dịch TD được định nghĩa như sau: mỗi cặp (t, s) ∈ r × r sao cho t, s ∈ r là một giao
dịch ts ∈ TD và được xác định như sau: iAk ∈ ts ⇔ t [Ak] = s [Ak]. Khi đó: ts.iAk ={
1 nếu iAk ∈ ts
0 nếu iAk /∈ ts
Ví dụ 7.1. Cho quan hệ sau:
Bảng 4. Một quan hệ r
Masv Quequan Truong Ketqua
1 Hue QH Dau
2 Hue NH Dau
3 Hue QH Rot
Ta có thể biểu diễn Bảng 4 thành cơ sở dữ liệu giao dịch TD như trong Bảng 5.
BIỂU DIỄN PHỤ THUỘC HÀM XẤP XỈ 173
Bảng 5. Một cơ sở dữ liệu giao dịch TD của r
ts iMasv iQuequan iTruong iKetqua
(1,1) 1 1 1 1
(1,2) 0 1 0 1
(1,3) 0 1 1 0
(2,1) 0 1 0 1
(2,2) 1 1 1 1
(2,3) 0 1 0 0
(3,1) 0 1 1 0
(3,2) 0 1 0 0
(3,3) 1 1 1 1
Định nghĩa 7.2. [7] Cho X,Y ⊂ R sao cho X ∩Y = ∅. Khi đó một phụ thuộc hàm xấp xỉ
X → Y trên quan hệ r là một luật kết hợp IX ⇒ IY trên cơ sở giao dịch TD. Và ta có độ
hỗ trợ và độ tin cậy như sau: Support (X → Y, r) = Support(IX ⇒ IY ,TD)
Confidence (X → Y, r) = Confidence(IX ⇒ IY ,TD)
Theo cách biểu diễn này thì độ hỗ trợ của tập thuộc tínhX là Support(X, r) = Support(IX ,TD).
Tính chất 7.1. [7]X, Y ⊂ R, X → Y là một phụ thuộc hàm khi và chỉ khi Confidence(IX ⇒
IY ,TD) = 1.
Định nghĩa 7.3. [7] Cho R = {A1, A2, ..., Am}, X,Y ⊂ R. Khi đó, độ hỗ trợ của X và
X → Y tương ứng là Support(X, r) = 1
n2
k∑
i=1
n2xi và Support(X → Y, r) = 1n2
k∑
i=1
l∑
j=1
n2xiyj .
Ví dụ 7.2. Trong Bảng 4, ta có: Support (Truong, r) = 5/9; Support ({Truong, Ketqua} , r) =
3/9.
Khi đó, ta có một số luật kết hợp trong TD tương ứng với các phụ thuộc hàm xấp xỉ
trong r như sau:
Bảng 6. Một số luật kết hợp tương ứng với phụ thuộc hàm xấp xỉ
Luật kết hợp Độ hỗ trợ Độ tin cậy Phụ thuộc hàm xấp xỉ
{iQuequan} ⇒ {iTruong} 5/9 5/9 {Quequan } → {Truong}
{iQuequan, iTruong} ⇒ {iKetqua} 1/3 3/5 {Quequan, Truong} → {Ketqua}
7.3. Độ hỗ trợ, độ tin cậy của phụ thuộc hàm xấp xỉ
Gọi ARS[X→Y ] =
{
ARij |∃t ∈ r : t [X] = xi và t [Y ] = yj
} ∀i = 1, k; ∀j = 1, l, trong đó
ARij là một luật kết hợp có dạng (X = xi) ⇒ (Y = yj), với Sij , Cij tương ứng là độ hỗ trợ, độ
tin cậy của ARij .
174 TRẦN DUY ANH
Tính chất 7.2. [7] Độ hỗ trợ của phụ thuộc hàm xấp xỉ X → Y được tính theo công thức
như sau:
Support(X → Y, r) = 1
n2
∑
ARij∈ARS[X→Y ]
n2xiyj =
∑
ARij∈ARS[X→Y ]
S2ij
Tính chất 7.3. [7] Độ tin cậy của một phụ thuộc hàm xấp xỉ được tính theo công thức
sau:
1
Confidence(X → Y, r) =
∑
ARij∈ARS[X→Y ]
S2ij∑
ARpq∈ARS[X→Y ]
S2pq
· 1
Cij
·
Ví dụ 7.3. Đối với Bảng 4, ta có:
1
Confidence({Quequan, Truong} → {Ketqua} , r) =
5
3
⇒Confidence({Quequan, Truong} → {Ketqua} , r) = 3
5
7.4. Biểu diễn độ phụ thuộc, độ đo lỗi thông qua luật kết hợp
Tính chất 7.4. [7] Cho phụ thuộc hàm xấp xỉX
γ(X,Y )→ Y , trong đó độ phụ thuộc γ(X,Y ) =
|POS(X,Y )|
|r| . Khi đó γ(X,Y ) =
∑
ARij∈ARS[X→Y ]|Cij=1 Sij .
Tính chất 7.5. [7] Độ đo lỗi g1 của phụ thuộc hàm X → Y ở Định nghĩa 3.1 được biểu
diễn như sau:
g1(X → Y, r) = Support (IX , TD)− Support (IX ⇒ IY , TD)
Tính chất 7.6. [7] Độ đo lỗi g2 của phụ thuộc hàm X → Y ở Định nghĩa 3.2 được biểu
diễn như sau:
g2(X → Y, r) = 1−
∑
ARij∈ARS[X→Y ]|Cij=1
Sij
Tính chất 7.7. [7] Cho phụ thuộc hàm xấp xỉ X → Y với
g3(X → Y, r) =
|r| − ∑
U∈piX
max
{
|V |
∣∣∣∣∣V ∈ piXY , V ⊆ U
}
|r|
Khi đó g3(X → Y, r) = 1−
K∑
i=1
max{Sij |ARij ∈ ARS[X→Y ]}
j=1,l
.
Tính chất 7.8. Cho g4(X → Y, r) là độ đo lỗi của phụ thuộc hàmX → Y , Confidence(IX ⇒
IY ,TD) là độ tin cậy của luật kết hợp IX ⇒ IY . Khi đó g4(X → Y, r) = 1−Confidence(IX ⇒
IY ,TD).
BIỂU DIỄN PHỤ THUỘC HÀM XẤP XỈ 175
Chứng minh. Ta có
g4(X → Y, r) =1−
∑
V ∈piXY
|V |2∑
U∈piX
|U |2 = 1−
k∑
i=1
l∑
j=1
|{t ∈ r|(t[X] = xi) ∧ (t[Y ] = yi)}|2
k∑
i=1
|{t ∈ r|t[X] = xi}|2
=1−
k∑
i=1
l∑
j=1
n2xiyj
k∑
i=1
n2xi
= 1− Support(IX ⇒ IY , TD)
Support(IX , TD)
=1− Confidence(IX ⇒ IY , TD).
Vậy g4(X → Y, r) = 1− Confidence(IX ⇒ IY , TD) 
Ví dụ 7.4. Đối với Bảng 1 ta có g4(A1 → A3, r) = 3/7 và Confidence(IA1 ⇒ IA3 , TD) = 4/7.
Do đó, g4(A1 → A3, r) = 1− Confidence(IA1 ⇒ IA3 , TD).
Tính chất 7.9. Mối liên hệ giữa g4(X → Y, r) và ARS[X→Y ]
g4(X → Y, r) = 1−
∑
ARpq∈ARS[X→Y ] S
2
pq∑
ARij∈ARS[X→Y ]
(
S2ij
Cij
)
Chứng minh. Ta có g4(X → Y, r) = 1− Confidence(IX ⇒ IY , TD). Mà
1
Confidence(X → Y, r) =
∑
ARij∈ARS[X→Y ]
S2ij∑
ARpq∈ARS[X→Y ]
S2pq
· 1
Cij
(Tính chất 7.3)
suy ra g4(X → Y ) =
1∑
ARpq∈ARS[X→Y ] S
2
pq
∑
ARij∈ARS[X→Y ]
(
S2ij
Cij
)
−1
1∑
ARpq∈ARS[X→Y ] S
2
pq
∑
ARij∈ARS[X→Y ]
(
S2
ij
Cij
) .
Do đó, g4(X → Y, r) = 1−
∑
ARpq∈ARS[X→Y ] S
2
pq∑
ARij∈ARS[X→Y ]
(
S2
ij
Cij
) . 
Ví dụ 7.5. Đối với Bảng 1 ta có g4(A1 → A3, r) = 3/7 (theo Định nghĩa 4.3) và
1−
∑
ARpq∈ARS[X→Y ] S
2
pq∑
ARij∈ARS[X→Y ]
(
S2ij
Cij
) = 1− 8/14 = 3/7.
8. KẾT LUẬN
Trong bài báo này chúng tôi đã nghiên cứu phụ thuộc hàm xấp xỉ dựa vào phân hoạch, ma trận
phân biệt được và luật kết hợp và đã đạt được một số kết quả sau:
176 TRẦN DUY ANH
1. Đề xuất độ đo lỗi g4 đối với phụ thuộc hàm và phân tích những thuận lợi của nó so với các độ
đo lỗi g1, g2, g3. Độ đo g4 không những đo được lỗi của phụ thuộc hàm mà còn đo được mức độ tập
trung hay không tập trung của các bộ dữ liệu. Sau đó xây dựng g4 trên phân hoạch thu gọn và biểu
diễn mối quan hệ giữa nó với độ tin cậy của luật kết hợp. Từ đó chúng ta có thể sử dụng các thuật
toán phát hiện luật kết hợp để phát hiện các phụ thuộc hàm xấp xỉ và ngược lại.
2. Đưa ra một định nghĩa mới về ma trận phân biệt được. Từ đó xem xét phụ thuộc hàm, biểu
diễn độ đo lỗi g1, độ đo lỗi g2, độ phụ thuộc và ý nghĩa thuộc tính thông qua ma trận phân biệt
được. Điều này làm cơ sở để nghiên cứu tiếp tục thuật toán rút gọn các thuộc tính dư thừa thông
qua các độ đo lỗi này.
TÀI LIỆU THAM KHẢO
[1] L. B. Cristofor, A Rough Set Based Generalization of Functional Denpendencies, Department
of Math and Computer Science, UMass/Boston, 2000.
[2] Rakesh Agrawal and Ramakrishnan Srikant, Fast algorithms for mining association rules in large
databases, In Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo, editors, Proceedings
of the 20th International Conference on Very Large Data Bases, VLDB, Santiago, Chile
(1994) 487-499.
[3] Ullas Nambiar, Subbarao Kamhampati, Mining Approximate Functional Dependencies and Con-
cept Similarities to Answer Imprecise Queries, Department of Computer Science, Arizona State
University, USA, 2004.
[4] Y. Huhtala, J Karkkainen, P. Porkka, H. Toivonnen, Tane: An Efficient Algorithm for Discovery
Functional and Approxiamate Dependencies, The Computer Journal, 42 (3) (1999) 100-111.
[5] J. Kivinen, H. Mannila, Approximate Inference of Functional Dependencies from Relations,
Theoretical Computer Science, 149 (1) (1995) 129-149.
[6] Stéphane Lopes, Jean-Marc Petit, Lotfi Lakhal, Functional and approximate dependency mining:
database and FCA points of view, J. Exp. Theor. Artif. Intell., 14(2-3) (2002) 93-114.
[7] Daniel Sánchez, José María Serano, Ignacio Blanco, Maria José Martin-Bautista, María Am-
paro Vila, Using association rules to mine for strong approximate dependencies, Data mining
knowledge discovery, Springer Science (2008) 313-348.
[8] Mohammed J. Zaki, Scalable algorithms for association mining. IEEE Transactions on Knowl-
edge and Data Engineering, 12(3) (2000) 372-390.
[9] Jan Komorowski, Lech Polkowski, Andrzej Skowron, Rough Set: A Tutorial, Institute of Math-
ematics, Warsaw University, 2000.
[10] Trần Duy Anh, Phát hiện các phụ thuộc hàm xấp xỉ theo cách tiếp cận tập thô, Tạp chí tin
học và điều khiển học, 23(3) (2007) 284-295
[11] Keyun Hu, Yuchang Lu, Chunyi Shi, Feature ranking in rough set, Department of Computer
science, Tsinghua University Beijing 100084, P.R.China, 2003.
[12] Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao, Mining frequent patterns without candidate
generation, Data Mining and Knowledge Discovery 8 (2004) 53-87.
Ngày nhận bài 21 - 3 - 2013
Nhận lại sau sửa ngày 8 - 9 - 2013