ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

Đinh Quang Thắng

MỘT SỐ ỨNG DỤNG
CỦA HẠT DỮ LIỆU

LUẬN VĂN THẠC SĨ

Hà Nội – 2005
-1-


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

Đinh Quang Thắng

MỘT SỐ ỨNG DỤNG
CỦA HẠT DỮ LIỆU

Ngành :
Công nghệ thông tin
Chuyên ngành:
Mã số: 1.01.1

LUẬN VĂN THẠC SĨ
NGƢỜI HƢỚNG DẪN KHOA HỌC:
PGS.TS HOÀNG CHÍ THÀNH


2.2.2.4 Các hàm thuộc thô .................................... Error! Bookmark not defined.
2.2.2.5 Một số tính chất của các xấp xỉ ................ Error! Bookmark not defined.
2.2.2.6 Sự phân lớp thô ......................................... Error! Bookmark not defined.
2.3. Mô hình lý thuyết quyết định sử dụng tập thô........ Error! Bookmark not defined.
2.3.1 Khái quát về thủ tục quyết định Bayes ............ Error! Bookmark not defined.
-3-


2.3.2 Mô hình lý thuyết quyết định sử dụng tập thô . Error! Bookmark not defined.
2.4 Kết luận.................................................................... Error! Bookmark not defined.
CHƢƠNG 3: KHAI PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU SỬ DỤNG CÁC
TẬP THÔ ...................................................................... Error! Bookmark not defined.
3.1 Tổng quan về khai phá tri thức ................................ Error! Bookmark not defined.
3.1.1 Giới thiệu.......................................................... Error! Bookmark not defined.
3.1.2 Khai phá tri thức và khai phá dữ liệu ............... Error! Bookmark not defined.
3.1.2.1 Quá trình KDD.......................................... Error! Bookmark not defined.
3.1.2.2 Khai phá dữ liệu ........................................ Error! Bookmark not defined.
3.2 Các tập thô và khai phá tri thức trong cơ sở dữ liệu Error! Bookmark not defined.
3.2.1 Làm sạch dữ liệu và tiền xử lý ......................... Error! Bookmark not defined.
3.2.1.1 Rút gọn dữ liệu ......................................... Error! Bookmark not defined.
3.2.1.2 Quản lý giá trị không đúng ....................... Error! Bookmark not defined.
3.2.1.3 Lựa chọn và trích chọn đặc trƣng ............. Error! Bookmark not defined.
3.2.2 Khai phá dữ liệu ............................................... Error! Bookmark not defined.
3.3 Khai phá luật kết hợp............................................... Error! Bookmark not defined.
3.3.1 Các luật kết hợp................................................ Error! Bookmark not defined.
3.3.2 Thuật giải tuần tự Apriori ................................ Error! Bookmark not defined.
3.3.3 Các thuật giải song song và phân tán ............... Error! Bookmark not defined.
3.3.3.1 Các kỹ thuật khai phá dữ liệu phân tán ..... Error! Bookmark not defined.
3.3.3.1.1 Kỹ thuật sinh các tập ứng cử ............. Error! Bookmark not defined.
3.3.3.1.2 Phép tỉa cục bộ các tập ứng cử .......... Error! Bookmark not defined.

CÁC KẾT QUẢ ĐÃ ĐƢỢC BÁO CÁO TẠI CÁC HỘI THẢO QUỐC GIA .... Error!
Bookmark not defined.
TÀI LIỆU THAM KHẢO ............................................................................................. 11

-5-


MỞ ĐẦU
Trong những năm gần đây, tính toán hạt đã đƣợc áp dụng trong rất nhiều lĩnh vực
nhƣ trí tuệ nhân tạo, phân tích khoảng, lƣợng tử hoá, lý thuyết tập thô, phân tích cụm,
học máy, cơ sở dữ liệu và một số lĩnh vực khác. Cho đến nay, tính toán hạt đã có sự
phát triển nhanh chóng và ngày càng có nhiều ngƣời tập trung nghiên cứu các ứng
dụng của nó.
Tính toán hạt là một thuật ngữ chỉ các lý thuyết, các phƣơng pháp, các kỹ thuật và
các công cụ sử dụng các hạt (là các nhóm, các lớp, hoặc các cụm của một tập) để giải
quyết các bài toán. Đề tài các hạt thông tin mờ đƣợc Zadeh đề xuất đầu tiên vào năm
1979 và đƣợc ông tiếp tục phát triển trong các bài báo công bố năm 1997. Đặc biệt,
Zadeh đã trình bày một mô hình tổng quát của tính toán hạt dựa trên lý thuyết tập mờ.
Các hạt đƣợc xây dựng và định nghĩa dựa trên các phép toán suy rộng. Mối quan hệ
giữa các hạt đƣợc biểu diễn bằng đồ thị mờ hoặc các luật nếu-thì mờ. Mặc dù các công
thức là khác với những nghiên cứu trong trí tuệ nhân tạo, nhƣng những ý tƣởng cơ bản
của chúng là giống nhau. Zadeh xác định ba khái niệm cơ bản của tính toán hạt theo
cách nhận thức của con ngƣời, cụ thể là phƣơng pháp kết hạt, phƣơng pháp tổ chức các
hạt và phƣơng pháp lập luận với các hạt. Sau đó lý thuyết về tính toán với các hạt
thông tin mờ đã đƣợc nghiên cứu bằng cách kết các hạt thông tin và lập luận với
chúng.
Sự cần thiết của việc kết hạt thông tin và tính dễ nhận đƣợc thông tin từ các hạt
thông tin trong giải quyết bài toán là một trong các lý do thực tế cho tính phổ biến của
tính toán hạt. Trong rất nhiều tình huống, khi một bài toán là không đầy đủ, không
chắc chắn hoặc thông tin không rõ ràng sẽ rất khó để phân biệt các phần tử một cách

trên một cách hiệu quả. Một phƣơng pháp thƣờng hay đƣợc sử dụng để giải quyết bài
toán quyết định trên là sử dụng thủ tục quyết định của Bayes. Luận văn trình bày tóm
tắt thủ tục quyết định Bayes này và xây dựng một mô hình lý thuyết quyết định sử
dụng các hạt dữ liệu dựa trên lý thuyết các tập thô.
Chƣơng 3: Khai phá tri thức trong cơ sở dữ liệu sử dụng tập thô: Với các hạt là
các xấp xỉ thô, luận văn nghiên cứu bài toán khai phá các luật kết hợp trong cơ sở dữ
liệu quan hệ. Thuật giải tuần tự Apriori đƣợc trình bày. Sau đó, luận văn trình bày tới
những ý tƣởng song song hoá của thuật giải này. Tốc độ của thuật giải sẽ tăng đáng kể
khi thực hiện các thuật giải song song với dữ liệu đƣợc tổ chức trong môi trƣờng dữ
liệu phân tán.
Chƣơng 4: Chƣơng trình thử nghiệm: Luận văn trình bày một cấu trúc dữ liệu
mới, cấu trúc dữ liệu T-tree. Cấu trúc này là phù hợp để cài đặt thuật giải Apriori vì nó
cho phép tìm kiếm các tập mục nhanh và tiết kiệm không gian lƣu trữ dữ liệu. Thuật
giải Apriori đƣợc cài đặt sử dụng cấu trúc dữ liệu này bằng ngôn ngữ lập trình Java.
Luận văn đƣợc thực hiện dƣới sự hƣớng dẫn của PGS.TS Hoàng Chí Thành, Bộ
môn Tin học, Khoa Toán-Cơ-Tin học trƣờng Đại học Khoa học Tự nhiên, Đại học
Quốc Gia Hà Nội. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hƣớng dẫn và có ý
kiến chỉ dẫn quí báu trong quá trình em làm luận văn. Em xin chân thành cảm ơn Thầy
giáo, TS Hà Quang Thuỵ đã cho em nhiều ý kiến quí báu để em hoàn thiện luận văn
hơn. Em xin cảm ơn các Thầy Cô giáo trong Bộ môn Tin học, các đồng nghiệp trong
Khoa Toán-Cơ-Tin học, Trƣờng Đại học Khoa học Tự nhiên, các Thầy Cô giáo Khoa
Công Nghệ Thông tin, Trƣờng Đại học Công nghệ, Đại học Quốc Gia Hà Nội đã tạo
điều kiện giúp đỡ em trong quá trình hoàn thành luận văn. Cuối cùng xin bày tỏ lòng

-7-


cảm ơn tới những ngƣời thân trong gia đình, bạn bè đã động viên và giúp đỡ tôi hoàn
thành luận văn này.


của phƣơng pháp kết hạt thông tin mờ trong logic mờ nhƣng mang nó tới một mức cao
hơn của tính tổng quát, thống nhất các nghiên cứu của nó và đề xuất các hƣớng nghiên
cứu mới” [3] (Zadeh, 1997).
“Tính toán hạt là một khái niệm của lý thuyết về phƣơng pháp kết hạt thông tin mờ,
lý thuyết tập thô và tính toán khoảng và là một phần trong toán học tính toán với các
hạt” [3] (Zadeh, 1997).
Có thể thấy rằng ý tƣởng chung nhất của tính toán hạt là sử dụng các nhóm, các lớp
hoặc cụm các phần tử đƣợc gọi là các hạt [3, 7]. Mặc dù đã có những ứng dụng cụ thể
sử dụng tính toán hạt, vẫn khó có thể đƣa ra một định nghĩa chính xác. Chúng ta có thể
-9-


coi tính toán hạt là một thuật ngữ chỉ các lý thuyết, các phƣơng pháp, các kỹ thuật và
các công cụ sử dụng các hạt trong quá trình giải bài toán. Dựa trên cách hiểu trực giác
trên, chúng ta sẽ xem xét một số vấn đề cơ bản và một số giải pháp có thể của nó.

1.2 Tại sao chúng ta nghiên cứu tính toán hạt
Có rất nhiều lý do để nghiên cứu tính toán hạt. Zadeh đã xác định ba vấn đề cơ bản
của tính toán hạt: phƣơng pháp kết hạt, tổ chức các hạt và lập luận với các hạt.
“Phƣơng pháp kết hạt bao gồm việc phân chia một tập tổng thể thành các phần, tổ
chức các hạt bao gồm việc tích hợp các phần trong một tập tổng thể và lập luận với các
hạt thực hiện việc sử dụng các mối quan hệ giữa các hạt để đi từ các điều kiện ban đầu
tới các kết quả mong muốn” [3]. Trong việc giải quyết bài toán, sử dụng các hạt thông
tin thƣờng đơn giản hơn sử dụng các thông tin chi tiết có lẽ là những lý do chính để
phát triển tính toán hạt. Khi một bài toán có độ không chắc chắn, tính không đầy đủ
hoặc thông tin không rõ ràng, có thể rất khó để phân biệt sự khác nhau giữa các phần
tử và hƣớng chúng ta tới nghiên cứu các hạt. Một ví dụ điển hình là lý thuyết các tập
thô [3, 7]. Tình trạng thiếu thông tin chỉ cho phép chúng ta xác định đƣợc các hạt thay
cho việc xác định các phần tử cụ thể. Trong một số tình huống, mặc dù các thông tin
chi tiết có thể có đƣợc, nhƣng sử dụng các hạt sẽ mang lại tính hiệu quả và các lời giải

[Lin, 1999b] Lin, T.Y. (1999b). Granular computing: Fuzzy logic and rough sets.
In Zadeh, L. and Kacprzyk, J., editors, Computing with Words in
Information/Intelligent Systems, pages 183–200. Physica-Verlag.

[3]

[Lin 2003] T. Y. Lin, "Granular Computing: Structures, Representations,
Applications and Future Directions." In: the Proceedings of 9th International
Conference, RSFDGrC 2003, Chongqing, China,May 2003, Lecture Notes on
Artificial Intelligence LNAI 2639, Springer-Verlag, 16-24.

[4]

[Zadeh, 1997] Zadeh, L.A. (1997). Towards a theory of fuzzy information
granulation and its centrality in human reasoning and fuzzy logic. Fuzzy Sets and
Systems, 19:111–127.

[5]

Lin, T.Y.: Granular computing. Rough Sets, Fuzzy Sets, Data Mining, and
Granular Computing, Proceedings of the 9th International Conference, Lecture
Notes in Artificial Intelligence 2639 (2003) 16-24.

[6]

Yao, Y.Y.: Granular computing: basic issues and possible solutions. Proceedings
of the 5th Joint Conference on Information Sciences (2000) 186-189
Yao, Y.Y.: Information granulation and rough set approximation. International
Journal of Intelligent Systems 16 (2001) 87-104
[Wang 2004] Wang,D.W.,Liau, C.J.,Hsu, T.-S. (2004), Medical privacy

mining, chapter 1, pages 136. MIT Press, Cambridge, MA, 1996.
[17] Sankar K. Pal, Pabitra Mitra. Data Mining in Soft Computing Framework: A
Survey, IEEE, 2003.
[18] Y. Q. Zhang, M. D. Fraser, R. A. Gagliano, and A. Kandel, \Granular neural
networks for numerical-linguistic data fusion and knowldege discovery," IEEE
Transactions on Neural Net-works, vol. 11, pp. 658{667, 2000.
[19] Tomasz Strkowski,Henryk Rybiski. A Distributed Version of Apriori Rule,
Generation Based on Rough Set Theory, Institute of Computer Science Warsaw
University of Technology, Warsaw.
[20] Agrawal R., Srikant R.: Fast Algorithms for Mining Association Rules in Large
Databases. VLDB 1994, 487-499.
[21] Jan G.Bazan, Hung Son Nguyen, Sinh Hoa Nguyen, Piotr Synak, Jakub
Wroblewski. Rought algorithms in Classification problem, 1998.
[22] Agrawal, R. Mannila, H. Srikant, R. Toivonen, H. Verkamo: Fast Discovery of
Association Rules, Proceedings of the Advances in Knowlwdge Discovery and
Data Mining, AAAT Press/The MIT Press, CA (1996), pp 307-328.
[23] Rakesh Agrawal, John C.Shafer. Parallel Mining of Association Rules, IBM
Almaden Research Center, CA 95120.
[24] J.Han and Y.Fu: Discovery of multiple-level association rules from large

[25]
[26]
[27]
[28]

databases. In Proc of 21st Int’s Conference on Very Large Databases, Zurich,
Switzerland, September 1995.
Andrew Kusiak. Rough Set Theory: A Data Mining Tool for Semiconductor
Manufacturing, IEEE, 2001.
[Wan] Guoyin Wang. Extension of rough set under incomplete information