Tóm tắt Luận văn Thạc sĩ Khoa học máy tính: Khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tương đương

i

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG -------------

TRẦN KHÁNH KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ SỬ DỤNG PHỦ TỐI THIỂU VÀ LỚP TƢƠNG ĐƢƠNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Thái Nguyên - 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

ii

MỤC LỤC

MỤC LỤC .................................................................................................................. i DANH MỤC VIẾT TẮT VÀ KÍ HIÊ ̣U .................................................................. iii DANH MỤC CÁC BẢNG BIỂU ............................................................................ iv

DANH MỤC CÁC HÌNH VẼ ................................................................................... v MỞ ĐẦU ........................................................................................................... 1 CHƢƠNG 1 ....................................................................................................... 4 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ ................................................................ 4 1.1. Khai phá dữ liệu ..................................................................................... 4 1.1.1. Khám phá tri thức và khai phá dữ liệu ............................................ 4 1.1.2. Kiến trúc của hệ thống khai phá dữ liệu ......................................... 6 1.1.3. Quá trình khai phá dữ liệu ............................................................... 7 1.1.4. Một số kỹ thuật khai phá dữ liệu ..................................................... 8 1.1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu ........................... 12 1.1.6. Một số ứng dụng của khai phá dữ liệu .......................................... 14 1.2. Khai phá phụ thuộc hàm và phụ thuộc hàm xấp xỉ .............................. 15 1.2.1. Khai phá phụ thuộc hàm. .............................................................. 15 1.2.2. Khai phá phụ thuộc hàm xấp xỉ .................................................... 19 1.2.2.1. Định nghĩa phụ thuộc hàm xấp xỉ .......................................... 20 1.2.2.2. Một số độ đo cơ bản ............................................................... 21

CHƢƠNG 2 THUẬT TOÁN KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ SỬ DỤNG PHỦ TỐI THIỂU VÀ LỚP TƢƠNG ĐƢƠNG ........................... 28 2.1. Lớp tƣơng đƣơng và phủ tối thiểu ....................................................... 29 2.1.1. Sự phân hoạch ............................................................................... 29 2.1.2. Phân hoạch mịn hơn ...................................................................... 31 2.1.3. Phủ tối thiểu .................................................................................. 32 2.1.4. Phụ thuộc hàm xấp xỉ và lớp tƣơng đƣơng ................................... 35 2.2. Thuật toán TANE sửa đổi ..................................................................... 38 2.2.1. Thủ tục chính của thuật toán TANE sửa đổi ................................. 38 2.2.2. Độ phức tạp của thuật toán TANE sửa đổi. .................................. 41

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

iii

2.3. Thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng ................................................................................................ 41 2.3.1. Mô tả thuật toán ............................................................................ 41 2.3.2. Độ phức tạp của thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng ............................................................ 44 2.3.3. Phân tích thử nghiệm, so sánh về độ phức tạp thời gian . ............ 45 2.3.3.1. Phân tích thử nghiệm. ............................................................ 45 2.3.3.2. So sánh về độ phức tạp thời gian (theo [8]) ........................... 46 CHƢƠNG 3 THỰC NGHIỆM KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ ... 48 3.1. Xây dựng chƣơng trình thực nghiệm ................................................... 48 3.1.1. Giới thiệu bài toán ......................................................................... 48 3.1.2. Dữ liệu thử nghiệm ....................................................................... 48 3.1.3. Xây dựng chƣơng trình thực nghiệm ............................................ 50 3.2. Thực nghiệm khai phá phụ thuộc hàm xấp xỉ ...................................... 50 3.3. Kết quả thực nghiệm ............................................................................ 51 KẾT LUẬN ..................................................................................................... 52 TÀI LIỆU THAM KHẢO ............................................................................... 53 PHỤ LỤC ........................................................................................................ 55

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

iv

DANH MỤC VIẾT TẮT VÀ KÍ HIỆU SỬ DỤNG TRONG LUẬN VĂN

Ký hiệu Diễn giải

Quan hê ̣ trên tâ ̣p thuô ̣c tính U

Tâ ̣p m thuô ̣c tính.

S = (U, F) Lƣơ ̣c đồ quan hê ̣ vớ i U là tập thuộc tính , F là tập các phụ thuộc hàm trên U

LĐQH Lƣơ ̣c đồ quan hê ̣

CSDL Cơ sở dữ liệu

PTH Phụ thuộc hàm

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

v

DANH MỤC CÁC BẢNG BIỂU

Bảng 1.1: Ví dụ về quan hệ ............................................................................. 17

Bảng 1.2: Các thuật toán khai phá phụ thuộc hàm ......................................... 19

Bảng 1.3. Bảng quan hệ ví dụ về PTH xấp xỉ ................................................. 21

Bảng 1.4: Bảng dữ liệu quan hệ số ................................................................. 24

Bảng 1.5: Bảng quan hệ ví dụ ......................................................................... 25

Bảng 1.6: Bảng quan hệ ví dụ về phụ thuộc hàm điều kiện ........................... 27

Bảng 2.1: Bảng quan hệ vi dụ cho phân hoạch ............................................... 30

Bảng 2.2: Bảng quan hệ ví dụ cho phân hoạch mịn hơn ................................ 32

Bảng 2.3: Bảng quan hệ ví dụ cho phụ thuộc hàm xấp xỉ .............................. 36

Bảng 2.4: Thời gian thực hiện cho cả hai thuật toán ...................................... 45

Bảng 2.5: So sánh độ phức tạp thời gian dựa trên T(n) của hai thuật toán ..... 46

Bảng 3.1: Dữ liệu trích chọn để khai phá. ...................................................... 49

Bảng 3.2: Bảng mã hóa các thuộc tính ............................................................ 49

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

vi

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Quá trình khám phá tri thức .............................................................. 5

Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu ........................................... 6

Hình 1.3: Quá trình khai phá dữ liệu................................................................. 7

Hình 1.4: Cây quyết định .................................................................................. 9

Hình 1.5: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu ................................. 10

Hình 1.6: Mẫu kết quả của nhiệm vụ hồi quy ................................................. 11

Hình 1.7: Các loại phụ thuộc dữ liệu .............................................................. 16

Hình 1.8 : Kỹ thuật phát hiện phụ thuộc hàm ................................................. 18

Hình 2.1: Dàn cho các thuộc tính (A, B, C, D, E) .......................................... 38

Hình 3.1: Dữ liệu đã mã hóa chuẩn bị cho khai phá ....................................... 50

Hình 3.2: Giao diện kết quả đƣợc khai phá phụ thuộc hàm xấp xỉ ................. 51

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

1

MỞ ĐẦU

1. Đặt vấn đề

Trong những năm gần đây, Công nghệ thông tin (CNTT) phát triển mạnh

mẽ đã tác động đến mọi mặt của xã hội, những thành tựu của công nghệ lƣu trữ

đã cho phép tạo ra những nguồn dữ liệu khổng lồ. Việc khai thác các nguồn dữ

liệu này ngày càng cấp thiết, đặt ra những thách thức lớn cho ngành CNTT, đặc

biệt là lĩnh vực khai phá dữ liệu. Với nguồn dữ liệu lớn nhƣ vậy thì việc tìm

kiếm, phân tích, xử lý và đƣa ra các thông tin cần thiết, phù hợp với thời gian và

yêu cầu là điều không dễ dàng.

Các phƣơng pháp khai thác cơ sở dữ liệu truyền thống ngày càng không đáp

ứng đƣợc nhu cầu thực tế này. Vì vậy các phƣơng pháp nghiên cứu, tiếp cận với

những công cụ cho phép phân tích, tổng hợp, khai phá tri thức từ dữ liệu một

cách thông minh, hiệu quả đã đƣợc nhiều nhà khoa học quan tâm nghiên cứu.

Khái niệm phụ thuộc hàm đóng một vai trò rất quan trọng trong lý thuyết

cơ sở dữ liệu quan hệ. Các phụ thuộc hàm rất hữu ích trong việc phân tích và

thiết kế cơ sở dữ liệu quan hệ nhƣ xác định khóa, xác định các dạng chuẩn,

các vấn đề về nhất quán dữ liệu ... Tuy nhiên trong thực tế do có một số giá trị

dữ liệu không chính xác hoặc một số ngoại lệ nào đó làm cho các phụ thuộc

hàm không thỏa. Sự phụ thuộc tuyệt đối này dƣờng nhƣ quá nghiêm ngặt khi

ta hình dung tới một quan hệ có hàng nghìn bộ, trong khi đó chỉ có khoảng

vài bộ vi phạm phụ thuộc hàm. Bỏ qua các phụ thuộc hàm này sẽ làm mất tính

chất phụ thuộc vốn có giữa các thuộc tính. Vì vậy các nhà nghiên cứu đã mở

rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm xấp xỉ theo một cách

thức, một nghĩa nào đó, các phụ thuộc hàm xấp xỉ (Approximate Functional

Dependencies - AFDs) này cho phép có một số lƣợng lỗi nhất định của các bộ

dữ liệu đối với phụ thuộc hàm.

Phụ thuộc hàm xấp xỉ đƣợc khai phá từ CSDL quan hệ biểu diễn các mối

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

2

quan hệ có ý nghĩa, có nhiều ứng dụng khác nhau nhƣ: Dự đoán giá trị thiếu

thuộc tính trong bảng quan hệ bằng cách sử dụng các giá trị của các thuộc tính

trong việc xác định tập hợp các AFDs, tối ƣu hóa truy vấn, viết lại câu truy

vấn, chuẩn hóa cơ sở dữ liệu để cho hiệu suất tốt hơn và thiết kế lƣu trữ hiệu

quả hơn,…

Luận văn sẽ tìm hiểu về phụ thuộc hàm xấp xỉ và nghiên cứu thuật toán

AFDMCEC, một thuật toán mới tìm các phụ thuộc hàm xấp xỉ trong các

CSDL lớn dựa trên độ đo xấp xỉ. Thuật toán này sử dụng một số khái niệm

trong lý thuyết thiết kế CSDL quan hệ, đặc biệt là các khái niệm phủ tối thiểu

và lớp tƣơng đƣơng.

2. Đối tƣợng và phạm vi nghiên cứu

Luận văn tìm hiểu tổng quan về khai phá dữ liệu, đi sâu tìm hiểu khái

niệm phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các tính chất, độ đo lỗi của phụ

thuộc hàm xấp xỉ, từ đó nghiên cứu thuật toán TANE sửa đổi và thuật toán

AFDMCEC tìm phụ thuộc hàm xấp xỉ.

3. Hƣớng nghiên cứu của đề tài

- Tìm hiểu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các độ đo lỗi của

chúng.

- Nghiên cứu về thuật toán khai phá phụ thuộc hàm xấp xỉ từ bảng quan

hệ.

4. Phƣơng pháp nghiên cứu

Phƣơng pháp nghiên cứu chính của luận văn là nghiên cứu lý thuyết kết

hợp với đánh giá thực nghiệm, cụ thể là: Phân tích, tổng hợp các kết quả

nghiên cứu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ, … đã công bố trên các

bài báo khoa học, hội thảo chuyên ngành trong và ngoài nƣớc. Từ đó, trình

bày làm rõ vấn đề khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp

tƣơng đƣơng.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

3

5. Ý nghĩa khoa học và thực tiễn

Phụ thuộc hàm đóng vai trò quan trọng trong lý thuyết CSDL quan hệ.

Tuy nhiên, trong thực tế do có một số giá trị dữ liệu không chính xác hoặc

một số ngoại lệ nào đó, làm cho các phụ thuộc hàm không thỏa mãn. Sự phụ

thuộc tuyệt đối này dƣờng nhƣ quá nghiêm ngặt khi ta hình dung một quan hệ

có hàng nghìn bộ, trong khi đó chỉ có vài bộ vi phạm phụ thuộc hàm. Do vậy,

mở rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm xấp xỉ, cho phép có

một số lỗi nhất định của các bộ dữ liệu, là rất cần thiết và có ý nghĩa cả về

mặt lý thuyết cũng nhƣ thực tiễn.

Các phụ thuộc hàm xấp xỉ không những giúp chúng ta thấy đƣợc mối

quan hệ tiềm ẩn giữa các thuộc tính mà còn giúp ta thuận tiện hơn trong việc

phân tích dữ liệu, đánh giá thông tin.

Phát hiện phụ thuộc hàm xấp xỉ trong CSDL là một vấn đề nghiên cứu hấp

dẫn và cũng là một trong những mục tiêu của phát hiện tri thức. Tiếp cận phụ

thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng của khai phá dữ

liệu là một hƣớng đi thú vị, hứa hẹn nhiều kết quả và ứng dụng hiệu quả trong

thực tiễn.

6. Cấu trúc luận văn:

Luận văn đƣợc trình bày trong 3 chƣơng:

Chƣơng 1: Tổng quan về khai phá dữ liệu và khai phá phụ thuộc hàm, phụ

thuộc hàm xấp xỉ.

Chƣơng 2: Thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu

và lớp tƣơng đƣơng.

Chƣơng 3: Thực nghiệm khai phá phụ thuộc hàm xấp xỉ.

Cuối cùng là kết luận của luận văn và tài liệu tham khảo.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

4

CHƢƠNG 1

TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ PHỤ THUỘC

HÀM, PHỤ THUỘC HÀM XẤP XỈ

1.1. Khai phá dữ liệu

1.1.1. Khám phá tri thức và khai phá dữ liệu

Khai phá dữ liệu (KPDL) là việc rút trích tri thức một cách tự động và hiệu

quả từ một khối dữ liệu lớn. Tri thức đó thƣờng ở dạng các mẫu có tính chất

không tầm thƣờng, không tƣờng minh (ẩn), chƣa đƣợc biết đến và có tiềm năng

mang lại lợi ích. Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức

từ cơ sở dữ liệu (Knowledge Discovery in Database – KDD). Ở đây chúng ta có

thể coi KPDL là cốt lõi của quá trình phát hiện tri thức.

Quá trình phát hiện tri thức gồm các bƣớc:

Bƣớc 1: Trích chọn dữ liệu (data selection): Là bƣớc trích chọn những tập

dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn (databases, data ware houses).

Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): Là bƣớc làm sạch dữ liệu

(xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…v.v), rút

gọn dữ liệu (sử dụng các phƣơng pháp thu gọn dữ liệu, histograms, lấy

mẫu…v.v), rời rạc hóa dữ liệu (dựa vào histograms, entropy, phân

khoảng,...v.v). Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và

đƣợc rời rạc hóa.

Bƣớc 3: Biến đổi dữ liệu (data transformation): Là bƣớc chuẩn hóa và

làm mịn dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ

thuật khai thác ở bƣớc sau.

Bƣớc 4: Khai phá dữ liệu (data mining): Đây là bƣớc quan trọng và tốn

nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai

phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn

đƣợc các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

5

Bƣớc 5: Đánh giá và biểu diễn tri thức (knowledge representation &

evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin

(tri thức) và mối liên hệ đặc biệt trong dữ liệu đã đƣợc khai thác ở bƣớc trên

biểu diễn theo dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu,

luật,…v.v. Đồng thời bƣớc này cũng đánh giá những tri thức khám phá đƣợc

theo những tiêu chí nhất định.

Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời dùng để

điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận đƣợc cũng có

thể đƣợc lƣu và sử dụng lại.

Các Tri thức

Các mẫu

Dữ liệu đã sạch

Dữ liệu đã chọn

5.Đánh giá và biểu diễn tri thức knowledge representation & evaluation

4.Khai phá dữ liệu data mining

Kho dữ liệu

3.Biến đổi dữ liệu data transformation

2. Tiền xử lý dữ liệu data preprocessing

1. Trích chọn dữ liệu data selection

Hình 1.1. Quá trình khám phá tri thức

Việc KPDL có thể đƣợc tiến hành trên một lƣợng lớn dữ liệu có trong

CSDL, các kho dữ liệu hoặc trong các loại lƣu trữ thông tin khác.

Các mẫu đáng quan tâm có thể đƣợc đƣa đến ngƣời dùng hoặc đƣợc lƣu trữ

trong một cơ sở tri thức.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

6

1.1.2. Kiến trúc của hệ thống khai phá dữ liệu

Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần phần

nhƣ hình 1.2.

- CSDL, kho dữ liệu hoặc các lƣu trữ thông tin khác (Databases, Data

ware house,…): Đây là một hay một tập CSDL, các kho dữ liệu, các trang tính

hay các dạng lƣu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp

dữ liệu có thể đƣợc thực hiện trên những dữ liệu này.

Giao diện đồ họa cho ngƣời dùng

(Graphical user interface)

(Pattern evaluation)

Đánh giá mẫu

Cơ sở dữ liệu

(Data mining engine)

Máy khai phá dữ liệu

(Knowledge-base)

(Database or Warehouse Server

Máy chủ CSDL hay ho dữ liệu

Làm sạch: Tích hợp dữ liệu, lọc

Cơ sở dữ liệu

Kho dữ liệu

Các lƣu trữ thông tin khác

Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu

- Máy chủ CSDL hay máy chủ kho dữ liệu (Database or Warehouse

Server): Máy chủ này có trách nhiệm lấy những dữ liệu tích hợp dựa trên các

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

7

yêu cầu khai phá của ngƣời dùng.

- Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để hƣớng

dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả.

- Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một

tập các modun chức năng để thực hiện công việc nhƣ: đặc trƣng hóa, kết hợp,

phân lớp, phân cụm, phân tích sự tiến hóa.

- Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tƣơng tác với

các modun KPDL để duyệt tìm các mẫu đáng đƣợc quan tâm. Nó có thể dùng

các ngƣỡng về độ quan tâm để lọc mẫu đã khám phá đƣợc. Cũng có thể modun

đánh giá mẫu đƣợc tích hợp vào modun khai phá, tùy theo cách cài đặt của

phƣơng pháp khai phá đƣợc dùng.

- Giao diện đồ họa ngƣời dùng (Graphical user interface): Bộ phận này

còn cho phép ngƣời dùng giao tiếp với hệ thống KPDL. Ngoài ra, bộ phận này

còn cho phép ngƣời dùng xem các lƣợc đồ CSDL, lƣợc đồ kho dữ liệu (hay các

cấu trúc dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng

khác nhau.

1.1.3. Quá trình khai phá dữ liệu

Thống kê tóm tắt

Mẫu

Giải thuật khai phá DL

Xác định dữ liệu liên quan

Thu thập và tiền xử lý DL

Quá trình khai phá dữ liệu đƣợc thể hiện bởi mô hình sau:

Dữ liệu trực tiếp

Xác định nhiệm vụ

Hình 1.3: Quá trình khai phá dữ liệu

+ Xác định nhiệm vụ: Xác định chính xác vấn đề cần giải quyết.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

8

+ Xác định các dữ liệu liên quan dùng để xây dựng giải pháp.

+ Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải

thuật khai phá dữ liệu có thể hiểu đƣợc. Ở đây có thể gặp một số vấn đề: dữ liệu

phải đƣợc sao ra nhiều bản (nếu đƣợc chiết suất vào các tệp), quản lý tập các tệp

dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay

đổi v.v.).

+ Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ

liệu: nhằm tìm đƣợc các mẫu (pattern) có ý nghĩa dƣới dạng biểu diễn tƣơng

ứng với các ý nghĩa đó.

1.1.4. Một số kỹ thuật khai phá dữ liệu

Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh

doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai

phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát

hiện đƣợc nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các

biến hoặc các đối tƣợng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự

đoán đƣợc những giá trị chƣa biết hoặc những giá trị tƣơng lai của các biến

đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà

con ngƣời có thể hiểu đƣợc.

Một số kỹ thuật chính của khai phá dữ liệu:

Phân lớp dữ liệu

Khái niệm phân lớp dữ liệu đƣợc Han và Kamber đƣa ra năm 2000. Phân

lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tƣợng thành những

lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá

trị của dữ liệu sẽ xuất hiện trong tƣơng lai.

Quá trình phân lớp dữ liệu đƣợc thực hiện qua hai bƣớc. Bước thứ nhất:

Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc

trƣng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

9

giám sát, học theo mẫu đƣợc cung cấp trƣớc. Bước thứ hai: Từ những lớp dữ

liệu hoặc những khái niệm đã đƣợc xác định trƣớc, dự đoán giá trị của những

đối tƣợng quan tâm.

Một kỹ thuật phân lớp dữ liệu đƣợc Han và Kamber đƣa ra là cây quyết định.

Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tƣơng ứng.

Kỹ thuật này đã đƣợc nhiều tác giả nghiên cứu và đƣa ra nhiều thuật toán.

Một ví dụ tiêu biểu về cây quyết định:

Hình 1.4: Cây quyết định

Trong hình 1.4 là một cây quyết định cho lớp mua laptop, chỉ ra một khách

hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh

giá mua laptop là Yes hay No. Sau khi mô hình này đƣợc xây dựng, chúng ta có

thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc tính

khách hàng mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng rộng

rãi trong nhiều hoạt động của đời sống thực.

Phân nhóm dữ liệu

Phân nhóm là kỹ thuật khai phá dữ liệu tƣơng tự nhƣ phân lớp dữ liệu. Tuy

nhiên, sự phân nhóm dữ liệu là quá trình học không đƣợc giám sát, là quá trình

nhóm những đối tƣợng vào trong những lớp tƣơng đƣơng, đến những đối tƣợng

trong một nhóm là tƣơng đƣơng nhau, chúng phải khác với những đối tƣợng

trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc về lớp nào

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

10

là phải xác định trƣớc, trong khi phân nhóm không xác định trƣớc. Trong phân

nhóm, những đối tƣợng đƣợc nhóm lại cùng nhau dựa vào sự giống nhau của

chúng. Sự giống nhau giữa những đối tƣợng đƣợc xác định bởi những chức

năng giống nhau. Thông thƣờng những sự giống về định lƣợng nhƣ khoảng

cách hoặc độ đo khác đƣợc xác định bởi những chuyên gia trong lĩnh vực của

mình.

Hình 1.5: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu

Đa số các ứng dụng phân nhóm đƣợc sử dụng trong sự phân chia thị trƣờng.

Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp có

thể cung cấp những dịch vụ khác nhau tới nhóm khách hàng một cách thuận lợi.

Ví dụ, dựa vào chi tiêu, số tiền trong tài khoản và việc rút tiền của khách hàng,

một ngân hàng có thể xếp những khách hàng vào những nhóm khác nhau. Với

mỗi nhóm, ngân hàng có thể cho vay những khoản tiền tƣơng ứng cho việc mua

nhà, mua xe,… Trong trƣờng hợp này ngân hàng có thể cung cấp những dịch vụ

tốt hơn và cũng chắc chắn rằng tất cả các khoản tiền cho vay đều có thể thu hồi

đƣợc. Ta có thể tham khảo một khảo sát toàn diện về kỹ thuật và thuật toán phân

nhóm trong.

Hồi qui (Regression): Là việc học một hàm ánh xạ từ một tập dữ liệu thành

một biến dự đoán có giá trị thực. Nhiệm vụ hồi qui tƣơng tự nhƣ phân lớp, điểm

khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc [6].

Việc dự báo các giá trị số thƣờng đƣợc làm bởi các phƣơng pháp thống kê cổ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

11

điển chẳng hạn nhƣ hồi qui tuyến tính. Tuy nhiên, phƣơng pháp mô hình hóa

Nợ

đƣờng hồi quy tuyến tính

Thu nhập

cũng đƣợc sử dụng.

+ 0 0 0 + 0 0 0 + + 0 0 + + 0 Hình 1.6: Mẫu kết quả của nhiệm vụ hồi quy 0 0 + + 0 0 + 0 Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lƣợng sinh vật phát

quang hiện thời trong khu rừng bằng cách dò tìm vi sóng bằng thiết bị cảm biến

từ xa; dự đoán khả năng tử vong của bệnh nhân khi biết các kết quả xét nghiệm

chẩn đoán; dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu

quảng cáo… hình 1.6 chỉ ra mẫu kết quả hồi quy tuyến tính đơn giản, ở đây

tổng số nợ đƣợc điều chỉnh cho phù hợp giống nhƣ một hàm thu nhập tuyến

tính. Việc điều chỉnh này là không đáng kể bởi vì chỉ tồn tại một tƣơng quan

yếu giữa hai biến.

Tổng hợp (summarization): Là công việc liên quan đến các phƣơng pháp

tìm kiếm một mô tả cô đọng cho tập con dữ liệu. Các kỹ thuật tổng hợp thƣờng

đƣợc áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động.

Mô hình hóa phụ thuộc (dependency modeling): Là việc tìm kiếm mô tả

các phụ thuộc quan trọng giữa các biến. Mô hình phụ thuộc tồn tại hai mức:

Mức cấu trúc của mô hình (thƣờng dƣới dạng đồ thị) xác định các biến phụ

thuộc cục bộ vào các biến khác;

Mức định lƣợng của mô hình xác định mức độ phụ thuộc của biến. Những

phụ thuộc này thƣờng đƣợc biểu thị dƣới dạng luật.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

12

Quan hệ phụ thuộc cũng có thể biểu diễn dƣới dạng mạng tin cậy [6]. Đó là

đồ thị có hƣớng không có dạng chu trình, các nút biểu diễn thuộc tính và trọng

số chỉ liên kết phụ thuộc giữa các nút đó.

Phát hiện sự thay đổi và độ lệch (change and deviation dectection):

Nhiệm vụ này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu

dựa vào các giá trị chuẩn hay độ đo đã biết trƣớc, phát hiện độ lệch đáng kể

giữa nội dung của tập con dữ liệu và nội dung mong đợi. Hai mô hình độ lệch

thƣờng dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là

sự thay đổi có nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác

nhau giữa dữ liệu trong hai tập con dữ liệu, tính cả trƣờng hợp tập con của đối

tƣợng này thuộc tập con kia, nghĩa là xác định dữ liệu trong một nhóm con của

đối tƣợng có khác nhau đáng kể so với toàn bộ đối tƣợng.

1.1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu

Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ

liệu thành các loại khác nhau.

Cơ sở dữ liệu quan hệ

Đến nay, hầu hết dữ liệu đƣợc lƣu giữ dƣới dạng cơ sở dữ liệu quan hệ. Cơ

sở dữ liệu quan hệ là một nguồn tài nguyên lớn nhất chứa những đối tƣợng mà

chúng ta cần khai phá. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu đƣợc mô

tả bởi một tập những thuộc tính và lƣu trong những bảng. Khai phá dữ liệu trên

cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá mẫu. Ví dụ, trong cơ sở dữ liệu

của một ngân hàng, ta có thể tìm đƣợc những khách hàng có mức chi tiêu cao, ta

có thể phân loại những khách hàng này dựa vào quá trình chi tiêu của họ. Cũng

với việc phân tích những mục tiêu của khách hàng, chúng ta có thể cung cấp

một số thông tin của khách hàng đến những doanh nghiệp khác. Giả sử rằng

một khách hàng chi mỗi tháng 500 đô la cho thời trang, nếu đƣợc phép, ngân

hàng có thể cung cấp thông tin về khách hàng này cho những cửa hàng thời

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

13

trang.

Cơ sở dữ liệu giao tác

Cơ sở dữ liệu giao tác là tập hợp những bản ghi giao dịch, trong đa số các

trƣờng hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ

chức. Với tính phổ biến của máy tính và thƣơng mại điện tử, ngày nay có rất

nhiều cơ sở dữ liệu giao tác.

Cơ sở dữ liệu không gian

Cơ sở dữ liệu không gian bao gồm hai phần: Phần thứ nhất là dữ liệu quan

hệ hay giao tác, phần thứ hai là thông tin định vị hoặc thông tin địa lý. Ví dụ,

những luật kết hợp trên cơ sở dữ liệu không gian mô tả mối quan hệ giữa các

đặc trƣng trong cơ sở dữ liệu không gian. Dạng của luật kết hợp không gian có

dạng X Y, với X, Y là tập hợp những vị từ không gian. Những thuật toán

khai phá luật kết hợp không gian tƣơng tự nhƣ khai phá luật kết hợp nhƣng

thêm những vị từ về không gian.

Cơ sở dữ liệu có yếu tố thời gian

Giống nhƣ cơ sở dữ liệu không gian, cơ sở dữ liệu có yếu tố thời gian bao

gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là

thông tin về thời gian xuất hiện dữ liệu ở phần thứ nhất. Những luật kết hợp có

yếu tố thời gian có nhiều thông tin hơn những luật kết hợp cơ bản. Ví dụ, từ luật

kết hợp cơ bản {Bia} {Thuốc lá}, với dữ liệu có yếu tố thời gian chúng ta có

thể có nhiều luật: Độ hỗ trợ của luật {Bia} {Thuốc lá} là 20% từ 9 giờ đến

13 giờ là 50% trong thời gian từ 19 giờ tới 22 giờ. Rõ ràng rằng, những ngƣời

bán lẻ có thể xác định chiến lƣợc để buôn bán tốt hơn.

Hầu hết nghiên cứu về lĩnh vực này ngày nay hình thành một hƣớng khai

phá dữ liệu mới gọi là khai phá mẫu lặp liên tục, khai phá tập mục dữ liệu

thƣờng xuyên trong cơ sở dữ liệu thời gian.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

14

Cơ sở dữ liệu đa phƣơng tiện

Số lƣợng trang web đang bùng nổ trên thế giới, web có mặt ở khắp mọi nơi,

duyệt web đã là nhu cầu của mọi tầng lớp trong xã hội. Thông tin trên web đang

phát triển với tốc độ rất cao, khai phá thông tin trên web (web mining) đã trở

thành một lĩnh vực nghiên cứu chính của khai phá dữ liệu, đƣợc các nhà nghiên

cứu đặc biệt quan tâm. Khai phá dữ liệu web thông thƣờng đƣợc chia thành ba

phạm trù chính: Khai phá cách dùng web (web usage mining), khai phá cấu trúc

web (web structure mining) và khai phá nội dung web (web content mining).

Khai phá cách dùng web tập trung vào việc khai phá thông tin của ngƣời

truy cập web. Với những thông tin này ngƣời khai phá dữ liệu có thể cung cấp

những thông tin hữu ích cho ngƣời dùng và các nhà kinh doanh.

1.1.6. Một số ứng dụng của khai phá dữ liệu

KPDL đƣợc vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác

nguồn dữ liệu phong phú đƣợc lƣu trữ trong các hệ thống thông tin. Tuỳ theo

bản chất của từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác

nhau.

KPDL đƣợc vận dụng có hiệu quả để giải quyết các bài toán phức tạp

trong những ngành đòi hỏi kỹ thuật cao nhƣ: tìm kiếm mỏ dầu từ ảnh viễn thám,

xác định vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc

trong các hệ thống sản xuất.

Phân nhóm và dự đoán là những kỹ thuật rất cần thiết cho việc quy hoạch

và phát triển hệ thống quản lý và sản xuất trong thực tế nhƣ: dự đoán tái sử dụng

điện năng cho các công ty cung cấp điện, lƣu lƣợng viễn thông cho các công ty

điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của sản phẩm

trên thị trƣờng cho các công ty tài chính hay phân nhóm khách hàng tiềm năng.

Ngoài ra KPDL còn đƣợc áp dụng trong việc giải quyết các vấn đề xã hội

nhƣ: phát hiện tội phạm hay tăng cƣờng an ninh xã hội và mang lại những hiệu

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

15

quả thiết thực cho các hoạt động trong đời sống hàng ngày.

Một số ứng dụng cụ thể nhƣ sau:

- KPDL đƣợc sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định.

- Trong sinh học: nó dùng để tìm kiếm, so sánh các hệ gen và thông tin di

truyền, tìm mối liên hệ giữa các hệ gen và chẩn đoán một số bệnh di truyền.

- Trong y học: KPDL giúp tìm ra mối liên hệ giữa các triệu chứng, chẩn

đoán bệnh.

- Tài chính và thị trƣờng chứng khoán: KPDL dùng để phân tích tình

hình tài chính, phân tích đầu tƣ, phân tích cổ phiếu.

- Khai thác dữ liệu web.

- Trong thông tin kỹ thuật: KPDL dùng để phân tích các sai hỏng, điều

khiển và lập lịch trình.

- Trong thông tin thƣơng mại: dùng để phân tích dữ liệu ngƣời dùng,

phân tích dữ liệu marketing, phân tích đầu tƣ, phát hiện các gian lận.

- Trong công nghiệp viễn thông: Phân tích nhu cầu và phân tích các mẫu

gian lận và xác định các mẫu khác thƣờng.

1.2. Khai phá phụ thuộc hàm và phụ thuộc hàm xấp xỉ

1.2.1. Khai phá phụ thuộc hàm

Phụ thuộc hàm biểu diễn mối quan hệ giữa các thuộc tính của một cơ sở dữ

liệu, một phụ thuộc hàm chỉ ra rằng giá trị của một thuộc tính đƣợc xác định

duy nhất bởi giá trị của một số thuộc tính khác. Phụ thuộc hàm đóng vai trò

quan trọng trong chuẩn hóa cơ sở dữ liệu, phát hiện các phụ thuộc hàm cũng có

thể giúp các nhà thiết kế cơ sở dữ liệu tách một lƣợc đồ quan hệ thành nhiều

lƣợc đồ quan hệ đạt dạng chuẩn cao hơn.

Một CSDL thiết kế không tốt trong là cơ sở dữ liệu có dƣ thừa thông tin,

gặp bất thƣờng cập nhật, bất thƣờng khi chèn, bất thƣờng khi xóa. Chuẩn hóa là

quá trình thiết kế lại lƣợc đồ cơ sở dữ liệu để đảm bảo cho nó không có các dị

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

16

thƣờng. Chuẩn hóa chia các quan hệ thành các quan hệ nhỏ hơn và mỗi quan hệ

nhỏ đó ở một dạng chuẩn mong muốn. Điều kiện để biến đổi từ dạng chuẩn này

sang dạng chuẩn kia là sự ràng buộc giữa các bộ thuộc tính trong quan hệ, ràng

buộc đó đƣợc biểu diễn bằng phụ thuộc hàm.

Phụ thuộc của các thuộc tính: có 3 loại phụ thuộc của các thuộc tính

thƣờng đƣợc khám phá là : phụ thuộc hàm (FD), phụ thuộc có điều kiện

(CFDs) và phụ thuộc bao gồm (INDs). Hình 1.7 biểu diễn các loại phụ thuộc

dữ liệu (theo [11]).

Khai phá dữ liệu

CFDs FD INDs

Hình 1.7: Các loại phụ thuộc dữ liệu

. Mỗi thuô ̣c Cho tâ ̣p hƣ̃u ha ̣n khác rỗng các thuô ̣c tính

tính có một miền giá trị tƣơng ứng . Mô ̣t quan hê ̣

trên U, ký hiệu R (U) hoă ̣c R nếu không sơ ̣ nhầm lẫn , là một tập con của tích

Descartes .

Mô ̣t cách hình thƣ́ c:

Các phần tử của quan hệ R đƣơ ̣c go ̣i là các bộ. Mô ̣t quan hê ̣ không chƣ́ a

bô ̣ nào đƣơ ̣c go ̣i là quan hê ̣ rỗng.

Kí hiệu: t[X] là phép chiếu của bộ t trên tập thuộc tính X, .

Định nghĩa 1.1: Mô ̣t phụ thuộc hàm (PTH) trên quan hê ̣ R (U) là một mệnh

đề có dạng X → Y (trong đó X, Y ⊆ U). Ta nói PTH X → Y đú ng trên quan hê ̣

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

17

R, nếu:

Khi PTH X → Y đú ng trên quan hê ̣ R. Ngƣờ i ta còn nói R thỏa PTH X →

Y và ký hiệu R (X → Y).

Ví dụ. Xét quan hệ R trên tâ ̣p thuô ̣c tính U = {T, A, B, C} cho trên bảng

1.1 nhƣ sau:

T A B C

1 a1 b1 c1 R = 2 a2 b2 c2

3 a2 b2 c3

Bảng 1.1: Ví dụ về quan hệ

Ta có : Chẳng ha ̣n R thỏa các PTH {T} → {A, B, C}, {C} → {T, A, B}, {A}

→ {B}, … và không thỏa PTH {B} → {C}, …

Nhƣ vâ ̣y, có thể thấy PTH (trên quan hê ̣) là sự phụ thuộc của một số thuộc

tính vào một số thuộc tính khác.

Mô ̣t că ̣p S = (U, F) vớ i U là tập các thuô ̣c tính và F là tập các PTH trên U

đƣơ ̣c go ̣i là mô ̣t lược đồ quan hê ̣ (LĐQH).

Quan hê ̣ R đƣơ ̣c go ̣i là thỏa tâ ̣p PTH F, ký hiệu R(F) nếu với mọi PTH

thì R (X → Y).

Cho tâ ̣p các PTH F trên U và X → Y là một PTH bất kỳ trên U. Ta nói F suy diễn logic PTH X → Y, ký hiệu F |= X → Y. Nếu vớ i mo ̣i quan hê ̣ R (U) sao cho R (F) thì R (X → Y).

Bao đó ng của tập PTH F trên U, ký hiệu F+ là tâ ̣p nhỏ nhất các PTH trên

U chƣ́ a F và thỏa các tính chất (A1) – (A3) nhƣ sau:

Với ∀ X, Y, Z ⊆ U:

(A1) Tính phản xạ Nếu Y ⊆ X thì X → Y ∈ F+

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

18

(A2) Tính gia tăng Nếu X → Y ∈ F+ thì X ⋃ Z → Y ⋃ Z ∈ F+

(A3) Tính bắc cầu Nếu X → Y ∈ F+ và Y → Z ∈ F+ thì X → Z ∈ F+

Rõ ràng F+ hƣ̃u ha ̣n vì U hƣ̃u ha ̣n.

Các tính chất từ (A1) – (A3) còn thƣờng đƣợc gọi là h ệ tiên đề

Armstrong hay tập quy tắ c suy diễn Armstrong.

Các kỹ thuật phát hiện phụ thuộc hàm

Phát hiện phụ thuộc hàm từ một bảng quan hệ đã đƣợc nhiều nhà nghiên

cứu quan tâm. Đã có nhiều thuật toán đƣợc đề xuất, hình 1.8 biểu diễn các

phƣơng pháp cùng một số thuật toán.

Từ trên xuống

Từ dƣới lên

Khai phá phụ thuộc hàm

Tên thuật toán

Tên thuật toán o TANE o FD_Miner o FUN o Negative Cover o Dep_Miner o FAST FD

Hình 1.8 : Kỹ thuật phát hiện phụ thuộc hàm

Bảng 1.2 trình bày một số thuật toán điển hình và các kỹ thuật sử dụng

trong thuật toán đó (theo [11]).

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

19

1999

TANE

Phân hoạch (Partitions)

2000

Dep-Miner

Tập khác biệt (Difference Set)

2001

FUN

Yka, Juha, Pasi and Hannu St_ephane Lopes, Jean-Marc Petit, and Lot_ Lakhal N. Novelli and R. Cicchetti,

2002

FD_Mine

Hong Yao and Hamelton

2008

FD_Discover

Jalal Atoum, Dojanah Bader and Arafat Awajan

Phụ thuộc hàm nhúng (Embedded FD) Phân hoạch và lớp tƣơng đƣơng (Partitions and Equivalences) Các lớp tƣơng đƣơng và phủ tối thiểu (Equivalent Classes and Minimal Cover)

2010

FDs Using Rough Sets

Tập thô (Rough sets)

2011

FDs via Bayes Net Analyses

Y.V.Sreevani, Prof. T. Venkat Narayana Rao Nittaya Kerdprasop and Kittisak Kerdprasop

Sử dụng mạng Bayes Net và Heuristics (Bayes Net and Heuristics)

Tác giả Năm Tên thuật toán Kỹ thuật sử dụng

Bảng 1.2: Các thuật toán khai phá phụ thuộc hàm

1.2.2. Khai phá phụ thuộc hàm xấp xỉ

Khái niệm phụ thuộc hàm đóng một vai trò rất quan trọng trong lý thuyết

cơ sở dữ liệu quan hệ. Các phụ thuộc hàm rất hữu ích trong việc phân tích và

thiết kế cơ sở dữ liệu quan hệ nhƣ xác định khóa, xác định các dạng chuẩn,

các vấn đề về nhất quán dữ liệu ... Tuy nhiên trong thực tế do có một số giá trị

dữ liệu không chính xác hoặc một số ngoại lệ nào đó làm cho các phụ thuộc

hàm không thỏa. Sự phụ thuộc tuyệt đối này dƣờng nhƣ quá nghiêm ngặt khi

ta hình dung tới một quan hệ có hàng nghìn bộ, trong khi đó chỉ có khoảng

vài bộ vi phạm phụ thuộc hàm. Bỏ qua các phụ thuộc hàm này sẽ làm mất tính

chất phụ thuộc vốn có giữa các thuộc tính. Vì vậy các nhà nghiên cứu đã mở

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

20

rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm xấp xỉ theo một cách

thức, một nghĩa nào đó, các phụ thuộc hàm xấp xỉ (Approximate Functional

Dependencies - AFDs) này cho phép có một số lƣợng lỗi nhất định của các bộ

dữ liệu đối với phụ thuộc hàm.

1.2.2.1. Định nghĩa phụ thuộc hàm xấp xỉ

Định nghĩa 1.2. [11] Cho quan hệ R (U) và X → Y là một PTH trên U.

Gọi S ⊆ R là quan hệ sao cho có số bộ ít nhất cần loại bỏ khỏi R để R\S thỏa

mãn PTH (X → Y). Khi đó tỷ số của |S| và |R| đƣợc gọi là độ đo lỗi của PTH X

→ Y trên R, ký hiệu g3 (X → Y, R).

Nhƣ vậy

Một cách tƣơng đƣơng

Độ đo lỗi trên còn đƣợc gọi là độ đo lỗi .

Có thể thấy nếu X → Y là một PTH đúng trên R thì độ đo lỗi

.

Cho ngƣỡng lỗi với . Ngƣời ta nói PTH X → Y là một

PTH xấp xỉ trên R ứng với ngƣỡng lỗi nếu . Khi đó

ngƣời ta còn nói PTH xấp xỉ X → Y đúng trên R ứng với ngƣỡng lỗi .

Ví dụ. Xét quan hệ R trên tập thuộc tính U = {A, B, C, D} cho trên bảng

1.3 nhƣ sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

21

Bộ A B C D

0 0 1 1

0 1 1 1

0 2 1 2

R = 1 2 0 0

2 0 0 0

2 0 2 0

1 1 2 1

Bảng 1.3. Bảng quan hệ ví dụ về PTH xấp xỉ

Xét PTH AB → C trên R (U).

Rõ ràng bỏ bộ 6 (hoặc bộ 5) thì PTH AB → C sẽ đúng trên quan hệ R. Tức

số bộ ít nhất cần loại khỏi quan hệ R để PTH AB → C đúng trên các bộ còn lại

là 1. Suy ra:

Với ngƣỡng lỗi . , ta có:

Do đó PTH AB → C là một PTH xấp xỉ trên R ứng với .

Lƣu ý: Khi chú ng ta nói xét mô ̣t PTH trên quan hê ̣ R(U) có nghĩa PTH đó

xác định trên tập thuộc tính U và muốn tìm hiểu xem PTH đó có đúng trên

quan hê ̣ R hay không.

1.2.2.2. Một số độ đo cơ bản

Khi nghiên cứu phát hiện các PTH xấp xỉ thì vấn đề xác định độ đo cho

các PTH xấp xỉ đóng vai trò cực kì quan trọng. Đã có nhiều tác giả đƣa ra

nhiều độ đo dựa vào nhiều cách khác nhau. Ở đây luận văn tìm hiểu một số độ

đo cơ bản.

Trong định nghĩa về PTH xấp xỉ khi có một bộ làm cho PTH không đúng.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

22

Ngƣời ta gọi bộ này là một trƣờng hợp ngoại lệ. Nhƣ vậy, PTH xấp xỉ chính

là PTH với các trƣờng hợp ngoại lệ. Các độ đo của PTH xấp xỉ dựa trên số

lƣợng các trƣờng hợp ngoại lệ. Nó là cơ sở để xác định , phát hiện các PTH

xấp xỉ.

Dƣới đây, ta xem xét một số cách mở rộng.

Cách 1: [4, 5, 6]

Cho quan hệ và phụ thuộc hàm . Ba độ đo lỗi của

trong đƣợc đề xuất nhƣ sau:

Đặt là một trong ba độ đo , , . Cho trƣớc , . Ta

đối với trong nếu . Ngƣợc nói là

lại là .

Cho quan hệ khi đó độ đo lỗi của một phụ thuộc hàm

đƣợc xác định nhƣ sau:

Từ đó đứng trên ứng với một ngƣỡng lỗi khi và

chỉ khi .

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

23

Cách 2:

Cho là một quan hệ trên tập thuộc tính trong đó

các thuộc tính có thể là thuộc tính định danh, rời rạc hoặc liên tục.

Đối với những thuộc tính định danh, ta tiến hành thực hiện ánh xạ tất cả các

giá trị có thể tới một tập các số nguyên dƣơng liền kề.

Định nghĩa khoảng cách giữa hai bộ giá trị trên tập thuộc tính: Với hai bộ

, ta kí hiệu là khoảng cách giữa và trên tập

thuộc tính đƣợc xác định nhƣ sau.

- Hàm max(x,y) là hàm chọn số lớn nhất trong hai số .

- Trƣờng hợp , tức ta qui ƣớc:

Khoảng cách giữa hai bộ giá trị trên tập thuộc tính có thể coi là hàm số

của các đối số là các bộ giá trị của quan hệ và tập các thuộc tính.

Định nghĩa phụ thuộc hàm xấp xỉ loại 2: Giả sử và với một số

cho trƣớc, , ta nói rằng xác định hàm mức (hoặc nói

rằng có phụ thuộc hàm xấp xỉ loại hai mức ), ký hiệu là

nếu với mọi cặp bộ , mà thì ta cũng có

.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

24

Ví dụ:

C B D E A

160 18 25 12 2.5

160.5 18 15 13 2.51

320 20 30 16 3.6

323 20 45 28 3.65

641 25 60 19 4.25

643 25 70 57 4.26

Bảng 1.4: Bảng dữ liệu quan hệ số

Ta thấy giữa các cột A, B có mối tƣơng quan với cột C, Với ta

kiểm tra điều kiện phụ thuộc hàm xấp xỉ loại 2: .

Với cặp hàng 1, 2 ta có:

Tƣơng tự kiểm tra với cặp hàng 3, 4 và 5, 6

Vậy ta có .

Một số tính chất của phụ thuộc hàm xấp xỉ loại 2:

- Tính chất 1: Cho là một quan hệ trên tập thuộc tính . Một phụ

thuộc hàm đúng trên cũng là phụ thuộc hàm xấp xỉ loại 2 với mức tùy

ý đúng trên . Tính chất này dễ dàng suy theo định nghĩa của

phụ thuộc hàm xấp xỉ loại 2.

- Tính chất 2: Cho là một quan hệ trên ; , , là 2 số

sao cho . Kí hiệu và là 2 phụ thuộc hàm

xấp xỉ loại 2 mức và mức giữa và trên , khi đó nếu

đúng trên thì cũng đúng trên .

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

25

- Tính chất 3 (Tính phản xạ): Nếu khi đó là phụ thuộc

hàm xấp xỉ loại 2 mức tùy ý .

- Tính chất 4 (Tính bắc cầu): Nếu và thì

- Tính chất 5 (Tính gia tăng): Với mọi và mức nào đó,

nếu thì .

Cách 3:

Cho là một lƣợc đồ quan hệ và là một quan hệ

trên với bộ. Khi đó độ thỏa mà thỏa ký hiệu là

, đƣợc định nghĩa nhƣ sau:

trong đó nếu và thì ,

; NTP là số cặp bộ trong và bằng ngƣợc lại

.

Ví dụ: Với quan hệ nhƣ bảng 1.5 dƣới đây, ta có:

(Trái cây Đồ uống) = 77.78%.

ID 1 2 3 4 5 6 7 8 Trái cây Vải Vải Vải Vải Vải Táo Táo Táo Đồ uống Coca Cola Coca Cola Spirit Spirit N/A Spirit Spirit Coca Cola

Bảng 1.5: Bảng quan hệ ví dụ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

26

Cách 4:

Xây dựng quan hệ tƣơng đƣơng trên nhƣ sau:

Quan hệ phân hoạch thành các lớp tƣơng đƣơng, mỗi lớp

tƣơng đƣơng là một tập con của chứa các bộ giống nhau trên . Ký hiệu

phân hoạch đó là .

Cho . Nếu thì ta

nói rằng thỏa . Ngƣợc lại, không thỏa .

For each do

If ( thỏa ) then .

Đặt . Ta nói r thỏa với cấp độ (với độ phụ thuộc ,

) ký hiệu là

Các tính chất:

. -

-

- Từ và không suy ra đƣợc , với

.

- Từ và suy ra , với .

- Từ và suy ra , với .

Cách 5: [7]

Phụ thuộc hàm điều kiện:

Định nghĩa 1.3: Một phụ thuộc hàm điều kiện có dạng ,

trong đó là một phụ thuộc hàm (kinh điển) và là một bộ mẫu với

các thuộc tính trong và . Bộ mẫu chứa các giá trị hằng và biến

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

27

không tên . Biến không tên có thể nhận một giá trị tùy ý trong miền

thuộc tính tƣơng ứng. Xét quan hệ đƣợc cho dƣới đây.

A B C D

001 124 12 34

001 124 21 43

002 157 34 69

002 157 34 61

002 158 89 62

002 158 89 90

003 167 78 96

Bảng 1.6: Bảng quan hệ ví dụ về phụ thuộc hàm điều kiện

Ta thấy không thỏa . Tuy nhiên thỏa ràng buộc

.

Theo định nghĩa phụ thuộc hàm điều kiện ta thấy ràng buộc

là một phụ thuộc hàm điều kiện có dạng

. Phụ thuộc hàm kinh điển là trƣờng hợp riêng của phụ

thuộc hàm điều kiện. Phụ thuộc hàm chính là phụ thuộc hàm điều

kiện dạng với . Phụ thuộc hàm điều

kiện đƣợc sử dụng trong bài toán làm sạch dữ liệu.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

28

CHƢƠNG 2

THUẬT TOÁN KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ

SỬ DỤNG PHỦ TỐI THIỂU VÀ LỚP TƢƠNG ĐƢƠNG

Trong chƣơng này trình bày thuật toán khai phá phụ thuộc hàm xấp xỉ sử

dụng phủ tối thiểu và lớp tƣơng đƣơng (viết tắt là AFDMCEC) để khai phá

các phụ thuộc hàm xấp xỉ từ những cơ sở dữ liệu dựa trên một độ đo sai số g3.

Thuật toán AFDMCEC sử dụng một vài khái niệm từ lý thuyết cơ sở dữ liệu,

lý thuyết của sự tƣơng đƣơng và phủ tối tiểu của những phụ thuộc hàm.

Những nghiên cứu đã có

Những động lực chính để thúc đẩy khai phá các phụ thuộc hàm từ cơ sở

dữ liệu là việc phát hiện những hình mẫu hữu ích từ dữ liệu và phát hiện các

mối quan hệ đáng chú ý giữa các biến trong cơ sở dữ liệu lớn. Trong một vài

trƣờng hợp, một phụ thuộc hàm có thể không đƣợc thỏa mãn bởi một vài bộ

dữ liệu. Phụ thuộc hàm nhƣ vậy có thể đƣợc nghĩ theo hƣớng đúng xấp xỉ.

Ví dụ: Phụ thuộc Phƣờng → Thành phố có thể đúng xấp xỉ.

Những phụ thuộc hàm xấp xỉ đặc trƣng tri thức quan trọng về cấu trúc của

quan hệ. Việc phát hiện ra những tri thức nhƣ vậy từ cơ sở dữ liệu có thể có

giá trị mang tính gợi ý cho một chuyên gia. Những phụ thuộc hàm xấp xỉ nhƣ

vậy tồn tại trong một số cơ sở dữ liệu vốn có những phụ thuộc đƣợc mong đợi

giữa các thuộc tính, nhƣng một vài bộ chứa lỗi hoặc biểu diễn cho những

trƣờng hợp ngoại lệ.

Việc khám phá những phụ thuộc hàm xấp xỉ không mong đợi nhƣng có ý

nghĩa là một điều thú vị và có ứng dụng nhiều trong khai phá dữ liệu.

Ví dụ: Một phụ thuộc hàm xấp xỉ trong một cơ sở dữ liệu của hợp các chất

hóa học liên kết những thuộc tính cấu trúc khác nhau gây ra ung thƣ có thể

cung cấp vài gợi ý giá trị cho những nhà hóa sinh về các nguyên nhân tiềm ẩn

của bệnh ung thƣ.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

29

Các ứng dụng của những phụ thuộc hàm xấp xỉ gồm: Dự đoán những giá

trị thiếu của các thuộc tính trong nhiều bảng quan hệ, sử dụng những giá trị

của các thuộc tính trong việc xác định tập các phụ thuộc hàm xấp xỉ, tối ƣu

hóa truy vấn viết lại câu hỏi, chuẩn hóa cơ sở dữ liệu để khai thác tốt hơn và

thiết kế lƣu trữ hiệu quả hơn.

Việc khai phá các phụ thuộc hàm xấp xỉ là tốn kém vì những lý do sau:

Các chiến lƣợc cắt tỉa cho những phụ thuộc hàm không ứng dụng trong

trƣờng hợp các phụ thuộc hàm xấp xỉ. Với các cơ sở dữ liệu có một số lớn các

thuộc tính thì không gian tìm kiếm lớn khiến các phƣơng pháp quyết định một

phụ thuộc có đúng hay không là tốn kém.

Trong những năm gần đây, một hƣớng nghiên cứu mới đã phát triển đó là

khai phá các phụ thuộc hàm. Các nhà nghiên cứu đã tập trung vào vấn đề tìm

tất cả những phụ thuộc hàm đúng trong một quan hệ cho trƣớc.

Nghiên cứu phát hiện các phụ thuộc hàm xấp xỉ gồm ba phần quan trọng:

Một là xác định một độ đo xấp xỉ cho các phụ thuộc hàm xấp xỉ. Hai là phát

triển các phƣơng pháp để áp dụng những phụ thuộc hàm xấp xỉ cho các vần

đề tồn tại từ trƣớc. Ba là phát triển các thuật toán để tính toán hiệu quả những

phụ thuộc hàm xấp xỉ.

Kivinen và Mannila định nghĩa một vài độ đo cho sai số của một phụ

thuộc và suy ra các cận để phát hiện các phụ thuộc với những sai số của một

phụ thuộc. Họ đã biểu thị e bởi g3.

2.1. Lớp tƣơng đƣơng và phủ tối thiểu

2.1.1. Sự phân hoạch

Một phụ thuộc hàm là đúng trên một quan hệ nếu

tất cả các bộ mà bằng nhau trên thì cũng bằng nhau trên , trong đó

. Việc kiểm tra xem các bộ bất kì bằng nhau trên vế trái thì

có bằng nhau trên vế phải của phụ thuộc hàm hay không.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

30

Các phƣơng pháp tiếp cận mở rộng cho các phụ thuộc xấp xỉ đƣợc nghiên

cứu và phát triển. Một trong những cách tiếp cận là sử dụng các lớp tƣơng

đƣơng và các phân hoạch.

Chúng ta dùng phƣơng pháp phân hoạch chia các bộ dữ liệu thành các

nhóm dựa trên những giá trị khác nhau của mỗi cột (thuộc tính). Với mỗi

thuộc tính, số các nhóm bằng với số các giá trị khác nhau của mỗi thuộc tính

đó. Mỗi nhóm đƣợc gọi là một lớp tƣơng đƣơng.

Hai bộ và là tƣơng đƣơng đối với một tập các thuộc tính cho

trƣớc nếu với mọi trong . Mỗi tập thuộc tính bất kỳ

phân hoạch các bộ của quan hệ thành các lớp tƣơng đƣơng. Chúng ta biểu thị

lớp tƣơng đƣơng của một bộ với một tập cho trƣớc bởi ,

tức là . Tập của các lớp

tƣơng đƣơng là một phân hoạch của theo . Nhƣ vậy mỗi lớp tƣơng

đƣơng ứng với một giá trị duy nhất cho tập thuộc tính và hợp của các lớp

tƣơng đƣơng bằng với quan hệ . Bậc của phân hoạch là số lớp

tƣơng đƣơng trong .

Ví dụ: Xét quan hệ.

TupleID A B E C D

1 a 2 $ Hoa 1

2 x 2 Hoa tulip 1

3 x 0 $ Cây thủy tiên 2

4 x 0 $ Hoa 2

5 y 0 Cây huệ 2

6 y 1 $ Phong lan 3

7 c Hoa 3

1 1 8 c # Bông hồng 3

Bảng 2.1: Bảng quan hệ ví dụ cho phân hoạch

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

31

Thuộc tính A có giá trị “1” chỉ trong các bộ 1 và 2 vì vậy chúng tạo thành

một lớp tƣơng đƣơng . Tƣơng tự, thuộc tính A có giá trị

“2” trong các bộ 3, 4, 5 và có giá trị “3” trong các bộ 6, 7, 8. Sau đây toàn bộ

các lớp tƣơng đƣơng của thuộc tính A: . Các lớp

tƣơng đƣơng với tổ hợp các thuộc tính là

.

Phân hoạch của các thuộc tính

2.1.2. Phân hoạch mịn hơn

Khái niệm phân hoạch mịn hơn liên quan trực tiếp với các phụ thuộc. Một

phân hoạch mịn hơn một phân hoạch khác nếu mỗi lớp tƣơng đƣơng

trong là tập con của một lớp tƣơng đƣơng nào đó của .

Một phụ thuộc hàm đúng nếu và chỉ nếu mịn hơn . Để

kiểm tra đúng hay không chúng ta kiểm tra có bằng với

hay không. Nếu mịn hơn thì có cùng số tƣơng

đƣơng với .

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

32

Ví dụ: Xét quan hệ cho trên bảng 2.2 sau:

B TupleID A E C D

a 1 1 2 $ Hoa

x 2 1 2 Hoa tulip

x 3 2 0 $ Cây thủy tiên

x 4 2 0 $ Hoa

y 5 2 0 Cây huệ

y 6 3 1 $ Phong lan

c 7 3 1 Hoa

c 8 3 1 #

Bông hồng Bảng 2.2: Bảng quan hệ ví dụ cho phân hoạch mịn hơn

Các lớp tƣơng đƣơng đối với thuộc tính , các

lớp tƣơng đƣơng đối với thuộc tính . Vì các lớp

tƣơng đƣơng của thuộc tính mịn hơn các lớp tƣơng đƣơng của thuộc tính

nên qua đó có thể phát hiện phụ thuộc hàm đƣợc thỏa mãn.

2.1.3. Phủ tối thiểu

Định nghĩa: Cho và là những tập phụ thuộc hàm trên tập thuộc

tính . Ta nói phủ nếu có , và nói và tƣơng đƣơng

nếu , và kí hiệu là F~G.

Bằng cách sử dụng thuật toán 2.1, có thể kiểm tra xem và có

tƣơng đƣơng không. Cần chú ý rằng: nếu mọi phụ thuộc hàm trong đều

thuộc thì mọi phụ thuộc hàm trong đều suy diễn đƣợc từ

(nghĩa là ). Với phụ thuộc hàm , để kiểm tra

, ta sẽ tính và kiểm chứng .

Bổ đề 2.1 Mỗi tập phụ thuộc hàm có một tập phụ thuộc hàm

tƣơng đƣơng với nó sao cho mỗi phần tử của đều có vế phải chỉ gồm một

thuộc tính.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

33

Chứng minh

Với mỗi , đặt:

Nhờ quy tắc tách và quy tắc hợp trong bổ đề 1.2, dễ dàng thấy rằng

thỏa mãn các yêu cầu của định lí.

Tập phụ thuộc hàm đƣợc gọi là tối tiểu nếu:

(i) Vế phải của mỗi phụ thuộc trong gồm đúng một thuộc tính.

(Không dƣ thừa thuộc tính nào ở vế phải).

(ii) Không tồn tại trong sao cho tƣơng

đƣơng với . (Không thể bỏ đi một phụ thuộc nào trong mà vẫn thu

đƣợc một tập phụ thuộc tƣơng đƣơng với nó).

(iii) Không tồn tại trong và tập con thực sự của sao

cho tƣơng đƣơng với . (Không thể bỏ đi bất kì

một thuộc tính nào ở vế trái của một phụ thuộc bất kì trong mà vẫn thu

đƣợc một tập phụ thuộc tƣơng đƣơng với nó).

Điều kiện thứ nhất đảm bảo rằng mọi phụ thuộc hàm trong không dƣ

thừa thuộc tính nào ở vế phải. Điều kiện thứ hai đảm bảo rằng không có

phụ thuộc hàm nào dƣ thừa. Điều kiện cuối cùng đảm bảo rằng mọi phụ thuộc

hàm trong không dƣ thừa thuộc tính nào ở vế trái.

Định lí 2.1

Với mỗi tập phụ thuộc hàm , đều tồn tại một tập phụ thuộc hàm tối tiểu

tƣơng đƣơng với nó.

1. Theo bổ đề 1.5, có tập phụ thuộc tƣơng đƣơng với mà các phần

tử của đều có vế phải gồm đúng một thuộc tính.

2. Loại bỏ từ những phụ thuộc hàm vi phạm (ii), ta thu đƣợc .

3. Loại bỏ những thuộc tính trong vế trái của các phụ thuộc hàm trong

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

34

làm cho nó vi phạm (iii), ta thu đƣợc .

Dễ dàng thấy rằng, là tối tiểu và tƣơng đƣơng với nên nó chính là

cần tìm.

Chú ý: Việc loại bỏ những phụ thuộc hàm và thuộc tính ở bƣớc 2 và bƣớc

3 trong phép chứng minh có thể cho ta những tập phụ thuộc hàm khác nhau

(thỏa mãn định lí 1.5), thậm chí chúng có số phần tử khác nhau.

Ví dụ:

Cho . Ta có thể tìm đƣợc hai

tập phụ thuộc tối tiểu tƣơng đƣơng với là:

loại bỏ từ trái sang phải ở điều kiện (ii)

loại bỏ từ phải sang trái.

Thuật toán 2.1: Tìm phủ tối tiểu của tập phụ thuộc hàm trên tập thuộc

tính .

INPUT: F, U

OUTPUT: G {G là phủ tối thiểu của F}

Bƣớc 1: . Tách tất cả các phụ thuộc hàm f của F thành phụ thuộc

hàm mà vế phải chỉ có một thuộc tính:

FOR

Bƣớc 2: Loại bỏ những phụ thuộc hàm không đầy đủ:(loại các thuộc tính

thừa ở vế trái các phụ thuộc hàm)

WHILE

Bƣớc 3: Loại bỏ những phụ thuộc hàm dƣ thừa:

FOR DO IF

Bƣớc 4: RETURN

Ta có thể diễn giải lại thuật giải nhƣ sau:

Ví dụ: Cho lƣợc đồ quan hệ Q(A,B,C,D) và tập phụ thuộc

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

35

Tìm phủ tối thiểu?

Bƣớc 1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính.

+ Ta có

Bƣớc 2. Bỏ các thuộc tính dƣ thừa ở vế trái.

+ Không xét vì vế trái chỉ có một thuộc tính.

+ Xét : Nếu bỏ A thì B+=BCD không chứa A nên không thể bỏ A.

Nếu bỏ B thì A+=A, không bỏ đƣợc thuộc tính nào.

: Nếu bỏ A thì B+=BCD không chứa A nên không thể bỏ A.

+ Xét Nếu bỏ B thì A+=A, không bỏ đƣợc thuộc tính nào.

Bƣớc 3. Loại khỏi F các phụ thuộc hàm dƣ thừa.

+ Xét

: Tính AB+=ABCD = Q nên loại bỏ : Tính AB+=ABCD = Q nên loại bỏ + Xét

+

: Tính B+=B không thể bỏ. : Tính C+=C không thể bỏ. +

Ví dụ:

. Ta có thể tìm đƣợc hai Cho

phụ thuộc hàm tối tiểu tƣơng đƣơng với F là:

2.1.4. Phụ thuộc hàm xấp xỉ và lớp tương đương

Đối với một số quan hệ, một vài phụ thuộc hàm có thể không thỏa mãn

cho tất cả các bộ. Vậy một phụ thuộc hàm có thể nghĩa theo hƣớng thỏa mãn

xấp xỉ.

Ví dụ:

Về những chiếc xe ôtô, nhãn mác xe đƣợc xác định bởi mô-đen. Dựa vào

điều đó, với mô-đen X6, chúng ta biết với xác suất cao nhãn mác xe là BMW,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

36

nhƣng cũng có một xác suất nhỏ rằng nhãn mác xe là Honđa. Phụ thuộc hàm

xấp xỉ đƣợc mong đợi đó đƣợc xác định bởi Mô-đen Nhãn mác xe.

Một định nghĩa chuẩn của một phụ thuộc xấp xỉ là dựa trên số

tối thiểu những hàng cần loại bỏ khỏi quan hệ để phụ thuộc đúng

trong . Sai số và đúng trong

. Độ đo có một cách hiểu tự nhiên nhƣ tỷ số của các hàng với

những ngoại lệ hoặc sai số ảnh hƣởng đến phụ thuộc. Cho một ngƣỡng sai số

, chúng ta nói rằng là một phụ thuộc xấp xỉ nếu và chỉ ,

lớn nhất là bằng . nếu

Một lớp tƣơng đƣơng của là hợp của một hoặc nhiều lớp tƣơng

đƣơng của đúng. Số tối thiểu các hàng cần loại bỏ là kích

thƣớc của trừ đi kích thƣớc của lớp lớn nhất. Lấy trên tất cả các lớp

tƣơng đƣơng của cho tổng số các bộ cần loại bỏ. Nhƣ vậy chúng ta

có:

và .

Ví dụ: Cho quan hệ

TupleID 1 2 3 4 5 6 7 8 A 1 1 2 2 2 3 3 3 B a x x x y y c c E 2 2 0 0 0 1 1 1 C $ $ $ $ # D Hoa Hoa tulip Cây thủy tiên Hoa Cây huệ Phong lan Hoa Bông hồng

Bảng 2.3: Bảng quan hệ ví dụ cho phụ thuộc hàm xấp xỉ

Để kiểm tra thỏa hoặc không, chúng ta tìm các lớp tƣơng đƣơng

của và các lớp tƣơng đƣơng của

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

37

. Vì lớp tƣơng đƣơng trong không

mịn hơn bất kỳ lớp nào trong , và tƣơng tự nhƣ vậy đối với các lớp khác

của . Do đó không thỏa.

Tuy nhiên trong ví dụ trên, có thể thỏa với một sai số nào đó

nếu chúng ta loại bỏ một vài bộ khỏi quan hệ đã cho. Đầu tiên chúng ta tìm

. Lớp tƣơng đƣơng trong

bằng lấy từ , có kích thƣớc lớn nhất của và là .

Lớp tƣơng đƣơng trong bằng lấy từ , có kích

thƣớc lớn nhất của và là 2. Cuối cùng lớp tƣơng đƣơng

của bằng lấy từ có kích thƣớc lớn nhất của và

là 2.

Từ đó . Nói cách ít nhất 3 bộ trong 8

bộ ở ví dụ trên cần loại bỏ để đƣợc thỏa mãn. Nhƣ vậy có thể nói

phụ thuộc hàm: thỏa mãn xấp xỉ với tỉ lệ sai số .

Quá trình phát hiện các phụ thuộc hàm xấp xỉ này đƣợc lặp lại cho tất cả

thuộc tính và cho tất cả các tổ hợp của chúng. Lấy ví dụ, cho một quan hệ với

5 thuộc tính (A, B, C, D, E) tập các ứng viên là {Ø, A, B, C, D, E, AB, AC,

AD, AE, BC, BD, BE, CD, CE, DE, ABC, ABD, ABE, ACD, ACE, ADE,

BCD, BCE, BDE, CDE, ABCD, ABCE, ABDE, ACDE, BCDE, ABCDE} cho

một tổng cộng 32 tổ hợp. Các thuộc tính ứng viên này của quan hệ đƣợc biểu

diễn nhƣ một dàn đƣợc chỉ rõ trong hình 2.1.

Mỗi nút trong hình 2 biểu diễn một tập thuộc tính ứng viên một cạch giữa

hai nút bất kỳ nhƣ E và ED chỉ ra phụ thuộc xấp xỉ: cần đƣợc kiểm

tra.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

38

Hình 2.1: Dàn cho các thuộc tính (A, B, C, D, E)

Phần tiếp theo sau trình bày thuật toán TANE đã đƣợc sửa đổi để tìm tất

cả các phụ thuộc hàm xấp xỉ dạng có độ đo lỗi , với

là ngƣỡng lỗi cho trƣớc .

2.2. Thuật toán TANE sửa đổi [5]

2.2.1. Thủ tục chính của thuật toán TANE sửa đổi

Sau đây là các thủ tục chính của thuật toán TANE sửa đổi để tính các phụ

thuộc hàm xấp xỉ:

Input: Quan hệ trên lƣợc đồ

Output: Các phụ thuộc hàm tối tiểu, không tầm thƣờng đúng trên

không đúng} .

không đúng}.

1.

2.

3.

4.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

39

5. while

6. COMPUTE_DEPENDENCIES

7. PRUNE

GENERATE_NEXT_LEVEL 8.

9.

Giải thích

khởi tạo bằng rỗng 1

bằng 2

bằng họ tất cả các tập một thuộc tính trong 3

4

5 while

6 Tính toán các phụ thuộc hàm trong mức

7 Prune tỉa để tìm kiếm và xóa các phụ thuộc hàm không cần

thiết

xây dựng các phụ thuộc hàm cho mức tiếp theo, dựa trên 8

9

Thủ tục: Tính các phụ thuộc hàm

Procedure COMPUTE_DEPENDENCIES

1 for each do

2

3 for each do

4 for each do

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

40

then if 5

output 6

remove from 7

8 If thỏa mãn then

remove all in from 9

Thủ tục: Tỉa

Procedure PRUNE

1 for each do

if do 2

3 delete from

if is a (super) key do 4

5 do for each

6 then if

7 output

8 delete from

Thuật toán TANE đã đƣợc sửa đổi để tính tất cả các phụ thuộc hàm xấp xỉ

tối tiểu với , với một giá trị ngƣỡng cho trƣớc.

Việc sửa đổi quan trọng là thay đổi việc kiểm tra tính thỏa trên dòng 5 của thủ

tục COMPUTE_DEPENDENCIES bởi:

If then

Thay dòng 8 của thủ tục COMPUTE_DEPENDENCIES bởi:

If thỏa mãn then

remove all in from .

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

41

2.2.2. Độ phức tạp của thuật toán TANE sửa đổi.

Với quan hệ có thuộc tính và bộ. Độ phức tạp thời gian của

thuật toán TANE sửa đổi phụ thuộc vào số bộ trong cơ sở dữ liệu , phụ

thuộc vào số tập trong tất cả các mức của dàn các thuộc tính ứng viên

và số khóa .

Do đó độ phức tạp của thuật toán TANE sửa đổi là:

.

Phần tiếp theo sau trình bày thuật toán tìm phụ thuộc hàm xấp xỉ dựa trên

một số khái niệm của lý thuyết thiết kế CSDL quan hệ là phủ tối thiểu và lớp

tƣơng đƣơng do tác giả Jalal Atoum (Khoa Khoa học Máy tính, Đại học Công

nghệ (PSUT), Jordan) đề xuất và công bố năm 2009 [8]

2.3. Thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu

và lớp tƣơng đƣơng

2.3.1. Mô tả thuật toán

Thuật toán khai phá phụ thuộc hàm xấp xỉ từ những cơ sở dữ liệu lớn

đƣợc trình bày dƣới đây dựa trên độ đo xấp xỉ . Trong đó có sử dụng một

số khái niệm của lý thuyết thiết kế cơ sở dữ liệu quan hệ, cụ thể là các khái

niệm phủ tối tiểu và những lớp tƣơng đƣơng (Mining Approximate Functional

Dependencies from Databases based on Minimal Cover and Equivalenc

Classes viết tắt là “AFDMCEC”). Thuật toán này làm giảm bớt số các thuộc

tính và các phụ thuộc hàm xấp xỉ cần kiểm tra bởi có kết hợp với một vài khái

niệm từ lý thuyết thiết kế cơ sở dữ liệu quan hệ.

Những khái niệm đầu tiên bao gồm việc tăng trƣởng tính phủ tối tiểu của

các phụ thuộc hàm xấp xỉ trong mỗi giai đoạn phát hiện những phụ thuộc hàm

này. Mục đính của cách làm này là để giảm tối thiểu số các phụ thuộc hàm

xấp xỉ cần kiểm tra. Trong khi đó khái niệm thứ hai bao gồm việc tính toán về

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

42

sự tƣơng đƣơng của các thuộc tính dựa trên bao đóng không tầm thƣờng của

chúng. Đối với mỗi cặp thuộc tính có cùng bao đóng, thuật toán loại đi một

trong chúng khỏi tập hợp các thuộc tính ứng viên. Nhƣ vậy thuật toán cũng

xem hai thuộc tính này là tƣơng đƣơng xấp xỉ . Điều này sẽ làm giảm

bớt số thuộc tính cần phải kiểm tra trong mỗi giai đoạn của thuật toán

AFDMCEC.

Sau đây là thủ tục chính của thuật toán khai phá phụ thuộc hàm xấp xỉ sử

dụng phủ tối thiểu và lớp tƣơng đƣơng.

Thuật toán

Input: Tập dữ liệu và những thuộc tính của nó

: Ngƣỡng sai số,

Output: Tập phụ thuộc hàm xấp xỉ tối tiểu MinimalApproximate_FDSet,

tập hợp ứng viên cho mức tiếp theo, EQ_Set

1. Bƣớc khởi tạo

Set

Nrows = Số hàng trong cơ sở dữ liệu.

Set FD_Set =

Approximate_FDSet =

Set EQ_Set =

Set Candidate_Set =

2. While Candidate_Set Do

For all Candidate_Set Do

Approximate_FDSet=ComputeMinimaiApproximate_FD

GenerateNextLevelCandidates(Candidate_Set)

3. Display ApproximateFD_Set

Thủ tục chính của thuật toán AFDMCEC gọi thủ tục tính toán phụ thuộc

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

43

hàm xấp xỉ tối tiểu ComputeMinimalApproximate_FD cho mỗi

trong tập ứng viên. Với mỗi thuộc tính , nếu

thì bổ sung vào tập phụ thuộc hàm xấp xỉ Approximate_FDSet, và

nếu bao đóng xấp xỉ của bằng với bao đóng xấp xỉ của thì bổ sung

vào tập phụ thuộc hàm xấp xỉ Approximate_FDSet, bổ sung

vào tập EQ_Set và loại bỏ khỏi tập ứng viên Candidate_Set.

Sau đây là các thủ tục đƣợc sử dụng trong chƣơng trình chính.

Thủ tục ComputeMinimalApproximate_FD :

// Thủ tục tính phụ thuộc hàm xấp xỉ tối tiểu

Procedure ComputeMinimalApproximate_FD(Xi)

Max = 0

TempList =

For each do

// Tập các lớp tƣơng đƣơng của thuộc tính Xi

// Tập các lớp tƣơng đƣơng của thuộc tính XiY

For all do

For all do

if then

if then

Add Max to Templist

For I = 1 to Len(Templist)

J = J + Templist(I)

Result = 1 – J/Nrows

If Result Then

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

44

Add to ApproximateFD_Set

If (approximate closure(Xi) = approximate closure (Y)) then

Add to ApproximateFD_Set

Add Xi to closure [Y]

Add to EQ_Set

Remove Y from candidate_set

Thủ tục GenerateNextLevelCandidates procedure:

//Thủ tục sinh các ứng viên mức tiếp

Procedure GenerateNextLevelCandidates(CANDIDATE_SET)

For each Candidate_Set do

For each Candidate_Set do

and then If

Set

If Xij TempList then

Delete Xij

else

Compute the partition of Xij

2.3.2. Độ phức tạp của thuật toán khai phá phụ thuộc hàm xấp xỉ sử

dụng phủ tối thiểu và lớp tương đương

Thuật toán AFDMCEC đề xuất sẽ kiểm tra toàn bộ bảng gồm bộ để

tìm tất cả những lớp tƣơng đƣơng với độ phức tập thời gian tỷ lệ với . Sau

đó phần chính của thuật toán AFDMCEC có một vòng lặp lặp lại lần. Vì

vậy, phần chính này có độ phức tạp thời gian tỷ lệ với . Trong mỗi lần lặp

của vòng lặp, có một lần gọi cho mỗi thủ tục sau.

1. ComputeMinimaiApproximate_FD(), mỗi lần gọi thủ tục này thực hiện

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

45

lần lặp. Trong mỗi lần lặp có một vòng lặp kiểm tra toàn bộ những ứng viên

trong mức đó có kích thƣớc . Do đó tổng thời gian của bƣớc này là

2. GenerateNextLevelCandidates(Candidate_set) thủ tục này thực hiện hai

vòng lặp lồng nhau, mỗi vòng lặp với lần lặp, cần một tổng thời gian bằng

. Vì vậy, tổng độ phức tạp thời gian đòi hỏi giải thuật AFDMCEC là:

2.3.3. Phân tích thử nghiệm, so sánh về độ phức tạp thời gian .

2.3.3.1. Phân tích thử nghiệm.

Theo kết quả của chạy cả hai thuật (TANE sửa đổi và AFDMCEC), trên

các tập dữ liệu UCI [9], cùng một tập các phụ thuộc hàm xấp xỉ đã đƣợc tạo

ra. Cho thấy các kết quả về thời gian thực tế của thuật toán TANE sửa đổi và

thuật toán AFDMCEC với các tập dữ liệu UCI với số thuộc tính và các bộ dữ

liệu thay đổi cùng với các giá trị ngƣỡng khác nhau trong việc phát hiện

tất cả các AFDs.

Bảng 2.4: Thời gian thực hiện cho cả hai thuật toán

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

46

Bảng 2.4 mô tả thời gian thực hiện cho thuật toán TANE sửa đổi và thuật

toán AFDMCEC đối với một số tập dữ liệu do J.Atoum (2009) thực nghiệm

với các ngƣỡng khác nhau.

Từ bảng 2.4 cùng một tập AFDs đƣợc tìm thấy hiệu quả hơn bằng cách sử

dụng thuật toán AFDMCEC so với thuật toán TANE sửa đổi. Có kết quả nhƣ

vậy là do có nhiều lớp tƣơng đƣơng hơn và dẫn tới có nhiều tập thuộc tính

tƣơng đƣơng hơn.

Nhiều tập thuộc tính tƣơng đƣơng hơn dẫn đến giảm bớt số các AFDs cần

kiểm tra. Tuy nhiên lƣu ý là khi giá trị ngƣỡng càng cao thì thời gian chạy

đòi hỏi của hai thuật toán sẽ càng giảm đi. Đây là điều đúng vì, với giá trị

ngƣỡng cao hơn thì tỷ lệ sai số đƣợc phép nhiều hơn và số các bộ cần loại

bỏ ít hơn trong việc tính g3.

2.3.3.2. So sánh về độ phức tạp thời gian (theo [8])

Chúng ta có sự so sánh về độ phức tạp thời gian đƣợc tính toán trƣớc đó

cho thuật toán AFDMCEC và thuật toán TANE sửa đổi nhƣ sau:

Modified Tane

Database Name # of Attribute # Of Tuples

AFDMCEC

Abalone

9

4,177

2304512

46378

Balance-scale

5

625

22588

1550

Breast-cancer

11

699

2501246

249838

Bridge

13

108

7260882

1386753

Chess

7

28,056

3614034

34671

Echocardiogram

13

132

7457490

1386777

Glass

11

214

1507966

249353

Iris

5

150

7388

1075

Nursery

9

12,960

6801408

55161

640233

103609

209

10

Machine Bảng 2.5: So sánh độ phức tạp thời gian dựa trên T(n) của hai thuật toán

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

47

Đánh giá kết quả chứng minh rằng thuật toán AFDMCEC thực hiện tốt

hơn phiên bản sửa đổi của thuật toán TANE. Thuật toán này hoạt động tốt với

các quan hệ lên đến hàng trăm ngàn bộ dữ liệu, và hƣớng tới việc cực tiêu hóa

thời gian đòi hỏi của các thuật toán nhằm phát hiện các phụ thuộc hàm xấp xỉ

trong các CSDL lớn.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

48

CHƢƠNG 3

THỰC NGHIỆM KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ

3.1. Xây dựng chƣơng trình thực nghiệm

3.1.1. Giới thiệu bài toán

Khi thiết kế cơ sở dữ liệu quan hệ, cần chọn ra tập các lƣợc đồ quan hệ

tốt nhất dựa trên một số tiêu chí nào đó. Để có thể thiết kế đảm bảo không có

sự dƣ thừa dữ liệu, đảm bảo tính nhất quán của dữ liệu cần quan tâm đến mối

ràng buộc giữa các dữ liệu trong quan hệ, đó chính là các phụ thuộc hàm. Phụ

thuộc hàm là một công cụ dùng để biểu diễn một cách hình thức các ràng

buộc toàn vẹn. Phƣơng pháp biểu diễn này có rất nhiều ƣu điểm, và đây là

một công cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ sở dữ liệu.

Trong khuôn khổ thực nghiệm của luận văn, tác giả thực nghiệm tìm

phụ thuộc hàm xấp xỉ trên tập dữ liệu của công ty tin học Ánh Sao trên địa

bàn thành phố Hải Dƣơng. Công ty thực hiện triển khai các dự án tại các địa

điểm khác nhau, mỗi dự án do một phòng chuyên môn đảm nhiệm và có nhân

viên phụ trách, thực hiện trên một khoảng thời gian (số tháng). Bảng 4.1 biểu

diễn dữ liệu quản lý triển khai các dự án tại các địa phƣơng. Vấn đề đặt ra là,

từ dữ liệu quản lý triển khai các dự án, phát hiện mối liên hệ giữa các thuộc

tính (chính là phụ thuộc hàm).

Bài toán: Cho tập dữ liệu quản lý triển khai các dự án và ngƣỡng sai số

. Tìm ra các phụ thuộc hàm xấp xỉ có sai số không vƣợt quá .

3.1.2. Dữ liệu thử nghiệm

Trong quý I và II của năm 2015, CSDL quản lý triển khai các dự án

lớn. Để thử nghiệm khai phá, ở đây chỉ trích chọn một phần nhỏ của dữ liệu

thực.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

49

Tên dự án Địa điểm dự án Tên phòng ban Tên nhân viên Thời gian

ProjectA TP Hải Dƣơng Giải pháp mạng Quỳnh Anh 7

ProjectB TP Hải Dƣơng Phần mềm ngoại Quỳnh Anh 5

ProjectD Chí Linh Phần mềm nội Quỳnh Anh 8

ProjectD Chí Linh Phần mềm nội Lan Anh 9

ProjectA TP Hải Dƣơng Giải pháp mạng Hồng Anh 6

ProjectB Sao Đỏ Phần mềm ngoại Lan Anh 6

ProjectD Ninh Giang Phần mềm nội Hải Hà 9

ProjectE Kim Thành Chăm sóc KH Hồng Anh 5

Bảng 3.1: Dữ liệu trích chọn để khai phá.

Chuyển đổi dữ liệu để khai phá:

Để chuẩn bị dữ liệu cho khai phá phụ thuộc hàm xấp xỉ, các thuộc tính

đƣợc mã hóa bởi tập số tự nhiên (tức là ánh xạ sang các số tự nhiên).

Thuộc tính Mã

Tên dự án (TenDA) A

Địa điểm dự án (DiadiemDA) B

Tên phòng ban (TenPB) C

Tên nhân viên (TenNV) D

Thời gian (Thoigian) E

Bảng 3.2: Bảng mã hóa các thuộc tính

Tiếp đến, dữ liệu đƣợc tiền xử lý đƣa về dạng Text, ghi trên tệp BANG.txt.

Mỗi giao tác đƣợc mô tả thành một dòng text trong tệp BANG.txt nhƣ sau: Liệt

kê mã giá trị các thuộc tính, các mã cách nhau một dấu cách. Hình 3.1 là tệp

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

50

BANG.txt biểu diễn một phần dữ liệu trong bảng 3.1.

Hình 3.1: Dữ liệu đã mã hóa chuẩn bị cho khai phá

Tệp BANG.txt biểu diễn dữ liệu đã tiền xử lý, chuẩn bị cho khai phá

phụ thuộc hàm xấp xỉ. Kết quả sẽ đƣợc ánh xạ ngƣợc lại để xác định tên thuộc

tính.

3.1.3. Xây dựng chương trình thực nghiệm

Chƣơng trình sử dụng thuật toán để khai phá phụ thuộc hàm xấp xỉ sử

dụng phủ tối thiểu và lớp tƣơng đƣơng, đƣợc trình bày trong chƣơng 2.

Chƣơng trình đƣợc xây dựng trên ngôn ngữ Free Pascal IDE và cài đặt

trên môi trƣờng hệ điều hành Windows 7 bản 32bit. Máy tính thực nghiệm có

cấu hình tối thiểu nhƣ sau:

- Tốc độ CPU: 2.0GHz; Dung lƣợng bộ nhớ RAM: 512MB

- Không gian trống trên ổ cứng: 1GB

Chƣơng trình đƣợc dịch thành tệp AFDMCEC.EXE. Để khởi động

chƣơng trình, nhấp đúp chuột vào biểu tƣợng AFDMCEC.EXE đƣợc đặt ở ổ

C trong thƣ mục ThucNghiem của chƣơng trình.

3.2. Thực nghiệm khai phá phụ thuộc hàm xấp xỉ

Trong hình 3.2 cho thấy ứng với ngƣỡng sai số ε = 0,3 có 8 phụ thuộc

hàm xấp xỉ đƣợc khai phá trên một số giao tác với 05 thuộc tính.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

51

Ở phụ thuộc hàm thứ 7, cho kết quả: AD → B, ánh xạ ngƣợc lại tên

thuộc tính, ta có PTH xấp xỉ: {TenDA, TenNV} → {DiadiemDA}.

Hình 3.2: Giao diện kết quả đƣợc khai phá phụ thuộc hàm xấp xỉ

3.3. Kết quả thực nghiệm

Chƣơng trình ứng dụng khai phá phụ thuộc hàm xấp xỉ đã thực hiện

thành công, cho ta kết quả tìm đƣợc các phụ thuộc hàm biểu diễn mối liên hệ

giữa các thuộc tính với ngƣỡng sai số ε = 0,3.

Kết quả thử nghiệm khai phá dữ liệu trên đã khẳng định những vấn đề

lý thuyết trong khai phá phụ thuộc hàm xấp xỉ đã trình bày ở chƣơng 2.

Kết quả khai phá phụ thuộc hàm xấp xỉ do chƣơng trình thực nghiệm

tìm đƣợc sẽ giúp cho việc thiết kế CSDL quản lý việc triển khai các dự án

đƣợc tốt hơn, cụ thể là giúp cho việc chuẩn hóa, tách lƣợc đồ quan hệ, đƣa về

dạng không dƣ thừa dữ liệu, đảm bảo tính nhất quán dữ liệu, đạt dạng chuẩn

cao hơn.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

52

KẾT LUẬN

1. Những kết quả chính của luận văn

Phụ thuộc hàm biểu diễn mối quan hệ giữa các thuộc tính của một cơ sở dữ

liệu, một phụ thuộc hàm chỉ ra rằng giá trị của một thuộc tính đƣợc xác định

duy nhất bởi giá trị của một số thuộc tính khác. Phụ thuộc hàm đóng vai trò

quan trọng trong chuẩn hóa cơ sở dữ liệu, phát hiện các phụ thuộc hàm cũng có

thể giúp các nhà thiết kế cơ sở dữ liệu tách một lƣợc đồ quan hệ thành nhiều

lƣợc đồ quan hệ đạt dạng chuẩn cao hơn.

Qua quá trình nghiên cứu đề tài “Khai phá phụ thuộc hàm xấp xỉ sử dụng

phủ tối thiểu và lớp tương đương”, luận văn đã đạt đƣợc một số kết quả:

- Tìm hiểu tổng quan về khai phá dữ liệu, khai phá phụ thuộc hàm trong

cơ sở dữ liệu quan hệ, mở rộng khai phá phụ thuộc hàm xấp xỉ và một số vấn đề

về độ đo lỗi của phụ thuộc hàm xấp xỉ.

- Tìm hiểu thuật toán TANE sửa đổi khai phá các phụ thuộc hàm và phụ

thuộc hàm xấp xỉ trong cơ sở dữ liệu, thuật toán AFDMCEC khai phá phụ

thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng. Nhận xét và đánh

giá về độ phức tạp của hai thuật toán.

- Cài đặt chƣơng trình Demo, khai phá các phụ thuộc hàm xấp xỉ sử dụng

phủ tối thiểu và lớp tƣơng đƣơng trên tập dữ liệu quản lý các dự án của Công ty

Ánh Sao, TP Hải Dƣơng.

2. Hƣớng nghiên cứu tiếp theo của luận văn

- Cải tiến chƣơng trình Demo để thực hiện trên cơ sở dữ liệu lớn hơn.

- Nghiên cứu các phƣơng pháp mới để khai phá các phụ thuộc hàm và phụ

thuộc hàm xấp xỉ trong cơ sở dữ liệu có hiệu quả cao hơn.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

53

TÀI LIỆU THAM KHẢO

Tiếng Việt:

[1] Trần Duy Anh (2007), “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, T. 23, S. 3, tr. 284 - 295.

[2] Trần Duy Anh (2014), “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”, Tạp chí Tin học và Điều khiển học,

30(2).

[3] Hồ Thuần (chủ biên), Hồ Cẩm Hà (2005), Các hệ cơ sở dữ liệu - Lý thuyết

và thực hành, NXB Giáo dục Việt Nam.

[4] Nguyễn Thanh Thủy (2003), “Phát hiện tri thức và khai phá dữ liệu:

Công cụ, phương pháp và ứng dụng”.

Tiếng Anh:

[4]. Kivinen J., and Mannila H. (1995), “Approximate Inference of Functional

Dependencies From Relations”. Theoretical Computer Science, Vol. 1, No. 49,

pp. 129-149.

[5] Huhtala Y., Karkkainen J., Porkka P., and Toivonen H., (1999). “Tane: An

efficient algorithm for discovering functional and approximate dependencies”.

The Computer Journal, Vol. 42, No. 2, pp. 100-111.

[6] Ronald S.King, James J.Legendre (2003), “Discovery of functional and

approximate dependencies in relational databases”, Journal of applied

mathematics and decision sciences, Vol. 7, No. 1, pp. 49 - 59.

[7] Wenfei Fan and et al (2011), “Discovering conditional functional

dependencies”, Ieee International Conference on Data Engineering, Vol. 23,

No. 5.

[8] J.Atoum (2009), “Mining Approximate Functional Dependencies from

Databases based on Minimal Cover and Equivalenc classes”, European J. of

cientific Research, Vol. 33, No. 2, pp. 338-346.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

54

[9] UCI Machine Learning Repository, http://www.ics.uci.edu /~mlearn/

MLRepository.html.

[10] Han J., and Kamber M. (2012), Data Mining: Concepts and

Techniques, Third Edition, Morgan Kaufmann, Series in Data Management

Systems.

[11] Anupama A Chavan, Vijay Kumar Verma (2013), Functional

Dependency Mining form Relational Database: A Survey, International

Journal of Engineering and Advanced Technology, ISSN: 2249 – 8958,

Volume-2, Issue-6.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

55

PHỤ LỤC

Mã nguồn chƣơng trình thực nghiệm:

uses crt;

Type mang=array[1..8]of string[8];

Var

AFDT:array[1..100] of string[10];

AFDP:array[1..100] of string[10];

EQT:array[1..100] of string[10];

EQP:array[1..100] of string[10];

Can:array[1..100] of string[10];

DL:array[1..50,'A'..'E'] of String[10];

List:array[1..50] of Byte;

R:String[5];

f1:text;

O:mang;

Procedure Nhap;

Var a1,a2:Byte;

a3:string[10];

Begin

assign(f1,'c:\Thucnghiem\BANG.txt');

Reset(f1);

for a1:=1 to 8 do

Begin

readln(f1,a3);

DL[a1,'A']:=a3[1];

DL[a1,'B']:=a3[3];

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

56

DL[a1,'C']:=a3[5];

DL[a1,'D']:=a3[7];

DL[a1,'E']:=a3[9];

End;

End;

{Thu tuc sinh hoan vi}

Procedure Hoanvi;

Var max,a,i,j:byte;

m,l,o,p,q:char;

e:Real;

Begin

R:='ABCDE';

i:=1;

for m:='A' to 'E' do

begin

Can[i]:=m;

inc(i);

End;

for m:='A' to 'E' do

for l:='A' to 'E' do

if(m

begin

Can[i]:=m+l;

inc(i);

End;

for m:='A' to 'E' do

for l:='A' to 'E' do

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

57

for o:='A' to 'E' do

if(m

begin

Can[i]:=m+l+o;

inc(i);

End;

for m:='A' to 'E' do

for l:='A' to 'E' do

for o:='A' to 'E' do

for p:='A' to 'E' do

if(m

begin

Can[i]:=m+l+o+p;

inc(i);

End;

Can[i]:='ABCDE';

End;

{Thu tuc phan hoach}

Procedure Phan_Hoach(X:char;var B:mang);

var L:array[1..8]of string[8];

j,dem1,dem2,a,i:byte;

M1:mang;

DLTG:array[1..8,'A'..'E']of string[8];

c:char;

xau,xau1:string[8];

Begin

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

58

for i:=1 to 8 do M1[i]:='';

dem2:=0;dem1:=1;

for dem2:=1 to 8 do

Begin

xau:='';

for i:=dem1 to 8 do

if DL[i,X]<>DL[dem1,X] then

begin

a:=i;

break;

end;

str(dem1,xau);

for i:= dem1+1 to 8 do

if DL[i,X]=DL[dem1,X] then

Begin

Str(i,xau1);

xau:=xau+xau1;

End;

M1[dem1]:=xau;

dem1:=a;

End;

for i:=1 to 7 do

for j:=8 downto i+1 do

if (pos(M1[j],M1[i])<>0)and(j>i) then M1[j]:='';

B:=M1;

End;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

59

{Phan hoach hai thuoc tinh}

Procedure PH(A,B:char;var C:mang);

var M,N:mang;

KT:string[8];

TG:array[1..50] of string[8];

i,j,k,k1,k2,k3:word;

Begin

Phan_Hoach(A,M);

Phan_Hoach(B,N);

for i:=1 to 50 do TG[i]:='';

for i:=1 to 8 do C[i]:='';

k:=1;

for i:=1 to 8 do

if M[i]<>'' then

Begin

for j:=1 to 8 do

if N[j]<>'' then

Begin

KT:='';

for k1:=1 to length(M[i]) do

for k2:=1 to length(N[j])do

if M[i][k1]=N[j][k2] then KT:=KT+N[j][k2];

TG[k]:=KT;

inc(k);

End;

End;

k3:=0;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

60

for i:=1 to k do

if TG[i]<>'' then

Begin

k3:=k3+1;

C[k3]:=TG[i];

End;

End;

{Thu tuc tinh cac phu thuoc ham xap xi}

Procedure Tinh_Phu_Thuoc_xap_xi;

Var max,a,i,j,k,k1,k2,dem1,dem2:byte;

i1,j1:byte;

e:Real;

c,L:Char;

Dau:array[1..5] of boolean;

TG,Y:String[5];

M,N,M1,N1:mang;

RY:string[100];

Begin

e:=0.3;R:='ABCDE';

Nhap;

Hoanvi;

for i:=1 to 100 do

Begin

AFDT[i]:='';

AFDP[i]:='';

EQT[i]:='';

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

61

EQP[i]:='';

End;

{Tinh Phu thuoc xap xi voi cac ung vien}

for a:=1 to 5 do

Begin

RY:='';TG:='';

for i:=1 to 5 do dau[i]:=true;

for i:=1 to length(R) do

for j:=1 to length(Can[a]) do

if Can[a][j]=R[i] then dau[i]:=false;

for i:=1 to 5 do

if dau[i]=true then RY:=RY+R[i];

for k1:=1 to length(RY) do

Begin

Phan_Hoach(Can[a][1],M);

PH(Can[a][1],RY[k1],N);

k:=0;

for i:=1 to 8 do

if M[i]<>'' then

Begin

max:=0;

for j:=1 to 8 do

if pos(N[j],M[i])<>0 then

if max<=length(N[j]) then

max:=length(N[j]);

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

62

k:=k+max;

End; if k=8 then k:=0;

if (1-(k/8))<=e then writeln(' ',Can[a],' -> ',RY[k1]);

End;

End;

for a:=6 to 15 do

Begin

if length(Can[a])>=2 then

Begin

RY:='';TG:='';

for i:=1 to 5 do dau[i]:=true;

for i:=1 to length(R) do

for j:=1 to length(Can[a]) do

if Can[a][j]=R[i] then dau[i]:=false;

for i:=1 to 5 do

if dau[i]=true then RY:=RY+R[i];

for i1:=1 to length(Can[a])-1 do

PH(Can[a][i1],Can[a][i1+1],M);

for j:=1 to length(RY[j]) do

Begin

PH(Can[a][i1],RY[j],N);

k:=0;

for i:=1 to 8 do

if M[i]<>'' then

Begin

max:=0;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

63

for j1:=1 to 8 do

if pos(N[j1],M[i])<>0 then

if max

max:=length(N[j1]);

k:=k+max;

End; if k=8 then k:=0;

if (1-(k/8)) <= e then writeln(' ',Can[a],' ->

',RY[j]);

End;

End;

End;

End;

BEGIN

clrscr;

writeln('Phu thuoc ham xap xi tim duoc la ');

Tinh_Phu_Thuoc_Xap_Xi;

Readln;

END.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn