CS490D: Introduction to Data Mining Prof. Chris CliftonSeminar Thursday: Support Vector MachinesCourse Outline www.cs.purdue.edu/~clifton/cs490dData Mining: Classification SchemesKnowledge Discovery in Databases: ProcessWhat Can Data Mining Do?What is Data Warehouse?Example of Star SchemaFrom Tables and Spreadsheets to Data CubesCube: A Lattice of CuboidsA Sample Data CubeWarehouse SummaryData PreprocessingMulti-Dimensional Measure of Data QualityMajor Tasks in Data PreprocessingHow to Handle Missing Data?How to Handle Noisy Data?Data TransformationData Reduction StrategiesPrincipal Component AnalysisDiscretizationData Preparation SummaryAssociation Rule MiningBasic Concepts: Association RulesThe Apriori Algorithm—An ExampleFP-Tree AlgorithmConstrained Frequent Pattern Mining: A Mining Query Optimization ProblemClassification: Model ConstructionClassification: Use the Model in PredictionNaïve Bayes ClassifierBayesian Belief NetworkDecision TreeAlgorithm for Decision Tree InductionAttribute Selection Measure: Information Gain (ID3/C4.5)Definition of EntropyAttribute Selection by Information Gain ComputationOverfitting in Decision TreesArtificial Neural Networks: A NeuronArtificial Neural Networks: TrainingSVM – Support Vector MachinesNon-separable caseNon-separable Cont.General SVMGeneral SVM Cont.MappingThe k-Nearest Neighbor AlgorithmCase-Based ReasoningRegress Analysis and Log-Linear Models in PredictionBagging and BoostingTest Taking HintsSlide 53CS490D:Introduction to Data MiningProf. Chris CliftonMarch 8, 2004Midterm ReviewMidterm Wednesday, March 10, in class. Open book/notes.CS490D Midterm Review 2Seminar Thursday:Support Vector Machines•Massive Data Mining via Support Vector Machines•Hwanjo Yu, University of Illinois–Thursday, March 11, 2004–10:30-11:30–CS 111•Support Vector Machines for:–classifying from large datasets–single-class classification–discriminant feature combination discoveryCS490D Midterm Review 3Course Outlinewww.cs.purdue.edu/~clifton/cs490d1. Introduction: What is data mining?–What makes it a new and unique discipline?–Relationship between Data Warehousing, On-line Analytical Processing, and Data Mining2. Data mining tasks - Clustering, Classification, Rule learning, etc.3. Data mining process: Data preparation/cleansing, task identification–Introduction to WEKA4. Association Rule mining5. Association rules - different algorithm types6. Classification/Prediction7. Classification - tree-based approaches8. Classification - Neural NetworksMidterm9. Clustering basics10.Clustering - statistical approaches11.Clustering - Neural-net and other approaches12.More on process - CRISP-DM–Preparation for final project13.Text Mining14.Multi-Relational Data Mining15.Future trendsFinalText: Jiawei Han and Micheline Kamber, Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, August 2000.CS490D Midterm Review 4Data Mining: Classification Schemes•General functionality–Descriptive data mining –Predictive data mining•Different views, different classifications–Kinds of data to be mined–Kinds of knowledge to be discovered–Kinds of techniques utilized–Kinds of applications adaptedCS490D Midterm Review 5adapted from:U. Fayyad, et al. (1995), “From Knowledge Discovery to Data Mining: An Overview,” Advances in Knowledge Discovery and Data Mining, U. Fayyad et al. (Eds.), AAAI/MIT PressDataTargetDataSelectionKnowledgeKnowledgePreprocessedDataPatternsData MiningInterpretation/EvaluationKnowledge Discovery in Databases: ProcessPreprocessingCS490D Midterm Review 6What Can Data Mining Do?•Cluster•Classify–Categorical, Regression•Summarize–Summary statistics, Summary rules•Link Analysis / Model Dependencies–Association rules•Sequence analysis–Time-series analysis, Sequential associations•Detect DeviationsCS490D Midterm Review 7What is Data Warehouse?•Defined in many different ways, but not rigorously.–A decision support database that is maintained separately from the organization’s operational database–Support information processing by providing a solid platform of consolidated, historical data for analysis.•“A data warehouse is a subject-oriented, integrated, time-variant, and nonvolatile collection of data in support of management’s decision-making process.”—W. H. Inmon•Data warehousing:–The process of constructing and using data warehousesCS490D Midterm Review 8Example of Star Schema time_keydayday_of_the_weekmonthquarteryeartimelocation_keystreetcitystate_or_provincecountrylocationSales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_salesMeasuresitem_keyitem_namebrandtypesupplier_typeitembranch_keybranch_namebranch_typebranchCS490D Midterm Review 9From Tables and Spreadsheets to Data Cubes•A data warehouse is based on a multidimensional data model which views data in the form of a data cube•A data cube, such as sales, allows data to be modeled and viewed in multiple dimensions–Dimension tables, such as item (item_name, brand, type), or time(day, week, month, quarter, year) –Fact table contains measures (such as dollars_sold) and keys to each of the related dimension tables•In data warehousing literature, an n-D base cube is called a base cuboid. The top most 0-D cuboid, which holds the highest-level of summarization, is called the apex cuboid. The lattice of cuboids forms a data cube.CS490D Midterm Review 10Cube: A Lattice of Cuboidsalltime item location suppliertime,itemtime,locationtime,supplieritem,locationitem,supplierlocation,suppliertime,item,locationtime,item,suppliertime,location,supplieritem,location,suppliertime, item, location, supplier0-D(apex) cuboid1-D cuboids2-D cuboids3-D cuboids4-D(base) cuboidCS490D Midterm Review 11A Sample Data CubeTotal annual salesof TVs in U.S.A.DateProductCountrysumsum TVVCRPC1Qtr2Qtr3Qtr4QtrU.S.ACanadaMexicosumCS490D Midterm Review 12Warehouse Summary•Data warehouse •A multi-dimensional model of a data warehouse–Star schema, snowflake schema, fact constellations–A data cube consists of dimensions & measures•OLAP operations: drilling, rolling, slicing, dicing and pivoting•OLAP servers: ROLAP, MOLAP, HOLAP•Efficient computation of data cubes–Partial vs. full vs. no materialization–Multiway array aggregation–Bitmap index and join index implementations•Further development of data cube technology–Discovery-drive and multi-feature cubes–From OLAP to OLAM