Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
TRẦN THU PHƯƠNG
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH
TIẾP CẬN TẬP THÔ LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành : Khoa học máy tính
Mã số : 60 48 01
vui, nỗi buồn, động viên tôi đi qua những khó khăn, để tôi vững bước vượt
qua những vất vả, quyết tâm hoàn thành luận văn này.
Tôi xin trân trọng cảm ơn bố mẹ, người thân, bạn bè, đồng nghiệp,
những người đã mang tới tất cả niềm tin, định hướng và theo dõi tôi trong
suốt chặng đường đời. Nâng đỡ và đến bên tôi những giây phút khó khăn nhất
của cuộc sống.
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
Tuy nhiên do thời gian có hạn, mặc dù đã nỗ lực cố gắng hết mình nhưng
chắc rằng luận văn khó tránh khỏi những thiếu sót. Rất mong được sự chỉ bảo,
góp ý tận tình của Quý thầy cô và các bạn.
Thanh Hóa, tháng 9 năm 2011
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
2.3 Một số thuật toán sử dụng lý thuyết tập thô 31
2.3.1. Thuật toán lựa chọn thuộc tính sử dụng tập thô theo phương pháp đánh
giá kinh nghiệm. 31
2.3.2. Thuật toán tìm tập rút gọn dựa vào cặp số phân biệt được 35
2.3.3. Thuật toán sử dụng các phép toán đại số 36
2.3.4 Thuật toán tìm lõi của bảng quyết định 39
2.3.5. Thuật toán tìm tập rút gọn theo xấp xỉ ngoài 39
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
2.3.6. Thuật toán tìm tập rút gọn theo xấp xỉ trong 40
2.4 Một số thuật toán lập nhóm văn bản 42
2.4.1. Thuật toán K – means 42
2.4.2. Thuật toán lập nhóm theo cây phân cấp 42
2.4.3. Xác định các thuật đại diện cho nhóm 44
2.4.4. Độ tương tự giữa văn bản và nhóm văn bản 44
2.5 Kết luận chƣơng 2 44
CHƢƠNG 3. SỬ DỤNG MỘT THUẬT TOÁN ĐỂ TÌM TẬP THUỘC TÍNH
RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ PHỤC VỤ 45
BÀI TOÁN TRA CỨU THÔNG TIN 45
3.1 Tra cứu thông tin 45
3.2 Tra cứu thông tin văn bản 46
3.2.1 Tra cứu thông tin văn bản 46
3.2.2 Xử lý hệ thống thông tin văn bản 47
3.2.3 Một số kỹ thuật tra cứu thông tin văn bản 48
3.3 Phƣơng pháp tra cứu thông tin áp dụng lý thuyết tập thô 50
3.3.1 Xây dựng tập văn bản 50
3.3.2 Gán trọng số cho thuật ngữ bởi dung sai xấp xỉ 50
Hình 4.1 Bảng thông tin tài liệu. 55
Hình 4.2. Bảng lƣu trữ thông tin các lĩnh vực. 55
Hình 4.3 Bảng lƣu trữ thông tin ngôn ngữ. 56
Hình 4.4. Bảng thông tin từ chủ đề. 56
Hình 4.5 Giao diện trang chủ hệ thống tra cứu. 57
Hình 4.6. Kết quả tra cứu của hệ thống. 58
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
DANH MỤC BẢNG BIỂU
Bảng 1.1 Bảng hệ thống thông tin về bệnh cúm. 22
Bảng 1.2 Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R
1
) 22
Bảng 1.3 Bảng rút gọn thứ hai của hệ thống bệnh cúm (R
2
) 22
Bảng 2.1 Bảng thông tin mô tả các đối tƣợng 34
Bảng 2.2. Khởi tạo ban đầu 34
Bảng 2.3 Chọn {a} 34
Bảng 2.4 Chọn {b} 35
Bảng 2.5 Chọn {d} 35
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
cho những người làm khoa học. Trên thực tế, đã có khá nhiều hệ thống thực hiện
công việc này theo những phương pháp khác nhau, tuy chưa đạt được hiệu quả tối
ưu nhưng cũng phần nào đáp ứng được các yêu cầu thông tin cho người sử dụng.
Mỗi phương pháp khác nhau đều thể hiện được những điểm mạnh riêng của nó và
việc lựa chọn phương pháp nào phụ thuộc vào những mục đích, yêu cầu và tiêu chí
riêng đặt ra.
Để khai thác có hiệu quả nguồn thông tin từ các cơ sở dữ liệu khổng lồ trên,
yêu cầu đặt ra là cần phải có những phương pháp tổ chức, khai thác dữ liệu nhanh,
tự động và chính xác để chuyển đổi kho dữ liệu khổng lồ này thành những tri thức
có ích, có ứng dụng thực tiễn cao. Từ đó các kỹ thuật khai phá dữ liệu (Data
Mining) và kỹ thuật khám phá, phát hiện tri thức (Knowledge Discovery) trở thành
một lĩnh vực được đặc biệt quan tâm trong lĩnh vực công nghệ thông tin.
Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
phát triển trong nhiều lĩnh vực khác nhau như y tế, giáo dục, kinh tế Đây cũng là
lĩnh vực liên quan đến nhiều ngành học như hệ cơ sở dữ liệu, trực quan hoá với
nhiều cách tiếp cận, sử dụng các kỹ thuật khác nhau như mạng nơron, lý thuyết tập
thô, biểu diễn tri thức Nhằm mục đích tìm hiểu, nghiên cứu một phần nào đó của
việc sử dụng kỹ thuật khai phá tri thức, khai phá dữ liệu trong thực tiễn. Tôi mạnh
dạn chọn đề tài “Xây dựng tập thuộc tính rút gọn theo cách tiếp cận tập thô”, từ
đó sử dụng một thuật toán để tìm tập rút gọn phục vụ bài toán: Tra cứu thông tin.
2. Mục tiêu của đề tài
Mục tiêu của đề tài là nghiên cứu lý thuyết tập thô và tập rút gọn, từ đó áp
dụng trong Bài toán: Tra cứu thông tin trên Web.
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
3. Đóng góp của đề tài
Đề tài đã nghiên cứu tập thô ở khía cạnh lý thuyết áp dụng trực tiếp vào bài
những quy luật nằm bên trong dữ liệu, đồng thời cũng không thể căn cứ vào những
phương pháp phân tích truyền thống được nữa. Trong một biển dữ liệu khổng lồ,
làm thế nào để lấy được những thông tin có giá trị, có tri thức, đã trở thành một
nhiệm vụ vô cùng quan trọng, con người mong muốn loại bỏ những dữ liệu thô để
chắt lọc những dữ liệu tinh. Kỹ thuật phát hiện tri thức và khai phá dữ liệu bắt
nguồn từ đây.
Khai phá tri thức trong các cơ sở dữ liệu (KDD-Knowledge Data
Development) là quá trình phát hiện những tri thức tiềm ẩn, không biết trước, và có
ích trong cơ sở dữ liệu. Đây là quá trình tự động rút trích, tìm kiếm các “tri thức” bị
che giấu trong một tập hợp “dữ liệu” rất lớn thông qua các mẫu, mô hình trong khối
dữ liệu. Quá trình khai phá tri thức thường được áp dụng để giải quyết một loạt các
yêu cầu nhằm phục vụ những mục đích nhất định và mang tính chất hướng nhiệm
vụ, không phải là phát hiện mọi tri thức mà phát hiện những tri thức phục vụ tốt một
nhiệm vụ đề ra. Vì vậy, quá trình phát hiện tri thức là một hoạt động tương tác giữa
một người sử dụng hoặc một chuyên gia phân tích với các công cụ tin học. Các
ngôn ngữ thường dùng để biểu diễn tri thức trong quá trình phát hiện tri thức từ các
cơ sở dữ liệu là các khung, các cây và đồ thị, các luật, các công thức logic mệnh
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
đề…Tri thức được rút ra có thể được dùng cho các mục đích cung cấp các hiểu biết
sâu sắc và hữu ích về hành vi của các đối tượng (giải thích dữ liệu) hay dự đoán giá
trị của những đối tượng mới (dự báo).
Phương pháp này thường giúp con người tạo ra các quyết định hoặc giải quyết
hiện tượng quan sát được. Tri thức ở đây có thể được hiểu là một biểu thức trong
một ngôn ngữ nào đó diễn tả một hoặc nhiều mối quan hệ giữa các thuộc tính trong
các dữ liệu đó, hay tri thức chính là các thông tin tích hợp, bao gồm các sự kiện và
các mối quan hệ giữa chúng. Vậy tri thức được xem như là dữ liệu ở mức trừu
- Lựa chọn các phương pháp khai phá dữ liệu.
- Khai phá dữ liệu để rút ra các mẫu, các mô hình.
1.1.2 Khai phá dữ liệu
Khai phá dữ liệu (DM-Data Mining) là một khái niệm ra đời vào cuối những
năm 80 của thế kỷ 20, từ những năm 90 nó bắt đầu khởi phát, cho tới thế kỷ 21, rất
nhiều các khái niệm gần đúng với nó ví dụ KDD (Knowledge Data Development),
phân tích dữ liệu, data fusion, data warehouse…
Trong lúc này, một lĩnh vực nằm trong ngành trí tuệ nhân tạo là học máy đang
không ngừng phát triển. Học máy làm nâng cao tính năng của những chương trình
máy tính, thu nhận được từ nhiều ngành khoa học khác nhau bao gồm: trí tuệ nhân
tạo, xác suất thống kê, tâm lý học, triết học…rồi căn cứ vào những mô hình học
khác nhau để đưa ra phương pháp học, ví dụ: học không giám sát, học có giám sát,
mạng neural và di truyền…
Tóm lại, Data Mining là việc tiến hành xử lý, khai phá từ trong kho dữ liệu
lớn, không hoàn chỉnh, nhiều nhiễu, mơ hồ, để trích rút ra những thông tin có giá
trị, có tri thức.
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
Khai phá dữ liệu là quá trình tìm kiếm, khám phá dưới nhiều góc độ khác nhau
nhằm phát hiện các mối liên hệ, quan hệ giữa các dữ kiện, đối tượng bên trong cơ
sở dữ liệu, kết quả của việc khai phá là xác định các mẫu hay các mô hình tồn tại
bên trong nhưng chúng nằm ẩn ở các cơ sở dữ liệu. Về bản chất, nó là giai đoạn duy
nhất rút trích và tìm ra được các mẫu, các mô hình hay thông tin mới, tri thức tiềm
ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán. Đây là giai đoạn
quan trọng nhất trong quá trình phát hiện ra tri thức từ cơ sở dữ liệu, các tri thức này
hỗ trợ trong việc ra quyết định, điều hành trong khoa học và kinh doanh, nó là quá
trình rất khó khăn, gặp phải nhiều vướng mắc như: quản lý các tệp dữ liệu, phải lặp
thường dùng phương sai của khẳng định để đo lường.
* Mô hình chuỗi thời gian (Time-Series)
Time-series chỉ sự thông qua sự tuần tự của thời gian tìm kiếm những mô hình
phát sinh. Tựa như hồi quy, nó cũng dùng để nhận biết giá trị tương lai của dữ liệu.
* Độ lệch (Deviation)
Trong độ lệch bao gồm rất nhiều tri thức, trong kho dữ liệu, dữ liệu tồn tại
những khác biệt, phát hiện những khác biệt trong kho dữ liệu là rất quan trọng. Độ
lệch giữa kết quả quan sát được, giữa giá trị trả về theo tính toán và kết quả thực
tế.
1.1.2.2 Một số kỹ thuật Khai phá dữ liệu
Các kỹ thuật của DM bao gồm học máy, trí tuệ nhân tạo và thống kê học. Trí
tuệ nhân tạo được áp dụng trong học máy thông qua các giải pháp của trí tuệ nhân
tạo để nâng cao hiệu quả học, giải quyết những vấn đề khoa học và kỹ thuật còn tồn
tại. Dưới đây là một số phương thức mà khai phá dữ liệu thường dùng:
* Mạng neural nhân tạo (Artificial Neural Networks)
Mạng neural là một trong những kỹ thuật được ứng dụng rất phổ biến hiện
nay, nó là cách tiếp cận tính toán mới liên quan đến việc phát triển các cấu trúc toán
học dựa trên nền tảng toán học vững vàng. Các phương pháp là kết quả của việc
nghiên cứu mô hình của hệ thống thần kinh con người. Mạng neural có thể đưa ra ý
nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể sử dụng để truy xuất
các mẫu và phát hiện ra các xu hướng quá phức tạp mà con người cũng như các kỹ
thuật máy tính khác không thể phát hiện được.
Mạng neural mô tả kết cấu của bộ não người. Cơ sở của nó là mô hình MP và
phương pháp học Hebb. Nó có 3 mô hình mạng thần kinh chính:
(1). Mạng lan truyền tiến (mô hình học không giám sát).
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
Giải thuật di truyền thường dùng để sản sinh ra cá thể tốt hơn ở đời sau nhằm
thỏa mãn một giá trị nào đó, thông qua quá trình di truyền, lai ghép, biến dị. Giải
thuật này thường dùng trong tính toán và phân loại học máy.
* Tập mờ (Fuzzy Set)
Lý thuyết tập mờ là một phương pháp tiện lợi trong việc xử lý và biểu diễn các
dạng dữ liệu không xác định. Tập mờ không chỉ sử dụng trong việc biểu diễn và xử
lý các dạng dữ liệu không toàn vẹn, không xác định mà còn sử dụng rất tốt trong
việc xử lý và phát triển các dạng cấu trúc mô hình dữ liệu không xác định, nó có
tính năng linh hoạt hơn nhiều so với những phương pháp truyền thống.
* Hệ thống miễn dịch nhân tạo(Artificial Immune System)
Hệ thống miễn dịch nhân tạo mô phỏng hệ thống miễn dịch sinh vật. Trong nó
bao gồm mạng neural, thuật giải di truyền, hệ thống tổ kiến,…Nó được coi như một
mô hình tiến hóa cấp cao, có khả năng kháng trừ các tác nhân khác và bảo trì sự ổn
định. Các khái niệm liên quan tới AIS:miễn dịch (Immunity), kháng thể (Antibody),
kháng nguyên (Antigen), Self and Non-Self, tế bào miễn dịch, tế bào B, tế bào T…
* Cây quyết định (Decision Trees)
Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân đối tượng dữ
liệu thành một số lớp nhất định, hoặc các giá trị của các đối tượng dữ liệu chưa
được biết sẽ được dự đoán, dự báo, là phương pháp dùng trong bài toán phân đoạn
dữ liệu theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính.
Trong khai phá dữ liệu, kỹ thuật này là một công cụ mạnh và hiệu quả trong việc
phân lớp và dự báo. Tri thức được rút ra trong kỹ thuật này thường được mô tả dưới
dạng tường minh, đơn giản, trực quan dễ hiểu đối với người sử dụng. Tuy nhiên, nó
đòi hỏi một không gian nhất định, để mô tả tri thức trong một phạm vi mà con
người có thể hiểu được.
Cây quyết định là sử dụng những thông tin lập luận để tìm kiếm những đặc
trưng trong lượng thông tin lớn để tạo thành các điểm. Trên thực tế, người ta thường
* Tập thô (Rough Set)
Thông qua những tri thức đã hiểu để tiến hành phân hoạch, mỗi một phân
hoạch là một tập được gọi là khái niệm, tư tưởng chủ yếu là lợi dụng kho tri thức đã
biết, để áp dụng vào trong một kho tri thức chưa toàn vẹn, chưa xác định để tiến
hành phân hoạch và xử lý.
Lý thuyết tập thô lần đầu tiên được đề xuất bởi Z.Pawiak và nhanh chóng
được xem như là công cụ xử lý các thông tin mơ hồ và không chắc chắn. Phương
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
18
pháp này đóng vai trò hết sức quan trọng trong trí tuệ nhân tạo và các ngành khoa
học khác liên quan đến nhận thức, đặc biệt là lĩnh vực máy học, thu nhận tri thức,
phân tích quyết định, phát hiện và khám phá tri thức từ cơ sở dữ liệu, các hệ chuyên
gia, hệ hỗ trợ quyết định, lập luận dựa trên quy nạp và nhận dạng.
Lý thuyết tập thô dựa trên giả thiết rằng để định nghĩa một tập hợp chúng ta
cần phải có thông tin về mọi đối tượng trong tập vũ trụ. Ví dụ, nếu các đối tượng là
các bệnh nhân bị một bệnh nhất định thì các triệu chứng của bệnh tạo thành thông
tin của bệnh nhân. Như vậy, tập thô có quan điểm hoàn toàn khác với quan điểm
truyền thống của tập hợp, trong đó mọi tập hợp đều được định nghĩa duy nhất bởi
các phần tử của nó mà không cần biết bất kỳ thông tin nào của các phần tử thuộc tập
hợp. Rõ ràng có thể tồn tại một số đối tượng giống nhau ở một số thông tin nào đó,
và ta nói rằng chúng có quan hệ không phân biệt được. Đây chính là quan hệ mấu
chốt và chính là điểm xuất phát của lý thuyết tập thô: biên giới của tập thô là không
rõ ràng, chúng ta phải xấp xỉ nó bằng các tập hợp khác, nhằm mục đích cuối cùng là
trả lời được rằng một đối tượng nào đó thuộc tập hợp hay không. Lý thuyết tập thô
với cách tiếp cận như vậy đã được ứng dụng rất rộng rãi.
1.2 Lý thuyết tập thô
1.2.1 Giới thiệu về tập thô
- X
U được gọi là tập thô trong K nếu X là tập thô trên với mọi R
IND(K).
* Lý thuyết tập Thô:
Lý thuyết tập thô được đề xuất và giới thiệu bởi giáo sư Zdzislaw PawLak vào
những năm 80 của thế kỷ XX và nhanh chóng được xem như là công cụ xử lý các
thông tin mơ hồ và không chắc chắn, nó là một trong những phương pháp đang
được nhiều nhà khoa học nghiên cứu và sử dụng trong quá trình khai phá tri thức từ
dữ liệu.
Phương pháp này đóng vai trò hết sức quan trọng trong trí tuệ nhân tạo và các
ngành khoa học khác liên quan đến nhận thức, đặc biệt là lĩnh vực máy học, thu
nhận tri thức, phân tích quyết định, phát hiện và khám phá tri thức từ cơ sở dữ liệu,
các hệ chuyên gia, hệ hỗ trợ quyết định, lập luận dựa trên quy nạp và nhận dạng. Hệ
thống thông tin được đưa ra bởi PawLak đại diện cho tri thức và quan hệ của dữ
liệu.
Lý thuyết tập thô được sử dụng trong nhiều giai đoạn khác nhau của tiến trình
xử lý thông tin như:
- Tổ chức bảng quyết định đại diện cho hệ thống thông tin.
- Tính toán xấp xỉ trên và xấp xỉ dưới của tập hợp.
- Phân tích tri thức.
- Tính toán mức độ quan trọng của một thuộc tính.
- Tìm thuật toán quyết định từ tập luật sinh.
- Xác định và ước lượng sự phụ thuộc của tập thuộc tính.
- Tính định tập tối thiểu các thuộc tính từ rút gọn.
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
là tập hữu hạn các đối tượng (
U
) được gọi là tập vũ trụ.
Trong nhiều ứng dụng thực tế, tập vũ trụ được phân chia thành các tập đối
tượng con bởi một tập các thuộc tính phân biệt được gọi là tập thuộc tính quyết
định. Hay nói cách khác, tập vũ trụ đã được phân lớp bởi thuộc tính quyết định. Hệ
thống thông tin chứa sự phân lớp này gọi là bảng quyết định.
Định nghĩa bảng quyết định:
Một cách tổng quát, bảng quyết định là một hệ thống thông tin bất kỳ có dạng:
),,( dCUT
, với
Td
là thuộc tính quyết định.
Các thuộc tính thuộc
C
được gọi là thuộc tính điều kiện.
Giả sử có
dCUT ,,
và
drd
vvvV , ,,
21
.
Thuộc tính quyết định
),,( DCUT
, trong đó tập
k
dddD , ,,
21
là tập các thuộc tính quyết định và
DC
.
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
21
Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại
các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính
quyết định.
Bảng quyết định được gọi là xác định nếu như mọi giá trị của tập thuộc tính
quyết định được xác định duy nhất bởi các thuộc tính điều kiện.
Bảng quyết định gọi là không xác định nếu như cùng một tập thuộc tính điều
kiện cho trước, thuộc tính quyết định có nhiều giá trị. Thuộc tính điều kiện có thể có
nhiều hơn hai giá trị, tuy nhiên thông dụng là kiểu giá trị nhị phân.
Bảng quyết định được gọi là nhất quán nếu
D
phụ thuộc vào hàm
C
, tức là
với mọi
C
trong
T
. Một thuộc tính là cần thiết khi và chỉ khi nó thuộc vào mọi tập
rút gọn của
C
. Core (nghĩa tiếng Anh là lõi) được mô tả như là một tập các thuộc
tính rút gọn nhất trong bảng thuộc tính. Điều đó được thể hiện trong mệnh đề về
sau:
Mệnh đề 1.1.
CredR
RCCore
Ví dụ: Xét một hệ thống thông tin
A
về bệnh cúm cho ở Bảng 1.1. Bảng này
có hai tập rút gọn là
1
R
{Đau cơ, Thân nhiệt} (thể hiện ở Bảng 1.2)
Và
2
R
Đau đầu
Đau cơ
Thân nhiệt
Cảm cúm
1
u
Có
Có
Bình thường
Không
2
u
Có
Có
Cao
Có
3
u
Có
Có
Rất cao
Có
4
u
Không
Có
Có
Bình thường
Không
2
u
Có
Cao
Có
3
u
,
6
u
Có
Rất cao
Có
5
u
Không
Cao
Không
Bảng 1.2 Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R
1
)
Đối tƣợng
Thuộc tính
5
u
Không
Cao
Không
6
u
Không
Rất cao
Có
Bảng 1.3 Bảng rút gọn thứ hai của hệ thống bệnh cúm (R
2
)
1.3 Kết luận chƣơng 1
Nội dung của chương 1 tập trung giới thiệu và tìm hiểu về khía cạnh phát
hiện tri thức (KDD-Knowledge Data Development) nói chung và một trong các
bước quan trọng của tiến trình này đó là khai phá dữ liệu (DM-Data Mining). Đồng
thời đề cập tới một kỹ thuật nhằm khai phá dữ liệu, đó là kỹ thuật sử dụng lý thuyết
tập thô.
Kỹ thuật phát hiện tri thức và khai phá dữ liệu nhằm phát hiện những tri thức
tiềm ẩn, không biết trước, và có ích trong cơ sở dữ liệu. Đây là quá trình tự động rút
XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
23
trích, tìm kiếm các “tri thức” bị che giấu trong một tập hợp “dữ liệu” rất lớn thông
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
24
CHƢƠNG 2. XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN
THEO CÁCH TIẾP CẬN TẬP THÔ
Trong chương này luận văn sẽ trình bày các phương pháp sử dụng lý thuyết
tập Thô để xây dựng một số thuật toán cơ bản để xây dựng tập rút gọn như Thuật
toán sử dụng các phép toán đại số; Thuật toán dựa vào cặp số phân biệt được; Thuật
toán xây dựng tập thuộc tính rút gọn….
Một định nghĩa luôn được sử dụng trong chương này là định nghĩa về bảng
quyết định đã được phát biểu trong chương 1.
2.1 Luật và quá trình khám phá Luật trong Bảng quyết định.
2.1.1 Định nghĩa về luật và các đặc trƣng.
Xét một bảng quyết định
),,( dCUT
X
biểu thị sự kết hợp giữa các từ nhận dạng (Descriptors) bao hàm trong các
thuộc tính điều kiện
C
;
Y
biểu thị một từ nhận dạng
vd
trong đó
v
là một giá trị bất kỳ nào đó của
thuộc tính quyết định
được tính như
sau:
k
PG
krelins
ll
l
bkk
N
PGN
PGPIpPGsXS
\
Với
krelins
PGN
là số các đối tượng quan sát thỏa mãn trong lần thứ
i
.
Copyright: Tài liệu đại học ©