Bài giảng Khai phá dữ liệu (Data mining) - Chương 7: Khai phá dữ liệu và công nghệ cơ sở dữ liệu - Võ Thị Ngọc Châu
hương 7: Khai phá dữ liệu và
công nghệ cơ sở dữ liệu
7.1. Tổng quan về công nghệ cơ sở dữ liệu
7.2. Khả năng hỗ trợ khai phá dữ liệu của
công nghệ cơ sở dữ liệu
7.3. Các ngôn ngữ truy vấn dành cho khai
phá dữ liệu
7.4. Hỗ trợ của các DBMS ngày nay dành
cho khai phá
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Khai phá dữ liệu (Data mining) - Chương 7: Khai phá dữ liệu và công nghệ cơ sở dữ liệu - Võ Thị Ngọc Châu", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Khai phá dữ liệu (Data mining) - Chương 7: Khai phá dữ liệu và công nghệ cơ sở dữ liệu - Võ Thị Ngọc Châu
11 Chương 7: Khai phá dữ liệu và công nghệ cơ sở dữ liệu Học kỳ 1 – 2011-2012 Khoa Khoa Học & Kỹ Thuật Máy Tính Trường Đại Học Bách Khoa Tp. Hồ Chí Minh Cao Học Ngành Khoa Học Máy Tính Giáo trình điện tử Biên soạn bởi: TS. Võ Thị Ngọc Châu (chauvtn@cse.hcmut.edu.vn) 22 Tài liệu tham khảo [1] Jiawei Han, Micheline Kamber, “Data Mining: Concepts and Techniques”, Second Edition, Morgan Kaufmann Publishers, 2006. [2] David Hand, Heikki Mannila, Padhraic Smyth, “Principles of Data Mining”, MIT Press, 2001. [3] David L. Olson, Dursun Delen, “Advanced Data Mining Techniques”, Springer-Verlag, 2008. [4] Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory, Methodology, Techniques, and Applications”, Springer-Verlag, 2006. [5] Hillol Kargupta, Jiawei Han, Philip S. Yu, Rajeev Motwani, and Vipin Kumar, “Next Generation of Data Mining”, Taylor & Francis Group, LLC, 2009. [6] Daniel T. Larose, “Data mining methods and models”, John Wiley & Sons, Inc, 2006. [7] Ian H.Witten, Eibe Frank, “Data mining : practical machine learning tools and techniques”, Second Edition, Elsevier Inc, 2005. [8] Florent Messeglia, Pascal Poncelet & Maguelonne Teisseire, “Successes and new directions in data mining”, IGI Global, 2008. [9] Oded Maimon, Lior Rokach, “Data Mining and Knowledge Discovery Handbook”, Second Edition, Springer Science + Business Media, LLC 2005, 2010. 33 Nội dung Chương 1: Tổng quan về khai phá dữ liệu Chương 2: Các vấn đề tiền xử lý dữ liệu Chương 3: Hồi qui dữ liệu Chương 4: Phân loại dữ liệu Chương 5: Gom cụm dữ liệu Chương 6: Luật kết hợp Chương 7: Khai phá dữ liệu và công nghệ cơ sở dữ liệu Chương 8: Ứng dụng khai phá dữ liệu Chương 9: Các đề tài nghiên cứu trong khai phá dữ liệu Chương 10: Ôn tập 44 Chương 7: Khai phá dữ liệu và công nghệ cơ sở dữ liệu 7.1. Tổng quan về công nghệ cơ sở dữ liệu 7.2. Khả năng hỗ trợ khai phá dữ liệu của công nghệ cơ sở dữ liệu 7.3. Các ngôn ngữ truy vấn dành cho khai phá dữ liệu 7.4. Hỗ trợ của các DBMS ngày nay dành cho khai phá dữ liệu 7.5. Tóm tắt 55 7.0. Tình huống 1 Người đang sử dụng thẻ ID = 1234 thật sự là chủ nhân của thẻ hay là một tên trộm? 66 7.0. Tình huống 2 Tid Refund Marital Status Taxable Income Evade 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 Ông A (Tid = 100) có khả năng trốn thuế??? 77 7.0. Tình huống 3 Ngày mai cổ phiếu STB sẽ tăng??? 88 7.0. Tình huống 4 Không (97%)3.02.0472008 Không (45%)4.55.5822007 Có (90%)7.59.5242006 Có (80%)6.07.0902005 Không3.55.582004 14 3 2 1 MãSV Có5.55.02004 Không2.54.02004 Có8.06.52004 Có8.59.02004 TốtNghiệpMônHọc2MônHọc1Khóa Làm sao xác định được khả năng tốt nghiệp của một sinh viên hiện tại? 99 7.0. Tình huống We are data rich, but information poor. “Necessity is the mother of invention”. - Plato 10 10 7.1. Tổng quan về công nghệ cơ sở dữ liệu Đặc điểm dữ liệu thu thập được cho quá trình khai phá dữ liệu (tóm tắt từ Chương 1) Bắt nguồn từ yêu cầu ứng dụng thực tiễn Dữ liệu thật/dữ liệu nhân tạo từ mô phỏng Cấu trúc từ đơn giản đến phức tạp Lượng dữ liệu lớn, biến động nhiều Lưu trữ lâu dài/lưu trữ tạm thời Æ Quản lý và tận dụng hiệu quả 11 11 7.1. Tổng quan về công nghệ cơ sở dữ liệu Đặc điểm kết quả thu được từ quá trình khai phá dữ liệu (tóm tắt từ Chương 1) Bắt nguồn từ yêu cầu ứng dụng thực tiễn Có tính mô tả hay dự đoán tùy thuộc vào quá trình khai phá cụ thể Cấu trúc từ đơn giản đến phức tạp Lượng kết quả lớn, biến động nhiều Nhiều tác vụ, nhiều giải thuật, nhiều lựa chọn giá trị thông số Lưu trữ lâu dài/lưu trữ tạm thời Æ Quản lý và tận dụng hiệu quả 12 12 7.1. Tổng quan về công nghệ cơ sở dữ liệu Mô hình hóa (modeling) Model: “a representation of something, either as a physical object which is usually smaller than the real object, or as a simple description of the object which might be used in calculations” ÆMô hình hóa dữ liệu cho quá trình khai phá ÆMô hình hóa kết quả từ quá trình khai phá 13 13 7.1. Tổng quan về công nghệ cơ sở dữ liệu Simple Data without Queries Simple Data with Queries Complex Data without Queries Complex Data with Queries I II III Pattern-matching (Similarity-based) Data Query Language (Precision-based) Numbers and Characters Video, Audio, Image, Text, 3D Graphical Data, etc. IV 14 14 7.1. Tổng quan về công nghệ cơ sở dữ liệu File Systems Relational DB Systems Object Relational DB SystemsObject (Oriented) DB Systems Simple Data Complex Data Simple Queries Complex Queries Source: M. Stonebraker, P. Brown with D. Moore, Object-Relational DBMS’s – Tracking the Next Great Wave, Morgan Kaufmann, 1999. 15 15 7.1. Tổng quan về công nghệ cơ sở dữ liệu Mô hình hóa ý niệm dữ liệu cho quá trình khai phá YesNoNoConceptual Schema Design Procedure Yes with sample populationsNoNoValidation technique 5NF relations1NF relations1NF relationsRelational mapping algorithm Predicate logic and linguistic Object oriented paradigmNoTheoretical Foundation NoClass methodNoObject behaviors RicherOCL expressionsFewerConstraints Relationship typeRelationship typeRelationship typeRelationships IdentifierOID (implicit)Key attributeObject identity -AttributeAttributeObject attribute --Weak entity typeSet of dependent objects Object typeClassEntity typeSet of objects of interest NIAM/ORMUMLERMConceptual Data Model 16 16 7.1. Tổng quan về công nghệ cơ sở dữ liệu Mô hình hóa luận lý dữ liệu cho quá trình khai phá Methods callingLogical pointer REF (system-generated) OID (system-generated)Fully encapsulated object with atomic/non-atomic attributes Object SQL:3, SQL:99, SQL:2003, OQL Foreign key (attribute values)/logical pointer REF (system- generated) Primary key (attribute values) / OID (ROWID, REFC) (system- generated) Relation/un-encapsulated object with atomic/non- atomic attributes Object Relational Nested relational algebra with nest/unnest operations Foreign key (attribute values) Primary key (attribute values) Nested relation with nested relation attributes Nested Relational Relational algebra, tuple relational calculus, SQL:89, SQL:92 Foreign key (attribute values) Primary key (attribute values) Relation with atomic attributes Relational LanguageReferential ConstraintIdentityKey ConstructData Model 17 17 7.1. Tổng quan về công nghệ cơ sở dữ liệu Mô hình hóa dữ liệu cho quá trình khai phá Data warehouse “A data warehouse is a subject-oriented, integrated, nonvolatile, and time-variant collection of data in support of management’s decisions.” UML conceptual model Star (relational)/multidimensional model Figure 2.5. The structure of the data warehouse. Source: W.H. Inmon. Building the data warehouse, 3rd Edition, John Wiley & Sons, Inc., 2001. 18 18 7.1. Tổng quan về công nghệ cơ sở dữ liệu Figure 1. Decision support system architecture, which consists of three principal components: a data warehouse server, analysis and data mining tools, and data warehouse back-end tools. Source: S. Chaudhuri, U. Dayal, V. Ganti, Database Technology for Decision Support Systems, Computer, IEEE, 2001, pp. 48-55. 19 19 7.1. Tổng quan về công nghệ cơ sở dữ liệu Mô hình hóa luận lý kết quả từ quá trình khai phá Motivations Large collection of discovered knowledge A diversity of discovered knowledge Pattern (discovered knowledge) is nicely managed by a so- called pattern management system just like data by a well- defined/developed/used DBMS. A logical model for patterns defined in [108-2003] Architectural issues Representation constructs: Pattern type, Pattern, Class Implicit constraints: Pattern-Pattern type, Pattern-Class, Class- Pattern-Pattern type Relationships between patterns Specialization, composition, refinement [108]. S. Rizzi, E. Bertino, B. Catania, M. Golfarelli, M. Halkidi, M. Terrovitis, P. Vassiliadis, M. Vazirginannis, E. Vrachnos. Towards a logical model for patterns. In Proceedings of the ER 2003, LNCS 2813, pp. 77-90, 2003. 20 20 Reference architecture for a pattern base management system using the logical model Source: S. Rizzi, E. Bertino, B. Catania, M. Golfarelli, M. Halkidi, M. Terrovitis, P. Vassiliadis, M. Vazirginannis, E. Vrachnos. Towards a logical model for patterns. In Proceedings of the ER 2003, LNCS 2813, pp. 77-90, 2003. 21 21 Related Works - [108-2003]Æ [73-2008] [108-2003] (architectural issues + representational constructs + pattern relationships) [4-2004] (framework) [97-2006] (review) [3-2006] (language and system development – PhD thesis) [87-2007] (Interoperability issues + support for application programs + driver development) [73-2008] (summary) 22 22 Related Works - [108-2003]Æ [105-2007] [108-2003] (architectural issues + representational constructs + pattern relationships) [12-2004, 2007] (formal definition, pattern warehouse, query types, predicates and operators) [105-2007] (more operators on pattern warehouse + indexing techniques – PhD thesis) 23 23 Related Works - [108-2003]Æ [101-2009] [108-2003] [99-2007] (model extension with superclass, ontology for knowledge evaluation of association rules and queries) [100-2008] (pattern comparison methods for clustering) [101-2009] (pattern comparison for crisp/fuzzy clustering, open source prototype development (PatternMiner) – PhD thesis) [98-2005] (Database approach: relational, object relational, and XML-based databases) 24 24 Related works 4. B. Catania, A. Maddalena, M. Mazza, E. Bertino, S. Rizzi. A framework for data mining pattern management. In Proceedings of PKDD 2004, LNAI 3202, pp. 87-98, 2004. 97. B. Catania, A. Maddalena. Pattern Management: Practice and Challenges. In Processing and Managing Complex Data for Decision Support, J. Darmont, O. Boussaid (eds.), Idea Group Publishing, 2006. 73. B. Catania. Towards effective solutions for pattern management. International Journal of Computer Science and Applications, Vol 5(3), 2008, 36-45. 98. E. Kotsifakos, I. Ntoutsi, Y. Theodoridis. Database support for data mining patterns. In Proceedings of the 10th Panhellenic Conference on Informatics (PCI’05), Advances in Informatics – Springer-Verlag LNCS 3746, 2005. 99. E.E. Kotsifakos, G. Marketos, Y. Theodoridis. A framework for integrating ontologies and pattern-bases. Data Mining with Ontologies: Implementations, Findings, and Frameworks, H.O. Nigro, S. G. Cisaro, D. Xodo (eds.), Chapter 12, IDEA Group, 2007. 100. E.E. Kotsifakos, I. Ntoutsi, Y. Vrahoritis, Y. Theodoridis. PATTERN-MINER: Integrated management and mining over data mining models (Demo). In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’08), 2008. 101. E.E. Kotsifakos. Pattern representation and management techniques – The PBMS concept. PhD Thesis, Department of Informatics, University of Piraeus, 2009. 3. A. Maddalena. A unified framework for heterogeneous pattern management. PhD thesis in Computer Science, University of Genova, April 2006. 87. A. Maddalena, B. Catania. Towards an interoperable solution for pattern management. In Proceedings of VLDB’07, 2007. 106. R. Meo, G. Psaila. An XML-based database for knowledge discovery. In Proceedings of the EDBT 2006 Workshops, LNCS 4254, pp. 814-828, 2006. 108. S. Rizzi, E. Bertino, B. Catania, M. Golfarelli, M. Halkidi, M. Terrovitis, P. Vassiliadis, M. Vazirginannis, E. Vrachnos. Towards a logical model for patterns. In Proceedings of the ER 2003, LNCS 2813, pp. 77-90, 2003. 105. M. Terrovitis. Modelling and operational issues for pattern base management systems. PhD Thesis, Computer Science Division, School of Electrical and Computer Engineering, National Technical University of Athens, 2007. 12. M. Terrovitis, P. Vassiliadis, S. Skiadopoulos, E. Bertino, B. Catania, A. Maddalena, S. Rizzi. Modeling and language support for the management of pattern-bases. Data & Knowledge Engineering 62 (2007) 368-397. 25 25 7.2. Khả năng hỗ trợ khai phá dữ liệu của công nghệ cơ sở dữ liệu Vấn đề quản lý Đúng dữ liệu Đúng người dùng Đúng lúc Vấn đề lưu trữ Lâu dài Tạm thời Vấn đề thao tác Hiệu quả -Dữ liệu cho quá trình khai phá -Kết quả từ quá trình khai phá 26 26 7.2. Khả năng hỗ trợ khai phá dữ liệu của công nghệ cơ sở dữ liệu Từ yêu cầu tri thức trong dữ liệu thu thập được ngày nay đến yêu cầu dành cho quá trình khai phá dữ liệu Từ yêu cầu của quá trình khai phá dữ liệu đến yêu cầu dành cho công nghệ cơ sở dữ liệu Æ conventional DBMS, in-memory DBMS, column-oriented DBMS, IR + DBMS, semantic technologies + DBMS, service-oriented DBMS, 27 27 7.3. Các ngôn ngữ truy vấn dành cho khai phá dữ liệu A data mining query language select the data to be mined and pre-process these data, specify the kind of patterns to be mined, specify the needed background knowledge (as item hierarchies when mining generalized association rules), define the constraints on the desired patterns, post-process extracted patterns. Source: J-F. Boulicaut, C. Masson, Data Mining Query Languages, Chapter 1 in: The Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach (Eds.), Springer, 2005, pp. 715-727. 28 28 7.3. Các ngôn ngữ truy vấn dành cho khai phá dữ liệu Proposals for association rule mining MSQL (Imielinski and Virmani, 1999) at the Rutgers University MINE RULE (Meo et al., 1998) at the University of Torino and the Politecnico di Milano DMQL (Han et al., 1996) at the Simon Fraser University OLE DB for DM by Microsoft Corporation (Netz et al., 2000) Source: J-F. Boulicaut, C. Masson, Data Mining Query Languages, Chapter 1 in: The Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach (Eds.), Springer, 2005, pp. 715-727. 29 29 7.3. Các ngôn ngữ truy vấn dành cho khai phá dữ liệu MSQL (Imielinski and Virmani, 1999) at the Rutgers University Source: J-F. Boulicaut, C. Masson, Data Mining Query Languages, Chapter 1 in: The Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach (Eds.), Springer, 2005, pp. 715-727. Inductive queries to mine rules Post-processing queries over a materialized collection of rules 30 30 7.3. Các ngôn ngữ truy vấn dành cho khai phá dữ liệu MINE RULE (Meo et al., 1998) at the University of Torino and the Politecnico di Milano Source: J-F. Boulicaut, C. Masson, Data Mining Query Languages, Chapter 1 in: The Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach (Eds.), Springer, 2005, pp. 715-727. 31 31 7.3. Các ngôn ngữ truy vấn dành cho khai phá dữ liệu DMQL (Han et al., 1996) at the Simon Fraser University Source: J-F. Boulicaut, C. Masson, Data Mining Query Languages, Chapter 1 in: The Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach (Eds.), Springer, 2005, pp. 715-727. 32 32 7.3. Các ngôn ngữ truy vấn dành cho khai phá dữ liệu OLE DB for DM by Microsoft Corporation (Netz et al., 2000) Source: J-F. Boulicaut, C. Masson, Data Mining Query Languages, Chapter 1 in: The Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach (Eds.), Springer, 2005, pp. 715-727. 33 33 7.4. Hỗ trợ của các DBMS ngày nay dành cho khai phá dữ liệu The SQL Multimedia and Applications Packages Standard (SQL/MM) An initiative developed and published by the International Organization for Standardization (ISO) Includes: Part 1: Framework Part 2: Full-Text Part 3: Spatial Part 5: Still Image Part 6: Data Mining Part 6 specifies an SQL interface to data mining applications and services through accessing data from SQL/MM-compliant relational databases. A standardized interface to data mining algorithms that can be layered atop any objectrelational database system and even deployed as middle-ware when required A collection of user-defined types provided for the key data mining functions, namely, Association Rule Discovery, Clustering, Classification and Regression Source: S. S. Anand, M. Grobelnik, F. Herrmann, D. Wettschereck, M. Hornick, C. Lingenfelder, N. Rooney, Knowledge discovery standards, Artif Intell Rev (2007) 27:21-56. 34 34 7.4. Hỗ trợ của các DBMS ngày nay dành cho khai phá dữ liệu The SQL Multimedia and Applications Packages Standard (SQL/MM) – Part 6 User-defined types related to data DM_LogicalDataSpec an abstraction for a set of data mining fields identified by their names DM_MiningData a description of data contained in tables, which represents the metadata required to access the data during training, test or application runs. DM_ApplicationData used to submit a single record of data for model application. Source: S. S. Anand, M. Grobelnik, F. Herrmann, D. Wettschereck, M. Hornick, C. Lingenfelder, N. Rooney, Knowledge discovery standards, Artif Intell Rev (2007) 27:21-56. 35 35 7.4. Hỗ trợ của các DBMS ngày nay dành cho khai phá dữ liệu The SQL Multimedia and Applications Packages Standard (SQL/MM) – Part 6 User-defined types related to the mining phases Training phase (CRISP-DM modelling) DM_Settings, DM_BldTask, DM_Model Testing phase (CRISP-DM evaluation) DM_TestTask, DM_Model, DM_TestResult Application phase (CRISP-DM deployment) DM_ApplTask, DM_Model, DM_Result, DM_ApplicationData Source: S. S. Anand, M. Grobelnik, F. Herrmann, D. Wettschereck, M. Hornick, C. Lingenfelder, N. Rooney, Knowledge discovery standards, Artif Intell Rev (2007) 27:21-56. 36 36 7.4. Hỗ trợ của các DBMS ngày nay dành cho khai phá dữ liệu Source: S. S. Anand, M. Grobelnik, F. Herrmann, D. Wettschereck, M. Hornick, C. Lingenfelder, N. Rooney, Knowledge discovery standards, Artif Intell Rev (2007) 27:21-56. 37 37 7.4. Hỗ trợ của các DBMS ngày nay dành cho khai phá dữ liệu Source: S. S. Anand, M. Grobelnik, F. Herrmann, D. Wettschereck, M. Hornick, C. Lingenfelder, N. Rooney, Knowledge discovery standards, Artif Intell Rev (2007) 27:21-56. The application retrieves the model with the statement: and calls the following to compute the predicted class: 38 38 7.4. Hỗ trợ của các DBMS ngày nay dành cho khai phá dữ liệu A number of vendor specific mining extensions to SQL Microsoft’s OLE DB for Data Mining (OLE-DB 2000): an approach which is specially designed for data mining needs—it combines SQL with a low level API (a set of COM interfaces) to achieve interoperability with other client and server technologies. MS Naïve Bayes, MS Decision Trees, MS Time Series, MS Clustering, MS Sequence Clustering, MS Association Rules, MS Neural Network IBM’s DB2 Intelligent Miner products contain a set of DB2 database extenders (DB2-IM 2004): incorporate data mining functionality into standard database SQL language in a relatively standard way. Functionality is based on IBM’s “Intelligent Miner” data mining product, now part of the IBM DB2 Data Warehouse Edition V9.1. Intelligent Miner fully implements SQL/MM data mining as well as most of PMML Oracle Data Mining (Oracle 2004): a set of functions available in Oracle’s database and accessible though PL/SQL (programming language available to database programmers) and through a Java interface. Decision Tree, Generalized Linear Models, Minimum Description Length, Naïve Bayes, Support Vector Machines, Apriori, k-Means, Non-Negative Matrix Factorization, One Class Support Vector Machine, Orthogonal Partitioning Clustering Source: S. S. Anand, M. Grobelnik, F. Herrmann, D. Wettschereck, M. Hornick, C. Lingenfelder, N. Rooney, Knowledge discovery standards, Artif Intell Rev (2007) 27:21-56. 39 39 7.5. Tóm tắt Data mining: “extracting or mining knowledge from large amounts of data” Need for effective and efficient data management Need for effective and efficient knowledge management Æ Database technologies: conceptual >> logical >> physical issues Data mining query languages: MSQL, MINE RULE, DMQL, OLE DB for DM Data mining seems to be less non-trivial to users. Current support for data mining from DBMSs From SQL standards: SQL/MM Part 6 for data mining functions: Association Rule Discovery, Clustering, Classification and Regression From Commercial DBMSs: Microsoft’s OLE DB for DM, IBM’s Intelligent Miner, Oracle Data Mining From Open source DBMSs: easily associated with open source data mining libraries 40 40 Hỏi & Đáp
File đính kèm:
- bai_giang_khai_pha_du_lieu_data_mining_chuong_7_khai_pha_du.pdf