Introduction to Data Mining: Concepts and Techniques

Motivation for Data Mining

  • Explosive Growth of Data: Humanity has transitioned from managing terabytes to petabytes of data.
  • Data Sources:
    • Business: E-commerce, stock exchange data, and transaction records.
    • Science: Bioinformatics, remote sensing data, and scientific simulations.
    • Society: Digital cameras, news media, and video platforms like YouTube.
  • Knowledge Gap: The current situation is described as "drowning in data but starving for knowledge."
  • Purpose of Data Mining: It serves as the automated analysis of massive datasets, driven by the principle that "necessity is the mother of invention."

Evolution of Sciences

Scientific inquiry has evolved through four major stages:

  1. Empirical Science (Before 1600): Based on observation and experiment.
  2. Theoretical Science (1600–1950s): Focused on creating theoretical models to generalize understanding and motivate experiments.
  3. Computational Science (1950s–1990s): Focused on simulations where closed-form mathematical solutions were unavailable.
  4. Data Science (1990–Present): Driven by the flood of data from scientific instruments and simulations. It involves scientific information management, acquisition, and visualization task scaling.

History and Evolution of Database Technology

  • 1960s: Development of basic data collection, database creation, IMS, and network DBMS.
  • 1970s: Emergence of the relational data model and RDBMS implementation.
  • 1980s: Rise of RDBMS, advanced data models (object-oriented, deductive, extended-relational), and application-specific DBMS (spatial, scientific).
  • 1990s: Focus on data warehousing, data mining, multimedia databases, and the Web.
  • 2000s: Advancements in stream data management, XML, global information systems, and diverse data mining applications.

Defining Data Mining and the KDD Process

  • Definition: Data mining (also known as knowledge discovery from data) is the extraction of interesting patterns or knowledge from massive datasets. These patterns must be:
    • Non-trivial.
    • Implicit.
    • Previously unknown.
    • Potentially useful.
  • Alternative Names: Knowledge Discovery in Databases (KDD), pattern analysis, business intelligence, data/information harvesting, and data archeology.
  • Exclusions: Simple search results, query processing, and deductive expert systems are not considered data mining.
  • Steps in the KDD Process:
    1. Data Cleaning: Removing noise.
    2. Data Integration: Combining multiple sources.
    3. Data Selection: Retrieving task-relevant data.
    4. Data Transformation: Transforming data into mining-ready forms.
    5. Data Mining: Searching for patterns (the core process).
    6. Pattern Evaluation: Identifying truly interesting patterns.
    7. Knowledge Presentation: Using visualization and representation.

Data Mining as a Confluence of Disciplines

Data mining is a multi-disciplinary field integrating:

  • Database Technology.
  • Statistics.
  • Machine Learning.
  • Pattern Recognition.
  • Algorithm development.
  • Visualization.

Challenges of Traditional Data Analysis

  • Scalability: Algorithms must be highly scalable to handle datasets reaching the petabyte scale.
  • High-Dimensionality: Some data, such as micro-arrays, involve tens of thousands of dimensions.
  • Data Complexity: Includes data streams, sensor data, time-series, temporal data, graphs/social networks, multi-linked data, and heterogeneous legacy databases.

Data Mining Functionalities

Multidimensional Concept Description
  • Characterization: Generalizing and summarizing data.
  • Discrimination: Contrasting different data classes, such as comparing "dry" versus "wet" regions.
Pattern Discovery
  • Association and Correlation: Finding frequent patterns.
    • Example: The relationship between the purchase of diapers and beer (0.5%,75%0.5\%, 75\%).
  • Classification: Building models/functions to describe and distinguish classes for future labels (e.g., classifying cars by gas mileage).
  • Prediction: Predicting unknown numerical values.
  • Cluster Analysis: Grouping data without known class labels. The goal is maximizing intra-class similarity and minimizing inter-class similarity (e.g., house distributions).
  • Outlier Analysis: Identifying exceptions or noise in data, often used in fraud detection.
  • Trend and Evolution Analysis: Includes regression, sequential pattern mining (e.g., buying a camera leads to buying larger memory cards), and periodicity analysis.

Top-10 Most Popular Data Mining Algorithms (ICDM’06)

The final top algorithms selected based on votes at ICDM’06 include:

  1. C4.5: Classification (61 votes).
  2. K-Means: Clustering (60 votes).
  3. SVM (Support Vector Machine): Statistical Learning (58 votes).
  4. Apriori: Association Analysis (52 votes).
  5. EM (Expectation-Maximization): Statistical Learning (48 votes).
  6. PageRank: Link Mining (46 votes).
  7. AdaBoost: Bagging and Boosting (45 votes).
  8. kNN (k-Nearest Neighbors): Classification (45 votes).
  9. Naive Bayes: Classification (45 votes).
  10. CART (Classification and Regression Trees): Classification (34 votes).

Other notable candidates included: HITS, BIRCH, GSP, PrefixSpan, CBA, Finding Reduct (Rough Sets), and gSpan (Graph Mining).

Business Intelligence and Applications

Market Analysis and Management
  • Sources: Credit transactions, loyalty cards, coupons, and customer calls.
  • Tasks: Target marketing, customer profiling, and customer requirement analysis.
Risk Management
  • Resource Planning: Summarizing spending and resource allocation.
  • Asset Evaluation: Cash flow analysis and contingent claim analysis.
  • Competition: Monitoring market directions and class-based pricing strategies.
Fraud Detection
  • Health Care: Identifying unnecessary tests or doctor rings.
  • Finance: Detecting money laundering or credit card fraud.
  • Telecomm: Phone-call fraud models based on destination, duration, and time.
  • Retail: Mitigating dishonest employee behavior (estimated at 38%38\% of retail shrink).

Measuring Pattern "Interestingness"

  • Interestingness Criteria: A pattern is interesting if it is easily understood, valid on test data, useful, novel, or validates a hypothesis.
  • Objective Measures: Based on statistics such as support and confidence.
  • Subjective Measures: Based on user belief, such as unexpectedness and actionability.
  • Interestingness Formulas:
    • Certainty (Confidence): P(A∣B)=#(A and B)#(B)P(A|B) = \frac{\#(A \text{ and } B)}{\#(B)}

Data Mining Query Language (DMQL)

Primitives of a Data Mining Task
  1. Task-relevant data: Identifying databases, tables, and selection conditions.
  2. Knowledge type to be mined: Identifying the specific task (e.g., clustering).
  3. Background knowledge: Concept hierarchies like schema hierarchies (street < city < state) or set-grouping (e.g., {20−39}=young\{20-39\} = \text{young}).
  4. Interestingness measures: Metrics for simplicity, certainty, utility, and novelty.
  5. Presentation: Formats like rules, charts, or tables.
Example DMQL Query
use database AllElectronics_db
use hierarchy location_hierarchy for T.branch, age_hierarchy for C.age
mine classification as promising_customers
in relevance to C.age, C.income, I.type, I.place_made, T.branch
from customer C, item I, transaction T
where I.item_ID = T.item_ID and C.cust_ID = T.cust_ID
  and C.income > 40,000 and I.price > 100
group by T.cust_ID
having sum(I.price) > 1,000
display as rules

System Integration and Architecture

Coupling Categories
  • No Coupling: Processing via flat files.
  • Loose Coupling: Fetching data from DB/DW systems.
  • Semi-tight Coupling: Implementation of specific primitives (sorting, indexing) within the DB system.
  • Tight Coupling: Full integration where mining queries are optimized based on database indices.
Typical Architecture
  • Graphical User Interface (GUI): Handles user interaction and visualization.
  • Pattern Evaluation: Determines interestingness.
  • Data Mining Engine: Core processing module.
  • Database/Data Warehouse Server: Manages data retrieval and integration.
  • Knowledge Base: Background knowledge for the mining process.

Major Issues in Data Mining

  • Methodology: Performance, handling noise, parallel/distributed methods, and knowledge fusion.
  • User Interaction: Ad-hoc mining queries and interactive visualization at multiple levels.
  • Social Impacts: Protecting data security, integrity, and privacy while implementing "invisible" data mining.