Tải miễn phí luận văn thạc sỹ
MỤC LỤC
Trang
LỜI CẢM ƠN . i
LỜI CAM ĐOAN ii
BẢNG CÁC KÍ HIỆU VIẾT TẮT vi
DANH SÁCH CÁC BẢNG . vii
DANH SÁCH CÁC HÌNH VẼ . viii
MỞ ĐẦU . 1
CHưƠNG 1.CƠ SỞ LÝ THUYẾT 3
1.1. Khám phá tri thức 3
1.1.1.Khái niệm 3
1.1.2. Các bước chính trong quá trình khám phá tri thức 3
1.1.3. Khai phá dữ liệu 5
1.2. Luật kết hợp 7
1.2.1. Một số khái niệm 7
1.1.2. Luật kết hợp 8
1.3. Bài toán tìm luật kết hợp 9
Hai giai đọan cơ bản của thuật toán khai phá luật kết hợp 10
1.4. Một số thuật toán tìm tập mục phổ biến 10
1.4.1. Thuật toán Apriori 10
1.4.2. Thuật toán FP_Growth 15
1.4.3. Nhận xét về các thuật toán 20
1.4.4. Thuật toán sinh luật kết hợp 21
1.5. Lý thuyết tập thô. 23
1.5.1. Hệ thống thông tin 23
1.5.2. Bảng quyết định 24
1.5.3. Xấp xỉ trên và xấp xỉ dưới 25
iv
1.5.4. Miền khẳng định 26
1.5.5. Thuộc tính cần thiết và không cần thiết 27
1.5.6. Rút gọn và lõi 27
1.6. Kết luận chương 1 29
CHưƠNG 2.CÁC PHưƠNG PHÁP ĐÁNH GIÁ LUẬT 31
2.1. Độ đo hữu ích của luật 32
2.1.1. Độ đo Lift 33
2.1.2. Độ đo Cosine 35
2.1.3. Nhận xét 36
2.2. Độ đo quan trọng của luật (RIM) 36
2.2.1.Định nghĩa 36
2.2.2. Ví dụ 38
2.2.3. Nhận xét 45
2.3. Độ đo quan trọng cải tiến (ERIM) 45
2.3.1. Phân cấp 46
2.3.2. Đánh giá độ quan trọng của luật dựa vào khái niệm phân cấp 47
2.3.3. Quá trình thực hiện 48
2.3.4. Các trường hợp đánh giá 49
2.3.5. Nhận xét 58
2.4. Kết luận chương 2 58
CHưƠNG 3.ỨNG DỤNG KIỂM CHỨNG . 60
3.1. Mô tả bài toán 60
3.2. Mô tả dữ liệu 60
3.3. Các bước thực hiện 62
3.3.1. Cài đặt ứng dụng 63
3.3.2. Luật mẫu 64
3.3.3. Tập luật được tạo ra 64
v
3.3.4. Tính độ đo RIM 645
3.3.5. Tính độ đo ERIM 66
3.4. Đánh giá 67
3.5. Ứng dụng luật 67
3.6. Kết luận chương 3 68
KẾT LUẬN VÀ HưỚNG PHÁT TRIỂN 69
Kết luận 69
Hướng phát triển 69
MỞ ĐẦU
Lý do chọn đề tài
Với sự phát triển vượt bật của công nghệ thông tin, các hệ quản trị cơ sở dữ
liệu có thể lưu trữ dữ liệu về hoạt động hàng ngày dễ dàng, dẫn đến việc hình thành
một khối lượng dữ liệu khổng lồ, đòi hỏi chúng ta, là những người sử dụng phải biết
khai thác, chọn lọc dữ liệu có ích cho mình. Các tri thức vừa học được có thể vận
dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu. Các phương
pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng
được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới là Khai phá dữ liệu
(Data Mining).
Khai phá dữ liệu đã được ứng dụng rất nhiều trong thực tế, nhất là trong lĩnh
vực tài chính và thị trường chứng khoán, thương mại, ý tế, sinh học, bưu chính viễn
thôn, nông nghiệp Một trong những chức năng được đề cập nhiều trong khai phá
dữ liệu là khám phá sự kết hợp giữa các mẫu trong dữ liệu hay còn gọi là luật kết
hợp. Số lượng luật kết hợp cũng tăng theo kích thước cơ sở dữ liệu, vì vậy, nhiều lý
thuyết được đưa ra để đánh giá độ quan trọng của luật. Trên cơ sở đó lựa chọn các
luật phù hợp cho ứng dụng. Đây là một hướng nghiên cứu mới và có ý nghĩa.
Mục tiêu
Luận văn tập trung nghiên cứu các phương pháp đánh giá độ quan trọng của
luật được sinh từ tập cơ sở dữ liệu, trên cơ sở luật kết hợp và lý thuyết tập thô.
Việc đánh giá độ quan trọng của luật nhằm hỗ trợ ra quyết định đối với một tổ
chức, doanh nghiệp, giúp cho quá trình phân tích từ tập dữ liệu được tốt hơn.
Bên cạnh đó, việc mô phỏng ứng dụng cũng được đặt ra để minh họa cho việc đánh
giá này.
Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu là các thuật toán khai phá luật kết hợp. Đồng thời
nghiên cứu hai phương pháp đánh giá độ quan trọng của luật là RIM và ERIM.
2
Phương pháp nghiên cứu
Nghiên cứu lý thuyết, phân tích, tổng hợp, mô phỏng, khái quát rút ra những
vấn đề cần thiết cho đề tài.
Ý nghĩa khoa học và thực tiễn đề tài
Khai phá dữ liệu là sự khám phá hiệu quả những tri thức từ cơ sở dữ liệu lớn,
và nó trở thành một vấn đề nóng cho việc đưa ra các quyết định.
Kỹ thuật khai phá luật kết hợp tuy hiệu quả nhưng cũng gặp một số bất lợi đối
với việc khai phá các dữ liệu lớn. Số luật tăng tỉ lệ thuận với cơ sơ dữ liệu càng làm
cho việc tìm kiếm tri thức trở nên khó khăn hơn.
Kết hợp với lý thuyết tập thô trong việc đánh giá độ quan trọng của các luật
sinh ra phần nào đã giải quyết được vấn đề sinh quá nhiều luật. Theo kỹ thuật này
các luật được đánh giá với các độ quan trọng khác nhau là độ quan trọng chủ quan
và độ quan trọng khách quan. Sự kết hợp này giúp cho các chuyên gia có cái nhìn
trực quan hơn trong việc vận dụng các luật thu được áp dụng vào thực tế.
Cấu trúc luận văn
Với mục tiêu đó, luận văn được chia làm ba chương
Chương 1: Cơ sở lý thuyết
Trong chương này trình bày tổng quan về khai phá dữ liệu,luật kết hợp và lý
thuyết tập thô.
Chương 2: Các phương pháp đánh giá luật
Chương này tập trung nghiên cứu các phương pháp đánh giá độ hữu ích của
luật, phương pháp RIM,ERIM.
Chương 3: Ứng dụng kiểm chứng
Chương này tập trung mô phỏng với dữ liệu kết quả học tập của bậc TCCN
ngành kế toán doanh nghiệp tại Trường Cao đẳng Công nghệ Thủ Đức.
TÀI LIỆU THAM KHẢO
[1] A. Mitnitski, X. Song, and K. Rockwood (2004), “The estimation of relative
fitness and frailty in communit y-dwelling older adults using self-report data”, J
Gerontol A Biol Sci Med Sci, pp. 627–632.
[2] Ho Tu Bao(1998), Introduction to Knowledge Discovery and Data Mining,
National Center for Natural Science and Technology.
[3] J. Li and N. Cercone(2006). “Introducing a rule importance measure”. In
J. F. Peters, A. Skowron, D. Dubois, J. W. Grzymala-Busse, M. Inuiguchi,
and L. Polkowski, editors, T. Rough Sets, volume 4100 of Lecture Notes in
Computer Science, pages 167–189. Springer.
[4] J. Li(2007). Rough Set Based Rule Evaluations and Their Applications.
PhD thesis,University of Waterloo, Waterloo, Canada.
[5] Jan Komorowski, Lech Polkowski, Andrzej Skowron (2000). Rough sets: A
tutorial.
[6] Jiye Li, Nick Cercone(2005). “Discovering and Ranking Important
Rules”. Granular Computing, IEEE International Conference on Volume 2.
[7] Jiye Li, Nick Cercone, W. H . Wong, Lisa Jing Yan(2009). “Enhancing Rule
Importance Measure Using Concept Hierarchy”. Faculty of Computer
Science and Engineering, York University.
[8] L. Geng and H. J. Hamilton(2006). “Interestingness measures for data
mining: A survey”. ACM Comput. Surv., 38(3):9.
[9] M. E. M. D. Beneditto and L. N. de Barros (2004), “Using concept
hierarchies in knowledge discovery”, volume 3171 of Lecture Notes in
Computer Science, pp. 255–265.
[10] Øhrn(1999). Discernibility and Rough Sets in Medicine: Tools and
Applications. PhD thesis, Department of Computer and Information
Science, Norwegian University of Science and Technology, Trondheim
Norway.
[11] Øhrn, Aleksander(2001): ROSETTA Technical Reference Manual.
Department of Com- puter and Information Science, Norwegian University
of Science and Technology, Trondheim, Norway. May 25
[12] P.Tan, V.Kumar, J.Sivastava(2002). “Selecting the Right Interestingness
Measure for Association Patterns”, in SIGKDD’02 ACM.
[13] R. Agrawal and R. Srikant (1994). “Fast algorithms for mining association
rules”. The International Conference on Very Large Databases, pages 487–
499.
[14] Rakesh Agrawal, Tomasz Imielinski, and Arun Swami (1993), “Mining
association rules between sets of items in large database”, In proc of the ACM
SIGMOD Conference on Management of Data, Washington, D.C.
[15] Y. Chen, G.-R. Xue, and Y. Yu (2008), “Advertising keyword suggestion
based on concept hierarchy”. InWSDM ’08: Proceedings of the international
conference on Web search and web data mining, pp. 251–260.
[16] Z. Pawlak(1991). “Rough Sets – Theoretical Aspects of Reasoning about
Data”. Kluwer Academic Publishers, Dordrecht.
[17]
[18]
Link download cho anh em ketnooi
Nhớ thank mình nhé
MỤC LỤC
Trang
LỜI CẢM ƠN . i
LỜI CAM ĐOAN ii
BẢNG CÁC KÍ HIỆU VIẾT TẮT vi
DANH SÁCH CÁC BẢNG . vii
DANH SÁCH CÁC HÌNH VẼ . viii
MỞ ĐẦU . 1
CHưƠNG 1.CƠ SỞ LÝ THUYẾT 3
1.1. Khám phá tri thức 3
1.1.1.Khái niệm 3
1.1.2. Các bước chính trong quá trình khám phá tri thức 3
1.1.3. Khai phá dữ liệu 5
1.2. Luật kết hợp 7
1.2.1. Một số khái niệm 7
1.1.2. Luật kết hợp 8
1.3. Bài toán tìm luật kết hợp 9
Hai giai đọan cơ bản của thuật toán khai phá luật kết hợp 10
1.4. Một số thuật toán tìm tập mục phổ biến 10
1.4.1. Thuật toán Apriori 10
1.4.2. Thuật toán FP_Growth 15
1.4.3. Nhận xét về các thuật toán 20
1.4.4. Thuật toán sinh luật kết hợp 21
1.5. Lý thuyết tập thô. 23
1.5.1. Hệ thống thông tin 23
1.5.2. Bảng quyết định 24
1.5.3. Xấp xỉ trên và xấp xỉ dưới 25
iv
1.5.4. Miền khẳng định 26
1.5.5. Thuộc tính cần thiết và không cần thiết 27
1.5.6. Rút gọn và lõi 27
1.6. Kết luận chương 1 29
CHưƠNG 2.CÁC PHưƠNG PHÁP ĐÁNH GIÁ LUẬT 31
2.1. Độ đo hữu ích của luật 32
2.1.1. Độ đo Lift 33
2.1.2. Độ đo Cosine 35
2.1.3. Nhận xét 36
2.2. Độ đo quan trọng của luật (RIM) 36
2.2.1.Định nghĩa 36
2.2.2. Ví dụ 38
2.2.3. Nhận xét 45
2.3. Độ đo quan trọng cải tiến (ERIM) 45
2.3.1. Phân cấp 46
2.3.2. Đánh giá độ quan trọng của luật dựa vào khái niệm phân cấp 47
2.3.3. Quá trình thực hiện 48
2.3.4. Các trường hợp đánh giá 49
2.3.5. Nhận xét 58
2.4. Kết luận chương 2 58
CHưƠNG 3.ỨNG DỤNG KIỂM CHỨNG . 60
3.1. Mô tả bài toán 60
3.2. Mô tả dữ liệu 60
3.3. Các bước thực hiện 62
3.3.1. Cài đặt ứng dụng 63
3.3.2. Luật mẫu 64
3.3.3. Tập luật được tạo ra 64
v
3.3.4. Tính độ đo RIM 645
3.3.5. Tính độ đo ERIM 66
3.4. Đánh giá 67
3.5. Ứng dụng luật 67
3.6. Kết luận chương 3 68
KẾT LUẬN VÀ HưỚNG PHÁT TRIỂN 69
Kết luận 69
Hướng phát triển 69
MỞ ĐẦU
Lý do chọn đề tài
Với sự phát triển vượt bật của công nghệ thông tin, các hệ quản trị cơ sở dữ
liệu có thể lưu trữ dữ liệu về hoạt động hàng ngày dễ dàng, dẫn đến việc hình thành
một khối lượng dữ liệu khổng lồ, đòi hỏi chúng ta, là những người sử dụng phải biết
khai thác, chọn lọc dữ liệu có ích cho mình. Các tri thức vừa học được có thể vận
dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu. Các phương
pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng
được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới là Khai phá dữ liệu
(Data Mining).
Khai phá dữ liệu đã được ứng dụng rất nhiều trong thực tế, nhất là trong lĩnh
vực tài chính và thị trường chứng khoán, thương mại, ý tế, sinh học, bưu chính viễn
thôn, nông nghiệp Một trong những chức năng được đề cập nhiều trong khai phá
dữ liệu là khám phá sự kết hợp giữa các mẫu trong dữ liệu hay còn gọi là luật kết
hợp. Số lượng luật kết hợp cũng tăng theo kích thước cơ sở dữ liệu, vì vậy, nhiều lý
thuyết được đưa ra để đánh giá độ quan trọng của luật. Trên cơ sở đó lựa chọn các
luật phù hợp cho ứng dụng. Đây là một hướng nghiên cứu mới và có ý nghĩa.
Mục tiêu
Luận văn tập trung nghiên cứu các phương pháp đánh giá độ quan trọng của
luật được sinh từ tập cơ sở dữ liệu, trên cơ sở luật kết hợp và lý thuyết tập thô.
Việc đánh giá độ quan trọng của luật nhằm hỗ trợ ra quyết định đối với một tổ
chức, doanh nghiệp, giúp cho quá trình phân tích từ tập dữ liệu được tốt hơn.
Bên cạnh đó, việc mô phỏng ứng dụng cũng được đặt ra để minh họa cho việc đánh
giá này.
Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu là các thuật toán khai phá luật kết hợp. Đồng thời
nghiên cứu hai phương pháp đánh giá độ quan trọng của luật là RIM và ERIM.
2
Phương pháp nghiên cứu
Nghiên cứu lý thuyết, phân tích, tổng hợp, mô phỏng, khái quát rút ra những
vấn đề cần thiết cho đề tài.
Ý nghĩa khoa học và thực tiễn đề tài
Khai phá dữ liệu là sự khám phá hiệu quả những tri thức từ cơ sở dữ liệu lớn,
và nó trở thành một vấn đề nóng cho việc đưa ra các quyết định.
Kỹ thuật khai phá luật kết hợp tuy hiệu quả nhưng cũng gặp một số bất lợi đối
với việc khai phá các dữ liệu lớn. Số luật tăng tỉ lệ thuận với cơ sơ dữ liệu càng làm
cho việc tìm kiếm tri thức trở nên khó khăn hơn.
Kết hợp với lý thuyết tập thô trong việc đánh giá độ quan trọng của các luật
sinh ra phần nào đã giải quyết được vấn đề sinh quá nhiều luật. Theo kỹ thuật này
các luật được đánh giá với các độ quan trọng khác nhau là độ quan trọng chủ quan
và độ quan trọng khách quan. Sự kết hợp này giúp cho các chuyên gia có cái nhìn
trực quan hơn trong việc vận dụng các luật thu được áp dụng vào thực tế.
Cấu trúc luận văn
Với mục tiêu đó, luận văn được chia làm ba chương
Chương 1: Cơ sở lý thuyết
Trong chương này trình bày tổng quan về khai phá dữ liệu,luật kết hợp và lý
thuyết tập thô.
Chương 2: Các phương pháp đánh giá luật
Chương này tập trung nghiên cứu các phương pháp đánh giá độ hữu ích của
luật, phương pháp RIM,ERIM.
Chương 3: Ứng dụng kiểm chứng
Chương này tập trung mô phỏng với dữ liệu kết quả học tập của bậc TCCN
ngành kế toán doanh nghiệp tại Trường Cao đẳng Công nghệ Thủ Đức.
TÀI LIỆU THAM KHẢO
[1] A. Mitnitski, X. Song, and K. Rockwood (2004), “The estimation of relative
fitness and frailty in communit y-dwelling older adults using self-report data”, J
Gerontol A Biol Sci Med Sci, pp. 627–632.
[2] Ho Tu Bao(1998), Introduction to Knowledge Discovery and Data Mining,
National Center for Natural Science and Technology.
[3] J. Li and N. Cercone(2006). “Introducing a rule importance measure”. In
J. F. Peters, A. Skowron, D. Dubois, J. W. Grzymala-Busse, M. Inuiguchi,
and L. Polkowski, editors, T. Rough Sets, volume 4100 of Lecture Notes in
Computer Science, pages 167–189. Springer.
[4] J. Li(2007). Rough Set Based Rule Evaluations and Their Applications.
PhD thesis,University of Waterloo, Waterloo, Canada.
[5] Jan Komorowski, Lech Polkowski, Andrzej Skowron (2000). Rough sets: A
tutorial.
[6] Jiye Li, Nick Cercone(2005). “Discovering and Ranking Important
Rules”. Granular Computing, IEEE International Conference on Volume 2.
[7] Jiye Li, Nick Cercone, W. H . Wong, Lisa Jing Yan(2009). “Enhancing Rule
Importance Measure Using Concept Hierarchy”. Faculty of Computer
Science and Engineering, York University.
[8] L. Geng and H. J. Hamilton(2006). “Interestingness measures for data
mining: A survey”. ACM Comput. Surv., 38(3):9.
[9] M. E. M. D. Beneditto and L. N. de Barros (2004), “Using concept
hierarchies in knowledge discovery”, volume 3171 of Lecture Notes in
Computer Science, pp. 255–265.
[10] Øhrn(1999). Discernibility and Rough Sets in Medicine: Tools and
Applications. PhD thesis, Department of Computer and Information
Science, Norwegian University of Science and Technology, Trondheim
Norway.
[11] Øhrn, Aleksander(2001): ROSETTA Technical Reference Manual.
Department of Com- puter and Information Science, Norwegian University
of Science and Technology, Trondheim, Norway. May 25
[12] P.Tan, V.Kumar, J.Sivastava(2002). “Selecting the Right Interestingness
Measure for Association Patterns”, in SIGKDD’02 ACM.
[13] R. Agrawal and R. Srikant (1994). “Fast algorithms for mining association
rules”. The International Conference on Very Large Databases, pages 487–
499.
[14] Rakesh Agrawal, Tomasz Imielinski, and Arun Swami (1993), “Mining
association rules between sets of items in large database”, In proc of the ACM
SIGMOD Conference on Management of Data, Washington, D.C.
[15] Y. Chen, G.-R. Xue, and Y. Yu (2008), “Advertising keyword suggestion
based on concept hierarchy”. InWSDM ’08: Proceedings of the international
conference on Web search and web data mining, pp. 251–260.
[16] Z. Pawlak(1991). “Rough Sets – Theoretical Aspects of Reasoning about
Data”. Kluwer Academic Publishers, Dordrecht.
[17]
You must be registered for see links
[18]
You must be registered for see links
Link download cho anh em ketnooi
You must be registered for see links
Nhớ thank mình nhé