Luận văn Tiếp cận lý thuyết tập thô do Z.Pawlak

Có thể đơn cử một số nhóm tác giả như: Hong Yao, Howard J. Hamilton & Cory J. Butz [32], Mannila, H., Toivonen, H. & Verkamo, A.I. [22] và Yka Huhtala, Juha Karkkainen, Pasi Porkka & Hannu Toivonen [15, 16]. Các nghiên cứu của chúng tôi cũng nhằm vào hai loại phụ thuộc khá quen thuộc trong cơ sở dữ liệu quan hệ, đó là phụ thuộc hàm và phụ thuộc đa trị. Ngoài việc đề xuất các thuật toán phát hiện và kiểm chứng các phụ thuộc trong dữ liệu, chúng tôi còn mở rộng các khái niệm này bằng cách sử dụng các công cụ của lý thuyết tập thô. Như chúng ta đã biết, sự phụ thuộc giữa các thuộc tính của cơ sở dữ liệu quan hệ biểu diễn hình dạng của cấu trúc trong quan hệ đó. Chẳng hạn như một phụ thuộc hàm X → Y biểu diễn sự phụ thuộc của giá trị thuộc tính Y theo giá trị 62 thuộc tính X: Những giá trị của thuộc tính X xác định duy nhất giá trị của thuộc tính Y . Hay phụ thuộc đa trị X →→ Y là sự phụ thuộc của Y vào X độc lập với các thuộc tính còn lại. Nhắc lại rằng, nếu X, Y là các tập thuộc tính, thì Y được gọi là phụ thuộc hàm [21, 29, 30] vào X trên U và ký hiệu X → Y nếu ∀u, v ∈ U : u(X) = v(X) ⇒ u(Y ) = v(Y ). (3.1) Hơn nữa, với các điều kiện X∩Y = ∅, X∪Y A, bằng cách đặt Z = A\(X∪Y ), ta nói Y là phụ thuộc đa trị [15, 16, 21, 22, 25, 29, 30] vào X trên U và ký hiệu X →→ Y nếu ∀u, v ∈ U : u(X) = v(X) ⇒ ∃t ∈ U :  t(X) = u(X), t(Y ) = u(Y ), t(Z) = v(Z). (3.2) Tuy nhiên, dữ liệu trong thực tế thường không thoả các điều kiện trong (3.1) và (3.2) của những phụ thuộc hàm và phụ thuộc đa trị một cách thực sự nghiêm ngặt trên cả tập đối tượng U . Vì vậy, trong chương này chúng tôi đề nghị các phụ thuộc mở rộng theo hai nghĩa khác nhau. Một là các phụ thuộc chỉ đúng trên tập con V các đối tượng của U . Trong trường hợp này, chúng ta sẽ có đánh gía về sai số của phụ thuộc và phụ thuộc tương ứng được gọi là "phụ thuộc xấp xỉ". Loại thứ hai chúng tôi xét khi giá trị của các thuộc tính nhận được có thể bị sai lệch và phụ thuộc được chấp nhận khi sai số của các giá trị thuộc tính ở mức độ "cho phép", phụ thuộc này chúng tôi gọi là "phụ thuộc mở rộng". Các khái niệm phụ thuộc xấp xỉ và phụ thuộc mở rộng sẽ được trình bày chi tiết trong các phần tiếp theo. Các thuật toán kiểm tra phụ thuộc và phụ thuộc xấp xỉ theo hai nghĩa trên được thực hiện trên cơ sở xây dựng ma trận phụ thuộc và dựa vào sự phân hoạch của quan hệ tương đương ứng với giá trị của các thuộc tính. 63 3.2. Khảo sát phụ thuộc bằng Ma trận phụ thuộc 3.2.1. Phụ thuộc và phụ thuộc xấp xỉ Trong phần này ta luôn xét A = (U,A) là một hệ thống thông tin với U là tập các đối tượng và A là tập các thuộc tính. Với mỗi u ∈ U và a ∈ A ta ký hiệu u(a) là giá trị thuộc tính a của đối tượng u. Nếu X ⊆ A là một tập các thuộc tính ta ký hiệu u(X) là bộ gồm các giá trị u(a) với a ∈ X. Vì vậy, nếu u và v là hai đối tượng thuộc U , ta sẽ nói u(X) = v(X) nếu u(a) = v(a) với mọi thuộc tính a ∈ X. Trong nhiều trường hợp ta không nhận được X →→ Y nhưng tồn tại một tập con V ⊂ U sao cho X →→ Y trên V , lúc đó ta ký hiệu X→→V Y . Nếu tập V như vậy nhận được bằng cách loại bỏ một số rất ít các đối tượng trong U , thì ta nói Y “phụ thuộc đa trị xấp xỉ“ vào X trên U . Rõ ràng ta cần chọn tập V như vậy càng lớn càng tốt và điều này sẽ gợi ý cho chúng ta cách đánh giá sai số của phụ thuộc hàm g3 (xem Mục 2.4.2.) lên phụ thuộc đa trị, cụ thể ta có định nghĩa như sau Định nghĩa 3.1. Cho X, Y ⊆ A. Ta gọi giá trị sau là sai số của phụ thuộc đa trị X →→ Y g3(X →→ Y ) := 1− max{Card(V ) | V ⊆ U,X→→V Y } Card(U) . Rõ ràng, X →→ Y đúng khi và chỉ khi g3(X →→ Y ) = 0. Trong nhiều trường hợp, ngoài các phụ thuộc đa trị, chúng ta cũng cần xác định các phụ thuộc xấp xỉ có sai số không vượt quá một giá trị ngưỡng  ∈ [0, 1) cho trước. Cho V ⊆ U và X ⊆ A. Ta gọi tập hợp sau dom(V,X) = {u(X) | u ∈ V } là miền giá trị của V trên X. Nhắc lại rằng, trên V tồn tại quan hệ tương đương IND(X|V ) xác định bởi ∀u, v ∈ V : (u, v) ∈ IND(X|V ) ⇔ u(X) = v(X). 64 Họ các lớp tương đương trên V , tương ứng với IND(X|V ), được ký hiệu là V/X. Bây giờ cho X, Y ⊆ A là hai tập con các thuộc tính. Giả sử U/X = {V1, V2, · · · , Vm}; Vi/Y = {V i1 , V i2 , · · · , V ini}; 1 ≤ i ≤ m. Nghĩa là, với mọi đối tượng u, v ∈ U , ta có u(X) = v(X) ⇔ ( ∃i : u, v ∈ Vi ) (3.3) u(X ∪ Y ) = v(X ∪ Y ) ⇔ ( ∃i, j : u, v ∈ V ij ) . (3.4) Định lý sau cho ta các đặc trưng của phụ thuộc hàm và phụ thuộc đa trị. Định lý 3.1. Cho X, Y ⊆ A. Đặt Z = A \ (X ∪ Y ). Khi đó, a) X → Y ⇔ Vi/Y = {Vi} (hay ni = 1), với mọi 1 ≤ i ≤ m. b) X →→ Y ⇔ dom(Vi, Z) = dom(V ij , Z), với mọi 1 ≤ i ≤ m, 1 ≤ j ≤ ni. Chứng minh. a) Hiển nhiên đúng xuất phát từ định nghĩa của phụ thuộc hàm và (3.3)-(3.4). b) (⇒) Giả sử X →→ Y . Vì bao hàm thức dom(Vi, Z) ⊃ dom(V ij , Z) là hiển nhiên, nên ta chỉ cần chứng minh dom(Vi, Z) ⊂ dom(V ij , Z), với mọi i, j. Thật vậy, nếu α ∈ dom(Vi, Z) thì ∃v ∈ Vi sao cho v(Z) = α. Lấy u ∈ V ij suy ra u ∈ Vi hay u(X) = v(X). Vì X →→ Y nên tồn tại t ∈ Vi sao cho t(Y ) = u(Y ) (nên t ∈ V ij ) và t(Z) = v(Z) = α. Vậy α ∈ dom(V ij , Z). (⇐) Giả sử dom(Vi, Z) = dom(V ij , Z), với mọi i, j. Lấy hai đối tượng bất kỳ u, v ∈ U mà u(X) = v(X), gọi i và j là các chỉ số sao cho u, v ∈ Vi và u ∈ V ij . Vì v ∈ Vi nên α = v(Z) ∈ dom(V i, Z) = dom(V ij , Z). Nghĩa là tồn tại đối tượng t ∈ V ij sao cho t(Z) = α. Vì t, u ∈ V ij nên t(X) = u(X) = v(X) và t(Y ) = u(Y ). Hơn nữa t(Z) = v(Z). Vậy X →→ Y . Ví dụ 3.1. Cho hệ thống quản lý các môn học của sinh viên với tập thuộc tính A = {a1, a2, a3, a4} trong đó a1, a2, a3, a4 lần lượt lưu môn học, mã sinh viên, tên sinh viên, lớp. 65 U a1 a2 a3 a4 u1 T01 101 G K1 u2 T01 102 H K1 u3 T01 103 I K1 u4 T01 104 J K1 u5 T02 101 G K1 u6 T02 102 H K1 u7 T02 103 I K1 u8 T02 104 J K1 u9 T05 201 E K2 u10 T05 202 F K2 u11 T05 203 K K2 u12 T06 201 E K2 u13 T06 202 F K2 u14 T06 203 K K2 Bảng 3.1: Bảng dữ liệu sinh viên. Từ hệ thống trên, đặt X = {a2}; Y = {a3} ta có: U/X = {V1 = {u1, u5}; V2 = {u2, u6}; V3 = {u3, u7}; V4 = {u4, u8}; V5 = {u9, u12}; V6 = {u10, u13}; V7 = {u11, u14}}. Mặt khác, Vi/Y = {Vi}, với mọi 1 ≤ i ≤ 7. Do đó X → Y Bây giờ ta xét X = {a4} và Y = {a1}. Rõ ràng X →→ Y . Chúng ta sẽ kiểm tra điều này theo kết quả của Định lý 3.1. Đặt Z = A \ (X ∪ Y ) = {a2, a3}, ta có U/X = {V1 = {u1, u2, u3, u4, u5, u6, u7, u8}; V2 = {u9, u10, u11, u12, u13, u14}} 66 V1/Y = {V 11 = {u1, u2, u3, u4}; V 12 = {u5, u6, u7, u8}} V2/Y = {V 21 = {u9, u10, u11}; V 22 = {u12, u13, u14}} dom(V1, Z) = {(101, G), (102, H), (103, I), (104, J)} dom(V 11 , Z) = {(101, G), (102, H), (103, I), (104, J)} = dom(V1, Z) dom(V 12 , Z) = {(101, G), (102, H), (103, I), (104, J)} = dom(V1, Z) dom(V2, Z) = {(201, E), (201, F ), (201, G)} dom(V 21 , Z) = {(201, E), (201, F ), (201, G)} = dom(V2, Z) dom(V 22 , Z) = {(201, E), (201, F ), (201, G)} = dom(V2, Z) Vậy X →→ Y. 3.2.2. Đặc trưng phụ thuộc bằng ma trận phụ thuộc Trong phần này chúng tôi trình bày thuật toán tìm tất cả vế phải của phụ thuộc đa trị X →→ Y và thuật toán kiểm tra phụ thuộc đa trị xấp xỉ chấp nhận được với sai số bé hơn hoặc bằng một giá trị ngưỡng không âm cho trước. Trước tiên, chúng tôi đưa vào khái niệm ma trận phụ thuộc nhằm cung cấp một công cụ mới cho việc kiểm định phụ thuộc đa trị một cách dễ dàng đồng thời mở ra một cách tiếp cận mới với phụ thuộc xấp xỉ. Trong mục trước, chúng ta đã đưa ra điều kiện cần và đủ để X →→ Y đúng. Dựa vào kết quả đó, chúng ta sẽ xây dựng thuật toán khả thi để kiểm tra một phụ thuộc đúng bằng sự phân hoạch trên các giá trị thuộc tính. Vẫn ký hiệu U/X = {V1, V2, · · · , Vm}. Với mỗi i cố định, ta ký hiệu dom(Vi, Z) = {α1, α2, · · · , αp}, Vi/Y = {V i1 , V i2 , · · · , V iq } (tức là q = ni), chúng ta sẽ thiết lập một ma trận phụ thuộc Di = (drs)p×q được định nghĩa bởi 67 drs = 1 nếu αr ∈ dom(V i s , Z), 0 nếu αr 6∈ dom(V is , Z), và ký hiệu ‖Di‖ = p∑ r=1 q∑ s=1 drs = q∑ s=1 p∑ r=1 drs. Từ định nghĩa suy ra drs = 1 khi và chỉ khi có một đối tượng t ∈ V is mà t(Z) = αr. Do đó tổng các số trên hàng thứ r của ma trận: q∑ s=1 drs chính là số các đối tượng (nằm rãi rác trong các V is ) có giá trị tại thuộc tính Z bằng αr, còn tổng các số trên cột thứ s: p∑ r=1 drs lại chính là Card(V i s ). Hiển nhiên ‖Di‖ = Card(Vi). Nói cách khác, số đối tượng của Vi chính là số các số 1 xuất hiện trong ma trận D i. Ta nói ma trận Di là dầy đặc nếu drs = 1, với mọi r, s. Một điều thú vị là phụ thuộc đa trị X →→ Y có thể được đặc trưng hoàn toàn bởi các ma trận Di. Điều đó được khẳng định trong định lý sau Định lý 3.2. X →→ Y ⇔ Di là ma trận dầy đặc với mọi i ∈ {1, 2, · · · ,m}. Chứng minh. Giả sử X →→ Y . Theo Định lý 3.1, với mọi i ta có dom(V is , Z) = dom(Vi, Z) = {α1, α2, · · · , αp}, 1 ≤ s ≤ q = ni. Do đó, drs = 1 với mọi r, s, nên D i là ma trận dầy đặc. Ngược lại, giả sử các Di đều là ma trận dầy đặc. Với mọi αr ∈ dom(Vi, Z) và V is (1 ≤ s ≤ q) ta có drs = 1 nên αr ∈ dom(V is , Z). Vậy, dom(Vi, Z) = dom(V is , Z). Tức là X →→ Y . Dễ thấy X →→ Y khi và chỉ khi X →→Vi Y , ∀i = 1..m. Định lý 3.2 thực ra khẳng định rằng X →→Vi Y nếu và chỉ nếu Di là ma trận dầy đặc. Từ đó, nếu X →/→ Y thì có ít nhất một ma trận Di không dầy đặc hay nói cách khác, tồn tại 68 Vi mà X →/→Vi Y . Một câu hỏi khá tự nhiên là nếu các Di "gần dầy đặc" thì Y có phụ thuộc xấp xỉ X hay không? Để đánh giá khả năng "gần dầy đặc" của họ ma trận phụ thuộc, dưới đây chúng tôi sẽ đưa ra khái niệm về độ dầy đặc của một họ ma trận. Cho C và D là các ma trận chỉ chứa các giá trị 0 hoặc 1. Ta nói C là ma trận con của D và ký hiệu là C ≺ D nếu C có thể thu được từ D bằng cách xoá đi một số hàng và cột nào đó. Nếu D không phải là ma trận dầy đặc, ta cần tìm ma trận con dầy đặc lớn nhất của D. Cụ thể, ta ký hiệu k(D) := max {‖C‖ | C ≺ D và C dầy đặc}. với ‖C‖ là tổng giá trị các phần tử của ma trận C. Bây giờ tương ứng với họ các ma trận {D1, D2, · · · , Dm}, ta gọi độ dầy đặc của họ ma trận này là giá trị sau s(D1, D2, · · · , Dm) := m∑ i=1 k(Di) m∑ i=1 ‖Di‖ . Rõ ràng, s(D1, D2, · · · , Dm) ≤ 1 và, từ Định nghĩa 3.1 và Định lý 3.1 ta có s(D1, D2, · · · , Dm) = 1 ⇔ X →→ Y ⇔ g3(X →→ Y ) = 0. Tổng quát hơn, ta có kết quả sau Định lý 3.3. s(D1, D2, · · · , Dm) = 1− e(X →→ Y ). Trước khi chứng minh định lý này, chúng ta cần làm rõ ý nghĩa của các ma trận con Ci ≺ Di. Như nhận xét sau Định lý 3.2, Di không dầy đặc khi và chỉ khi X →/→Vi Y . Lúc đó, ta cần xoá một số đối tượng trong Vi để thu được tập Wi ⊂ Vi mà X →→Wi Y . Theo Định lý 3.1, tồn tại giá trị αr ∈ dom(Vi, Z) mà αr 6∈ dom(V is , Z), với một s nào đó. Như vậy, để thu được tập hợp Wi ⊂ Vi có khả 69 năng thoả mãn phụ thuộc X →→Wi Y ta cần thực hiện một trong hai thao tác cơ bản: (A): Xoá tất các cả đối tượng t trong lớp V is (B): Xoá tất cả các đối tượng t ∈ Vi mà t(Z) = αr Nếu thực hiện thao tác (A) thì tập Wi ⊂ Vi thu được sẽ tương ứng với ma trận con Ci nhận được từ Di bằng cách xoá đi cột s. Còn nếu thực hiện thao tác (B) thì tập Wi ⊂ Vi thu được sẽ tương ứng với ma trận con Ci nhận được từ Di bằng cách xoá đi hàng r. Như vậy, để có được phụ thuộc đúng X →→Wi Y chúng ta cần phải xoá đi các dòng và cột trên ma trận phụ thuộc Di để có được ma trận con dầy đặc Ci. Số đối tượng phải xoá chính là tổng số phần tử có giá trị 1 trên các dòng và cột của Di bị xoá. Tức là Card(Vi \ Wi) = ‖Di‖ − ‖Ci‖, hay Card(Wi) = ‖Ci‖. Tóm lại, việc tìm tập con Wi lớn nhất của Vi thoả mãn X →→Wi Y tương đương với việc tìm ma trận dầy đặc Ci ≺ Di có ‖Ci‖ cực đại (tức là ‖Ci‖ = k(Di)). Chứng minh Định lý 3.3. Từ những phân tích trên ta thấy, nếu gọi Wi là tập con có số phần tử lớn nhất của Vi, thoả mãn X →→Wi Y , thì Card(Wi) = k(Di). Mặt khác, để ý rằng Card(U) = m∑ i=1 ‖Di‖. Nên từ Định nghĩa 3.1 ta có g3(X →→ Y ) = 1− m∑ i=1 Card(Wi) m∑ i=1 ‖Di‖ = 1− s(D1, D2, · · · , Dm). Định lý được chứng minh. Để minh hoạ cho kết quả định lý trên, chúng ta xét hệ thống cho trong Bảng 3.2. Trong đó, U/X = {V1, V2}; V1 = {t1, t2, t3, t4, t5, t6, t7, t8, t9, t10}; V2 = {t11, t12}, V1/Y = {V 11 , V 12 , V 13 }; V 11 = {t1, t2, t3, t4}; V 12 = {t5, t6, t7}; V 13 = {t8, t9, t10}, 70 dom(V1, Z) = {α1, α2, α3, α4, α5} dom(V 11 , Z) = {α1, α2, α3, α4} dom(V 12 , Z) = {α3, α4, α5} dom(V 13 , Z) = {α1, α2, α4} V2/Y = {V 21 , V 22 }; V 21 = {t11}; V 22 = {t12}, dom(V2, Z) = dom(V 2 1 , Z) = dom(V 2 2 , Z) = {α5}. U X Y Z t1 1 A α1 t2 1 A α2 t3 1 A α3 t4 1 A α4 t5 1 B α3 t6 1 B α4 t7 1 B α5 t8 1 C α1 t9 1 C α2 t10 1 C α4 t11 2 B α5 t12 2 C α5 Bảng 3.2: Dữ liệu của hệ thống. 71 Hai ma trận D1 và D2 lần lượt được thiết lập như sau D1 =  V 11 V 1 2 V 1 3 α1 1 0 1 α2 1 0 1 α3 1 1 0 α4 1 1 1 α5 0 1 0  ; D2 =  V 21 V 22 α5 1 1  . Rõ ràng, D2 dầy đặc. Tuy vậy, D1 không dầy đặc nên X →/→ Y trên U . Có thể kiểm chứng được các ma trận con dầy đặc lớn nhất của D1 và D2 là C1 =  V 11 V 1 3 α1 1 1 α2 1 1 α4 1 1  ; C 2 =  V 21 V 22 α5 1 1  . Điều đó tương ứng với việc xoá hoàn toàn lớp V 12 = {t5, t6, t7}, các đối tượng trong V1 có t(Z) = α3 là {t3, t5}, có t(Z) = α5 là {t7} (tổng số có 4 đối tượng cần xoá). Độ dầy đặc của {D1, D2} là s(D1, D2) = ‖C1‖+ ‖C2‖ ‖D1‖+ ‖D2‖ = 8 12 = 2 3 . Do đó, ta có sai số phụ thuộc g3(X →→ Y ) = 1− 2 3 = 1 3 . Từ Định lý 3.3 và ví dụ trên ta thấy, chỉ cần làm việc trên các ma trận phụ thuộc, cụ thể là từ giá trị độ dầy đặc của họ ma trận phụ thuộc, chúng ta có thể tính được sai số phụ thuộc và từ đó khẳng định phụ thuộc có chấp nhận được hay không. Trong phần sau chúng ta sẽ bàn chi tiết vấn đề này. 72 3.3. Thuật toán kiểm định và tìm kiếm phụ thuộc 3.3.1. Thuật toán tính độ dầy đặc của dãy ma trận Bài toán đặt ra đầu tiên là với dãy ma trận {D1, D2, · · · , Dm} cho trước, hãy xác định độ dầy đặc của chúng. Từ định nghĩa ta thấy việc xác định s(D1, D2, · · · , Dm) chủ yếu dựa vào việc tính giá trị k(Di). Vì vậy, chúng tôi sẽ tập trung xây dựng thuật toán tìm kiếm các ma trận dầy đặc Ci ≺ Di sao cho ‖Ci‖ = k(Di). Để dễ hình dung, chúng tôi trình bày ý tưởng thuật toán thông qua một ví dụ cụ thể. Chúng ta hãy khảo sát lại hệ thống được cho trong Bảng 3.2. Ta cần phải xác định các ma trận dầy đặc C1 và C2, lớn nhất có thể, sao cho C1 ≺ D1 và C2 ≺ D2. Trong ma trận D1, chúng ta cần cân nhắc xem nên giữ lại số drs nào cho ma trận C1. Rõ ràng, các giá trị drs = 0 (như d1,2, d2,2...) bắt buộc phải được loại bỏ. Đối với các drs = 1 chúng ta thử tính toán xem cần loại bỏ tối thiểu bao nhiêu số 1 khác trong ma trận nếu quyết định giữ lại vị trí này. Chẳng hạn, đối với d1,1. Nếu cho phép d1,1 ∈ C1 thì bắt buộc phải loại đi cột 2 (V 12 ) và dòng 5 (α5) (vì nếu đã giữ lại d1,1 mà còn giữ lại dòng 5 hoặc cột 2 thì ma trận thu được không dầy đặc), do đó số giá trị 1 cần xoá ít nhất là 3. Ta đặt g1,1 = 3 và gọi đó là hệ số loại bỏ của d1,1. Tương tự, đối với d5,2, nếu muốn giữ lại vị trí này cho C 1 ta cần xoá các cột 1, 3 và các dòng 1, 2, nên phải xoá ít nhất là g5,2 = 7 số 1. Rõ ràng là những vị trí có hệ số loại bỏ càng bé càng cần được ưu tiên giữ lại cho ma trận C1. Một cách tự nhiên, ta gán grs = ∞ cho các vị trí drs = 0. Cuối cùng ta nhận được ma trận G1, gọi là ma trận hệ số loại bỏ của D1: D1 =  V 11 V 1 2 V 1 3 α1 1 0 1 α2 1 0 1 α3 1 1 0 α4 1 1 1 α5 0 1 0  → G1 =  V 11 V 1 2 V 1 3 α1 3 ∞ 4 α2 3 ∞ 4 α3 4 5 ∞ α4 1 4 3 α5 ∞ 7 ∞  73 Nhìn vào ma trận này ta thấy vị trí (4, 1) có hệ số loại bỏ bé nhất (g4,1 = 1) nên quyết định giữ lại vị trí này. Điều đó dẫn đến việc phải xoá đi dòng 5, ma trận D1 trở thành (số 0 in đậm cho biết vị trí mới bị xoá). D1 =  V 11 V 1 2 V 1 3 α1 1 0 1 α2 1 0 1 α3 1 1 0 α4 1 1 1 α5 0 0 0  Từ đây, tính lại ma trận hệ số G1, chọn giữ lại vị trí có hệ số (dương) bé nhất, xoá các dòng cột thích hợp rồi viết lại ma trận D1, tính ma trận G1... Quá trình lặp này kết thúc khi ta nhận được ma trận G1 chỉ chứa các giá trị 0 và ∞. Cụ thể, tiếp tục thao tác đối với ma trận trên ta được ↪→ G1 =  V 11 V 1 2 V 1 3 α1 2 ∞ 3 α2 2 ∞ 3 α3 3 5 ∞ α4 0 4 2 α5 ∞ ∞ ∞  → D1 =  V 11 V 1 2 V 1 3 α1 1 0 1 α2 1 0 1 α3 1 0 0 α4 1 0 1 α5 0 0 0  → ↪→ G1 =  V 11 V 1 2 V 1 3 α1 0 ∞ 1 α2 0 ∞ 1 α3 3 ∞ ∞ α4 0 ∞ 1 α5 ∞ ∞ ∞  → D1 =  V 11 V 1 2 V 1 3 α1 1 0 1 α2 1 0 1 α3 0 0 0 α4 1 0 1 α5 0 0 0  → 74 ↪→ G1 =  V 11 V 1 2 V 1 3 α1 0 ∞ 0 α2 0 ∞ 0 α3 ∞ ∞ ∞ α4 0 ∞ 0 α5 ∞ ∞ ∞  . Cuối cùng ta nhận được ma trận con dầy đặc C1 gồm sáu số 1. Đó cũng chính là số các giá trị 0 còn lại trong ma trận G1. Lúc đó, k(D1) = ‖C1‖ = 6. Đối với D2 thì cũng bằng kỹ thuật như trên ta thu được G2 = (0 0). Nên C2 = D2 và k(D2) = ‖C2‖ = 2. Bây giờ chúng tôi sẽ đưa ra thuật toán tìm các k(Di). Trước hết, đối với mỗi ma trận phụ thuộc Di, chúng ta cần xây dựng ma trận hệ số phụ thuộc Gi (thủ tục Compute_Gi). Một cách tổng quát, ma trận Gi = (grs) được xây dựng như sau: Nếu drs = 0 thì đặt grs = ∞, ngược lại, nếu drs = 1 thì grs là tổng số các số 1 tối thiểu cần phải loại để giữ lại số 1rs trong ma trận phụ thuộc D i, những số 1 chắc chắn bị loại là những số nằm trên dòng u mà dus = 0 hoặc nằm trên cột v mà drv = 0. Nói cách khác, khi giữ lại số 1rs thì phải loại các số 1uv nếu dus ∗ drv = 0. Tóm lại, ta có grs =  ∞ nếu drs = 0,∑ dus×drv=0 duv nếu drs = 1. Rõ ràng, grs = ∞ nếu drs = 0, grs = 0 nếu drs = 1 và việc giữ lại vị trí này không đòi hỏi phải xoá đi bất kỳ số 1 nào. Cuối cùng, grs = l > 0 nếu drs = 1 và việc giữ lại vị trí này đòi hỏi phải xoá đi ít nhất l số 1 khác. Nếu ma trận Gi chỉ gồm các giá trị 0 và ∞ thì các vị trí tương ứng với giá trị 0 sẽ xác định một ma trận con dầy đặc của Di, thuật toán dừng. Trong trường hợp ngược lại, chúng ta cần xác định vị trí 1hv với ghv > 0 đáng được giữ lại nhất. Với ý nghĩa của các grs như đã phân tích trên, rõ ràng vị trí này cần thoả mãn điều kiện 75 sau ghv = min{grs | grs > 0}. Với quyết định giữ lại giá trị 1hv ta phải xoá đi các số 1rs liên quan (tức là thoả mãn dhs ∗ drv = 0) và nhận được ma trận Di mới (thủ tục Modify_Di). Quá trình tiếp tục cho đến khi nhận được ma trận Gi chỉ gồm các giá trị 0 và ∞. Thuật toán được trình bày chi tiết như sau: Thuật toán 3.1. Xác định k(Di) Input: Di. Output: k(Di). Method: 1. k := ‖Di‖; 2. Compute_Gi; 3. Xác định ghv = min{grs | grs > 0}; 4. Nếu ghv = ∞ thì Output k và dừng; Ngược lại, sang 5; 5. k := k − ghv; 6. Modify_Di; 7. Quay lại 2; Proc Compute_Gi 1. For r ∈ {1..pi}; s ∈ {1..qi} do 2. If drs = 0 then grs := ∞ 3. Else 4. Begin 5. grs := 0; 6. For u ∈ {1..pi}; v := {1..qi} do 76 7. If dus ∗ drv = 0 then 8. grs := grs + duv; 9. End EndProc Compute_Gi; Proc Modify_Di 1. For r ∈ {1..pi}; s ∈ {1..qi} do 2. If drv ∗ dhs = 0 then 3. drs := 0. EndProc Modify_Di Giả sử ma trận Di có kích thước pi × qi. Lúc đó, thủ tục Compute_Gi có độ phức tạp tính toán O(p2i q 2 i ), còn thủ tục Modify_D i có độ phức tạp tính toán O(piqi). Do đó, độ phức tạp của mỗi vòng lặp là O(p 2 i q 2 i ) và thuật toán xác định k(Di) có độ phức tạp tính toán trong trường hợp xấu nhất là O(p3i q 3 i ). Chú ý rằng, nếu ký hiệu xi = Card(Vi) = ‖Di‖ thì ta có ước lượng: xi ≤ piqi ≤ x2i . 3.3.2. Thuật toán kiểm định phụ thuộc xấp xỉ Trong phần này, chúng ta sẽ đánh giá xem với hai tập thuộc tính đã cho X, Y ⊆ A, phụ thuộc X →→ Y có chấp nhận được với một sai số  hay không. Từ Định lý 3.2 và Định lý 3.3, chúng ta thấy rằng, phụ thuộc X →→ Y là chấp nhận được nếu s(D1, D2, · · · , Dm) ≥ 1− . Tức là m∑ i=1 k(Di) ≥ (1− ) Card(U). Thuật toán được xây dựng như sau Thuật toán 3.2. Kiểm tra phụ thuộc chấp nhận được 77 Input: Hệ thống thông tin A = (U,A), Các tập X, Y ⊆ A; Giá trị ngưỡng  ≥ 0. Output: g3(X →→ Y ) ≤  ? Method: 1. s := 0; 2. OK:= TRUE; 3. For i ∈ {1..m} do 4. Begin 5. Xây dựng Di; 6. s := s + k(Di); 7. If s ≥ (1− )× Card(U) then Exit; 8. End; 9. OK:= FALSE; Trong thuật toán trên, m chính là số lớp tương đương của IND(X). Giả sử Card(U) = n và mỗi ma trận Di có kích thước pi × qi. Khi đó việc xây dựng các ma trận Di có thể thực hiện bằng cách sắp xếp các đối tượng trong U , vì vậy độ phức tạp của thuật toán xây dựng dãy các ma trận Di là O(nlogn) và độ phức tạp của thuật toán kiểm chứng phụ thuộc xấp xỉ được xác định bởi vòng lặp For ở 3. Thực chất ở đây chúng ta thực hiện hai vòng lặp, một vòng lặp xây dựng các Di và một vòng lặp tính sai số phụ thuộc. Vòng lặp tính sai số phụ thuộc có độ phức tạp trong trường hợp xấu nhất là O( m∑ i=1 p3i q 3 i ). Vì piqi ≤ x2i , nên độ phức tạp tính toán của Thuật toán 3.2 không vượt quá O(nlogn + m∑ i=1 x6i ). 78 3.3.3. Thuật toán tìm kiếm phụ thuộc tối tiểu vế phải Một phụ thuộc X →→ Y được gọi là tối tiểu vế phải và ký hiệu X→→minY nếu với mọi Y ′ ⊂ Y , X →/→ Y ′. Ta đã biết rằng, nếu X →→ Y thì Y = Y1∪Y2∪· · ·∪Yn với X→→minYi với mọi 1 ≤ i ≤ n. Vì vậy, trong phần này chúng tôi chỉ đặt vấn đề tìm kiếm tất cả các phụ thuộc tối tiểu vế phải với vế trái X là một tập con cho trước các thuộc tính. Thuật toán chúng tôi sắp đề nghị sử dụng một phần ý tưởng của Thuật toán Tane [25] được các tác giả này thiết kế nhằm tìm các phụ thuộc hàm không tầm thường dạng X \ {c} → c. Cụ thể, chúng tôi sẽ tìm các tập con Y ⊆ A thoả mãn X→→minY theo thứ tự tăng dần của Card(Y ). Nghĩa là, việc tìm kiếm vế phải của phụ thuộc xuất phát từ họ các tập có một phần tử, tập có hai phần tử ... Gọi Li là họ các tập thuộc tính Y có kích thước i và có khả năng thoả X →→ Y . Vì X→→minY thì X ∩ Y = ∅ nên chúng ta khởi tạo L1 := {{a} | a ∈ A \X}. Hơn nữa, nếu Y ∈ Li và X→→minY thì Y không thể là tập con của tập Y ′ ∈ Lj với j > i mà X→→minY ′, nói cách khác, Y sẽ không tham gia vào việc xây dựng họ Lj, với mọi j > i. Vì vậy ở đây chúng tôi dùng thêm họ Mi lưu các tập Z ∈ Li mà X →/→ Z và xây dựng họ Li+1 dựa vào Mi. Cụ thể, sau khi tìm tất cả các phụ thuộc X→→minY với Y ∈ Li, chúng ta xây dựng Li+1 bằng cách lấy hợp hai tập bất kỳ Y1, Y2 ∈ Mi, nếu hợp này cho ta một tập có i + 1 phần tử thì đưa nó vào Li+1. Rõ ràng, ban đầu chúng ta cần khởi tạo Mi bằng Li, và sau đó mỗi khi có một phụ thuộc X →→ Y đúng với Y ∈ Li thì loại Y khỏi Mi. Cuối cùng, nếu Z = A \ (X ∪ Y ) thì từ X →→ Y ta cũng có X →→ Z và Card(Y ) + Card(Z) = Card(A \ X). Vì vậy quá trình tìm kiếm của chúng tôi chỉ diễn ra trong các họ Li với i ≤ Card(A \X)/2. Thuật toán 3.3. Tìm kiếm tất cả phụ thuộc tối tiểu. Input: Hệ thống thông tin A = (U,A), Tập con X ⊆ A. 79 Output: Tất cả phụ thuộc X→→minY. Method: 1. i := 1; 2. L1 := {{a} | a ∈ A \X}; 3. While i ≤ Card(A \X)/2 do 4. Mi := Li; 5. For Y ∈ Mi do 6. If X →→ Y then 7. Output X→→minY ; 8. Mi := Mi \ {Y }; 9. EndIf; 10. EndFor; 11. Compute_Li+1; 12. i := i + 1; 13. EndWhile; Proc Compute_Li+1 1. Li+1 := ∅; 2. For X, Y ∈ Mi, X 6= Y do 3. Z := X ∪ Y ; 4. If Card(Z) = i + 1 then 5. Li+1 := Li+1 ∪ {Z}; 6. EndIf; 7. EndFor; 80 EndProc Compute_Li+1; Độ phức tạp tính toán của thuật toán này được xác định bởi vòng lặp While ở 3. Tại mỗi bước của vòng lặp, chúng ta xét tất cả các phần tử của Mi và kiểm tra phụ thuộc, sau đó tính Li+1 theo Mi. Chú ý rằng Card(Mi) ≤ Cik (Cik là tổ hợp k chập i phần tử, với k = Card(A \X)). Mặt khác, độ phức tạp của thuật toán kiểm tra phụ thuộc là O(nlogn + m∑ i=1 x6i ), còn độ phức tạp của thủ tục Compute_Li+1 là O(C2Card(Mi)) = O(Card(Mi) 2). Vì vậy độ phức tạp tính toán của Thuật toán 3.3 trong trường hợp xấu nhất là O( k/2∑ i=1 Cik × (nlogn + m∑ i=1 x6i )) = O(2 k/2 × (nlogn + m∑ i=1 x6i )). Trong đó, k = Card(A \ X), n = Card(U), m là số lớp tương đương của IND(X) và xi là lực lượng của lớp tương đương Vi, 1 ≤ i ≤ m. 3.4. Mở rộng phụ thuộc hàm và phụ thuộc đa trị Trong ví dụ về dữ liệu sinh viên cho trong Bảng 3.1, các thuộc tính mã sinh viên, họ tên là phụ thuộc đa trị vào thuộc tính lớp, nghĩa là mọi sinh viên trong cùng một lớp sẽ phải học các môn như nhau. Đó là theo cách đào tạo niên chế. Bây giờ, nếu nhà trường đào tạo theo tín chỉ, trong đó có một số học phần tự chọn, và với mỗi học phần như vậy các sinh viên trong một lớp có thể học các môn khác nhau (nhưng được xem là tương đương), thì chúng ta vẫn có lý do để nói rằng các thuộc tính mã sinh viên, họ tên phụ thuộc đa trị vào thuộc tính lớp, mặc dù lúc này điều kiện (3.2) không còn đúng nữa. Rõ ràng là trong trường hợp này các định nghĩa như trên không còn phù hợp. Mặt khác, trong thực tế không hiếm khi những dữ liệu thu nhận được không còn chính xác như vốn có. Điều này chắc chắn cũng làm cho chúng ta không phát hiện hết mọi phụ thuộc từ cơ sở dữ liệu. Để góp phần phát hiện các phụ thuộc tiềm ẩn trong dữ liệu, trong phần này chúng tôi sẽ cố gắng đưa ra một cách tiếp cận mở rộng của các khái niệm phụ thuộc 81 hàm và phụ thuộc đa trị. Các khái niệm mở rộng này được thiết lập dựa trên một hàm đánh giá độ tương tự giữa các giá trị trong bảng dữ liệu, cũng gần như nhát cắt được trình bày trong [9]. Tuy nhiên các tác giả trong [9] xây dựng các nhát cắt như một quan hệ tương đương, do đó hai giá trị có quan hệ với nhau có thể khác biệt rất lớn vì tính chất bắc cầu suy dẫn sẽ dẫn đến điều đó, trong khi nhiều ứng dụng thực tế không đòi hỏi điều này, thậm chí khó có thể đáp ứng được. Trong cách xây dựng của chúng tôi, khi sự tương tự giữa hai giá trị đạt đến một mức độ nhất định, chúng ta có thể xem hai giá trị này là “đồng nhất“. Với cách tiếp cận này, các phụ thuộc thực ra cũng là một kiểu phụ thuộc xấp xỉ. Để kiểm chứng một phụ thuộc mở rộng nào đó, chúng tôi cũng sẽ sử dụng một kiểu ma trận phụ thuộc tương tự như đã làm để kiểm tra phụ thuộc trong Mục 3.2. trong phần phụ thuộc xấp xỉ. 3.4.1. Quan hệ tương tự Cho hệ thống thông tin A = (U,A). Với mỗi V ⊆ U và X ⊆ A, ta gọi miền giá trị của V trên X là tập hợp dom(V,X) := {u(X) | u ∈ V }. Khi V = U ta viết dom(X) thay cho dom(U,X) và hơn nữa, nếu X = {a}, ta chỉ viết một cách đơn giản: Ia = dom({a}). Để mở rộng các khái niệm phụ thuộc, trên các tập giá trị Ia, ngoài quan hệ bằng nhau thông thường ta giả định là tồn tại một quan hệ tương tự, phản ánh độ gần nhau giữa các giá trị. Một cách chính xác, một ánh xạ s : Ia × Ia → [0, 1] được gọi là quan hệ tương tự trên tập Ia nếu hai điều kiện sau thỏa mãn: a) s(a1, a2) = s(a2, a1), với mọi a1, a2 ∈ Ia, b) s(a1, a2) = 1 ⇔ a1 = a2. s(a1, a2) được gọi là độ tương tự giữa hai giá trị a1 và a2. Cho α ∈ [0, 1], hai giá trị a1 và a2 được gọi là α−tương tự, và ký hiệu a1 =α a2, nếu s(a1, a2) ≥ α. Rõ ràng 82 khi hàm s chỉ nhận hai giá trị 0 và 1, thì với mọi α > 0, a1 =α a2 khi và chỉ khi a1 = a2. Cho tập thuộc tính B = {b1, b2, · · · , bm} ⊆ A và ξ, η ∈ dom(B). Khi đó ξ và η có thể xem là hai dãy (ξ1, ξ2, · · · , ξm) và (η1, η2, · · · , ηm), với ξi, ηi ∈ Ibi , 1 ≤ i ≤ m. Độ tương tự giữa ξ và η được định nghĩa là giá trị: S(ξ, η) = min{s(ξi, ηi) | 1 ≤ i ≤ m}. (3.5) Bây giờ, giả sử ξ ∈ dom(B) và E ⊆ dom(B), ta gọi độ thuộc của ξ vào E là độ tương tự lớn nhất giữa ξ với các giá trị trong E. Cụ thể, giá trị này được xác định bởi: µ(ξ, E) = max η∈E S(ξ, η). Một cách tự nhiên, ta tiếp tục dùng ký hiệu ξ =α η nếu S(ξ, η) ≥ α và nói rằng ξ và η là α−tương tự. Cũng vậy, ta nói ξ thuộc vào tập E với mức α, và ký hiệu ξ ∈α E, nếu µ(ξ, E) ≥ α. Mệnh đề dưới đây cho ta một số tính chất cơ bản của các khái niệm này mà việc chứng minh có thể được suy ra trực tiếp từ định nghĩa. Mệnh đề 3.4. Cho B ⊆ A, E ⊆ dom(B), ξ, η ∈ dom(B), ta có a) S(ξ, η) = S(η, ξ); S(ξ, η) = 1 ⇔ ξ = η. b) 0 ≤ µ(ξ, E) ≤ 1; µ(ξ, E) = 1 ⇔ ξ ∈ E. c) Nếu E ⊆ E ′ ⊆ dom(B), thì µ(ξ, E) ≤ µ(ξ, E ′). d) ξ ∈α E ⇔ ∃η ∈ E, ξ =α η. Ví dụ 3.2. Xét hệ thống với ba thuộc tính: a (tên lập trình viên), b (trình độ chuyên môn), c (ngôn ngữ lập trình sử dụng) được cho trong Bảng 3.3, còn quan hệ tương tự giữa các giá trị trong từng thuộc tính được cho bởi Bảng 3.4 và Bảng 3.5. 83 a b c A Đại học PASCAL A Đại học FORTRAN A Đại học COBOL A Trung cấp PASCAL A Trung cấp C A Trung cấp FORTRAN A Thạc sĩ COBOL A Thạc sĩ PASCAL B Đại học C B Đại học PASCAL Bảng 3.3: Bảng dữ liệu về các lập trình viên b Đại học Trung cấp Thạc sĩ Đại học 1 0.6 0.8 Trung cấp 0.6 1 0.3 Thạc sĩ 0.8 0.3 1 Bảng 3.4: Quan hệ tương tự trên Ib c FORTRAN COBOL PASCAL C FORTRAN 1 0.9 0.7 0.8 COBOL 0.9 1 0.7 0.6 PASCAL 0.7 0.7 1 0.8 C 0.8 0.6 0.6 1 Bảng 3.5: Quan hệ tương tự trên Ic 84 Đặt B = {b, c}, ξ= (Đại học, FORTRAN), η= (Thạc sĩ, COBOL), với ξ, η ∈ dom(B), ta có S(ξ, η) = min{s(Đại học, Thạc sĩ), s(FORTRAN, COBOL)} = min{0.8, 0.9} = 0.8. Mặt khác, với E ={Đại học,Trung cấp} ⊆ Ib và Thạc sĩ ∈ Ib, ta có µ(Thạc sĩ, E) = max{s(Thạc sĩ, Đại học), s(Thạc sĩ, Trung cấp)} = max{0.8, 0.3} = 0.8. Như vậy, ξ =0.8 η và Thạc sĩ ∈0.8 E. 3.4.2. Phụ thuộc mở rộng và các tính chất Dựa trên quan hệ α−tương tự trên các tập giá trị, chúng ta sẽ đưa ra các khái niệm phụ thuộc hàm và phụ thuộc đa trị mở rộng. Một cách chính xác, chúng ta có các định nghĩa sau Định nghĩa 3.2. Cho X, Y ⊆ A và α, β ∈ [0, 1]. Ta nói Y là (α, β)−phụ thuộc hàm vào X trên U và ký hiệu X α,β−→ Y nếu ∀u, v ∈ U : u(X) =α v(X) ⇒ u(Y ) =β v(Y ). Khi α = β = 1 ta nhận được định nghĩa phụ thuộc hàm kinh điển. Định nghĩa 3.3. Cho X, Y ⊆ A (với X ∩ Y = ∅, X ∪ Y A) và α, β ∈ [0, 1]. Đặt Z = A \ (X ∪ Y ). Ta nói Y là (α, β)−phụ thuộc đa trị vào X trên U , và ký hiệu X α,β→→ Y , nếu với mọi cặp đối tượng u, v ∈ U sao cho u(X) =α v(X), tồn tại đối tượng t ∈ U sao cho t(X) =α u(X), đồng thời thỏa mãn một trong hai điều kiện a) t(Y ) = u(Y ) và t(Z) =β v(Z), b) t(Y ) =β u(Y ) và t(Z) = v(Z). 85 Rõ ràng, khi α = β = 1 hai điều kiện trên là đồng nhất và trùng với (3.2), nên ta cũng nhận được khái niệm phụ thuộc đa trị kinh điển. Khi α = 1, nếu X 1,β−→ Y , ta gọi Y là β−phụ thuộc hàm vào X. Tương tự, X 1,β→→ Y thì Y được gọi là β−phụ thuộc đa trị vào X. Từ các định nghĩa mở rộng trên dễ kiểm tra được rằng, nếu 0 ≤ α ≤ α′ ≤ 1, và 0 ≤ β′ ≤ β ≤ 1 thì X α,β−→ Y (X α,β→→ Y ) kéo theo X α′,β′−→ Y (X α′,β′→→ Y ). Ngoài ra, một số tính chất của phụ thuộc hàm và phụ thuộc đa trị vẫn còn đúng đối với các phụ thuộc mở rộng. Điều đó được khẳng định trong mệnh đề dưới đây Mệnh đề 3.5. Cho X, Y, Z ⊆ A, α, β ∈ [0, 1]. Khi đó a) Nếu Y ⊆ X thì X α,β−→ Y, với mọi 0 ≤ β ≤ α ≤ 1. b) Nếu X α,β−→ Y thì X ∪ Z α,γ−→ Y ∪ Z, với γ = min{α, β}. c) Nếu X α,β−→ Y và Y β,γ−→ Z, thì X α,γ−→ Z. d) Nếu X α,β→→ Y và A \ (X ∪ Y ) 6= ∅ thì X α,β→→ A \ (X ∪ Y ). e) Nếu X α,β−→ Y thì X α,β→→ Y. Chứng minh. a) Hiển nhiên đúng vì nếu Y ⊆ X thì với mọi đối tượng u, v ∈ U , u(X) =α v(X) kéo theo u(Y ) =β v(Y ). b) Với mọi cặp đối tượng u, v ∈ U nếu u(X∪Z) =α v(X∪Z) thì u(Z) =α v(Z) và u(X) =α v(X). Vì X α,β−→ Y nên u(Y ) =β v(Y ). Do đó u(Y ∪Z) =min{α,β} v(Y ∪Z). Vậy X ∪ Z α,γ−→ Y ∪ Z, với γ = min{α, β}. c) Với mọi cặp đối tượng u, v ∈ U nếu u(X) =α v(X) thì u(Y ) =β v(Y ) do X α,β−→ Y . Mặt khác, vì Y β,γ−→ Z, nên u(Z) =γ v(Z). Vậy X α,γ−→ Z. d) Không mất tính tổng quát, giả sử X ∩ Y = ∅. Khi đó, đặt Z = A \ (X ∪ Y ), thì Y = A \ (X ∪ Z). Từ X α,β→→ Y suy ra với mọi cặp đối tượng u, v ∈ U 86 mà u(X) =α v(X) thì tồn tại đối tượng t ∈ U sao cho t(X) =α u(X) và t(Y ) = u(Y ), t(Z) =β v(Z) hoặc t(Y ) =β u(Y ), t(Z) = v(Z). Do đó X α,β→→ Z. e) Đặt Z = A \ (X ∪ Y ). Do X α,β−→ Y nên với mọi cặp đối tượng u, v ∈ U mà u(X) =α v(X) ta có v(Y ) =β u(Y ). Bằng cách chọn t = v ta nhận được t(X) =α u(X), t(Z) = v(Z) và t(Y ) =β u(Y ). Vậy X α,β→→ Y . Ví dụ 3.3. Xét hệ thống A = (U, {X, Y, Z}) được cho trong Bảng 3.6, các quan hệ tương tự trên VX , VY và VZ được cho trên Bảng 3.7. Khi đó, dễ thấy X →/→ Y . Nhưng X (0.8,0.9)→→ Y . U X Y Z t1 x1 y1 z1 t2 x2 y2 z1 t3 x3 y3 z2 t4 x3 y1 z2 t5 x1 y3 z3 t6 x1 y2 z3 t7 x4 y1 z1 t8 x4 y1 z2 Bảng 3.6: Dữ liệu của hệ thống. X x1 x2 x3 x4 x1 1 0.8 0.6 0.3 x2 0.8 1 0.9 0.4 x3 0.6 0.9 1 0.4 x4 0.3 0.4 0.4 1 Y y1 y2 y3 y1 1 0.5 0.7 y2 05 1 0.9 y3 0.7 0.9 1 Z z1 z2 z3 z1 1 0.6 0.7 z2 06 1 0.8 z3 0.7 0.8 1 Bảng 3.7: Các quan hệ tương tự trên IX , IY và IZ . 87 3.4.3. Đặc trưng β−phụ thuộc bằng ma trận phụ thuộc Trong Mục 3.2. để nghiên cứu phụ thuộc đa trị, chúng ta đã thiết lập ma trận phụ thuộc dựa vào phân hoạch trên các giá trị thuộc tính và đã chứng minh được rằng, X →→ Y đúng khi và chỉ khi ma trận phụ thuộc là dầy đặc, tức là mọi phần tử của ma trận đều có giá trị 1. Trong trường hợp ma trận phụ thuộc là gần đặc (tức là chứa phần lớn các số 1), thì ta cũng nhận được một phụ thuộc đa trị xấp xỉ (tức là bỏ đi một số ít đối tượng nào đó của bảng dữ liệu thì nhận được phụ thuộc đúng). Trên cơ sở các kết quả này, một thuật toán kiểm chứng phụ thuộc và phụ thuộc xấp xỉ dựa vào ma trận phụ thuộc cũng đã được thiết lập. Phát triển ý tưởng đó, ở đây chúng ta sẽ xây dựng một ma trận có vai trò tương tự trong việc xác định β−phụ thuộc đa trị. Giả sử X,Y ⊆ A và U/X = {U1, U2, · · · , Um}. Rõ ràng, X 1,β→→ Y đúng trên U khi và chỉ khi X 1,β→→ Y đúng trên mọi Ui. Do đó, ở đây ta chỉ hạn chế việc kiểm tra phụ thuộc trên mỗi Ui cố định. Ký hiệu Z = A \ (X ∪ Y ). Giả sử dom(Ui, Y ) = {ξ1, ξ2, · · · , ξp(i)} và dom(Ui, Z) = {η1, η2, · · · , ηq(i)}. Với mỗi ξj, ηk ta ký hiệu Ej := {t(Z) | t ∈ Ui; t(Y ) = ξj} ⊆ dom(Ui, Z); Fk := {t(Y ) | t ∈ Ui; t(Z) = ηk} ⊆ dom(Ui, Y ). Ta gọi ma trận phụ thuộc mở rộng, tương ứng với lớp Ui, là D i = (djk)p(i)×q(i), với các thành phần djk được xác định bởi: djk := max{µ(ξj, Fk), µ(ηk, Ej)}. Ma trận Di được gọi là β−dầy đặc nếu với mọi j, k ta đều có djk ≥ β, hay, một cách tương đương: hoặc ξj ∈β Fk hoặc ηk ∈β Ej. Tương tự như phụ thuộc đa trị kinh điển, β−phụ thuộc đa trị cũng có thể được đặc trưng hoàn toàn bằng họ các ma trận phụ thuộc mở rộng Di. Điều đó được khẳng định trong định lý sau 88 Định lý 3.6. Y là β−phụ thuộc đa trị vào X khi và chỉ khi Di là β−dầy đặc, với mọi 1 ≤ i ≤ m. Chứng minh. Giả sử X 1,β→→ Y . Chúng ta sẽ chứng minh mọi Di đều là ma trận β−dầy đặc. Thật vậy, với mọi 1 ≤ j ≤ p(i) và 1 ≤ k ≤ q(i), tồn tại hai đối tượng u, v ∈ Ui sao cho u(Y ) = ξj và v(Z) = ηk. Vì u và v cùng thuộc lớp Ui nên u(X) = v(X). Theo định nghĩa của β−phụ thuộc đa trị, tồn tại đối tượng t ∈ Ui thoả mãn một trong hai điều kiện sau a) t(Y ) = u(Y ) = ξj và t(Z) =β v(Z) = ηk, b) t(Y ) =β u(Y ) = ξj và t(Z) = v(Z) = ηk. Nếu trường hợp a) xãy ra thì t(Z) ∈ Ej và ηk =β t(Z). Do đó, µ(ηk, Ej) ≥ β. Tương tự, nếu b) xãy ra thì µ(ξj, Fk) ≥ β. Cả hai trường hợp đó đều dẫn đến djk ≥ β. Vì điều này đúng với mọi djk nên D i là ma trận β−dầy đặc. Ngược lại, giả sử mọi Di đều là ma trận β− dầy đặc. Cho hai đối tượng tuỳ ý u, v ∈ U thoả mãn u(X) = v(X). Lúc đó, u và v phải thuộc cùng một lớp tương đương Ui nào đó. Đặt ξj = u(Y ) và ηk = v(Z). Do djk ≥ β nên ta có i) hoặc µ(ξj, Fk) ≥ β, ii) hoặc µ(ηk, Ej) ≥ β. Nếu i) đúng thì tồn tại t ∈ Ui sao cho t(Z) = ηk = v(Z) và t(Y ) =β ξj = u(Y ), còn nếu ii) đúng thì tồn tại t ∈ Ui sao cho t(Y ) = ξj = u(Y ) và t(Z) =β ηk = v(Z). Trong cả hai trường hợp, t đều thoả mãn điều kiện của Định nghĩa 3.3. Vậy X 1,β→→ Y và định lý đã được chứng minh. Ví dụ 3.4. Xét hệ thống A = (U, {X, Y, Z}) được cho trong Bảng 3.8, các quan hệ tương tự trên VY và VZ được cho trên Bảng 3.9. 89 U X Y Z t1 x1 y1 z1 t2 x1 y2 z1 t3 x1 y3 z2 t4 x1 y1 z2 t5 x1 y3 z3 t6 x1 y2 z3 t7 x2 y1 z1 t8 x2 y1 z2 Bảng 3.8: Bảng dữ liệu. Y y1 y2 y3 y1 1 0.5 0.7 y2 05 1 0.9 y3 0.7 0.9 1 Z z1 z2 z3 z1 1 0.6 0.7 z2 06 1 0.8 z3 0.7 0.8 1 Bảng 3.9: Các quan hệ tương tự trên IY và IZ . 90 Khi đó, ta có X 1, 0.8→→ Y . U/X = {U1, U2}, với U1 = {t1, t2, t3, t4, t5, t6} và U2 = {t7, t8}. Trên lớp U1 ta có dom(U1, Y ) = {y1, y2, y3}, dom(U1, Z) = {z1, z2, z3} và E1 = {t(Z) | t ∈ U1, t(Y ) = y1} = {z1, z2}; E2 = {t(Z) | t ∈ U1, t(Y ) = y2} = {z1, z3}; E3 = {t(Z) | t ∈ U1, t(Y ) = y3} = {z2, z3}; F1 = {t(Y ) | t ∈ U1, t(Z) = z1} = {y1, y2}; F2 = {t(Y ) | t ∈ U1, t(Z) = z2} = {y1, y3}; F3 = {t(Y ) | t ∈ U1, t(Z) = z3} = {y2, y3}. Từ đó các phần tử của ma trận D1 được xác định bởi: d11 = max{µ(y1, F1), µ(z1, E1)} = max{1; 1} = 1; d12 = max{µ(y1, F2), µ(z2, E1)} = max{1; 1} = 1; d13 = max{µ(y1, F3), µ(z3, E1)} = max{0.7; 0.8} = 0.8; d21 = max{µ(y2, F1), µ(z1, E2)} = max{1; 1} = 1; d22 = max{µ(y2, F2), µ(z2, E2)} = max{0.9; 0.8} = 0.9; d23 = max{µ(y2, F3), µ(z3, E2)} = max{1; 1} = 1; d31 = max{µ(y3, F1), µ(z1, E3)} = max{0.9; 0.7} = 0.9; d32 = max{µ(y3, F2), µ(z2, E3)} = max{1; 1} = 1; d33 = max{µ(y3, F3), µ(z3, E3)} = max{1; 1} = 1. Tương tự, trên lớp U2 ta có dom(U2, Y ) = {y1}, dom(U2, Z) = {z1, z2} và bằng tính toán đơn giản ta thu được các phần tử của ma trận D2 là d11 = d12 = 1. Tóm lại, ta được 91 D1 =  1 1 0.8 1 0.9 1 0.9 1 1  , D2 = ( 1 1 ) . Rõ ràng với β ≤ 0.8 thì cả hai ma trận D1 và D2 đều β−dầy đặc. Do đó X 1,β→→ Y , với mọi β ≤ 0.8. Trong khi đó, nếu β > 0.8 thì D1 không β−dầy đặc nên X 1,β →/→ Y . 3.4.4. Thuật toán kiểm định β−phụ thuộc đa trị Từ Định lý 3.6, chúng ta thấy việc kiểm tra phụ thuộc dạng X 1,β→→ Y thực chất là kiểm tra tính β−dầy đặc của tất cả các ma trân phụ thuộc mở rộng Di. Vì vậy trước hết chúng ta cần xây dựng thuật toán tính các ma trận Di và sau đó sẽ thiết lập thuật toán kiểm định β−phụ thuộc. Cũng cần lưu ý là họ các lớp tương đương U/X = {U1, U2, · · · , Um} có thể nhận được sau một phép sắp xếp các đối tượng trong U theo thứ tự các giá trị trong dom(X). Vì vậy, thuật toán sau chỉ tính Di đối với một Ui cho trước. Thuật toán 3.4. Tính Di. Input: Tập thuộc tính A, các tập con X,Y ⊆ A, Lớp tương đương thứ i của quan hệ IND(X): Ui, Các quan hệ tương tự trên các thuộc tính. Output: Di = (djk)p(i)×q(i). Method: 1. Tính dom(Ui, Y ) = {ξ1, ξ2, · · · , ξp(i)}; dom(Ui, Z) = {η1, · · · , ηq(i)}; 2. For j := 1 to p(i) do 3. For k := 1 to q(i) do 92 4. Begin 5. d1 := 1; { µ(ξj, Fk)} 6. d2 := 1; { µ(ηk, Ej)} 7. For t ∈ Ui do 8. Begin 9. If (t(Z) = ηk) and (S(ξj, t(Y )) < d1) then 10. d1 := S(ξj, t(Y )); 11. If (t(Y ) = ξj) and (S(ηk, t(Z)) < d2) then 12. d2 := S(ηk, t(Z)); 13. End. 14. djk := max{d1, d2}; 15. End. Để tính dom(Ui, Y ) = {ξ1, ξ2, · · · , ξp(i)}; dom(Ui, Z) = {η1, · · · , ηq(i)}; chúng ta có thể lần lượt thực hiện các thao tác sau: 1. Khởi tạo p(i) = q(i) = 0; dom(Ui, Y ) = dom(Ui, Z) = {}; 2. For t ∈ Ui do 3. Begin 4. If t(Y ) 6∈ dom(Ui, Y ) then 5. Begin 6. inc(p(i)); 7. ξp(i) := t(Y ); 8. dom(Ui, Y ) := dom(Ui, Y ) ∪ {ξp(i)}; 9. End; 93 10. If t(Z) 6∈ dom(Ui, Z) then 11. Begin 12. inc(q(i)); 13. ηq(i) := t(Z); 14. dom(Ui, Z) := dom(Ui, Z) ∪ {ηq(i)}; 15. End; 16. End. Sử dụng Thuật toán 3.4 ta nhận được thuật toán kiểm định β−phụ thuộc đa trị như sau: Thuật toán 3.5. Kiểm định β−phụ thuộc đa trị. Input: Tập đối tượng U , Tập thuộc tính A, các tập con X, Y ⊆ A, Các quan hệ tương tự trên các thuộc tính, Mức β ∈ [0, 1]. Output: X 1,β→→ Y ? Method: 1. Phân hoạch U/X = {U1, U2, · · · , Um}; 2. OK:=True; i:=0; 3. Repeat 4. inc(i); 5. Tính Di; 6. If Di không β−dầy đặc then 7. OK:=False; 94 8. Until (Not OK) or (i = m). 3.5. Kết luận Như vậy, bằng hai cách tiếp cận khác nhau, trong chương này chúng ta đã mở rộng các khái niệm phụ thuộc hàm và phụ thuộc đa trị là những định nghĩa mở rộng của các khái niệm phụ thuộc kinh điển. Các phụ thuộc này nói chung là các phụ thuộc xấp xỉ của hệ thống. Cách thứ nhất, chúng ta thu hẹp miền tác động của phụ thuộc hàm và phụ thuộc đa trị, nếu miền này "đủ lớn" thì phụ thuộc tương ứng sẽ được chấp nhận kèm theo đánh giá "sai số". Cách thứ hai, sử dụng quan hệ tương tự giữa các giá trị của những thuộc tính, theo cách tiếp cận này, chúng ta đã đưa ra các khái niệm (α, β)− phụ thuộc hàm và phụ thuộc đa trị, Việc đưa ra các khái niệm mới này là thực sự có ý nghĩa trong thực tế bởi nhiều lý do khác nhau. Ngoài việc chứng minh một số tính chất cơ bản của các phụ thuộc mở rộng, dựa vào ma trận phụ thuộc, chúng tôi còn đưa ra được một tiêu chuẩn đại số để xác định một phụ thuộc hàm, một phụ thuộc đa trị đồng thời đưa ra thuật toán tìm tất cả phụ thuộc tối tiểu. Đối với các phụ thuộc theo nghĩa mở rộng, cũng bằng cách sử dụng họ các ma trận phụ thuộc, chúng tôi đã đưa ra thuật toán kiểm định phụ thuộc xấp xỉ và (1, β)− phụ thuộc đa trị. Đối với trường hợp α < 1, việc kiểm chứng phụ thuộc đa trị sẽ phức tạp hơn và không thể dùng họ các ma trận phụ thuộc. Bởi vì họ này được xây dựng dựa trên các lớp tương đương của quan hệ không phân biệt trên X, trong khi với α < 1 thì quan hệ α−tương tự không còn là quan hệ tương đương nữa. Vì vậy trong vấn đề nghiên cứu mở rộng phụ thuộc đa trị, việc xây dựng tiêu chuẩn kiểm định (α, β)−phụ thuộc với α và β tuỳ ý là một bài toán còn có thể được tiếp tục nghiên cứu. 95 Chương PHẦN KẾT LUẬN Phát hiện luật theo tiếp cận của lý thuyết tập thô do Z. Pawlak [24] đề xuất là một trong những phương pháp đang được nhiều nhà khoa học nghiên cứu và sử dụng trong quá trình khai phá tri thức từ dữ liệu. Do dữ liệu thực tế thường đa dạng, không đầy đủ, thiếu chính xác mà lại dư thừa nên việc chọn lọc thuộc tính được đặt ra nhằm loại bỏ các thuộc tính dư thừa mà vẫn giữ được đầy đủ ý nghĩa của bảng dữ liệu đang xét. Ngoài ra, việc phát hiện các mối ràng buộc vốn có trong dữ liệu cũng cho các nhà nghiên cứu và quản lý có một cái nhìn đầy đủ hơn với dữ liệu họ đang có. Đó là những vấn đề chính luận án nghiên cứu. Kết quả của luận án có thể trình bày tóm lược như sau: 1. Xây dựng các thuật toán heuristic tìm tập rút gọn của bảng quyết định với độ phức tạp theo thời gian là đa thức. Các thuật toán này được xây dựng trên cơ sở đưa ra tiêu chuẩn đánh giá một tập con các thuộc tính điều kiện là tập rút gọn. Hai thuật toán đầu dựa trên độ phụ thuộc của tập thuộc tính điều kiện và khả năng đóng góp của một thuộc tính được tính toán chỉ trên các phép toán của đại số quan hệ. Thuật toán thứ ba dựa vào số cặp đối tượng phân biệt được trên một tập thuộc tính cho trước. Ý tưởng của thuật toán này dựa trên ma trận phân biệt được. Tuy nhiên, kích thước của ma trận này rất lớn đối với bảng dữ liệu lớn, vì vậy việc tìm kiếm tập rút gọn theo ma trận này như 96 phương pháp trình bày trong [26, 27] khó thực hiện. Thuật toán trong luận án đề nghị không hề tính toán các phần tử của ma trận. 2. Xây dựng các thuật toán tìm tập rút gọn xấp xỉ dựa vào các thuật toán trong Phần 1. 3. Thiết lập đặc trưng của phụ thuộc hàm và phụ thuộc đa trị bằng ma trận phụ thuộc. 4. Đưa ra điều kiện cần và đủ cho phụ thuộc đa trị dựa vào quan hệ “không phân biệt được“, từ đó xây dựng thuật toán kiểm định phụ thuộc và phụ thuộc đa trị xấp xỉ. 5. Xây dựng thuật toán tìm kiếm phụ thuộc đa trị tối tiểu vế phải. 6. Mở rộng phụ thuộc hàm và phụ thuộc đa trị dựa vào quan hệ tương tự trên tập giá trị của các thuộc tính và đưa ra các tính chất của phụ thuộc mở rộng. 7. Đặc trưng β−phụ thuộc bằng ma trận phụ thuộc và đưa ra thuật toán kiểm định β−phụ thuộc đa trị. Các hướng có thể tiếp tục nghiên cứu 1. Đưa ra giải pháp rút gọn trên bảng dữ liệu thiếu thông tin. 2. Xây dựng tiêu chuẩn đại số kiểm định phụ thuộc đa trị mở rộng trong trường hợp tổng quát. 97 Tài liệu tham khảo [1] Hoàng Thị Lan Giao (2005), “Một số thuật toán tìm tập rút gọn của bảng quyết định sử dụng các phép toán của đại số quan hệ“, Tạp chí Khoa học, Khoa học Tự nhiên và Công nghệ, Đại học Quốc gia Hà Nội, T.XXI (2PT), 41-48. [2] Hồ Thuần, Hoàng Thị Lan Giao (2005), “Một thuật toán tìm tập rút gọn sử dụng ma trận phân biệt được“, Chuyên san Các công trình nghiên cứu triển khai Viễn thông và CNTT, (15), tr. 83-87. [3] Hồ Thuần, Hoàng Thị Lan Giao (2006), “Khám phá phụ thuộc đa trị dựa vào ma trận phụ thuộc“, Tin học và điều khiển(1), tr. . [4] Hồ Thuần, Hoàng Thị Lan Giao (2006), “Mở rộng phụ thuộc hàm và phụ thuộc đa trị“, Tin học và điều khiển (đã gửi đăng). [5] Hoàng Thị Lan Giao (2006), “Khai phá luật theo tiếp cận tập thô“, Đề tài NCKH cấp Bộ trọng điểm B2005-07-02 , nghiệm thu tháng 3/2006. [6] Hà Quang Thuỵ (1996), Tập thô và đánh giá hệ thông tin nền, Tạp chí Khoa học Đại học Quốc gia Hà Nội, KHTN, XII (3). Tài liệu tiếng Anh [7] Ho Tu Bao (1996), Introduction to Knowledge Discovery and Data Mining, Insti- tude of Information Technology National Center for Natural Science and Tech- nology. 98 [8] Shrabonti Ghosh, S.S.Alam (2003), “Generalized Rough Approach to Reduction of a Decíion Table“, International Journal of Intelligent Systems Vol. 18, 499-508. [9] Shrabonti Ghosh, Ranjit Biswas, S.S. Alam (2004), “Reduction of the Decision Table: A Roughset Approach“, International Journal of Intelligent Systems, Vol 19. [10] Paolo Guidici (2003), Applied Data Mining, Statistical Methods for Business and Industry, Faculty of Economics, University of Pavia, Italy. [11] Jiawei Han, Micheline Kamber (2001), Data Mining: Concepts and Techniques, Morgan Kaupmann Publishers. [12] Nguyen S. Hoa, Nguyen H. Son (1996), “Some Efficient Algorithms for Rough Set Methods" Proceedings of the sixth International Conference on Information Processing Management of Uncertainty in Knowledge-Based Systems, 1451-1456. [13] Nguyen S. Hoa, Andrzej Skowron, Piotr Synak (1997), “Knowledge Discovery in Databases: Rough Set Approach“ Proc. of the Seventh International Fuzzy Sys- tems Association World Congress, Vol II, pp. 204-209, IFSA’97, Prague, Czech Republic. [14] Xiaohua Hu, Jianchao Han, T.Y.Lin (2004), “A New Rough Sets Model Based on Database Systems" Fundamenta Informaticae XX 1-18. [15] Yka Huhtala, Juha Karkkainen, Pasi Porkka and Hannu Toivonen (1999), “Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependen- cies“ The Computer Journal, Vol 42, No 2. [16] Yka Huhtala, Juha Karkkainen, Pasi Porkka and Hannu Toivonen (1998), “Ef- ficient Discovery of Functional and Approximate Dependencies using Partitions“ In Proc, 14th Int. Conf. on Data Engineering, IFFE Computer Society Press. 99 [17] Jyrki Kivinen, Heikki Mannila (1995), “Approximate Inference of Functional Dependencies from Relation“, Theoretical Computer Science 149(1), 129-149. [18] Jan Komorowski, Zdzislaw Pawlak, Lech Polkowski, Andrzej Skowron (1999), Rough Sets: A Tutorial. [19] Boris Kovalerchuk, Evgenii Vityaev (2001), Data Mining in Finance: Advances in Relational and Hybrid Methods, Kluwer Academic Publishers, The 2nd Print- ing. [20] Tadeusz Luba, Janusz Rybnik (1992), Rought Sets and Some Aspects of Logic Synthesis in Hanbook of Aplicatión and Advances of the Rough Sets Theory: Intelligent Decision Support Edited by Roman Slowinski, 181-199. [21] David Maier (1983), The Theory of Relational Databases (Computer Science Press, Rockville, Maryland. [22] Mannila, H., Toivonen, H. and Verkamo, A.I. (1997) , “Discovery of frequency episodes in event sequences“ Data Mining and Knowledge Discovery, I, 259 - 289. [23] Tetsuya Murai, Yoshiharu Sato (2000), Association Rules from the Point of View of madal Logic and Rough Set, The 4th Asian Fuzzy Systems Symposium. [24] Pawlak Z. (1991), Rough Sets- Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht. [25] Iztok Savnik and Peter A. Flash (2000), “Discovery of multivalued dependencies from ralations“ Intelligent data Analysis, 4(3,4) 195 - 211. [26] Andrzej Skowron, Rauszer C. (1992), “ The Discernibility Matrices and Func- tions in Information Systems" Intelligent Decision Support. Handbook of Appli- cations and Advances of the Rough Sets Theory, Kluwer, Dordrecht, 331–362. [27] AndrzejSkowron, Ning Zong (2000), Rought Sets in KDD, Tutorial Notes, Copy- right 2000. 100 [28] Nguyen Hung Son, Marcin Szczuka (2005), Rough Set in KDD, Tutorial Notes of The Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining, Ha Noi. [29] Ho Thuan (1986), “Contribution to the theory of relational databases“, Tanul- manyok 184/1986, Studies 184/1986. Budapest, Hungary. [30] Jeffrey D. Ullman (1988), Principles of Database and Knowledge-Base Systems, Volume I, Computer Science Press, Rockville, Maryland. [31] Jakub Wro’blewski (2000), “Analyzing relational databases using rough set based methods“ Proc. of IPMU 2000, Madrid, Spain. Universidad Politecnica de Madrid 2000, Vol 1, pp. 256 - 262. [32] Hong Yao, Howard J. Hamilton and Cory J. Butz (2002), “FD_Mine: Discov- ering Functional Dependencies in a Database Using Equivalences“ University of Regina Computer Sciences Department Technical Report CS-02-04, ISBN 0- 7731-0441-0. 101 Các công trình đã công bố liên quan đến luận án 1. Hoàng Thị Lan Giao (2005), “Một số thuật toán tìm tập rút gọn của bảng quyết định sử dụng các phép toán của đại số quan hệ“, Tạp chí Khoa học, Khoa học Tự nhiên và Công nghệ, Đại học Quốc gia Hà Nội, T.XXI (2PT), 41-48. 2. Hồ Thuần, Hoàng Thị Lan Giao (2005), “Một thuật toán tìm tập rút gọn sử dụng ma trận phân biệt được“, Chuyên san Các công trình nghiên cứu triển khai Viễn thông và CNTT, (15), tr. 83-87. 3. Hồ Thuần, Hoàng Thị Lan Giao (2006), “Khám phá phụ thuộc đa trị dựa vào ma trận phụ thuộc“, Tin học và điều khiển(1), tr 4. Hồ Thuần, Hoàng Thị Lan Giao (2006), “Mở rộng phụ thuộc hàm và phụ thuộc đa trị“, Tin học và điều khiển (đã gửi đăng). 5. Hoàng Thị Lan Giao (2006), “Khai phá luật theo tiếp cận tập thô“, Đề tài NCKH cấp Bộ trọng điểm B2005-07-02 , nghiệm thu tháng 3/2006. Các báo cáo khoa học đã tham gia 1. Hội nghị Khoa học Trường Đại học Công nghệ kỷ niệm 5 năm thành lập Khoa Công nghệ. 2. Hội thảo Tin học Toàn quốc, Hải Phòng tháng 8/2005. 3. Hội thảo Khoa học quốc gia "Nghiên cứu phát triển và ứng dụng Công nghệ Thông tin và Truyền thông" (ICT.Rda), 5/2006.