1、 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 1 Data Mining: IntroductionLecture Notes for Chapter 1Introduction to Data MiningbyTan, Steinbach, Kumar Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 2 lLots of data is being collected and warehoused Web data, e-commerce purch
2、ases at department/grocery stores Bank/Credit Card transactionslComputers have become cheaper and more powerfullCompetitive Pressure is Strong Provide better, customized services for an edge (e.g. in Customer Relationship Management)Why Mine Data? Commercial ViewpointWhy Mine Data? Scientific Viewpo
3、intlData collected and stored at enormous speeds (GB/hour) remote sensors on a satellite telescopes scanning the skies microarrays generating gene expression data scientific simulations generating terabytes of datalTraditional techniques infeasible for raw datalData mining may help scientists in cla
4、ssifying and segmenting data in Hypothesis Formation Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 4 Mining Large Data Sets - MotivationlThere is often information “hidden” in the data that is not readily evidentlHuman analysts may take weeks to discover useful informationlMuch of the d
5、ata is never analyzed at all0500,0001,000,0001,500,0002,000,0002,500,0003,000,0003,500,0004,000,00019951996199719981999The Data GapTotal new disk (TB) since 1995Number of analysts From: R. Grossman, C. Kamath, V. Kumar, “Data Mining for Scientific and Engineering Applications” Tan,Steinbach, Kumar I
6、ntroduction to Data Mining 4/18/2004 5 What is Data Mining?lMany Definitions Non-trivial extraction of implicit, previously unknown and potentially useful information from data Exploration & analysis, by automatic or semi-automatic means, of large quantities of data in order to discover meaningful p
7、atterns Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 6 What is (not) Data Mining?l What is Data Mining? Certain names are more prevalent in certain US locations (OBrien, ORurke, OReilly in Boston area) Group together similar documents returned by search engine according to their contex
8、t (e.g. Amazon rainforest, A,)l What is not Data Mining? Look up phone number in phone directory Query a Web search engine for information about “Amazon” Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 7 lDraws ideas from machine learning/AI, pattern recognition, statistics, and database
9、systemslTraditional Techniquesmay be unsuitable due to Enormity of data High dimensionality of data Heterogeneous, distributed nature of dataOrigins of Data MiningMachine Learning/Pattern RecognitionStatistics/AIData MiningDatabase systems Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 8
10、 Data Mining TaskslPrediction Methods Use some variables to predict unknown or future values of other variables.lDescription Methods Find human-interpretable patterns that describe the data.From Fayyad, et.al. Advances in Knowledge Discovery and Data Mining, 1996 Tan,Steinbach, Kumar Introduction to
11、 Data Mining 4/18/2004 9 Data Mining Tasks.lClassification PredictivelClustering DescriptivelAssociation Rule Discovery DescriptivelSequential Pattern Discovery DescriptivelRegression PredictivelDeviation Detection Predictive Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 10 Classificati
12、on: DefinitionlGiven a collection of records (training set ) Each record contains a set of attributes, one of the attributes is the class.lFind a model for class attribute as a function of the values of other attributes.lGoal: previously unseen records should be assigned a class as accurately as pos
13、sible. A test set is used to determine the accuracy of the model. Usually, the given data set is divided into training and test sets, with training set used to build the model and test set used to validate it. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 11 Classification ExampleTidRef
14、undMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10categoricalcategoricalcontinuousclassRefundMaritalStatusTaxableIncomeCheatNoSingle75K?YesMarried50K?NoMar
15、ried150K?YesDivorced90K?NoSingle40K?NoMarried80K?10TestSetTraining SetModelLearn Classifier Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 12 Classification: Application 1lDirect Marketing Goal: Reduce cost of mailing by targeting a set of consumers likely to buy a new cell-phone product
16、. Approach:uUse the data for a similar product introduced before. uWe know which customers decided to buy and which decided otherwise. This buy, dont buy decision forms the class attribute.uCollect various demographic, lifestyle, and company-interaction related information about all such customers.
17、Type of business, where they stay, how much they earn, etc.uUse this information as input attributes to learn a classifier model.From Berry & Linoff Data Mining Techniques, 1997 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 13 Classification: Application 2lFraud Detection Goal: Predict
18、fraudulent cases in credit card transactions. Approach:uUse credit card transactions and the information on its account-holder as attributes. When does a customer buy, what does he buy, how often he pays on time, etcuLabel past transactions as fraud or fair transactions. This forms the class attribu
19、te.uLearn a model for the class of the transactions.uUse this model to detect fraud by observing credit card transactions on an account. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 14 Classification: Application 3lCustomer Attrition/Churn: Goal: To predict whether a customer is likely
20、 to be lost to a competitor. Approach:uUse detailed record of transactions with each of the past and present customers, to find attributes. How often the customer calls, where he calls, what time-of-the day he calls most, his financial status, marital status, etc. uLabel the customers as loyal or di
21、sloyal.uFind a model for loyalty.From Berry & Linoff Data Mining Techniques, 1997 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 15 Classification: Application 4lSky Survey Cataloging Goal: To predict class (star or galaxy) of sky objects, especially visually faint ones, based on the tel
22、escopic survey images (from Palomar Observatory). 3000 images with 23,040 x 23,040 pixels per image. Approach:uSegment the image. uMeasure image attributes (features) - 40 of them per object.uModel the class based on these features.uSuccess Story: Could find 16 new high red-shift quasars, some of th
23、e farthest objects that are difficult to find!From Fayyad, et.al. Advances in Knowledge Discovery and Data Mining, 1996 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 16 Classifying GalaxiesEarlyIntermediateLateData Size: 72 million stars, 20 million galaxies Object Catalog: 9 GB Image D
24、atabase: 150 GB Class: Stages of FormationAttributes: Image features, Characteristics of light waves received, etc.Courtesy: http:/aps.umn.edu Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 17 Clustering DefinitionlGiven a set of data points, each having a set of attributes, and a simila
25、rity measure among them, find clusters such that Data points in one cluster are more similar to one another. Data points in separate clusters are less similar to one another.lSimilarity Measures: Euclidean Distance if attributes are continuous. Other Problem-specific Measures. Tan,Steinbach, Kumar I
26、ntroduction to Data Mining 4/18/2004 18 Illustrating ClusteringxEuclidean Distance Based Clustering in 3-D space.Intracluster distancesare minimizedIntercluster distancesare maximized Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 19 Clustering: Application 1lMarket Segmentation: Goal: s
27、ubdivide a market into distinct subsets of customers where any subset may conceivably be selected as a market target to be reached with a distinct marketing mix. Approach: uCollect different attributes of customers based on their geographical and lifestyle related information.uFind clusters of simil
28、ar customers.uMeasure the clustering quality by observing buying patterns of customers in same cluster vs. those from different clusters. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 20 Clustering: Application 2lDocument Clustering: Goal: To find groups of documents that are similar to
29、 each other based on the important terms appearing in them. Approach: To identify frequently occurring terms in each document. Form a similarity measure based on the frequencies of different terms. Use it to cluster. Gain: Information Retrieval can utilize the clusters to relate a new document or se
30、arch term to clustered documents. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 21 Illustrating Document ClusteringlClustering Points: 3204 Articles of Los Angeles Times.lSimilarity Measure: How many words are common in these documents (after some word filtering).CategoryTotalArticlesCo
31、rrectlyPlacedFinancial555364Foreign341260National27336Metro943746Sports738573Entertainment354278 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 22 Clustering of S&P 500 Stock DataDiscovered ClustersIndustry Group1Applied-Matl-DOWN,Bay-Network-Down,3-COM-DOWN,Cabletron-Sys-DOWN,CISCO-DOWN
32、,HP-DOWN,DSC-Comm-DOWN,INTEL-DOWN,LSI-Logic-DOWN,Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down,Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOWN,Sun-DOWNTechnology1-DOWN2Apple-Comp-DOWN,Autodesk-DOWN,DEC-DOWN,ADV-Micro-Device-DOWN,Andrew-Corp-DOWN,Computer-Assoc-DOWN,Circuit-City-DOWN,Compaq-DOWN, EMC-C
33、orp-DOWN, Gen-Inst-DOWN,Motorola-DOWN,Microsoft-DOWN,Scientific-Atl-DOWNTechnology2-DOWN3Fannie-Mae-DOWN,Fed-Home-Loan-DOWN,MBNA-Corp-DOWN,Morgan-Stanley-DOWNFinancial-DOWN4Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP,Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP,Schlumberger-UPOil-UPz Observe
34、 Stock Movements every day. z Clustering points: Stock-UP/DOWNz Similarity Measure: Two points are more similar if the events described by them frequently happen together on the same day. zWe used association rules to quantify a similarity measure. Tan,Steinbach, Kumar Introduction to Data Mining 4/
35、18/2004 23 Association Rule Discovery: DefinitionlGiven a set of records each of which contain some number of items from a given collection; Produce dependency rules which will predict occurrence of an item based on occurrences of other items.TIDItems1Bread, Coke, Milk2Beer, Bread3Beer, Coke, Diaper
36、, Milk4Beer, Bread, Diaper, Milk5Coke, Diaper, MilkRules Discovered: Milk - Coke Diaper, Milk - Beer Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 24 Association Rule Discovery: Application 1lMarketing and Sales Promotion: Let the rule discovered be Bagels, - Potato Chips Potato Chips a
37、s consequent = Can be used to determine what should be done to boost its sales. Bagels in the antecedent = Can be used to see which products would be affected if the store discontinues selling bagels. Bagels in antecedent and Potato chips in consequent = Can be used to see what products should be so
38、ld with Bagels to promote sale of Potato chips! Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 25 Association Rule Discovery: Application 2lSupermarket shelf management. Goal: To identify items that are bought together by sufficiently many customers. Approach: Process the point-of-sale d
39、ata collected with barcode scanners to find dependencies among items. A classic rule -uIf a customer buys diaper and milk, then he is very likely to buy beer.uSo, dont be surprised if you find six-packs stacked next to diapers! Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 26 Associatio
40、n Rule Discovery: Application 3lInventory Management: Goal: A consumer appliance repair company wants to anticipate the nature of repairs on its consumer products and keep the service vehicles equipped with right parts to reduce on number of visits to consumer households. Approach: Process the data
41、on tools and parts required in previous repairs at different consumer locations and discover the co-occurrence patterns. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 27 Sequential Pattern Discovery: DefinitionlGiven is a set of objects, with each object associated with its own timeline
42、 of events, find rules that predict strong sequential dependencies among different events.lRules are formed by first disovering patterns. Event occurrences in the patterns are governed by timing constraints.(A B) (C) (D E)= msng (Fire_Alarm)lIn point-of-sale transaction sequences, Computer Bookstore
43、: (Intro_To_Visual_C) (C+_Primer) - (Perl_for_dummies,Tcl_Tk) Athletic Apparel Store: (Shoes) (Racket, Racketball) - (Sports_Jacket) Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 29 RegressionlPredict a value of a given continuous valued variable based on the values of other variables,
44、assuming a linear or nonlinear model of dependency.lGreatly studied in statistics, neural network fields.lExamples: Predicting sales amounts of new product based on advetising expenditure. Predicting wind velocities as a function of temperature, humidity, air pressure, etc. Time series prediction of
45、 stock market indices. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 30 Deviation/Anomaly DetectionlDetect significant deviations from normal behaviorlApplications: Credit Card Fraud Detection Network Intrusion DetectionTypical network traffic at University level may reach over 100 mill
46、ion connections per day Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 31 Challenges of Data MininglScalabilitylDimensionalitylComplex and Heterogeneous DatalData QualitylData Ownership and DistributionlPrivacy PreservationlStreaming Data Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 32 Materialsl“Introduction to Data Mining”, Pang-Ning Tan, Michael Steinbach, Vipin Kumarl“Mining Massive Datasets”, Jure Leskovec, Anand Rajaraman, and Jeff Ullman
