DATA WAREHOUSING AND

DATA MINING
[Link] - ARTIFICIAL INTELLIGENCE

(4th Semester)

As Per the Latest Regulations of Manonmaniam Sundaranar University

Syllabus (Regulation -2024 -2025)

ARUNACHALA ARTS & SCIENCE (WOMEN)

COLLEGE

Prepared By
Mrs. Berlin Rose J M.E.,
 UNIT I: Data Warehousing and Online Analytical Processing
Data Warehouse – Major Features of a Data Warehouse – Operational Database
Systems and Data Warehouses – Three-tier Data Warehousing Architecture – Data
Warehouse Models – Extraction, Transformation, and Loading – Metadata Repository
– Multidimensional Data Model – Schemas for Multidimensional Data Models –
Concept Hierarchies – OLAP Operations.
UNIT II: Data Mining Fundamentals
Data Mining – Knowledge Discovery from Databases – Data Objects and Attribute
Types – Mean, Median, and Mode – Range, Quartiles, and Interquartile Range –
Outliers – Variance and Standard Deviation – Data Preprocessing – Major Tasks in Data
Preprocessing – Forms of Data Preprocessing – Data Cleaning – Missing Values –
Noisy Data – Data Cleaning as a Process.
UNIT III: Mining Frequent Patterns, Associations, and Correlations
Market Basket Analysis – Frequent Itemsets, Closed Itemsets, and Association Rules –
Apriori Algorithm – Pattern-Growth Approach for Mining Frequent Itemsets – Mining
Frequent Itemsets Using the Vertical Data Format – Mining Closed and Max Patterns –
Correlation Analysis.
UNIT IV: Classification
Classification – General Approach to Classification – Decision Tree Induction – Basic
Algorithm for Inducing a Decision Tree from Training Tuples – Attribute Selection
Measures: Information Gain – Gain Ratio – Gini Index.
UNIT V: Clustering
Cluster Analysis – Requirements for Cluster Analysis – Overview of Basic Clustering
Methods Partitioning Methods: k-means clustering – k-medoids clustering –
Hierarchical Methods: Agglomerative versus Divisive Hierarchical Clustering –
Balanced Iterative Reducing and Clustering using Hierarchies – Chameleon –
Probabilistic Hierarchical Clustering.
Text Book
1. Jiawei Han, Micheline Kamber and Jian Pei, Data Mining Concepts and
Techniques, Third Edition, Morgan Kaufmann Publishers, 2012.
2. Han and M. Kamber, “Data Mining Concepts and Techniques”, 2001, Harcourt
India Pvt. Ltd, New Delhi.
References Book
1. K.P. Soman, Shyam Diwakar, V. Ajay “Insight into Data Mining Theory and
Practice “, Prentice Hall of India Pvt. Ltd, New Delhi
2. Parteek Bhatia, „Data Mining and Data Warehousing: Principles and Practical
Techniques‟, Cambridge University Press, 2019

1
 UNIT I
Data Warehousing and Online Analytical Processing
Data Warehouse – Major Features of a Data Warehouse – Operational Database
Systems and Data Warehouses – Three-tier Data Warehousing Architecture – Data
Warehouse Models – Extraction, Transformation, and Loading – Metadata Repository
– Multidimensional Data Model – Schemas for Multidimensional Data Models –
Concept Hierarchies – OLAP Operations.

DATA WAREHOUSE
 A data warehouse is a type of data management system that is designed to enable
and support business intelligence (BI) activities, especially analytics.
 A Data Warehouse (DW) is a relational database that is designed for query and
analysis rather than transaction processing.
 It includes historical data derived from transaction data from single and multiple
sources.
 A Data Warehouse provides integrated, enterprise-wide, historical data and
focuses on providing support for decision-makers for data modelling and
analysis.
 A Data Warehouse is a group of data specific to the entire organization, not only
to a particular group of users.
 It is not used for daily operations and transaction processing but used for making
decisions.
 A Data Warehouse can be viewed as a data system with the following attributes:
 It is a database designed for investigative tasks, using data from various
applications.
 It supports a relatively small number of clients with relatively long
interactions.
 It includes current and historical data to provide a historical perspective of
information.
 Its usage is read-intensive.
 It contains a few large tables.

2
MAJOR FEATURES OF A DATA WAREHOUSE

 A data warehouse is a centralized repository for storing and managing large

amounts of data from various sources for analysis and reporting.
 It is optimized for fast querying and analysis, enabling organizations to make
informed decisions by providing a single source of truth for data.
 Data warehousing typically involves transforming and integrating data from
multiple sources into a unified, organized, and consistent format.

Subject-Oriented
 A data warehouse is also subject-oriented, which means that the data is organized
around specific subjects, such as customers, products, or sales.
 This allows for easy access to the data relevant to a specific subject, as well as
the ability to track the data over time.
Integrated
 A data warehouse integrates various heterogeneous data sources like RDBMS,
flat files, and online transaction records.
 It requires performing data cleaning and integration during data warehousing to
ensure consistency in naming conventions, attributes types, etc., among different
data sources.

3
Time-Variant
 A data warehouse is also time-variant, which means that the data is stored with
a time dimension.
 It founds various time limit which are structured between the large datasets and
are held in online transaction process (OLTP).
 The time limits for data warehouse is wide-ranged than that of operational
systems.
 The data resided in data warehouse is predictable with a specific interval of time
and delivers information from the historical perspective.
 Another feature of time-variance is that once data is stored in the data warehouse
then it cannot be modified, alter, or updated.
Non-Volatile
 The data warehouse is a physically separate data storage, which is transformed
from the source operational RDBMS.
 The operational updates of data do not occur in the data warehouse, i.e., update,
insert, and delete operations are not performed.
 It usually requires only two procedures in data accessing: Initial loading of data
and access to data.
 Therefore, the DW does not require transaction processing, recovery, and
concurrency capabilities, which allows for substantial speedup of data retrieval.
 Non-Volatile defines that once entered into the warehouse, and data should not
change.

4
OPERATIONAL DATABASE SYSTEMS AND DATA WAREHOUSES

 The Operational Database is the source of information for the data warehouse.
 It includes detailed information used to run the day to day operations of the
business.
 The data frequently changes as updates are made and reflect the current value of
the last transactions.
 Operational Database Management Systems also called as OLTP (Online
Transactions Processing Databases), are used to manage dynamic data in real-
time.
 Data Warehouse Systems serve users or knowledge workers in the purpose of
data analysis and decision-making.
 Such systems can organize and present information in specific formats to
accommodate the diverse needs of various users.
 These systems are called as Online-Analytical Processing (OLAP) Systems.

5
 Operational Database Data Warehouse

Data warehousing systems are typically

Operational systems are designed to support
designed to support high-volume analytical
high-volume transaction processing.
processing (i.e., OLAP).

Operational systems are usually concerned Data warehousing systems are usually
with current data. concerned with historical data.

Data within operational systems are mainly Non-volatile, new data may be added
updated regularly according to need. regularly. Once Added rarely changed.

It is designed for analysis of business

It is designed for real-time business dealing
measures by subject area, categories, and
and processes.
attributes.

It is optimized for a simple set of It is optimized for extent loads and high,
transactions, generally adding or retrieving a complex, unpredictable queries that access
single row at a time per table. many rows per table.

It is optimized for validation of incoming

Loaded with consistent, valid information,
information during transactions, uses
requires no real-time validation.
validation data tables.

It supports a few concurrent clients relative

It supports thousands of concurrent clients.
to OLTP.

Operational systems are widely process- Data warehousing systems are widely
oriented. subject-oriented

Operational systems are usually optimized Data warehousing systems are usually
to perform fast inserts and updates of optimized to perform fast retrievals of
associatively small volumes of data. relatively high volumes of data.

Data In Data Out

6
 Less Number of data accessed. Large Number of data accessed.

Relational databases are created for on-line Data Warehouse designed for on-line
transactional Processing (OLTP) Analytical Processing (OLAP)

THREE-TIER DATA WAREHOUSING ARCHITECTURE

 The three-tier architecture consists of the source layer (containing multiple

source system),
 The reconciled layer and the data warehouse layer (containing both data
warehouses and data marts).
 The reconciled layer sits between the source data and data warehouse.
 The main advantage of the reconciled layer is that it creates a standard reference
data model for a whole enterprise.
 At the same time, it separates the problems of source data extraction and
integration from those of data warehouse population.
 In some cases, the reconciled layer is also directly used to accomplish better
some operational tasks, such as producing daily reports that cannot be
satisfactorily prepared using the corporate applications or generating data flows
to feed external processes periodically to benefit from cleaning and integration.
 Data Warehouses usually have a three-level (tier) architecture that includes:

1. Bottom Tier (Data Warehouse Server)

2. Middle Tier (OLAP Server)
3. Top Tier (Front end Tools)

Bottom Tier (Data Warehouse Server)

 A bottom-tier that consists of the Data Warehouse server, which is almost
always an RDBMS.
 It may include several specialized data marts and a metadata repository.

7
  Data from operational databases and external sources (such as user profile data
provided by external consultants) are extracted using application program
interfaces called a gateway.
 A gateway is provided by the underlying DBMS and allows customer programs
to generate SQL code to be executed at a server.

Middle Tier (OLAP Server)

 A middle-tier which consists of an OLAP server for fast querying of the data
warehouse.
 The OLAP server is implemented using either
1. A Relational OLAP (ROLAP) model, i.e., an extended
relational DBMS that maps functions on multidimensional
data to standard relational operations.
2. A Multidimensional OLAP (MOLAP) model, i.e., a
particular purpose server that directly implements
multidimensional information and operations.
8
Top Tier (Front end Tools)
 A top-tier that contains front-end tools for displaying results provided by
OLAP, as well as additional tools for data mining of the OLAP-generated data.
 The metadata repository stores information that defines DW objects.
 It includes the following parameters and information for the middle and the top-
tier applications:

1. A description of the DW structure, including the warehouse schema, dimension,

hierarchies, data mart locations, and contents, etc.
2. Operational metadata, which usually describes the currency level of the stored
data, i.e., active, archived or purged, and warehouse monitoring information, i.e.,
usage statistics, error reports, audit, etc.
3. System performance data, which includes indices, used to improve data access
and retrieval performance.
4. Information about the mapping from operational databases, which provides
source RDBMSs and their contents, cleaning and transformation rules, etc.
5. Summarization algorithms, predefined queries, and reports business data, which
include business terms and definitions, ownership information, etc.
DATA WAREHOUSE MODELS

 Data modelling refers to the process of handling and designing the data model
within a data warehouse platform.
 It consists of making an appropriate database schema so as to transfer the data
that can be stored and of useful to user.
 Data warehouse modeling is used for two reasons, first is that relationship within
the warehouse data can be visualised through the schema
 Second is that the cost is reduced and efficiency is increased with the help of
well-designed schema which allow effective data warehouse structure to occur.
 Data warehouse modeling is the process of designing the schemas of the detailed
and summarized information of the data warehouse.

9
  The goal of data warehouse modeling is to develop a schema describing the
reality, or at least a part of the fact, which the data warehouse is needed to
support.

Types of Data Warehouse Models

10
 Figure: A recommended approach for data warehouse development

Enterprise Warehouse
 An Enterprise warehouse collects all of the records about subjects spanning the
entire organization.
 It supports corporate-wide data integration, usually from one or more operational
systems or external data providers, and it's cross-functional in scope.
 It generally contains detailed information as well as summarized information and
can range in estimate from a few gigabyte to hundreds of gigabytes, terabytes,
or beyond.
 An enterprise data warehouse may be accomplished on traditional mainframes,
UNIX super servers, or parallel architecture platforms.
 It required extensive business modeling and may take years to develop and build.

11
Data Mart
 A data mart includes a subset of corporate-wide data that is of value to a specific
collection of users.
 The scope is confined to particular selected subjects.
 For example, a marketing data mart may restrict its subjects to the customer,
items, and sales.
 The data contained in the data marts tend to be summarized.
Data Marts is divided into two parts:
 Independent Data Mart: Independent data mart is sourced from data
captured from one or more operational systems or external data providers, or
data generally locally within a different department or geographic area.
 Dependent Data Mart: Dependent data marts are sourced exactly from
enterprise data-warehouses.
Virtual Warehouses
 Virtual Data Warehouses is a set of perception over the operational database.
 For effective query processing, only some of the possible summary vision may
be materialized.
 A virtual warehouse is simple to build but required excess capacity on
operational database servers.
EXTRACTION, TRANSFORMATION, AND LOADING

 The mechanism of extracting information from source systems and bringing it

into the data warehouse is commonly called ETL, which stands for Extraction,
Transformation and Loading.
 The ETL process requires active inputs from various stakeholders, including
developers, analysts, testers, top executives and is technically challenging.
 To maintain its value as a tool for decision-makers, Data warehouse technique
needs to change with business changes.

12
How ETL Works?
ETL consists of three separate phases:

Extraction:
 The first step of the ETL process is extraction.
 In this step, data from various source systems is extracted which can be in various
formats like relational databases, No SQL, XML, and flat files into the staging
area.

13
  It is important to extract the data from various source systems and store it into
the staging area first and not directly into the data warehouse because the
extracted data is in various formats and can be corrupted also.
 Hence loading it directly into the data warehouse may damage it and rollback
will be much more difficult.
 Therefore, this is one of the most important steps of ETL process.
Transformation:
 The second step of the ETL process is transformation.
 In this step, a set of rules or functions are applied on the extracted data to convert
it into a single standard format. It may involve following processes/tasks:
 Filtering – loading only certain attributes into the data warehouse.
 Cleaning – filling up the NULL values with some default values,
mapping U.S.A, United States, and America into USA, etc.
 Joining – joining multiple attributes into one.
 Splitting – splitting a single attribute into multiple attributes.
 Sorting – sorting tuples on the basis of some attribute (generally key-
attribute).
Loading:
 The third and final step of the ETL process is loading.
 In this step, the transformed data is finally loaded into the data warehouse.
 Sometimes the data is updated by loading into the data warehouse very
frequently and sometimes it is done after longer but regular intervals.
 The rate and period of loading solely depends on the requirements and varies
from system to system.
Advantages of ETL process in data warehousing:
 Improved data quality: ETL process ensures that the data in the data warehouse
is accurate, complete, and up-to-date.
 Better data integration: ETL process helps to integrate data from multiple
sources and systems, making it more accessible and usable.

14
  Increased data security: ETL process can help to improve data security by
controlling access to the data warehouse and ensuring that only authorized users
can access the data.
 Improved scalability: ETL process can help to improve scalability by providing
a way to manage and analyze large amounts of data.
 Increased automation: ETL tools and technologies can automate and simplify
the ETL process, reducing the time and effort required to load and update data
in the warehouse.
Disadvantages of ETL process in data warehousing:
 High cost: ETL process can be expensive to implement and maintain, especially
for organizations with limited resources.
 Complexity: ETL process can be complex and difficult to implement, especially
for organizations that lack the necessary expertise or resources.
 Limited flexibility: ETL process can be limited in terms of flexibility, as it may
not be able to handle unstructured data or real-time data streams.
 Limited scalability: ETL process can be limited in terms of scalability, as it may
not be able to handle very large amounts of data.
 Data privacy concerns: ETL process can raise concerns about data privacy, as
large amounts of data are collected, stored, and analyzed.
METADATA REPOSITORY
 A metadata repository is a database or other storage mechanism that is used to
store metadata about data.
 A metadata repository can be used to manage, organize, and maintain metadata
in a consistent and structured manner, and can facilitate the discovery, access,
and use of data.
 A metadata repository may contain metadata about a variety of types of data,
such as documents, images, audio and video files, and other types of digital
content.

15
  The metadata in a metadata repository may include information about the
content, format, structure, and other characteristics of data, and may be organized
using metadata standards and schemas.
 There are many types of metadata repositories, ranging from simple file systems
or spreadsheets to complex database systems.
 The choice of metadata repository will depend on the needs and requirements
of the organization, as well as the size and complexity of the data that is being
managed.
 Metadata repositories can be used in a variety of contexts, such as libraries,
museums, archives, and online platforms.
 They can be used to improve the discoverability and ranking of content in search
engines, and to provide context and additional information about search results.
 Metadata repositories support data governance by detailing data ownership,
usage, and access controls.
 They also enhance interoperability by describing data content, format, and
structure, enabling seamless exchange between systems and applications.
 Metadata repositories support data preservation by detailing context,
provenance, and preservation needs.
 They also aid visualization by describing data structure and content, enabling
interactive and customizable visualizations.
Benefits of Metadata Repository
1. It provides a set of tools for enterprise-wide metadata management.
2. It eliminates and reduces inconsistency, redundancy, and underutilization.
3. It improves organization control, simplifies management, and accounting of
information assets.
4. It increases coordination, understanding, identification, and utilization of
information assets.
5. It enforces CASE development standards with the ability to share and reuse
metadata.
6. It leverages investment in legacy systems and utilizes existing applications.
7. It provides a relational model for heterogeneous RDBMS to share information.
16
 8. It gives useful data administration tool to manage corporate information assets
with the data dictionary.
9. It increases reliability, control, and flexibility of the application development
process.
MULTIDIMENSIONAL DATA MODEL

 The multi-Dimensional Data Model is a method which is used for ordering data
in the database along with good arrangement and assembling of the contents in
the database.
 The Multi Dimensional Data Model allows customers to interrogate analytical
questions associated with market or business trends, unlike relational databases
which allow customers to access data in the form of queries.
 They allow users to rapidly receive answers to the requests which they made by
creating and examining the data comparatively fast.
 OLAP (online analytical processing) and data warehousing uses multi
dimensional databases.
 It is used to show multiple dimensions of the data to users.
 It represents data in the form of data cubes.
 Data cubes allow to model and view the data from many dimensions and
perspectives.
 It is defined by dimensions and facts and is represented by a fact table.
 Facts are numerical measures and fact tables contain measures of the related
dimensional tables or names of the facts.

17
Stage 1 : Assembling data from the client :
 In first stage, a Multi Dimensional Data Model collects correct data from the
client.
 Mostly, software professionals provide simplicity to the client about the range of
data which can be gained with the selected technology and collect the complete
data in detail.
Stage 2 : Grouping different segments of the system :
 In the second stage, the Multi Dimensional Data Model recognizes and classifies
all the data to the respective section they belong to and also builds it problem-
free to apply step by step.
Stage 3 : Noticing the different proportions :
 In the third stage, it is the basis on which the design of the system is based.
 In this stage, the main factors are recognized according to the user’s point of
view.
 These factors are also known as “Dimensions”.
Stage 4 : Preparing the actual-time factors and their respective qualities :
 In the fourth stage, the factors which are recognized in the previous step are used
further for identifying the related qualities.
 These qualities are also known as “attributes” in the database.
Stage 5 : Assessing the Validity and Quality of Listed Factors
 In the fifth stage, A Multi Dimensional Data Model separates and differentiates
the actuality from the factors which are collected by it.
 These actually play a significant role in the arrangement of a Multi Dimensional
Data Model.
Stage 6 : Designing a Schema Based on Collected Data
 In the sixth stage, on the basis of the data which was collected previously, a
Schema is built.

18
SCHEMAS FOR MULTIDIMENSIONAL DATA MODELS
 Multidimensional data models are designed to support analytical processing,
typically used in data warehousing and business intelligence.
 These models organize data into schemas to facilitate efficient querying and
analysis.
 The most common schema types include:
1. Star Schema
o Central Fact Table: Contains quantitative metrics (measures) and foreign
keys referencing dimension tables.
o Dimension Tables: Provide descriptive attributes (dimensions) for
analysis, such as time, location, and product details.
o Simple structure with a single-layer design, optimizing for query
performance.

2. Snowflake Schema
o Normalized Dimension Tables: Dimension tables are further broken into
related sub-tables to reduce redundancy.
o More complex than star schema but requires less storage due to
normalization.
o Useful for complex hierarchies and minimizing update anomalies.

19
 3. Galaxy Schema (Fact Constellation)
o Multiple Fact Tables: Shares dimension tables among different fact
tables.
o Supports complex scenarios involving multiple business processes or
subject areas.
o Suitable for large-scale, integrated data warehousing environments.

CONCEPT HIERARCHIES
 Concept hierarchies are a foundational element in data warehousing and
multidimensional data models, facilitating data abstraction and analysis.
 They organize data into multiple levels of granularity, allowing users to navigate
and analyze information at varying depths.
20
  A concept hierarchy represents a series of mappings from a set of low-level
concepts to larger-level, more general concepts.
 Concept hierarchy organizes information or concepts in a hierarchical structure
or a specific partial order, which are used for defining knowledge in brief, high-
level methods, and creating possible mining knowledge at several levels of
abstraction.
Hierarchical Organization
 Concept hierarchies define a top-down or bottom-up relationship between
higher-level (general) and lower-level (detailed) concepts.
 Example: Country → State → City → Neighborhood.
Levels of Granularity
 Support data abstraction by representing data at different levels of detail.
 Enable operations like drill-down (move to finer details) and roll-up (aggregate
data to a higher level).
Dynamic Aggregation
 Facilitate on-the-fly summarization of data for meaningful analysis, e.g.,
calculating total sales at the city, state, or country level.
Types of Concept Hierarchies
Schema Hierarchy –
 Schema hierarchy represents the total or partial order between attributes in the
database.
 It can define existing semantic relationships between attributes.
 In a database, more than one schema hierarchy can be generated by using
multiple sequences and grouping of attributes.
Set-Grouping Hierarchy –
 A set-grouping hierarchy constructs values for a given attribute or dimension
into groups or constant range values.
 It is also known as instance hierarchy because the partial series of the hierarchy
is represented on the set of instances or values of an attribute.
 These hierarchies have more functional sense and are so approved than other
hierarchies.

21
Operation-Derived Hierarchy –
 Operation-derived hierarchy is represented by a set of operations on the data.
 These operations are defined by users, professionals, or the data mining system.
 These hierarchies are usually represented for mathematical attributes.
 Such operations can be as easy as range value comparison, as difficult as a data
clustering and data distribution analysis algorithm.
Rule-based Hierarchy –
 A rule-based hierarchy is a type of concept hierarchy constructed using
predefined rules or conditions that define relationships between different levels
of data.
 It is commonly employed in data warehousing, OLAP systems, and knowledge
discovery to organize and analyze data efficiently.
OLAP OPERATIONS
 Online Analytical Processing (OLAP) operations enable multidimensional
analysis of data in data warehouses, facilitating deep insights for decision-
making.
 These operations allow users to explore data interactively from different
perspectives and levels of detail.
 Here is the list of OLAP operations
 Roll-up
 Drill-down
 Slice and dice
 Pivot (rotate)
Roll-Up
 Aggregates data to a higher level of granularity.
 Example: Summarizing sales data from the daily level to the monthly or yearly
level.
 Achieved by climbing up a concept hierarchy (e.g., City → State → Country).

22
Drill-Down
 Opposite of roll-up, providing more detailed data by moving to a lower level of
granularity.
 Example: Breaking down yearly sales data into monthly or daily data.
 Performed by descending a concept hierarchy or introducing additional
attributes.

Slice
 Extracts a subset of the data by filtering on a single dimension.
 Example: Viewing sales data for the year 2023 only.

23
 Result is a "slice" of the multidimensional cube.

 Here Slice is performed for the dimension "time" using the criterion time = "Q1".
 It will form a new sub-cube by selecting one or more dimensions.
Dice
 Extracts a subset of data by applying filters on multiple dimensions.
 Example: Viewing sales data for 2023 in the "Electronics" category and the
"North America" region.
 Produces a smaller cube containing only the filtered data.

 (location = "Toronto" or "Vancouver")

 (time = "Q1" or "Q2")
 (item =" Mobile" or "Modem")

24
Pivot (Rotate)
 Reorients the data cube for a different perspective.
 Example: Changing the view from "Product by Region" to "Region by Product."
 Helps in exploring relationships and patterns in the data.

Drill-Across
 Combines data from multiple fact tables within the same cube.
 Example: Analyzing correlations between sales data and customer demographic
data.
Drill-Through
 Navigates from aggregated data in the cube to its underlying transactional data
in the database.
 Example: Viewing individual sales transactions that contribute to monthly sales
totals.

25
 UNIT II
Data Mining Fundamentals
Data Mining – Knowledge Discovery from Databases – Data Objects and Attribute
Types – Mean, Median, and Mode – Range, Quartiles, and Interquartile Range –
Outliers – Variance and Standard Deviation – Data Preprocessing – Major Tasks in Data
Preprocessing – Forms of Data Preprocessing – Data Cleaning – Missing Values –
Noisy Data – Data Cleaning as a Process.
DATA MINING
 Data mining is the process of extracting knowledge or insights from large
amounts of data using various statistical and computational techniques.
 The data can be structured, semi-structured or unstructured, and can be stored in
various forms such as databases, data warehouses, and data lakes.
 Data mining is the act of automatically searching for large stores of information
to find trends and patterns that go beyond simple analysis procedures.
 Data mining utilizes complex mathematical algorithms for data segments and
evaluates the probability of future events.
 Data Mining is also called Knowledge Discovery of Data (KDD).

26
Types of Data Mining
Relational Database
 A relational database is a collection of multiple data sets formally organized by
tables, records, and columns from which data can be accessed in various ways
without having to recognize the database tables.
 Tables convey and share information, which facilitates data searchability,
reporting, and organization.
Data warehouses:
 A Data Warehouse is the technology that collects the data from various sources
within the organization to provide meaningful business insights.
 The huge amount of data comes from multiple places such as Marketing and
Finance.
 The extracted data is utilized for analytical purposes and helps in decision-
making for a business organization.
 The data warehouse is designed for the analysis of data rather than transaction
processing.
Data Repositories:
 The Data Repository generally refers to a destination for data storage.
 However, many IT professionals utilize the term more clearly to refer to a
specific kind of setup within an IT structure.
 For example, a group of databases, where an organization has kept various kinds
of information.
Object-Relational Database:
 A combination of an object-oriented database model and relational database
model is called an object-relational model.
 It supports Classes, Objects, Inheritance, etc.
Transactional Database:
 A transactional database refers to a database management system (DBMS) that
has the potential to undo a database transaction if it is not performed
appropriately.

27
  Even though this was a unique capability a very long while back, today, most of
the relational database systems support transactional database activities.
Advantages
-making

ion support in healthcare

Disadvantages

KNOWLEDGE DISCOVERY FROM DATABASES

 Knowledge Discovery from Databases (KDD) is the overall process of
identifying valid, novel, and useful patterns from large datasets.
 It encompasses the entire process of data mining, from data collection to the final
extraction of knowledge, and includes several stages to ensure that the results are
valuable and applicable.
 The process begins with determining the KDD objectives and ends with the
implementation of the discovered knowledge.
 At that point, the loop is closed, and the Active Data Mining starts. Subsequently,
changes would need to be made in the application domain.
 For example, offering various features to cell phone users in order to reduce
churn.
 This closes the loop, and the impacts are then measured on the new data
repositories, and the KDD process again.

28
Data Selection
Identify and collect the relevant data from the dataset for analysis.

Data Preprocessing (Cleaning and Integration)

 Clean the data by removing errors, duplicates, and inconsistencies.
 Integrate data from multiple sources if needed.
 Example: Handling missing values or merging customer data from different
branches.
Data Transformation
 Format the data into a structure suitable for mining (e.g., normalizing or
aggregating).
 Example: Converting textual data into numerical form for analysis.
Data Mining
 Apply algorithms and techniques to identify patterns, trends, or relationships.
 Example: Using clustering to group customers by purchasing habits.
Pattern Evaluation
 Evaluate the discovered patterns to ensure they are meaningful and useful.
 Example: Discarding patterns with low statistical significance.

29
Knowledge Representation
 Present the discovered knowledge in an understandable format, such as graphs,
charts, or reports.
 Example: A report showing customer segments with visualizations.
DATA OBJECTS AND ATTRIBUTE TYPES
Data Object
 Data objects are the entities or items in a dataset that you analyze.
 Each data object is described by a set of attributes.
Eg:
customer in a retail dataset (attributes: name, age, purchase history).
product in an inventory dataset (attributes: product ID, price, category).
Types of Data Objects:
1. Records: Data objects organized as rows in a database or table.
o Example: Customer records in a CRM system.
2. Images, Videos, and Multimedia: Non-tabular objects, such as pictures or
videos.
o Example: Medical imaging data.
3. Graphs or Networks: Data represented as nodes and edges.
o Example: Social networks or road maps.
4. Time-Series Data: Sequences of data points ordered by time.
o Example: Stock prices or weather patterns.
Attribute Types
 Attribute data is defined as a type of data that can be used to describe or quantify
an object or entity.
 Attribute values are numbers or symbols assigned to an attribute.
 The type of the attribute can be determined based on the assigned value.

30
Nominal Attributes
 The values of a nominal attribute are symbols or names of things. Each value
represents some kind of category, code, or state.
 Nominal attributes are also referred to as Qualitative and Categorical attributes.
 The values of nominal attributes do not have any meaningful order.
Example
Attributes Possible Values
hair_color black, brown, red, green, and so on.
marital_status single, married, divorced, and widowed.
occupation teacher, doctor, farmer, student and so on.
 The nominal attribute values do not have any meaningful order about them and
they are not quantitative.
 It makes no sense to find the mean (average) value or median (middle) value for
such an attribute.
 However, we can find the attribute’s most commonly occurring value (mode)
Binary Attributes
 A binary attribute is a special nominal attribute with only two states: 0 or 1.
Where 0 typically means that the attribute is absent, and 1 means that it is present.
Symmetric Binary Attribute
 A binary attribute is symmetric if both of its states are equally valuable and carry
the same weight.
Example: the attribute gender having the states male and female.

31
Asymmetric Binary Attribute
 A binary attribute is asymmetric if the outcomes of the states are not equally
important.
Example: Test results for COVID patient: Positive (1) and Negative (0).
 By convention, we code the most important outcome, which is usually the rarest
one, by 1 (e.g., COVID positive) and the other by 0 (e.g., COVID negative).
Ordinal Attributes
 An ordinal attribute is an attribute with possible values that have a meaningful
order or ranking among them, but the magnitude between successive values is
not known.
 Ordinal attributes are also referred to as Qualitative and Categorical attributes.
Example: An ordinal attribute drink_size corresponds to the size of drinks available at
a fast-food restaurant.
 This attribute has three possible values: small, medium, and large.
 The values have a meaningful sequence (which corresponds to increasing drink
size);
Interval-Scaled Attributes
 Interval-scaled attributes are measured on a scale of equal-size units.
 The values of interval-scaled attributes have order and can be positive, 0, or
negative.
 We can compare and quantify the difference between values of interval
attributes.
Examples:
A temperature attribute is an interval attribute.
 We can quantify the difference between values.
 For example, a temperature of 20oC is five degrees higher than a temperature of
15oC.
Calendar dates is another example for an interval attribute.
 Temperatures in Celsius do not have a true zero point, that is, 0oC does not
indicate “no temperature.”

32
  Calendar dates do not have a true zero point, that is, the year 0 not the beginning
of the time.
 Although we can compute the difference between temperature values, we cannot
talk of one temperature value as being a multiple of another.
 Without a true zero, we cannot say, for instance, that 10oC is twice as warm as
5oC.
 That is, we cannot speak of the values in terms of ratios.
 The central tendency of an interval attribute can be represented by its mode, its
median (middle value in an ordered sequence), and its mean Data.
Ratio Attribute
 A ratio attribute is a numeric attribute with an inherent zero point.
Examples:
 number_of_words in a documents object.
 count attribute such as years of experience for employee object.
 Attributes to measure weight, height, latitude, and longitude coordinates.
 With an amount attribute we can say “you are 100 times richer with $100 than
with $1”.
MEAN, MEDIAN, AND MODE
 Mean, median, and mode are measures of central tendency used in statistics to
summarize a set of data.
 Mean (x̅ or μ):
 The mean, or arithmetic average, is calculated by summing all the
values in a dataset and dividing by the total number of values.
 It’s sensitive to outliers and is commonly used when the data is
symmetrically distributed.
 Median (M):
 The median is the middle value when the dataset is arranged in ascending
or descending order.
 If there’s an even number of values, it’s the average of the two middle
values.
 The median is robust to outliers and is often used when the data is skewed.
33
  Mode (Z):
 The mode is the value that occurs most frequently in the dataset.
 Unlike the mean and median, the mode can be applied to both numerical
and categorical data.
 It’s useful for identifying the most common value in a dataset.
MEAN
 Mean is the sum of all the values in the data set divided by the number of values
in the data set.
 It is also called the Arithmetic Average. Mean is denoted as x̅ and is read as x
bar.
 The formula to calculate the mean is:
Mean (x̅) = Sum of Values / Number of Values
 If x1, x2, x3,……, xn are the values of a data set then the mean is calculated as:
x̅ = (x1 + x2 + x3 + . . . + xn) / n
Example: Find the mean of data sets 10, 30, 40, 20, and 50.
Solution:
Mean of the data 10, 30, 40, 20, 50 is
Mean = (sum of all values) / (number of values)
Mean = (10 + 30 + 40 + 20+ 50) / 5 = 30
MEDIAN
 A Median is a middle value for sorted data.
 The sorting of the data can be done either in ascending order or descending order.
 A median divides the data into two equal halves.
 The formula to calculate the median of the number of terms if the number of
terms is even is shown in below:

34
  The formula to calculate the median of the number of terms if the number of
terms is odd is shown in the image below:

Example: Find the median of given data set 30, 40, 10, 20, and 50.
Solution:
Median of the data 30, 40, 10, 20, 50 is,
Step 1: Order the given data in ascending order as:
10, 20, 30, 40, 50
Step 2: Check n (number of terms of data set) is even or odd and find the median of the
data with respective ‘n’ value.
Step 3: Here, n = 5 (odd)
Median = [(n + 1)/2]th term
Median = [(5 + 1)/2]th term
= 30
MODE
 A mode is the most frequent value or item of the data set.
 A data set can generally have one or more than one mode value.
 If the data set has one mode then it is called “Uni-modal”.
 Similarly, If the data set contains 2 modes then it is called “Bimodal” and if the
data set contains 3 modes then it is known as “Trimodal”.
 If the data set consists of more than one mode then it is known as “multi-
modal”(can be bimodal or trimodal).
 There is no mode for a data set if every number appears only once.
 In statistical notation, the symbol “Z” is commonly used to represent the mode
of a dataset.
 It indicates the value or values that occur most frequently within the dataset.

35
  This symbol is widely utilised in statistical discourse to signify the mode,
enhancing clarity and precision in statistical discussions and analyses.
Mode Formula
Mode = Highest Frequency Term
Example: Find the mode of the given data set 1, 2, 2, 2, 3, 3, 4, 5.
Solution:
Given set is {1, 2, 2, 2, 3, 3, 4, 5}
 As the above data set is arranged in ascending order.
 By observing the above data set we can say that,
Mode = 2
 As, it has highest frequency (3)

RANGE, QUARTILES, AND INTERQUARTILE RANGE

 These three measures are used to analyze data spread, detect variability, and
identify outliers in datasets.
 They are particularly useful in data preprocessing, exploration, and cleaning
during data mining.
Range
 The range is the simplest measure of data spread.
 It calculates the difference between the maximum and minimum values in a
dataset.
Formula:
Range=Maximum value−Minimum value

36
Characteristics:
 Measures the total spread of data.
 Provides a quick understanding of variability in a dataset.
 Sensitive to outliers because extreme values directly influence the range.
Example:
For the dataset [3,7,10,15,20]
 Maximum = 20, Minimum = 3
Range=20−3=17
Applications in Data Mining:
 Used in exploratory data analysis (EDA) to quickly identify the spread of the
data.
 Helps to flag potential outliers (e.g., extreme highs or lows).
 Supports initial data cleaning by understanding data variability.
Quartiles
 Quartiles divide a sorted dataset into four equal parts, where each part represents
25% of the data.
 Quartiles provide detailed insights into how the data is distributed.
Key Quartiles:
1. Q1 (First Quartile):
o Represents the 25th percentile (25% of the data lies below Q1).
2. Q2 (Second Quartile):
o The 50th percentile (the median); 50% of data lies below Q2.
3. Q3 (Third Quartile):
o Represents the 75th percentile (75% of the data lies below Q3).
How to Calculate Quartiles:
1. Sort the dataset.
2. Find the median (Q2).
3. Split the data below and above the median to find Q1 and Q3.
Example:
For the dataset [2,4,6,8,10,12,14]
 Q1 = 4 (25% of data is below 4)

37
  Q2 = 8 (Median of the dataset)
 Q3 = 12 (75% of data is below 12)
Applications in Data Mining:
 Quartiles are used to understand data distribution and detect skewness.
 Crucial in visualizations like box plots, which display data spread and highlight
outliers.
 Helps identify the central tendency and spread of skewed data.
Interquartile Range (IQR)
 The Interquartile Range (IQR) measures the spread of the middle 50% of the
data.
 It is the difference between the third quartile (Q3) and the first quartile (Q1).
Formula:
IQR=Q3−Q1
Characteristics:
 IQR is resistant to outliers because it focuses on the central part of the data.
 Helps identify the range within which most values lie.
Outlier Detection Using IQR:
 A value is considered an outlier if it lies:
Below Q1−1.5×IQR or Above Q3+1.5×IQR
Example:
For the dataset [2,4,6,8,10,12,14]
 Q1 = 4, Q3 = 12
IQR=Q3−Q1=12−4=8
To detect outliers:
 Lower limit = Q1−1.5×IQR=4−(1.5×8)=−8
 Upper limit = Q3+1.5×IQR=12+(1.5×8)=24
 Thus, any value outside [−8,24] is an outlier.
Applications in Data Mining:
 Outlier Detection: IQR is widely used for identifying anomalies in the data.
 Skewed Data Analysis: IQR works well for non-normal data distributions.

38
  Data Preprocessing: Helps in removing or flagging outliers before model
building.
 Box Plot Visualization: IQR is a key component for creating box plots to
visualize data variability and outliers.

Real-World Applications in Data Mining

1. Outlier Detection:
o IQR is commonly used to detect anomalies in financial data, fraud
detection, or sensor data analysis.
2. Data Cleaning:
o Remove extreme values that can distort results in machine learning
models.
3. Exploratory Data Analysis (EDA):
o Use range, quartiles, and IQR to summarize and visualize data variability.

39
 4. Healthcare Analytics:
o Analyze patient vitals like blood pressure or cholesterol levels to detect
abnormal readings.
5. Income Distribution Analysis:
o Quartiles and IQR are used to analyze skewed income levels, where a
small group earns exceptionally high amounts.

OUTLIERS
 Outlier is a data object that deviates significantly from the rest of the data objects
and behaves in a different manner.
 They can be caused by measurement or execution errors.
 The analysis of outlier data is referred to as outlier analysis or outlier mining.
 An outlier cannot be termed as a noise or error
Types of Outliers
Outliers are divided into three different types

1. Global or point outliers

2. Collective outliers
3. Contextual or conditional outliers

40
Global Outliers
 Global outliers are also called point outliers.
 Global outliers are taken as the simplest form of outliers.
 When data points deviate from all the rest of the data points in a given data set,
it is known as the global outlier.
 In most cases, all the outlier detection procedures are targeted to determine the
global outliers.
 The green data point is the global outlier.

Collective Outliers
 In a given set of data, when a group of data points deviates from the rest of the
data set is called collective outliers.
 Here, the particular set of data objects may not be outliers, but when you
consider the data objects as a whole, they may behave as outliers.
 To identify the types of different outliers, you need to go through background
information about the relationship between the behavior of outliers shown by
different data objects.
 For example, in an Intrusion Detection System, the DOS package from one
system to another is taken as normal behavior.
 Therefore, if this happens with the various computer simultaneously,
 It is considered abnormal behavior, and as a whole, they are called collective
outliers.
 The green data points as a whole represent the collective outlier.

41
Contextual Outliers
 As the name suggests, "Contextual" means this outlier introduced within a
context.
 For example, in the speech recognition technique, the single background noise.
Contextual outliers are also known as Conditional outliers.
 These types of outliers happen if a data object deviates from the other data points
because of any specific condition in a given data set.
 As we know, there are two types of attributes of objects of data: contextual
attributes and behavioral attributes.
 Contextual outlier analysis enables the users to examine outliers in different
contexts and conditions, which can be useful in various applications.
 For example, A temperature reading of 45 degrees Celsius may behave as an
outlier in a rainy season.
 Still, it will behave like a normal data point in the context of a summer season.
 In the given diagram, a green dot representing the low-temperature value in June
is a contextual outlier since the same value in December is not an outlier.

42
VARIANCE AND STANDARD DEVIATION
 Variance and Standard Deviation are the important measures used in
Mathematics and Statics to find the meaning from a large set of data.
 The different formulas for Variance and Standard Deviation are highly used in
mathematics to determine the trends of various values in mathematics.
 Variance is the measure of how the data points vary according to the mean while
standard deviation is the measure of the central tendency of the distribution of
the data.
Variance
 Variance is defined as, “The measure of how far the set of data is dispersed from
their mean value”.
 Variance is represented with the symbol σ2.
 In other words, we can also say that the variance is the average of the squared
difference from the mean.
Properties of Variance
Various properties of the Variance of the group of data are,
 As each term in the variance formula is firstly squared and then their mean is
found, it is always a non-negative value,
 i.e. mean can be either positive or can be zero but it can never be negative.
 Variance is always measured in squared units.
 For example, if we have to find the variance of the height of the student in a
class,
 If the height of the student is given in cm then the variance is calculated in cm2.
Variance Formula
There are two formulas for Variance, that are:
 Population Variance
 Sample Variance
Formula for Population Variance
The mathematical formula to find the variance of the given data is,

43
 Where,
 σ2 is the Variance of the Population,
 N is the Number of Observation in the Population,
 Xi is the ith observation in the Population, and
 x̄ is the mean of the Population.
 This formula is also called the Population variance formula as it is used
for finding the variation in the population data.
Standard Deviation
 In data mining, standard deviation is a key statistical measure that plays a
significant role in analyzing and understanding data variability. It
 measures the dispersion or spread of data points around the mean (average).
 A low standard deviation indicates that the data points are close to the mean,
whereas a high standard deviation suggests that the data points are more spread
out.
 Also define the standard deviation as the square root of the variance.
Properties of Standard Deviation
Data Distribution Understanding
 Standard deviation helps determine the shape and spread of the data, allowing
analysts to decide which algorithms or models are most suitable for analysis.
Outlier Detection
 Outliers significantly impact the standard deviation.
 By identifying large deviations from the mean, standard deviation helps detect
anomalies,

44
  which is critical for fraud detection, network intrusion detection, or health data
analysis.
Feature Scaling and Normalization
 Many machine learning algorithms require normalized data, and standard
deviation is used to rescale features (e.g., Z-score normalization).
Clustering and Segmentation
 In clustering algorithms like K-Means, standard deviation determines the
compactness of clusters and the distance of data points from the cluster centers.
Risk Assessment
 In domains like finance, standard deviation measures volatility and risk by
analyzing the fluctuation of data over time.
Noise Identification
 Standard deviation helps distinguish between natural variability in data and noisy
data.
DATA PREPROCESSING
 Data processing is collecting raw data and translating it into usable information.
 The raw data is collected, filtered, sorted, processed, analyzed, stored, and then
presented in a readable format.
 It is usually performed in a step-by-step process by a team of data scientists and
data engineers in an organization.
 The data processing is carried out automatically or manually.
 Nowadays, most data is processed automatically with the help of the computer,
which is faster and gives accurate results.
 Thus, data can be converted into different forms.
 It can be graphic as well as audio ones. It depends on the software used as well
as data processing methods.
 After that, the data collected is processed and then translated into a desirable
form as per requirements, useful for performing tasks.
 The data is acquired from Excel files, databases, text file data, and unorganized
data such as audio clips, images, GPRS, and video clips.

45
  Data processing is crucial for organizations to create better business strategies
and increase their competitive edge.
 By converting the data into a readable format like graphs, charts,
and documents, employees throughout the organization can understand and use
the data.
MAJOR TASKS IN DATA PREPROCESSING / FORMS OF DATA
PREPROCESSING
 Data preprocessing is an important process of data mining.
 In this process, raw data is converted into an understandable format and made
ready for further analysis.
 The motive is to improve data quality and make it up to mark for specific tasks.

Data Cleaning –
 Data cleaning routines operate to “clean” the information by filling in missing
values, smoothing noisy information, identifying or eliminating outliers, and
resolving deviation.
 If users understand the data are dirty, they are unlikely to trust the results of some
data mining that has been used.

46
  Moreover, dirty data can make confusion for the mining phase, resulting in
unstable output.
 Some mining routines have some phase for dealing with incomplete or noisy
information, they are not always potent.
 Instead, they can concentrate on preventing overfitting the information to the
function being modeled.
Data Integration –
 Data integration is the procedure of merging data from several disparate sources.
 While performing data integration, it must work on data redundancy,
inconsistency, duplicity, etc.
 In data mining, data integration is a record preprocessing method that includes
merging data from a couple of the heterogeneous data sources into coherent data
to retain and provide a unified perspective of the data.
 Data integration is especially important in the healthcare industry.
 Integrated data from multiple patient data and clinics assist clinicians in
recognizing medical disorders and diseases by integrating data from multiple
systems into an individual perspective of beneficial data from which beneficial
insights can be derived.
Data transformation –
 In data transformation, where data are transformed or linked into forms
applicable for mining by executing summary or aggregation operations.
 In Data transformation, it includes −

 Smoothing − It can work to remove noise from the data. Such techniques
includes binning, regression, and clustering.
 Aggregation − In aggregation, where summary or aggregation services are
used to the data. For instance, the daily sales data can be aggregated to
calculate monthly and annual total amounts.
Data Reduction –
 The objective of Data reduction is to define it more compactly.

47
 When the data size is smaller, it is simpler to use sophisticated and
computationally high-cost algorithms.
 The reduction of the data can be in terms of the multiple rows (records) or terms
of the multiple columns (dimensions).
 In dimensionality reduction, data encoding schemes are used so as to acquire a
reduced or “compressed” description of the initial data.
 Examples involve data compression methods (e.g., wavelet transforms and
principal components analysis), attribute subset selection (e.g., removing
irrelevant attributes), and attribute construction (e.g., where a small set of more
beneficial attributes is changed from the initial set).

Figure: Forms of Data Preprocessing

48
DATA CLEANING
 Data cleaning in data mining is the process of identifying and correcting errors,
inconsistencies, and inaccuracies in the dataset to improve data quality and
reliability.
 Since real-world data often contains missing values, noise, duplicates, and
inconsistencies, data cleaning is a critical step to ensure accurate results during
data analysis and model building.
Major Tasks in Data Cleaning
1. Handling Missing Values
 Missing data can arise due to sensor errors, incomplete surveys, or data
collection issues.
Techniques to Handle Missing Values:
 Ignore or Remove Records:
o Remove rows or columns with missing data (useful if the missing
percentage is very low).
 Imputation:
o Replace missing values with mean, median, mode, or other statistical
measures.
o Advanced methods include using predictive models (e.g., regression,
KNN) to estimate missing values.
 Default Value Assignment:
o Replace missing values with default placeholders (e.g., “0” or
“Unknown”).
 Interpolation:
o Fill missing values using trends in the data (linear or polynomial
interpolation).
2. Removing or Handling Noise
 Noise refers to random errors or irrelevant variations in the data, which can
mislead data mining results.

49
Techniques for Noise Removal:
 Binning:
o Group values into bins and smooth data within each bin.
o Example: Replace a set of values in a bin with the mean or median of the
bin.
 Regression:
o Use a regression model to smooth noisy data.
 Clustering:
o Detect and filter out outliers using clustering algorithms (e.g., DBSCAN).
 Smoothing Methods:
o Apply techniques like moving averages or exponential smoothing to
smooth fluctuations.
3. Removing Duplicates
 Duplicate records arise from data integration or improper data collection
processes.
Techniques to Remove Duplicates:
 Identify records with identical values in key attributes.
 Use deduplication tools or algorithms to eliminate redundancies.
 Perform entity resolution to ensure unique identification of records.
4. Correcting Inconsistent Data
 Inconsistencies occur due to errors in data entry, integration of multiple datasets,
or formatting issues.
Examples of Inconsistencies:
 Different formats for dates: DD/MM/YYYY vs. MM-DD-YYYY.
 Inconsistent units: kilograms vs. pounds.
 Spelling errors: “USA” vs. “U.S.A.”
Techniques for Correction:
 Standardize formats using transformation rules.
 Implement validation rules to ensure consistency.
 Use string matching or correction algorithms to fix typos.

50
5. Outlier Detection and Handling
 Outliers are data points that deviate significantly from other observations.
 Outliers can occur due to errors or genuine variations.
Techniques to Handle Outliers:
 Statistical Methods:
o Use Z-score or IQR (Interquartile Range) to detect outliers.
 Clustering Methods:
o Algorithms like DBSCAN can identify outliers as low-density points.
 Capping and Flooring:
o Replace outliers with threshold values (e.g., 5th and 95th percentiles).
 Transformation:
o Apply log transformations or scaling to minimize outlier impact.
MISSING VALUES
 Missing values in data refer to the absence of certain observations in a dataset,
which can occur due to various reasons, such as errors during data collection,
transmission, or entry.
 Handling missing values is crucial for accurate data analysis, as they can bias
results or reduce the performance of machine learning models.
 Data can be missing for many reasons like technical issues, human errors,
privacy concerns, data processing issues, or the nature of the variable itself.
 Understanding the cause of missing data helps choose appropriate handling
strategies and ensure the quality of your analysis.
 It’s important to understand the reasons behind missing data:
 Identifying the type of missing data: Is it Missing Completely at
Random (MCAR), Missing at Random (MAR), or Missing Not at
Random (MNAR)?
 Evaluating the impact of missing data: Is the missingness causing
bias or affecting the analysis?
 Choosing appropriate handling strategies: Different techniques are
suitable for different types of missing data.

51
Types of Missing Values
 There are three main types of missing values:
Missing Completely at Random (MCAR):
 MCAR is a specific type of missing data in which the probability of a data point
being missing is entirely random and independent of any other variable in the
dataset.
 In simpler terms, whether a value is missing or not has nothing to do with the
values of other variables or the characteristics of the data point itself.
Missing at Random (MAR):
 MAR is a type of missing data where the probability of a data point missing
depends on the values of other variables in the dataset,
 but not on the missing variable itself.
 This means that the missingness mechanism is not entirely random, but it can be
predicted based on the available information.
Missing Not at Random (MNAR):
 MNAR is the most challenging type of missing data to deal with.
 It occurs when the probability of a data point being missing is related to the
missing value itself.
 This means that the reason for the missing data is informative and directly
associated with the variable that is missing.
NOISY DATA
 Noisy data refers to data that contains errors, irrelevant information, or random
variations that do not reflect the true values or patterns in the dataset.
 Noise can distort analysis, hinder model performance, and reduce the reliability
of insights in data mining and machine learning processes.
Types of Noise
 A large number of components determine the quality of a dataset.
 Among them, the class labels and the attribute values directly influence the
quality of a classification dataset.
 Two types of noise can be distinguished in a given dataset.

52
1. Class Noise
 Class noise occurs when the class labels (target variable) in the dataset are
incorrectly assigned or mislabeled.
 It is specific to supervised learning tasks where the target variable plays a critical
role.
Causes of Class Noise
 Human Error: Incorrect labeling during manual annotation.
 Ambiguous Data: Instances that are difficult to categorize into specific
classes.
 Data Integration Issues: Conflicts when combining datasets with different
labeling schemes.
 Misleading Features: When features are weak indicators of the true class.

Examples of Class Noise

Feature True Class Noisy Class

Email Text Spam Not Spam

Image of Dog Dog Cat

Medical Data Healthy Diseased

 Attribute noise occurs when features (attributes) in the dataset contain errors,
inconsistencies, or irrelevant values.

53
Causes of Attribute Noise
 Measurement Errors: Faulty instruments or sensors (e.g., wrong temperature
reading).
 Data Entry Errors: Typographical mistakes during data input.
 Sensor or Transmission Failures: Data corruption while transferring.
 Data Transformation Issues: Errors during scaling or standardization.

Examples of Attribute Noise

Feature True Value Noisy Value

Age 30 300

Temperature 98.6°F 1000°F

Salary $50000 $5000000

 Removing noise from a data set is termed data smoothing. The following ways
can be used for Smoothing:
1. Binning
 Binning is a technique where we sort the data and then partition the data into
equal frequency bins.
 Then you may either replace the noisy data with the bin mean bin median or the
bin boundary.
 This method is to smooth or handle noisy data.
 First, the data is sorted then, and then the sorted values are separated and stored
in the form of bins.
 There are three methods for smoothing data in the bin.

o Smoothing by bin mean method: In this method, the values in the bin
are replaced by the mean value of the bin.
o Smoothing by bin median: In this method, the values in the bin are
replaced by the median value.

54
 o Smoothing by bin boundary: In this method, the using minimum and
maximum values of the bin values are taken, and the closest boundary
value replaces the values.

2. Regression
 This is used to smooth the data and help handle data when unnecessary data is
present.
 For the analysis, purpose regression helps decide the suitable variable.
 Linear regression refers to finding the best line to fit between two variables so
that one can be used to predict the other.
 Multiple linear regression involves more than two variables.
 Using regression to find a mathematical equation to fit into the data helps to
smooth out the noise.
3. Clustering
 This is used for finding the outliers and also in grouping the data. Clustering is
generally used in unsupervised learning.
DATA CLEANING AS A PROCESS
 Data cleaning is an essential step in the data mining process.
 It is crucial to the construction of a model.
 The step that is required, but frequently overlooked by everyone, is data cleaning.
 The major problem with quality information management is data quality.
 Problems with data quality can happen at any place in an information system.
 Data cleansing offers a solution to these issues.
 Data cleaning is the process of correcting or deleting inaccurate, damaged,
improperly formatted, duplicated, or insufficient data from a dataset.
 Even if results and algorithms appear to be correct, they are unreliable if the data
is inaccurate.
 There are numerous ways for data to be duplicated or incorrectly labeled when
merging multiple data sources.
Steps for Cleaning Data
 You can follow these fundamental stages to clean your data even if the
techniques employed may vary depending on the sorts of data your firm stores:

55
1. Remove duplicate or irrelevant observations
 Remove duplicate or pointless observations as well as undesirable observations
from your dataset.
 The majority of duplicate observations will occur during data gathering.
 Duplicate data can be produced when you merge data sets from several sources,
scrape data, or get data from clients or other departments.
 One of the most important factors to take into account in this procedure is de-
duplication.
 Those observations are deemed irrelevant when you observe observations that
do not pertain to the particular issue you are attempting to analyze.

2. Fix structural errors

 When you measure or transfer data and find odd naming practices, typos, or
wrong capitalization, such are structural faults.
 Mislabelled categories or classes may result from these inconsistencies.
 For instance, "N/A" and "Not Applicable" might be present on any given sheet,
but they ought to be analyzed under the same heading.

3. Filter unwanted outliers

 There will frequently be isolated findings that, at first glance, do not seem to fit
the data you are analyzing.
 Removing an outlier if you have a good reason to, such as incorrect data entry,
will improve the performance of the data you are working with.
 However, occasionally the emergence of an outlier will support a theory you
are investigating.
 And just because there is an outlier, that doesn't necessarily indicate it is
inaccurate.
 To determine the reliability of the number, this step is necessary.
 If an outlier turns out to be incorrect or unimportant for the analysis, you might
want to remove it.

56
4. Handle missing data
 Because many algorithms won't tolerate missing values, you can't overlook
missing data.
 There are a few options for handling missing data. While neither is ideal, both
can be taken into account, for example:
 Although you can remove observations with missing values, doing so will result
in the loss of information, so proceed with caution.
 Again, there is a chance to undermine the integrity of the data since you can be
working from assumptions rather than actual observations when you input
missing numbers based on other observations.
 To browse null values efficiently, you may need to change the way the data is
used.

5. Validate and QA
 As part of fundamental validation, you ought to be able to respond to the
following queries once the data cleansing procedure is complete:
o Are the data coherent?
o Does the data abide by the regulations that apply to its particular field?
o Does it support or refute your working theory? Does it offer any new
information?
o To support your next theory, can you identify any trends in the data?
o If not, is there a problem with the data's quality?

57
 UNIT III
Mining Frequent Patterns, Associations, and Correlations
Market Basket Analysis – Frequent Itemsets, Closed Itemsets, and Association Rules –
Apriori Algorithm – Pattern-Growth Approach for Mining Frequent Itemsets – Mining
Frequent Itemsets Using the Vertical Data Format – Mining Closed and Max Patterns –
Correlation Analysis.
MARKET BASKET ANALYSIS
 Market Basket Analysis (MBA) is a popular technique in data mining used to
understand the relationships between different items purchased together in a
retail setting.
 It is a type of association rule learning that helps businesses analyse customer
purchase behaviour and uncover patterns that can inform product placement,
promotions, and marketing strategies.

 Market Basket Analysis (MBA) is a data mining technique used to identify

patterns in the purchasing behavior of customers.
 In a supermarket, the items placed in a shopping cart by a customer are logged
at checkout.
 By analyzing this transactional data, the supermarket can identify relationships
between items frequently purchased together.
 For example, if customers who buy bread often also purchase butter, this
relationship can inform decisions like product placement, promotions, or
bundling strategies.

58
  MBA uses measures such as support, confidence, and lift to evaluate the strength
of these associations.
 This analysis helps businesses optimize their sales and improve customer
experience.
 For example, suppose 5000 transactions have been made through a popular e-
Commerce website.
 Now they want to calculate the support, confidence, and lift for the two products.
 For example, let's say pen and notebook, out of 5000 transactions, 500
transactions for pen, 700 transactions for notebook, and 1000 transactions for
both.
Support
 It has been calculated with the number of transactions divided by the total
number of transactions made,
Support = freq(A, B)/N
 support(pen) = transactions related to pen/total transactions
 i.e support -> 500/5000=10 percent

Confidence
 Whether the product sales are popular on individual sales or through combined
sales has been calculated.
 That is calculated with combined transactions/individual transactions.
Confidence = freq (A, B)/ freq(A)
 Confidence = combine transactions/individual transactions
 i.e confidence-> 1000/500=20 percent

Lift
 Lift is calculated for knowing the ratio for the sales.
Lift = confidence percent/ support percent
 Lift-> 20/10=2

59
FREQUENT ITEMSETS, CLOSED ITEMSETS, AND ASSOCIATION RULES
Frequent Itemsets
 A frequent itemset is a set of items that appear together in a transaction dataset
with a frequency above a specified threshold, called minimum support.
 Definition: An itemset I is considered frequent if its support is greater than or
equal to a given threshold.
 Support: The fraction or percentage of transactions that contain the itemset I.
Number of transactions containing I
𝑆𝑢𝑝𝑝𝑜𝑟𝑡 (𝐼) =
𝑇𝑜𝑡𝑎𝑙 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑟𝑎𝑛𝑠𝑎𝑐𝑡𝑖𝑜𝑛
Example:
 In a dataset of 100 transactions, if {Bread, Butter} appears in 25 transactions, its
support is 25%.
 If the minimum support threshold is 20%, {Bread, Butter} is a frequent itemset.
Closed Itemsets
 A closed itemset is a frequent itemset for which there is no superset with the
same support.
 Definition: An itemset I is closed if no proper superset of I has the same support
as I.
 Purpose: Closed itemsets help reduce redundancy by eliminating non-closed
frequent itemsets while preserving all essential information.
 Example:
o {Bread, Butter} has support = 25.
o If {Bread, Butter, Milk} also has support = 25, then {Bread, Butter} is
not a closed itemset because the superset {Bread, Butter, Milk} has the
same support.
o If no superset has the same support, {Bread, Butter} is a closed itemset.
Association Rules
 Association rules are conditional statements that describe relationships between
items in a dataset.
 They are derived from frequent itemsets and indicate how likely items are to be
purchased together.

60
  Format: A→B ("If A, then B").
o A = Antecedent (LHS, items on the left-hand side).
o B = Consequent (RHS, items on the right-hand side).
 Metrics:
o Support: The proportion of transactions containing both A and B.
o Confidence: The likelihood of purchasing B given that A is purchased.
Confidence(A→B)=Support(A∪B)/Support(A)
o Lift: The strength of association between A and B.
Lift(A→B)=Confidence(A→B)/Support(B)
 If Lift > 1, A and B are positively associated.
 Example:
o Rule: {Bread} → {Butter}
 Support = 20% (transactions containing both Bread and Butter).
 Confidence = 70% (70% of transactions with Bread also have
Butter).
 Lift > 1 (suggests a strong association).
APRIORI ALGORITHM
 The Apriori algorithm is a classic data mining algorithm used to identify frequent
itemsets and generate association rules in a transactional database.
 It is widely applied in market basket analysis to discover relationships between items.

61
  It is particularly employed in market basket analysis to identify relationships between
items that are frequently purchased together.
 The algorithm uses a breadth-first search strategy to explore the space of possible
itemsets efficiently.
Algorithm
1. Input:
o A transaction dataset D.
o Minimum support threshold min-sup.
2. Output:
o All frequent itemsets.
3. Procedure:
o Step 1: Candidate Generation (Level-wise Approach)
 Start with single-item sets (1-itemsets).
 Use the Apriori property to generate candidate itemsets of size k+1
from frequent itemsets of size k.
o Step 2: Support Counting
 Scan the database to calculate the support for each candidate
itemset.
 Discard itemsets that do not meet the minimum support threshold.
o Step 3: Repeat
 Repeat steps 1 and 2 until no more candidate itemsets can be
generated.
o Step 4: Association Rule Generation
 Use frequent itemsets to generate association rules that meet the
minimum confidence threshold.
Working Example
 Let’s consider a transaction dataset DDD:

62
 Minimum Support Threshold = 2 transactions.
Step 1: Find 1-itemsets (Frequent Items)
Count the support for each single item.

Item Support Count

Milk 4

Bread 4

Butter 4

 All items are frequent (support ≥ 2).

Step 2: Generate Candidate 2-itemsets
Combine frequent 1-itemsets to form candidate 2-itemsets:
 {Milk, Bread}, {Milk, Butter}, {Bread, Butter}
Calculate support:
Itemset Support Count

{Milk, Bread} 3

{Milk, Butter} 3

{Bread, Butter} 3

 All candidate 2-itemsets are frequent.

Step 3: Generate Candidate 3-itemsets
 Combine frequent 2-itemsets to form candidate 3-itemsets:
 {Milk, Bread, Butter}
Calculate support:
Itemset Support Count

{Milk, Bread, Butter} 2

{Milk, Bread, Butter} is frequent.
Step 4: Stop
 No larger frequent itemsets can be generated.

63
Step 5: Generate Association Rules
 From frequent itemsets, generate rules and calculate confidence:
 Rule: {Milk, Bread} → {Butter}
o Confidence = Support({Milk, Bread, Butter}) / Support({Milk, Bread})
= 2/3=66.7%.
 Similar rules can be generated for other itemsets.
Advantages of Apriori Algorithm
1. Simple and easy to implement.
2. Reduces the search space using the Apriori property.
3. Works well for small and medium-sized datasets.
Disadvantages
1. Multiple Scans: Requires multiple scans of the database, which can be time-
consuming.
2. Computational Complexity: Generating and testing candidates becomes
expensive for large datasets.
3. Sparse Data: In sparse datasets, the number of candidates can explode.
PATTERN-GROWTH APPROACH FOR MINING FREQUENT ITEMSETS
 The Pattern-Growth Approach is an efficient method for discovering frequent
itemsets in large datasets, addressing the limitations of the Apriori algorithm.
 Unlike Apriori, which generates a large number of candidate itemsets and
repeatedly scans the database,
 The pattern-growth approach reduces both the candidate generation and database
scanning overhead.
Steps in Pattern-Growth Approach
1. Database Compression:
o A compact structure, such as an FP-tree (Frequent Pattern Tree), is built
from the transactional database.
o The FP-tree efficiently compresses the data while retaining all necessary
information for mining frequent patterns.

64
 2. Recursive Pattern Growth:
o Starting from the frequent 1-itemsets, the algorithm recursively projects
the database into smaller conditional sub-databases.
o Frequent patterns are grown by appending items to existing patterns.
3. Divide and Conquer:
o For each frequent item, construct a conditional FP-tree (subtree) that
contains transactions having that item.
o Recursively mine frequent patterns from the conditional FP-tree.
Steps of FP-Growth:
1. Construct the FP-Tree:
o Scan the database once to find frequent 1-itemsets and their counts.
o Order items in transactions based on descending frequency.
o Build the FP-tree by inserting transactions as paths, sharing common
prefixes.
2. Mine the FP-Tree:
o Starting with the least frequent item in the tree (bottom-up), construct its
conditional pattern base (set of paths leading to the item).
o Build a conditional FP-tree for that item.
o Recursively mine frequent patterns by growing prefixes with the item.
3. Stop Condition:
o Stop when no frequent itemsets can be grown further.

65
 1. One root is labelled as "null" with a set of item-prefix subtrees as children and a
frequent-item-header table.
2. Each node in the item-prefix subtree consists of three fields:
o Item-name: registers which item is represented by the node;
o Count: the number of transactions represented by the portion of the path
reaching the node;
o Node-link: links to the next node in the FP-tree carrying the same item name
or null if there is none.

3. Each entry in the frequent-item-header table consists of two fields:

o Item-name: as the same to the node;
o Head of node-link: a pointer to the first node in the FP-tree carrying the item
name.

MINING FREQUENT ITEMSETS USING THE VERTICAL DATA FORMAT

 The Vertical Data Format is an alternative approach to the traditional horizontal

transaction representation in frequent itemset mining.
 It represents data in terms of items and the transaction IDs (TIDs) where each
item appears.
 This format is particularly useful for efficiently calculating support counts and
discovering frequent itemsets.
Vertical Data Representation:
 In the vertical format, each item is associated with a TID-list (a list of transaction
IDs containing that item).
 Example: For a dataset:

66
  The vertical format becomes:

Item TID-List

A {1, 2, 3, 4}

B {1, 3, 4, 5}

C {1, 2, 3, 4, 5}

D {2, 5}

E {2, 3}
Support Counting:
 The support count of an itemset can be determined by intersecting the TID-lists
of the individual items in that itemset.
 The size of the resulting TID-list gives the support count.
Frequent Itemset Generation:
 Start with single items and their TID-lists.
 Combine TID-lists of items to generate candidate itemsets (k-itemsets) and
compute their support using intersection.
 Prune itemsets that do not meet the minimum support threshold.
Steps for Mining Frequent Itemsets in Vertical Format
1. Step 1: Convert Data to Vertical Format
o Transform the horizontal transaction dataset into the vertical format by
creating TID-lists for each item.
2. Step 2: Generate Frequent 1-Itemsets
o Count the support of each item by checking the size of its TID-list.
o Retain items whose support meets the minimum support threshold.
3. Step 3: Generate Candidate k-Itemsets
o Combine the TID-lists of frequent (k-1)-itemsets to generate TID-lists for
k-itemsets.
o Use TID-list intersection to compute support efficiently.
4. Step 4: Prune Infrequent Itemsets
o Remove itemsets that do not satisfy the minimum support threshold.
5. Step 5: Repeat

67
 o Continue until no more frequent itemsets can be generated.
Advantages of the Vertical Data Format
1. Efficient Support Counting:
o Support is computed using TID-list intersections, which is faster than
scanning the database multiple times.
2. Compact Representation:
o TID-lists provide a compressed view of transactions for each item.
3. Scalability:
o Works well for datasets with many transactions but a limited number of
unique items.
Disadvantages
1. Memory Usage:
o TID-lists may require significant memory for large datasets.
2. Sparse Data:
o Intersection of TID-lists can become less efficient for sparse datasets
where overlaps are minimal.
MINING CLOSED AND MAX PATTERNS
 In frequent itemset mining, it is often inefficient to mine all frequent itemsets because
the result set can be very large, especially for dense datasets.
 Instead, closed patterns and max patterns are mined to reduce redundancy while still
retaining useful information.
Closed Patterns
 A closed itemset is an itemset where no superset has the same support as the
itemset itself.
Formal Definition
 An itemset X is closed if there is no itemset Y such that:

 X⊂Y (i.e., X is a subset of Y)

 Support(X)=Support(Y)
 Closed itemsets retain the support count information and eliminate redundant
itemsets.

68
Example
 Consider the following transaction database:

TID Items Purchased

1 A, B, C

2 A, B, D

3 A, B, C

4 A, B, C, D

5 A, C
 Frequent Itemsets with Support:
o {A} → 5
o {A,B}→ 4
o {A,B,C} → 3
o {A,B,D}→ 2
o {A,C} → 4
 Closed Itemsets:
o {A,B,C}: No superset has the same support (support = 3).
o {A,B,D}: No superset has the same support (support = 2).
o {A,C}: No superset has the same support (support = 4).
 Here, {A,B} is not closed because {A,B,C} has the same support (3).
Benefits of Mining Closed Itemsets
1. Reduces Redundancy:
o Closed itemsets eliminate non-closed subsets, reducing the result set
size.
2. Retains Support Information:
o Closed itemsets still provide complete support count information for
frequent itemsets.
3. Improved Efficiency:
o Fewer itemsets to output and analyze.

69
Max Patterns (Maximal Itemsets)
 A maximal frequent itemset is a frequent itemset that has no frequent supersets.
Formal Definition
 An itemset X is maximal frequent if there is no itemset Y such that:
 X⊂Y (i.e., X is a subset of Y)
 Support(Y)≥min-sup
 Maximal patterns are a subset of frequent itemsets and represent the largest
frequent itemsets.
Example
 Using the same transaction database:

Items
TID
Purchased

1 A, B, C

2 A, B, D

3 A, B, C

4 A, B, C, D

5 A, C
 Frequent Itemsets with Support:
o {A} → 5
o {A,B} → 4
o {A,B,C} → 3
o {A,B,D} → 2
o {A,C} → 4
 Maximal Itemsets:
o {A,B,C}: No frequent superset exists.
o {A,B,D}: No frequent superset exists.
 Here, {A,B} is not maximal because {A,B,C} is frequent and a superset of
{A,B}.

70
Benefits of Mining Max Patterns
1. Compact Representation:
o Maximal patterns represent the largest frequent itemsets, significantly
reducing the number of itemsets output.
2. Efficiency:
o Reduces computational overhead by focusing only on maximal itemsets.
3. Simpler Interpretation:
o Provides a high-level overview of frequent itemsets without redundancy.
CORRELATION ANALYSIS
 Correlation analysis is a statistical technique used to evaluate the strength and direction
of the relationship between two or more variables.
 It helps in understanding whether and how variables are related, which is crucial for
making data-driven decisions, predictions, and extracting insights from the data.
Correlation Coefficient (r):
 The correlation coefficient measures the degree of relationship between two
variables.
 It is typically calculated using Pearson's correlation formula:

where:
 Xi and Yi are the values of variables X and Y,
 μX and μY are the means of X and Y.
The value of r ranges from -1 to 1:
 +1: Perfect positive correlation (as one variable increases, the other increases in
perfect proportion).
 -1: Perfect negative correlation (as one variable increases, the other decreases in
perfect proportion).
 0: No correlation (no linear relationship between the variables).

71
 Types of Correlation:
 Positive Correlation: When one variable increases, the other also increases
(e.g., height and weight).
 Negative Correlation: When one variable increases, the other decreases (e.g.,
price and demand).
 No Correlation: When changes in one variable do not predict changes in another
variable (e.g., shoe size and intelligence).
Types of Correlation Coefficients:
 Pearson’s correlation: Measures the linear relationship between two continuous
variables.
 Spearman’s rank correlation: Measures the relationship between two ranked
variables, often used when the data is not linearly related.
 Kendall’s tau: Similar to Spearman's rank but uses a different method for rank
comparison.
 Point-Biserial correlation: Used when one variable is continuous and the other
is binary.

Steps in Correlation Analysis

1. Data Collection: Collect data for the variables of interest. The data can be
continuous or ordinal, depending on the method used (e.g., Pearson for
continuous, Spearman for ordinal).
2. Preprocessing: Clean the data by handling missing values, outliers, and ensuring
that data types are appropriate for the analysis.

72
3. Choosing the Correlation Method:
o For continuous variables: Use Pearson's correlation.
o For ordinal or non-linear data: Use Spearman’s or Kendall’s
correlation.
4. Calculation of Correlation: Compute the correlation coefficient using the
selected method. This can often be done using statistical tools or libraries in
Python, R, or Excel.

73
 UNIT IV
Classification
Classification – General Approach to Classification – Decision Tree Induction – Basic
Algorithm for Inducing a Decision Tree from Training Tuples – Attribute Selection
Measures: Information Gain – Gain Ratio – Gini Index.

CLASSIFICATION

 Classification is to identify the category or the class label of a new observation.

First, a set of data is used as training data.
 The set of input data and the corresponding outputs are given to the algorithm.
 So, the training data set includes the input data and their associated class labels.
 Using the training dataset, the algorithm derives a model or the classifier.
 The derived model can be a decision tree, mathematical formula, or a neural
network.
 In classification, when unlabeled data is given to the model, it should find the
class to which it belongs.
 The new data provided to the model is the test data set.
 Classification is the process of classifying a record.
 One simple example of classification is to check whether it is raining or not.
 The answer can either be yes or no. So, there is a particular number of choices.
 Sometimes there can be more than two classes to classify. That is
called multiclass classification.
GENERAL APPROACH TO CLASSIFICATION
 Data classification is a two-step process, consisting of a learning step (where a
classification model is constructed) and a classification step (where the model is
used to predict class labels for given data).
 In the first step, a classifier is built describing a predetermined set of data classes
or concepts.

74
 This is the learning step (or training phase), where a classification algorithm
builds the classifier by analyzing or “learning from” a training set made up of
database tuples and their associated class labels.
 Each tuple/sample is assumed to belong to a predefined class, as determined by
the class label attribute
 In the second step, the model is used for classification.
 First, the predictive accuracy of the classifier is estimated.
 If we were to use the training set to measure the classifier’s accuracy, this
estimate would likely be optimistic, because the classifier tends to overfit the
data.
 Accuracy rate is the percentage of test set samples that are correctly classified
by the model

75
DECISION TREE INDUCTION / BASIC ALGORITHM FOR INDUCING A
DECISION TREE FROM TRAINING TUPLES
 Decision Tree is a supervised learning method used in data mining for
classification and regression methods.
 It is a tree that helps us in decision-making purposes.
 The decision tree creates classification or regression models as a tree structure.
 It separates a data set into smaller subsets, and at the same time, the decision tree
is steadily developed.
 The final tree is a tree with the decision nodes and leaf nodes.
 A decision node has at least two branches.
 The leaf nodes show a classification or decision.
 We can't accomplish more split on leaf nodes-The uppermost decision node in a
tree that relates to the best predictor called the root node.
 Decision trees can deal with both categorical and numerical data.
Key factors:
Entropy:
 Entropy refers to a common way to measure impurity.
 In the decision tree, it measures the randomness or impurity in data sets.

76
Information Gain:
 Information Gain refers to the decline in entropy after the dataset is split.
 It is also called Entropy Reduction.
 Building a decision tree is all about discovering attributes that return the highest
data gain.

Structure of a Decision Tree

 Root Node: Represents the entire dataset and the initial decision to be made.
 Internal Nodes: Represent decisions or tests on attributes. Each internal node
has one or more branches.
 Branches: Represent the outcome of a decision or test, leading to another node.
 Leaf Nodes: Represent the final decision or prediction. No further splits occur
at these nodes.
 The following decision tree is for the concept buy_computer that indicates
whether a customer at a company is likely to buy a computer or not.
 Each internal node represents a test on an attribute. Each leaf node represents a
class.

77
78
ATTRIBUTE SELECTION MEASURES
 An attribute selection measure is a heuristic for choosing the splitting test that
“best” separates a given data partition, D, of class-labeled training tuples into
single classes.
 If it can split D into smaller partitions as per the results of the splitting criterion,
ideally every partition can be pure (i.e., some tuples that fall into a given partition
can belong to the same class).
 Conceptually, the “best” splitting criterion is the most approximately results in
such a method.
 Attribute selection measures are called a splitting rules because they decides how
the tuples at a given node are to be divided.
 The attribute selection measure supports a ranking for every attribute defining
the given training tuples.
 The attribute having the best method for the measure is selected as the splitting
attribute for the given tuples.
 If the splitting attribute is constant-valued or if it is restricted to binary trees,
accordingly, either a split point or a splitting subset should also be decided as an
element of the splitting criterion.
 The tree node generated for partition D is labeled with the splitting criterion,
branches are increase for each result of the criterion, and the tuples are isolated
accordingly.
 There are three famous attribute selection measures including information gain,
gain ratio, and gini index.
Information Gain:
 It is used to find the changes in Entropy after splitting the dataset based on
attributes.
 It is used to tell how much information an attribute can provide us about the
class.
 We choose the feature that directs to the most significant reduction in Entropy,
as it provides more information.

79
  Information Gain can be calculated with the help of the following formula:

o "IG (A)" is the Information Gain of dataset "D" based on attribute A.

o "Entropy (D)" is the Entropy of dataset "D".
o "|Dv|" is the number of instances in subset v.
o "|D|" is the total number of instances in dataset "D".
o "Entropy(Dv)" is the Entropy of each subset v.

Gini Index:

 It is also called the Gini coefficient, Gini impurity, or Gini ratio.

 It is used to find the impurity present in the dataset.
 It finds out the probability of all the splits inside the tree.
 It helps decide how to split a dataset while building the decision tree.
 The value of the Gini index lies between 0 and 1.
 In a decision tree, each node is an attribute that contains information.
 We will calculate the Gini index at each node, and wherever the Gini index is
lowest, it will be selected for the tree-splitting criteria.
 The mathematical formula for calculating the Gini Index is given below:

In the above formula,

o Gini (D) is the Gini Index of the dataset "D".

o Pi is the probability of data points in the dataset that belong to the i-th class.

80
 UNIT V
Clustering
Cluster Analysis – Requirements for Cluster Analysis – Overview of Basic Clustering
Methods Partitioning Methods: k-means clustering – k-medoids clustering –
Hierarchical Methods: Agglomerative versus Divisive Hierarchical Clustering –
Balanced Iterative Reducing and Clustering using Hierarchies – Chameleon –
Probabilistic Hierarchical Clustering.
CLUSTER ANALYSIS
 Cluster analysis, also known as clustering, is a method of data mining that groups
similar data points together.
 The goal of cluster analysis is to divide a dataset into groups (or clusters) such
that the data points within each group are more similar to each other than to data
points in other groups.
 This process is often used for exploratory data analysis and can help identify
patterns or relationships within the data that may not be immediately obvious.
 There are many different algorithms used for cluster analysis, such as k-means,
hierarchical clustering, and density-based clustering.
 The choice of algorithm will depend on the specific requirements of the analysis
and the nature of the data being analyzed.
 Cluster Analysis is the process to find similar groups of objects in order to form
clusters.
 It is an unsupervised machine learning-based algorithm that acts on unlabelled
data.
 A group of data points would comprise together to form a cluster in which all
the objects would belong to the same group.
 Clustering helps to splits data into several subsets.
 Each of these subsets contains data similar to each other, and these subsets are
called clusters.
 Now that the data from our customer base is divided into clusters, we can make
an informed decision about who we think is best suited for this product.

81
A good clustering algorithm aims to obtain clusters whose:

o The intra-cluster similarities are high, It implies that the data present inside the
cluster is similar to one another.
o The inter-cluster similarity is low, and it means each cluster holds data that is not
similar to other data.

REQUIREMENTS FOR CLUSTER ANALYSIS

There are the following requirements of clustering in data mining which are as
follows
Scalability –
 Some clustering algorithms work well on small data sets including fewer than
some hundred data objects.
 A huge database can include millions of objects.
 Clustering on a sample of a given huge data set can lead to partial results.
 Highly scalable clustering algorithms are required.

82
Ability to deal with different types of attributes –
 Some algorithms are designed to cluster interval-based (numerical) information.
 However, applications can require clustering several types of data, including
binary, categorical (nominal), and ordinal data, or a combination of these data
types.
Discovery of clusters with arbitrary shape –
 Some clustering algorithms determine clusters depending on Euclidean or
Manhattan distance measures.
 Algorithms that depend on such distance measures tend to discover spherical
clusters with the same size and density.
 But, a cluster can be of any shape.
 It is essential to develop algorithms that can recognize clusters of arbitrary
shapes.
Minimal requirements for domain knowledge to determine input parameters –
 Some clustering algorithms needed users to input specific parameters in cluster
analysis (including the number of desired clusters).
 The clustering results can be absolutely sensitive to input parameters.
 Parameters are difficult to decide, especially for data sets including high-
dimensional objects.
 This not only task users, but it also creates the quality of clustering difficult to
control.
Ability to deal with noisy data –
 Most real-world databases include outliers or missing, unknown, or erroneous
information.
 Some clustering algorithms are keen on such data and can lead to clusters of poor
quality.
Incremental clustering and insensitivity to the order of input records –
 Some clustering algorithms cannot include newly inserted information (i.e.,
database updates) into current clustering structures and, instead, must decide a
new clustering from scratch.

83
  Some clustering algorithms are sensitive to the order of input records.
 Given a set of data objects, including algorithm can return dramatically different
clusterings depending on the order of presentation of the input objects.
 It is essential to develop incremental clustering algorithms and algorithms that
are insensitive to the order of input.
High dimensionality –
 A database or a data warehouse can include multiple dimensions or attributes.
 Some clustering algorithms are good at managing low-dimensional data,
containing only two to three dimensions.
 Human eyes are best at determining the quality of clustering for up to three
dimensions.
 It is used to find clusters of data objects in high-dimensional space is complex,
especially treating that such data can be inadequate and highly skewed.
OVERVIEW OF BASIC CLUSTERING METHODS PARTITIONING
METHODS
 Clustering is an unsupervised data mining technique used to group data objects
into clusters such that objects in the same cluster are more similar to each other
than to objects in other clusters.
 Partitioning methods are one of the fundamental approaches to clustering.
K-MEANS CLUSTERING
 K-Means Clustering is an unsupervised learning algorithm that is used to solve
the clustering problems in machine learning or data science.
 We will learn what is K-means clustering algorithm, how the algorithm works,
along with the Python implementation of k-means clustering.
 K-Means Clustering is an Unsupervised Learning algorithm, which groups the
unlabeled dataset into different clusters.
 Here K defines the number of pre-defined clusters that need to be created in the
process,
 As if K=2, there will be two clusters, and for K=3, there will be three clusters,
and so on.

84
  The algorithm takes the unlabeled dataset as input, divides the dataset into k-
number of clusters, and repeats the process until it does not find the best clusters.
 The value of k should be predetermined in this algorithm.
 The k-means clustering algorithm mainly performs two tasks:
o Determines the best value for K center points or centroids by an iterative
process.
o Assigns each data point to its closest k-center. Those data points which are
near to the particular k-center, create a cluster.

o Hence each cluster has datapoints with some commonalities, and it is away
from other clusters.
o The below diagram explains the working of the K-means Clustering
Algorithm:

The working of the K-Means algorithm is explained in the below steps:

Step-1: Select the number K to decide the number of clusters.
Step-2: Select random K points or centroids. (It can be other from the input dataset).
Step-3: Assign each data point to their closest centroid, which will form the predefined
K clusters.
Step-4: Calculate the variance and place a new centroid of each cluster.
Step-5: Repeat the third steps, which means reassign each datapoint to the new closest
centroid of each cluster.
Step-6: If any reassignment occurs, then go to step-4 else go to FINISH.
Step-7: The model is ready.

85
K-MEDOIDS CLUSTERING
o K-Medoids and K-Means are two types of clustering mechanisms in Partition
Clustering.
o First, Clustering is the process of breaking down an abstract group of data
points/ objects into classes of similar objects such that all the objects in one
cluster have similar traits. ,
o A group of n objects is broken down into k number of clusters based on their
similarities.
o K-medoids is an unsupervised method with unlabelled data to be clustered.
o It is an improvised version of the K-Means algorithm mainly designed to deal
with outlier data sensitivity.
o Compared to other partitioning algorithms, the algorithm is simple, fast, and
easy to implement.
The partitioning will be carried on such that:
1. Each cluster must have at least one object
2. An object must belong to only one cluster
Medoid: A Medoid is a point in the cluster from which the sum of distances to other
data points is minimal.
There are three types of algorithms for K-Medoids Clustering:
1. PAM (Partitioning Around Clustering)
2. CLARA (Clustering Large Applications)
3. CLARANS (Randomized Clustering Large Applications)
o PAM is the most powerful algorithm of the three algorithms but has the
disadvantage of time complexity.
o The following K-Medoids are performed using PAM.
o In the further parts, we'll see what CLARA and CLARANS are.
Algorithm:
[Link]: select k random points out of the n data points as the medoids.
[Link] each data point to the closest medoid by using any common distance metric
methods.

86
[Link] the cost decreases: For each medoid m, for each data o point which is not a
medoid:
o Swap m and o, associate each data point to the closest medoid, and recompute
the cost.
o If the total cost is more than that in the previous step, undo the swap.

Let’s consider the following example: If a graph is drawn using the above data points,
we obtain the following:

Step 1: Let the randomly selected 2 medoids, so select k = 2, and let C1 -(4, 5) and C2
-(8, 5) are the two medoids.
Step 2: Calculating cost. The dissimilarity of each non-medoid point with the medoids
is calculated and tabulated:

87
 o Here we have used Manhattan distance formula to calculate the distance
matrices between medoid and non-medoid points.
o That formula tell that Distance = |X1-X2| + |Y1-Y2|.
o Each point is assigned to the cluster of that medoid whose dissimilarity is
less. Points 1, 2, and 5 go to cluster C1 and 0, 3, 6, 7, 8 go to cluster C2.
o The Cost = (3 + 4 + 4) + (3 + 1 + 1 + 2 + 2) = 20
Step 3: randomly select one non-medoid point and recalculate the cost.
o Let the randomly selected point be (8, 4).
o The dissimilarity of each non-medoid point with the medoids – C1 (4, 5) and
C2 (8, 4) is calculated and tabulated.

o Each point is assigned to that cluster whose dissimilarity is less.

o So, points 1, 2, and 5 go to cluster C1 and 0, 3, 6, 7, 8 go to cluster C2.
o The New cost = (3 + 4 + 4) + (2 + 2 + 1 + 3 + 3) = 22 Swap Cost = New
Cost – Previous Cost = 22 – 20 and 2 >0
o As the swap cost is not less than zero, we undo the swap.
o Hence (4, 5) and (8, 5) are the final medoids.
88
HIERARCHICAL METHODS
o Hierarchical clustering methods group data into a hierarchy of clusters,
represented as a tree-like structure called a dendrogram.
o These methods do not require the number of clusters k as input, unlike
partitioning methods.
o Instead, a hierarchy of clusters is built by merging or splitting clusters.
AGGLOMERATIVE VERSUS DIVISIVE HIERARCHICAL CLUSTERING
[Link]. Parameters Agglomerative Clustering Divisive Clustering
1. Category Bottom-up approach Top-down approach
Each data point starts in its own All data points start in a
cluster, and the algorithm single cluster, and the
Approach recursively merges the closest algorithm recursively splits
2.
pairs of clusters until a single the cluster into smaller sub-
cluster containing all the data clusters until each data
points is obtained. point is in its own cluster.
Agglomerative clustering is
Comparatively less
generally more computationally
expensive as divisive
expensive, especially for large
Complexity clustering only requires the
datasets as this approach requires
3. level calculation of distances
the calculation of all pairwise
between sub-clusters,
distances between data points,
which can reduce the
which can be computationally
computational burden.
expensive.
Divisive clustering may
create sub-clusters around
Agglomerative clustering can
outliers, leading to
handle outliers better than divisive
4. Outliers suboptimal clustering
clustering since outliers can be
results.
absorbed into larger clusters

89
 Divisive clustering can be
Agglomerative clustering tends to
more difficult to interpret
Interpretab produce more interpretable results
since the dendrogram
ility since the dendrogram shows the
shows the splitting process
5. merging process of the clusters,
of the clusters, and the user
and the user can choose the
must choose a stopping
number of clusters based on the
criterion to determine the
desired level of granularity.
number of clusters.
Implement
Scikit-learn provides multiple
ation
linkage methods for Divisive clustering is not
6. agglomerative clustering, such as currently implemented in
“ward,” “complete,” “average,” Scikitlearn.
and “single,”

Here are some of the

Here are some of the applications
applications in which
in which Agglomerative
Divisive Clustering is used
Clustering is used :
:
Image segmentation, Customer
7. Example Market segmentation,
segmentation, Social network
Anomaly detection,
analysis, Document clustering,
Biological classification,
Genetics, genomics, etc., and
Natural language
many more.
processing, etc.

BALANCED ITERATIVE REDUCING AND CLUSTERING USING HIERARCHIES

o BIRCH is a hierarchical clustering algorithm designed for large datasets.
o It incrementally and dynamically clusters incoming multi-dimensional data
points while maintaining efficiency in both time and memory usage.
o BIRCH is particularly useful when clustering massive datasets that do not fit
into memory.
Features of BIRCH
 Designed for large datasets.
 Incremental clustering: Processes data points in one scan (or a small number of
scans), making it suitable for streaming or massive datasets.
 Uses a Clustering Feature Tree (CF Tree) to summarize data efficiently.
 Handles noise and outliers effectively.
 Allows for refining clusters in later stages.

90
Clustering Feature (CF)
o BIRCH introduces a data summarization concept called Clustering Feature
(CF), which is used to represent clusters compactly.
A Clustering Feature (CF) of a subcluster is a triple:

Where:
 NNN: Number of data points in the cluster.
 LSLSLS: Linear sum of the data points.

SS: Sum of the squared data points.

From the CF, key properties of the cluster can be computed:

 Centroid: Centroid=LS/N Radius (measure of cluster tightness):

o Diameter: Distance between two farthest points in the cluster.

CF Tree
o The CF Tree is a balanced tree structure used to store the clustering features
of clusters.
o It summarizes the data in a memory-efficient manner and allows quick access
to cluster information.
Structure of the CF Tree:
 Leaf Nodes: Contain clustering features (CF entries) representing clusters of
data points.

91
  Non-leaf Nodes: Contain CF entries that summarize the CFs of their child nodes.
 The tree maintains a branching factor (B), which controls the number of children
per node.
CF Tree Properties:
1. Height-Balanced Tree: Ensures efficiency when inserting or retrieving CFs.
2. Node Threshold: A threshold TTT defines the maximum radius or diameter a
cluster can have in a leaf node.
3. Clusters that exceed the threshold are split, and CF entries are adjusted
recursively up the tree.
BIRCH Algorithm Steps
Phase 1: Build the CF Tree
1. Insert data points one by one into the CF Tree.
2. For each point, find the nearest CF entry in a leaf node.
3. If the point can be absorbed into an existing CF (within threshold T), update the
CF.
4. If not, create a new CF entry. If the leaf node overflows, split the node.
5. Repeat until all points are processed.
Phase 2: Condense the CF Tree (Optional)
 Further condense the CF Tree to reduce its size.
 Remove outliers or merge clusters based on tighter thresholds.
Phase 3: Global Clustering
 Apply another clustering algorithm (e.g., k-means or hierarchical clustering) to
the CF entries in the leaf nodes.
 This step refines the clusters produced in Phase 1.
Phase 4: Cluster Refinement
 Refine the resulting clusters as needed by redistributing points or adjusting
cluster centroids.
Advantages of BIRCH
1. Scalability: Handles large datasets efficiently due to incremental clustering.
2. Memory Efficiency: Summarizes data using the CF Tree structure, saving
memory.

92
 3. Speed: Processes data in a single scan (or small scans), reducing computational
overhead.
4. Handles Noise: Effectively deals with noise and outliers during clustering.
5. Versatility: Combines hierarchical clustering with other methods like k-means
for refinement.
Limitations of BIRCH
1. Sensitive to Order: Results can depend on the order in which data points are
inserted.
2. Threshold Parameter T: Choosing an appropriate threshold for cluster radius or
diameter can be challenging.
3. Limited to Spherical Clusters: Works best for clusters with spherical shapes.
4. Single Pass Trade-off: Early decisions about clusters can sometimes lead to
suboptimal results.
CHAMELEON
o Chameleon is a hierarchical clustering algorithm that uses dynamic modeling
to decide the similarity among pairs of clusters.
o It was changed based on the observed weaknesses of two hierarchical
clustering algorithms such as ROCK and CURE.
o ROCK and related designs emphasize cluster interconnectivity while
neglecting data regarding cluster proximity.
o CURE and related design consider cluster proximity yet neglect cluster
interconnectivity.
o In Chameleon, cluster similarity is assessed depending on how well-
connected objects are inside a cluster and on the proximity of clusters.
o Especially, two clusters are combined if their interconnectivity is high and
they are close together.
o It does not base on a static, user-supplied model and can automatically adapt
to the internal features of the clusters being combined.
o The merge process supports the discovery of natural and homogeneous
clusters and is used for all types of data considering a similarity function can
be defined.

93
 o Chameleon needs the k-nearest-neighbor graph technique to make a sparse
graph,
o Where each vertex of the graph defines a data object, and there exists an edge
among two vertices (objects) if one object is between the k-most-similar
objects of the other.
o The edges are weighted to reflect the similarity among objects.
o Chameleon uses a graph partitioning algorithm to partition the k-nearest-
neighbor graph into a large number of relatively small subclusters.
o It can use an agglomerative hierarchical clustering algorithm that repeatedly
merges subclusters based on their similarity.
o It can determine the pairs of most similar subclusters, it takes into account
both the interconnectivity as well as the closeness of the clusters.
o The k-nearest-neighbor graph captures the approach of neighborhood
dynamically: the neighborhood radius of an object is decided by the density
of the region in which the object resides.
o In a dense area, the neighborhood is represented narrowly.
o In a sparse region, it is represented more widely.
o This influence results in more natural clusters, in comparison with density-
based methods like DBSCAN that instead use a worldwide neighborhood.
o Furthermore, the density of the region is recorded as the weight of the edges.
o Especially, the edges of a dense region tend to weigh more than that of a
sparse region.
o The graph-partitioning algorithm partitions the k-nearest-neighbor graph
such that it makes smaller the edge cut.
o That is, cluster C is subdivided into sub-clusters Ciand Cj to minimize the
weight of the edges that can be cut should C be bisected into Ci and Cj .
o Edge cut is indicated EC (Ci, Cj )and determines the absolute
interconnectivity between cluster Ci and Cj .
PROBABILISTIC HIERARCHICAL CLUSTERING
o Hierarchical clustering refers to an unsupervised learning procedure that
determines successive clusters based on previously defined clusters.

94
 o It works via grouping data into a tree of clusters.
o Hierarchical clustering stats by treating each data points as an individual
cluster.
o The endpoint refers to a different set of clusters, where each cluster is
different from the other cluster, and the objects within each cluster are the
same as one another.
There are two types of hierarchical clustering

o Agglomerative Hierarchical Clustering

o Divisive Clustering

Agglomerative hierarchical clustering

o Agglomerative clustering is one of the most common types of hierarchical
clustering used to group similar objects in clusters.
o Agglomerative clustering is also known as AGNES (Agglomerative
Nesting).
o In agglomerative clustering, each data point act as an individual cluster and
at each step, data objects are grouped in a bottom-up method.
o Initially, each data object is in its cluster. At each iteration, the clusters are
combined with different clusters until one cluster is formed.
Agglomerative hierarchical clustering algorithm

1. Determine the similarity between individuals and all other clusters. (Find
proximity matrix).
2. Consider each data point as an individual cluster.
3. Combine similar clusters.
4. Recalculate the proximity matrix for each cluster.
5. Repeat step 3 and step 4 until you get a single cluster.

95
Step 1:
o Consider each alphabet (P, Q, R, S, T, V) as an individual cluster and find
the distance between the individual cluster from all other clusters.
Step 2:
o Now, merge the comparable clusters in a single cluster.
o Let’s say cluster Q and Cluster R are similar to each other so that we can
merge them in the second step.
o Finally, we get the clusters [ (P), (QR), (ST), (V)]
Step 3:
o Here, we recalculate the proximity as per the algorithm and combine the two
closest clusters [(ST), (V)] together to form new clusters as [(P), (QR),
(STV)]
Step 4:
o Repeat the same process.
o The clusters STV and PQ are comparable and combined together to form a
new cluster. Now we have [(P), (QQRSTV)].
Step 5:
o Finally, the remaining two clusters are merged together to form a single
cluster [(PQRSTV)]

96
Divisive Hierarchical Clustering
o Divisive hierarchical clustering is exactly the opposite of Agglomerative
Hierarchical clustering.
o In Divisive Hierarchical clustering, all the data points are considered an
individual cluster, and in every iteration,
o The data points that are not similar are separated from the cluster.
o The separated data points are treated as an individual cluster. Finally, we are
left with N clusters.

Advantages of Hierarchical clustering

o It is simple to implement and gives the best output in some cases.

o It is easy and results in a hierarchy, a structure that contains more information.
o It does not need us to pre-specify the number of clusters.

Disadvantages of hierarchical clustering

o It breaks the large clusters.

o It is Difficult to handle different sized clusters and convex shapes.
o It is sensitive to noise and outliers.
o The algorithm can never be changed or deleted once it was done previously.

97