Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG
DƢƠNG ĐỨC NGUYÊN NGHIÊN CỨU MỘT SỐ THUẬT TOÁN LIÊN QUAN ĐẾN
TẬP RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC: GS.TS VŨ ĐỨC THI
Thái Nguyên – 2013
Xin chân thành bày tỏ lòng biết ơn đến toàn thể quý thầy cô đã giảng dạy và
truyền đạt kiến thức cho tôi để tôi có thể hoàn thành các môn học trong xuất thời
gian học cao học tại trƣờng Đại học Thái Nguyên.
Xin gửi lời cảm ơn tới ban lãnh đạo cùng toàn thể các thầy cô trong trƣờng
Đại học Công Nghệ Thông Tin và Truyền Thông Đại Học Thái Nguyên đã tạo điều
kiện thuận lợi cho tôi trong thời gian tôi học tập và nghiên cứu tại đây.
Xin chân thành bày tỏ lòng biết ơn đến gia đình, những ngƣời đã không
ngừng động viên, hỗ trợ và tạo mọi điều kiện tốt nhất cho tôi trong suốt thời gian
học tập và thực hiện luận văn.
Cuối cùng, tôi xin chân thành bày tỏ lòng cảm ơn đến các anh chị, các đồng
nghiệp đã hỗ trợ cho tôi rất nhiều trong suốt quá trình học tập, nghiên cứu và thực
hiện đề tài luận văn thạc sĩ một cách hoàn chỉnh.
Thái Nguyên, tháng 8 năm 2013.
Học viên Dƣơng Đức Nguyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iii
MỤC LỤC
MỞ ĐẦU 1
CHƢƠNG 1: MỘT SỐ KHÁI NIỆM CƠ BẢN 4
1.1. Quá trình khai phá tri thức từ cơ sở dữ liệu 4
1.1.1. Xác định vấn đề 5
1.1.2. Thu thập và tiền xử lí dữ liệu 5
1.2. Khai phá dữ liệu 7
1.2.1. Một số quan niệm về khai phá dữ liệu 7
1.2.2.Nhiệm vụ của khai phá dữ liệu 7
2.5. Thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định nhất quán 48
2.6. Thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định nhất quán 51
2.7. Thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm 52
2.8. Tổng kết chƣơng 2 56
CHƢƠNG 3: CÀI ĐẶT CHƢƠNG TRÌNH TÌM TẬP TẤT CẢ CÁC THUỘC
TÍNH RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN 57
1. Đặt vấn đề 57
2. Yêu cầu hệ thống và cấu hình cho máy 57
2.1. Yêu cầu hệ thống 57
2.2. Cấu hình cho máy 57
3. Giới thiệu chƣơng trình và cách sử dụng 58
3.1 Cấu trúc chƣơng trình 58
3.2. Giới thiệu chƣơng trình 60
4. Thực hiện thuật toán với bộ dữ liệu Flu, EXAMPLE1, EXAMPLE 61
4.1. Bộ dữ liệu “Flu” 61
4.2. Bộ dữ liệu “EXAMPLE1” 63
4.3. Bộ dữ liệu “EXAMPLE” 65
5. Kiểm thử 67
6. Tổng kết chƣơng 67
KẾT LUẬN VÀ ĐỀ NGHỊ 68
TÀI LIỆU THAM KHẢO 69 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
v
DANH MỤC CÁC BẢNG
Bảng 1.1 Bảng thông tin về bệnh cúm 16
Bảng 1.2. Bảng quyết định về bệnh cúm 19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
vii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Ký hiệu, từ viết tắt
Diễn giải
IS = (U,A,V,f)
Hệ thông tin, hệ thông tin đầy đủ
IIS = (U,A,V,f)
Hệ thông tin không đầy đủ
DS =(U,C
D,V,f)
Bảng quyết định, bảng quyết định đầy đủ
IDS =(U,C
D,V,f)
Bảng quyết định không đầy đủ
U
Số đối tƣợng
C
Số thuộc tính điều kiện trên bảng quyết định
A
Số thuộc tính trong hệ thông tin
B
X
Quan hệ B không phân biệt
d
j
(K(P),K(Q))
Khoảng cách giữa K(P) và K(Q) trong hệ thông tin đầy đủ
dựa trên entropy Liang mở rộng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
MỞ ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin
đã làm cho khả năng thu thập và lƣu trữ thông tin của hệ thống thông tin tăng
nhanh một cách nhanh chóng. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là
cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lƣợng dữ liệu
khổng lồ kia thành các tri thức có ích. Từ đó, các kỹ thuật khai phá dữ liệu đã trở
thành một lĩnh vực thời sự của nền công nghệ thông tin thế giới hiện nay nói
chung và Việt Nam nói riêng.
Khai phá dữ liệu đang đƣợc áp dụng một cách rộng rãi trong nhiều lĩnh vực
kinh doanh và đời sống khác nhau: Market tinh, tài chính ngân hàng và bảo hiểm,
khoa học kinh tế…Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ
thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu đƣợc
nhiều lợi ích to lớn.
Trong lý thuyết tập thô, dữ liệu đƣợc biểu diễn thông qua một hệ thông tin
IS=(U,A) với U là tập các đối tƣợng và A là tập thuộc tính. Phƣơng pháp tiếp cận
chính của lý thuyết tập thô là dựa trên quan hệ không phân biệt đƣợc để đƣa ra các
tập xấp xỉ dƣới và xấp xỉ trên của nó. Xấp xỉ dƣới bao gồm các đối tƣợng chắc chắn
thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tƣợng có khả năng thuộc về tập đó.
Nếu tập xấp xỉ dƣới bằng tập xấp xỉ trên thì tập đối tƣợng cần quan sát là tập rõ.
Ngƣợc lại là tập thô. Các tập xấp xỉ là cơ sở để đƣa ra các kết luận từ tập dữ liệu.
C đƣợc gọi
là tập rút gọn của thuộc tính điều kiện C nếu R là tập tối thiểu thỏa mãn phụ thuộc
hàm R→{d}. Xét quan hệ r trên tập thuộc tính R
C{d} đƣợc gọi là một tập tối
thiểu của thuộc tính {d} nếu R là tập thuộc tính tối thiểu thỏa mãn phụ thuộc hàm
R→{d}. Do đó, khái niệm tập rút gọn của bảng quyết định tƣơng đƣơng với tập tối
thiểu của thuộc tính {d} trên quan hệ, và một vài bài toán trên bảng quyết định liên
quan đến tập rút gọn có thể đƣợc giải quyết bằng một số kết quả liên quan đến tập
tối thiểu của một thuộc tính trong cơ sở dữ liệu quan hệ; bao gồm bài toán tìm tập
tất cả các thuộc tính rút gọn, bài toán tìm họ tất cả các tập rút gọn, bài toán trích lọc
tri thức dƣới dạng các phụ thuộc hàm từ bảng quyết định, bài toán xây dựng bảng
quyết định từ tập phụ thuộc hàm cho trƣớc. Cho đến nay, hƣớng tiếp cận này chƣa
đƣợc nhiều tác giả quan tâm nghiên cứu.
Trên bảng quyết định nhất quán, vấn đề nhiên cứu đặt ra là xây dựng các thuật
toán có ý nghĩa liên quan đến tập rút gọn sử dụng một số kết quả liên quan đến tập
tối thiểu của một thuộc tính trong một cơ sở dữ liệu quan hệ.
Mục tiêu nghiên cứu của đề tài
- Tổng hợp kiến thức cơ bản nhất liên quan đến tập rút gọn và bảng quyết định
nhất quán.
- Dựa trên lý thuyết đã tổng kết đƣợc, đi xâu vào tìm hiểu, nghiên cứu một số
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
thuật toán liên quan đến tập rút gọn trên bảng quyết định nhất quán. Cài đặt thuật
toán tìm tập tất cả các thuộc tính rút gọn của bảng quyết định nhất quán.
Ý nghĩa khoa học của đề tài
- Đây là lĩnh vực đƣợc nhiều nhà khoa học nghiên cứu và đã có đóng góp
nhiệm vụ.
- Chuyển đổi dữ liệu (Data Transformation): Chuyển dữ liệu về những dạng
phù hợp cho việc khai thác.
- Khai phá dữ liệu (Data mining): Các kỹ thuật đƣợc áp dụng để trích xuất
thông tin có ích hoặc các mẫu điển hình trong dữ liệu.
- Đánh giá mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu đƣợc.
- Trình diễn dữ liệu (Knowledge presentation): Biểu diễn những tri thức khai
phá đƣợc cho ngƣời sử dụng.
Hình 1.1. Quá trình khám phá tri thức từ cơ sở dữ liệu
Hình 1.1 mô tả 5 giai đoạn trong quá trình khám phá tri thức từ cơ sở đến dữ
liệu. Mặc dù có 5 giai đoạn nhƣ trên trong quá trình khám phá tri thức từ cơ sở dữ
liệu là một quá trình tƣơng tác lặp đi lặp lại theo chu trình liên tục kiểu xoáy trôn
ốc, trong đó lần lặp sau hoàn chỉnh hơn lần lặp trƣớc. Ngoài ra, giai đoạn sau lại
3. Khai thác dữ liệu- trích ra các
mẫu/mô
hình
2. Thu thập và tiền xử lí dữ liệu
1. Hiểu và xác định vấn đề
5. Đƣa kết quả vào thực tiễn
4. Minh hoạ và đánh giá tri thức Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
dựa trên kết quả theo kiểu thác nƣớc. Đây là một quá trình biện chứng mang tính
chất khoa học của lĩnh vực phát hiện tri thức và là phƣơng pháp luận trong việc xây
thông tin về thu nhập. Nếu thông tin về thu nhập là quan trọng trong quá trình khai
thác dữ liệu để phân tích hành vi khách hàng thì rõ ràng là ta không thể chấp nhận
đƣa các dữ liệu khuyết thiếu vào đƣợc.
d. Mã hóa:
Các Phƣơng pháp dùng để chọn lọc, làm sạch, làm giàu dữ liệu sẽ đƣợc mã
hóa dƣới dạng các thủ tục, chƣơng trình hay tiện ích nhằm tự động hóa việc kết
xuất, biến đổi và di chuyển dữ liệu. Các hệ thống con đó có thể đƣợc thực thi định
kỳ làm tƣơi dữ liệu phục vụ cho việc phân tích.
1.1.3. Khai thác dữ liệu
Giai đoạn khai thác dữ liệu đƣợc bắt đầu sau khi dữ liệu đã đƣợc thu thập và
tiến hành xử lí. Trong giai đoạn này, công việc chủ yếu là xác định đƣợc bài toán
khai thác dữ liệu, tiến hành lựa chọn phƣơng pháp khai thác phù hợp với dữ liệu có
đƣợc và tách ra các tri thức cần thiết.
Thông thƣờng, các bài toán khai thác dữ liệu bao gồm: Các bài toán mang tính
chất mô tả - đƣa ra những tính chất chung nhất của các dữ liệu, các bài toán khai
thác dự báo - bao gồm cả việc thực hiện các suy diễn trên dữ liệu. Tùy theo bài toán
xác định đƣợc mà ta lựa chọn các phƣơng pháp khai thác dữ liệu cho phù hợp.
1.1.4. Minh họa và đánh giá tri thức
Các tri thức phát hiện từ cơ sở dữ liệu cần đƣợc tổng hợp dƣới dạng các báo
cáo phục vụ cho các mục đích hỗ trợ quyết định khác nhau.
Do nhiều phƣơng pháp khai thác có thể đƣợc áp dụng nên các kết quả có mức
độ tốt/xấu khác nhau. Việc đánh giá các kết quả thu đƣợc là cần thiết, giúp tạo cơ sở
cho các quyết định chiến lƣợc. Thông thƣờng chúng đƣợc tổng hợp, so sánh bằng
các biểu đồ và đƣợc kiểm nghiệm, tin học hoá. Công việc này thƣờng là của các
chuyên gia, các nhà phân tích và quyết định.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
1.2. Khai phá dữ liệu
Do là một lĩnh vực đa ngành, khai phá dữ liệu thu hút các lĩnh vực khoa học
khác nhƣ trí tuệ nhân tạo, cơ sở dữ liệu, hiển thị dữ liệu, marketing, toán học, vận
trù học sinh, nhận dạng mẫu, tính toán thống kê…
Điều mà khai phá dữ liệu có thể làm rất tốt là phát hiện ra những giả thuyết
mạnh trƣớc khi sử dụng những công cụ tính toán thống kê. Mô hình dự báo sử dụng
kỹ thuật phân cụm (Crustering) để chia nhóm các sự vật, sự kiện sau đó rút ra các
luật nhằm tìm ra đặc trƣng cho mỗi nhóm và cuối cùng đề nghị một mô hình. Ví dụ,
những bạn đọc đăng ký dài hạn của một tạp chí có thể phân nhóm dựa theo nhiều
tiêu trí khác nhau (lứa tuổi, giới tính, thu nhập…), sau đó tạp chí căn cứ vào đặc
trƣng riêng của từng nhóm để đề ra mức phí thu trong năm sao cho phù hợp nhất.
Chúng ta thấy, những nhiệm vụ cơ bản nhất của khai phá dữ liệu là:
- Phân cụm, phân loại, phân nhóm, phân lớp. Nhiệm vụ là trả lời câu hỏi; khai
phá luật kết hợp; Lập mô hình dự báo, bao gồm hai nhiệm vụ; Phân tích đối tƣợng
ngoài cuộc; Phân tích sự tiến hoá.
1.2.3. Triển khai việc khai phá dữ liệu
Nhóm các tác giả CABENAETAL. Đề nghị triển khai quá trình khai phá dữ
liệu theo 5 bƣớc.
Bước 1: Xác định rõ mục tiêu thƣơng mại cần khai phá.
Bước 2: Chuẩn bị dữ liệu (thu thập, tiền xử lí, chuyển đổi khuôn dạng dữ liệu
nếu thấy cần thiết).
Bước 3: Khai phá dữ liệu (chọn thuật toán thích hợp).
Bước 4: Phân tích kết quả thu đƣợc (xem có gì thú vị không ?).
Bước 5: Xử lí các tri thức thu lƣợm đƣợc (nhằm đề ra kế hoạch khai thác các
thông tin mới).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
1.2.4. Một số ứng dụng khai phá dữ liệu
Hiện nay, kỹ thuật khai phá dữ liệu đang đƣợc áp dụng một cách rộng rãi trong
trong các ứng dụng về phân đoạn thị trƣờng, phân đoạn khách hàng, nhận dạng
mẫu, phân loại trang web Ngoài ra phân cụm dữ liệu còn có thể đƣợc sử dụng nhƣ
một bƣớc tiền xử lí cho các thuật toán khai phá dữ liệu khác.
b. Phân lớp dữ liệu: Mục tiêu của phƣơng pháp phân lớp dữ liệu là dự đoán
nhãn lớp cho các mẫu dữ liệu. Quá trình phân lớp dữ liệu thƣờng gồm hai bƣớc:
Xây dựng mô hình và sử dụng mô hình để phân lớp dữ liệu.
Bước 1: Một mô hình sẽ đƣợc xây dựng dựa trên việc phân tích các mẫu dữ
liệu có sẵn. Mỗi mẫu tƣơng ứng với một lớp, đƣợc quyết định bởi một thuộc tính
gọi là thuộc tính lớp. Các lớp dữ liệu này còn đƣợc gọi là lớp dữ liệu huấn luyện
(training data set). Các nhãn lớp của tập dữ liệu đều phải đƣợc xác định trƣớc khi
xây dựng mô hình.
Bước 2: Sử dụng mô hình để phân lớp dữ liệu. Trƣớc hết chúng ta phải tính độ
chính xác của mô hình. Nếu độ chính xác là chấp nhận đƣợc, mô hình sẽ đƣợc sử
dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tƣơng lai.
c. Phƣơng pháp hồi quy: Phƣơng pháp hồi quy khác với phân lớp dữ liệu ở
chỗ: Hồi quy dùng để dự đoán về các giá trị liên tục còn phân lớp dữ liệu chỉ dùng
để dự đoán về các giá trị rời rạc.
Hồi quy là một hàm học ánh xạ mục dữ liệu thành một biến dự đoán có giá trị
thực. Có rất nhiều ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, chẳng hạn nhƣ
khả năng đánh giá 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 chỉ tiêu quảng cáo
d. Khai phá luật kết hợp: Mục tiêu của phƣơng pháp này là phát hiện và đƣa
ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Một đầu ra của giải
thuật khai phá dữ liệu là luật kết hợp tìm đƣợc. Chẳng hạn phân tích cơ sở dữ liệu
bán hàng nhận đƣợc thông tin về những khách hàng mua máy tính có khuynh hƣớng
mua phần mềm quản lý tài chính trong cùng lần mua đƣợc miêu tả trong luật kết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
- Cơ sở dữ liệu hoặc kho dữ liệu phục vụ: Là kết quả lấy dữ liệu có liên quan
trên cơ sở khai phá dữ liệu của ngƣời dùng.
- Cơ sở tri thức: Đó là lĩnh vực tri thức đƣợc sử dụng để hƣớng dẫn việc tìm
hoặc đánh giá các mẫu kết quả thu đƣợc
- Mô tả khai phá dữ liệu: Bao gồm tập các modul chức năng để thực hiện các
nhiệm vụ mô tả đặc điểm, kết hợp, phân lớp, phân cụm dữ liệu
- Đánh giá mẫu: Thành phần này sử dụng các độ đo và tƣơng tác với modul
khai phá dữ liệu để tập trung vào tìm các mẫu quan tâm.
- Giao diện ngƣời dùng: Đây là modul giữa ngƣời dùng và hệ thống khai phá
dữ liệu. Cho phép ngƣời dùng tƣơng tác với hệ thống trên cơ sở những truy vấn hay
tác vụ, cung cấp thông tin cho việc tìm kiếm.
1.2.7. Quá trình khai phá dữ liệu
Các thuật toán khai phá dữ liệu thƣờng đƣợc mô tả nhƣ những chƣơng trình
hoạt động trực tiếp trên tệp dữ liệu. Với phƣơng pháp máy học và thống kê trƣớc
đây, thƣờng thì bƣớc đầu tiên các thuật toán nạp toàn bộ tệp dữ liệu vào bộ nhớ. Khi
chuyển sang các ứng dụng công nghiệp liên quan đến việc khai thác các kho dữ liệu
lớn, mô hình này không thể ứng dụng bởi vì không thể nạp hết các dữ liệu vào bộ
nhớ mà còn khó có thể chiết xuất ra những tệp đơn giản để phân tích.
Quá trình khai phá dữ liệu (Hình 1.3) bắt đầu bằng cách xác định chính xác
vấn đề cần giải quyết. Tiếp đến là xác định dữ liệu liên quan dùng để xây dựng giải
pháp. Bƣớc tiếp theo là thu thập các dữ liệu liên quan và xử lí chúng thành dạng sao
cho thuật toán khai phá có thể hiểu đƣợc.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
M
ẫu
Copyright: Tài liệu đại học ©