Mining Methods - Mining Various Kinds of Association Rules

Unit-2

Introduction

• Data mining is the process of extracting hidden patterns from large data sets.
• One of the fundamental techniques in data mining is association rule mining.
• To identify relationships between items in a dataset, Association rule mining is used.
• Multilevel Association Rule mining is an extension of Association Rule mining.
• Multilevel Association Rule mining is a powerful tool that can be used to discover patterns and trends.

Multilevel Association Rule in data mining

Multilevel Association Rule mining is a technique that extends Association Rule mining to discover relationships between items at different levels of granularity.

Multilevel Association Rule mining can be classified into two types:

1. multi-dimensional Association Rule
2. multi-level Association Rule

1. Multi-level Association Rule mining

This is used to find relationships between items at different levels of granularity. For example, in a retail dataset, multi-level Association Rule mining can be used to find relationships between individual items and categories of items.

Association rules generated from mining data at multiple levels of abstraction are called multiple-level or multilevel association rules.

Using Uniform Minimum Support For All Levels (Referred To As Uniform Support):

The same minimum support threshold is used when mining at each level of abstraction

Using reduced minimum support at lower levels (referred to as reduced support):

•Each level of abstraction has its own minimum support threshold.

•The deeper the level of abstraction, the smaller the corresponding threshold

Using item or group-based minimum support (referred to as group-based support):

Because users or experts often have insight as to which groups are more important than others, it is sometimes more desirable to set up user-specific, item, or group based minimal support thresholds when mining multilevel rules.

2. Multi-dimensional Association Rule mining

This is used to find relationships between items in different dimensions of a dataset.

For example, in a sales dataset, multi-dimensional Association Rule mining can be used to find relationships between products, regions, and time.

• Association rules that imply a single predicate, that is, the predicate buys Is called as single dimensional or intra dimensional association rule.

Example:

buys(X, “digital camera”) ⇒ buys(X, “HP printer”)

• It contains a single distinct predicate (e.g., buys) with multiple occurrences (i.e., the predicate occurs more than once within the rule.

Single Dimensional Or Intra Dimensional Association Rule

• Association rules that involve two or more dimensions or predicates can be referred to as multidimensional association rules

Ex:age(X, “20...29”) ∧ occupation(X, “student”) ⇒ buys (X,“laptop”)

• Each of which occurs only once in the rule. Hence, we say that it has no repeated predicates.
• Multidimensional association rules with no repeated predicates are called inter dimensional association rules.

Multidimensional Association Rules

Multidimensional association rules with repeated predicates, which contain multiple occurrences of some predicates. These rules are called hybrid-dimensional association rule

Example:

age(X, “20...29”)∧buys(X, “laptop”)⇒buys(X, “HP printer”)

​

Hybrid-dimensional Association Rule

Association and Correlation in Data Mining

• Association is a technique used in data mining to identify the relationships or co-occurrences between items in a dataset.
• Correlation Analysis is a data mining technique used to identify the degree to which two or more variables are related or associated with each other.
• Correlation refers to the statistical relationship between two or more variables, where the variation in one variable is associated with the variation in another variable.
• Correlation can be positive, negative, or zero, depending on the direction and strength of the relationship between the variables.

Types of Correlation Analysis in Data Mining

There are three main types of correlation analysis used in data mining.

1. Pearson Correlation Coefficient
2. Kendall Rank Correlation
3. Spearman Rank Correlation

Pearson Correlation Coefficient

• Pearson correlation measures the linear relationship between two continuous variables.
• It ranges from -1 to +1, where -1 indicates a perfect negative correlation, 0 indicates no correlation, and +1 indicates a perfect positive correlation.
• The Pearson correlation coefficient between two variables, X and Y, is calculated as.,

Kendall Rank Correlation

• Kendall Rank Correlation is a measure used to find how similar two lists are in terms of the order or rank of their items.
• It looks at pairs of items from each list and checks if their relative ranking (which comes first, which comes second) is the same in both lists.
• If it is, they’re considered a "concordant" pair; if not, they’re a "discordant" pair.

The Kendall Rank Correlation score ranges from -1 to +1:

+1 means the rankings are in complete agreement (perfect positive correlation),

0 means there is no consistent pattern,

-1 means the rankings are in complete disagreement (perfect negative correlation).

Spearman Rank Correlation

• Spearman correlation uses the actual numerical ranks of the data instead of counting the number of concordant and discordant pairs.
• The formula for Spearman correlation is -

where

d is the difference between the ranks of the paired observations

n is the number of observations.

Constraint Based Association Rules:

• A data mining process may uncover thousands of rules from a given set of data, most of which end up being unrelated or uninteresting to the users.
• Users have a good sense of which “direction” of mining may lead to interesting patterns and the “form” of the patterns or rules they would like to find.
• A good heuristic is to have the users specify such intuition or expectations as constraints to confine the search space. This strategy is known as constraint-based mining.

Constraint based mining provides

User Flexibility: provides constraints on what to be mined.

System Optimization: 

Explores constraints to help efficient mining.

The constraints can include the following:

Knowledge type constraints: These specify the type of knowledge to be mined, such as association or correlation.

Data constraints: These specify the set of task-relevant data.

Dimension/level constraints: These specify the desired dimensions (or attributes) of the data, or levels of the concept hierarchies, to be used in mining.

Interestingness constraints: These specify thresholds on statistical measures of rule interestingness, such as support, confidence, and correlation.

Rule constraints: These specify the form of rules to be mined. Such constraints may be expressed as rule templates, as the maximum or minimum number of predicates that can occur in the rule antecedent or consequent, or as relationships among attributes, attribute values, and/or aggregates. The constraints can be specified using a high-level declarative data mining query language and user interface.

Graph Pattern Mining

• Graph mining is a process in which the mining techniques are used in finding a pattern or relationship in the given real-world collection of graphs.
• By mining the graph, frequent substructures and relationships can be identified which helps in clustering the graph sets, finding a relationship between graph sets, or discriminating or characterizing graphs.
• This task is important since data is naturally represented as graph in many domains (e.g. social networks, chemical molecules, map of roads in a country). It is thus desirable to analyze graph data to discover interesting, unexpected, and useful patterns, that can be used to understand the data or take decisions.

What is a graph: A graph is a set of vertices and edges, having some labels.

Types of graphs: connected and disconnected 

A connected graph in this context is a graph where it is possible to go from any node to any node cities by following the roads.  If a graph is not connected, it is said to be a disconnected graph.

Types of graphs: Directed and Undirected

A graph where vertices and edges. Some edges can be travelled in both directions(directed graph) while some edges may be travelled in only a single direction is known as undirected graph.

 Frequent Sub-graph Mining

•  The goal of sub-graph mining is to discover interesting subgraph(s) appearing in a set of graphs (a graph database).
• Sub-graph has been considered as interesting if it appears multiple times in a set of graphs. In other words, we want to discover sub-graphs that are common to multiple graphs.
• The task of finding frequent sub-graphs in a set of graphs is called  frequent subgraph mining.
• a graph database (a set of graphs)
• a parameter called the minimum support threshold (minsup).

A frequent subgraph is a subgraph that appears in at least minsup graphs from a graph database.

set the minsup parameter to 3

 subgraph is frequent and is said to have a support (a frequency) of 3 since it appears in three of the input graphs.

the minsup parameter is generally set by trial and error.  If this parameter is set too high, few subgraphs will be found, while if it is set too low, hundred or millions of subgraphs may be found, depending on the input database.

Mining frequent subgraphs in a single graph

• frequent subgraph mining that consists of finding all frequent subgraphs in a single graph rather than in a graph database.
• This graph contains seven vertices and six edges. If we perform frequent subgraph mining on this single graph by setting the minsup parameter to 2

​

These subgraphs are said to be frequent because they appear at least twice in the input graph.

Algorithms Used: Gspan, Closed Graph