Association Rules algorithm [support,confidence]

In assotiation rules each rule has a [support, confidence] part. In Microsoft Association Rules there is a [probability,importance] measure in each rule and importance can be greater that 1.

I found the following in msdn but i'm not sure if i understood correctly.

MINIMUM_PROBABILITY: Specifies the minimum probability that a rule is true. For example, setting this value to 0.5 specifies that no rule with less than fifty percent probability is generated.
The default is 0.4.

MAXIMUM_SUPPORT: Specifies the maximum number of cases in which an itemset can have support. If this value is less than 1, the value represents a percentage of the total cases. Values greater than 1 represent the absolute number of cases that can contain the itemset.
The default is 1.

My questions are
1) Can i explain the [probability,importance] in [support,confidence]? If yes, how?
2) What importance>1 means?

Thank you in advance.

MS Association Rules still has [support, confidence] like any other AR implementation. If you take a rule of the form

A -> B

Support is the number of times the itemset A occurs, and confidence is the probability that B occurs when A occurs. Importance is a different measure that indicates the lift of the rule e.g. the increase in probability of the target over the probability of the target at random, which is why it can be greater than 1.

In the DM viewers, the support is indicated on the Itemset page.

|||

If i have a rule A,B => C and an itemset A,B,C with support 2000 then the support of the rule is 2000? How can i calculate the confidence then?

Thank you for your reply.

|||

If your rule is A,B=>C then:

Confidence == Probability == Numberof(A,B,C) / Numberof(A,B)

|||That was very helpful thank you :)|||Hi all,

I am trying to make an algorithm that also takes into account how "important" an association rule is. I found that "importance" is something that I am missing.

Ho is importance calculated ?

greetz,
Alex|||

The formula, with some details, is discussed in this thread:

http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=290186&SiteID=1

Association algorithm itemsets

What is the algorithm that generates the itemsets in the Association model? I'm looking to possibly use this part of the Association algorithm (i.e. the grouping into itemsets) in a separate plug-in algorithm.

The algorithm is based on the 'a priori' technique. Basically, 1-itemsets are filtered based on certain thresholds, then the algorithm moves to computing 2-itemsets and so on. Brief details on how Microsoft Association Rules work: http://msdn2.microsoft.com/en-us/library/ms174916.aspx

Hope this helps

Association algorithm - Importance of a rule

Can anyone tell me, how the Business íntelligence Studio calculates the importance of a rule. I can't find the formula. I know some formulas, but the result in SQL Server is completly different.

Thanks!

For rules, the importance is calculated using the following formula:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

An importance of 0 means there is no association between A and B. A positive

importance score means that the probability of B goes up when A is true. A

negative importance score means that the probability of B goes down when A

is true.

Below is an example of the correlation counts of donut and muffin derived

from a purchase database. Each cell value represents the number of

transactions. For example, 15 out of 100 transactions include a customer

purchasing both donuts and muffins.

Donut Not Donut Total

Muffin 15 5 20

Not muffin 75 5 80

Total 90 10 100

The support, probability, and importance of related itemsets and rules for

donut and muffin:

Support({Donut}) = 90

Support({Muffin}) = 20

Support ({Donut, Muffin}) = 15

Probability({Donut}) = 90/100 = 0.9

Probability({Muffin}) = 20/100 = 0.2

Probability({Donut, Muffin}) = 15/100 = 0.15

Probability(Donut|Muffin) = 15/20 = 0.75

Probability(Muffin|Donut) = 15/90 = 0.167

Importance({Donut, Muffin}) = 0.15/(0.2*0.9) = 0.833

Importance (Donut=>Muffin) = ln(Probability(Donut|Muffin)

/Probability(Donult|Not Muffin))= ln(0.8) = -0.223

Importance(Muffin=>Donut) = ln(Probability(Muffin|Donut)

/Probability(Muffin| Not Donut)) = ln(0.33) = -1.100

From the importance of the itemset {Donut, Muffin}, we can see Donut and

Muffin are negatively correlated; it is rather unlikely for someone who buys

a Muffin to also buy a Donut.

The Importance score is also known as Weight of Evidence (WOE).

|||

Hi,thanks a lot for your answer!

I recalculated the importance with your formulas and compared this with the results of the microsoft association algorithm.

Your formula for the importance is almost right, but it calculates the importance for

Muffin =>Donut and not Donut => Muffin

and it must be "log" and not "ln" !!

So at the end, this must be the right formula:

Importance(Muffin =>Donut) = log(Probability(Donut|Muffin) / Probability(Donut|Not Muffin) )

and for

Importance(Donut=> Muffin) = log(Probability(Muffin|Donut) / Probability(Muffin|Not Donut) )

UllaH

|||

Acutually at the beginning of Jamie's answer, the formular has been already there correctly:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

Regards,

|||

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

It makes more sense to me if a and b are switched in the log function

Can some one point me to a Microsoft Research Paper "With all due respect to all" not just odiscussion Onions that discusses the theoretical background for calculating Rule importance?

Musa

|||Dear all,

I try to run the "donuts and muffins" example by using SQL 2005 BI but I didnot have the results as the formula you instruct (Importance (A=>B) = log ( p(a|b) / p(a|not b) ) ). Please explain me more detail.

probability importance
0.938 0.105302438 F3 = NotMuffin -> F2 = Donut








0.833 0.218055761 F2 = Donut -> F3 = NotMuffin


0.75 -0.105302438 F3 = Muffin -> F2 = Donut


0.5 -0.218055761 F2 = NotDonut -> F3 = NotMuffin


0.5 0.458637849 F2 = NotDonut -> F3 = Muffin

Thank you very much.
Your truthly,

Association algorithm - Importance of a rule

Can anyone tell me, how the Business íntelligence Studio calculates the importance of a rule. I can't find the formula. I know some formulas, but the result in SQL Server is completly different.

Thanks!

For rules, the importance is calculated using the following formula:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

An importance of 0 means there is no association between A and B. A positive

importance score means that the probability of B goes up when A is true. A

negative importance score means that the probability of B goes down when A

is true.

Below is an example of the correlation counts of donut and muffin derived

from a purchase database. Each cell value represents the number of

transactions. For example, 15 out of 100 transactions include a customer

purchasing both donuts and muffins.

Donut Not Donut Total

Muffin 15 5 20

Not muffin 75 5 80

Total 90 10 100

The support, probability, and importance of related itemsets and rules for

donut and muffin:

Support({Donut}) = 90

Support({Muffin}) = 20

Support ({Donut, Muffin}) = 15

Probability({Donut}) = 90/100 = 0.9

Probability({Muffin}) = 20/100 = 0.2

Probability({Donut, Muffin}) = 15/100 = 0.15

Probability(Donut|Muffin) = 15/20 = 0.75

Probability(Muffin|Donut) = 15/90 = 0.167

Importance({Donut, Muffin}) = 0.15/(0.2*0.9) = 0.833

Importance (Donut=>Muffin) = ln(Probability(Donut|Muffin)

/Probability(Donult|Not Muffin))= ln(0.8) = -0.223

Importance(Muffin=>Donut) = ln(Probability(Muffin|Donut)

/Probability(Muffin| Not Donut)) = ln(0.33) = -1.100

From the importance of the itemset {Donut, Muffin}, we can see Donut and

Muffin are negatively correlated; it is rather unlikely for someone who buys

a Muffin to also buy a Donut.

The Importance score is also known as Weight of Evidence (WOE).

|||

Hi,thanks a lot for your answer!

I recalculated the importance with your formulas and compared this with the results of the microsoft association algorithm.

Your formula for the importance is almost right, but it calculates the importance for

Muffin =>Donut and not Donut => Muffin

and it must be "log" and not "ln" !!

So at the end, this must be the right formula:

Importance(Muffin =>Donut) = log(Probability(Donut|Muffin) / Probability(Donut|Not Muffin) )

and for

Importance(Donut=> Muffin) = log(Probability(Muffin|Donut) / Probability(Muffin|Not Donut) )

UllaH

|||

Acutually at the beginning of Jamie's answer, the formular has been already there correctly:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

Regards,

|||

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

It makes more sense to me if a and b are switched in the log function

Can some one point me to a Microsoft Research Paper "With all due respect to all" not just odiscussion Onions that discusses the theoretical background for calculating Rule importance?

Musa

|||Dear all,

I try to run the "donuts and muffins" example by using SQL 2005 BI but I didnot have the results as the formula you instruct (Importance (A=>B) = log ( p(a|b) / p(a|not b) ) ). Please explain me more detail.

probability importance
0.938 0.105302438 F3 = NotMuffin -> F2 = Donut








0.833 0.218055761 F2 = Donut -> F3 = NotMuffin


0.75 -0.105302438 F3 = Muffin -> F2 = Donut


0.5 -0.218055761 F2 = NotDonut -> F3 = NotMuffin


0.5 0.458637849 F2 = NotDonut -> F3 = Muffin

Thank you very much.
Your truthly,

Association algorithm - Importance of a rule

Can anyone tell me, how the Business íntelligence Studio calculates the importance of a rule. I can't find the formula. I know some formulas, but the result in SQL Server is completly different.

Thanks!

For rules, the importance is calculated using the following formula:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

An importance of 0 means there is no association between A and B. A positive

importance score means that the probability of B goes up when A is true. A

negative importance score means that the probability of B goes down when A

is true.

Below is an example of the correlation counts of donut and muffin derived

from a purchase database. Each cell value represents the number of

transactions. For example, 15 out of 100 transactions include a customer

purchasing both donuts and muffins.

Donut Not Donut Total

Muffin 15 5 20

Not muffin 75 5 80

Total 90 10 100

The support, probability, and importance of related itemsets and rules for

donut and muffin:

Support({Donut}) = 90

Support({Muffin}) = 20

Support ({Donut, Muffin}) = 15

Probability({Donut}) = 90/100 = 0.9

Probability({Muffin}) = 20/100 = 0.2

Probability({Donut, Muffin}) = 15/100 = 0.15

Probability(Donut|Muffin) = 15/20 = 0.75

Probability(Muffin|Donut) = 15/90 = 0.167

Importance({Donut, Muffin}) = 0.15/(0.2*0.9) = 0.833

Importance (Donut=>Muffin) = ln(Probability(Donut|Muffin)

/Probability(Donult|Not Muffin))= ln(0.8) = -0.223

Importance(Muffin=>Donut) = ln(Probability(Muffin|Donut)

/Probability(Muffin| Not Donut)) = ln(0.33) = -1.100

From the importance of the itemset {Donut, Muffin}, we can see Donut and

Muffin are negatively correlated; it is rather unlikely for someone who buys

a Muffin to also buy a Donut.

The Importance score is also known as Weight of Evidence (WOE).

|||

Hi,thanks a lot for your answer!

I recalculated the importance with your formulas and compared this with the results of the microsoft association algorithm.

Your formula for the importance is almost right, but it calculates the importance for

Muffin =>Donut and not Donut => Muffin

and it must be "log" and not "ln" !!

So at the end, this must be the right formula:

Importance(Muffin =>Donut) = log(Probability(Donut|Muffin) / Probability(Donut|Not Muffin) )

and for

Importance(Donut=> Muffin) = log(Probability(Muffin|Donut) / Probability(Muffin|Not Donut) )

UllaH

|||

Acutually at the beginning of Jamie's answer, the formular has been already there correctly:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

Regards,

|||

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

It makes more sense to me if a and b are switched in the log function

Can some one point me to a Microsoft Research Paper "With all due respect to all" not just odiscussion Onions that discusses the theoretical background for calculating Rule importance?

Musa

|||Dear all,

I try to run the "donuts and muffins" example by using SQL 2005 BI but I didnot have the results as the formula you instruct (Importance (A=>B) = log ( p(a|b) / p(a|not b) ) ). Please explain me more detail.

probability

importance

0.938

0.105302438

F3 = NotMuffin -> F2 = Donut

0.833

0.218055761

F2 = Donut -> F3 = NotMuffin

0.75

-0.105302438

F3 = Muffin -> F2 = Donut

0.5

-0.218055761

F2 = NotDonut -> F3 = NotMuffin

0.5

0.458637849

F2 = NotDonut -> F3 = Muffin

Thank you very much.
Your truthly,

Association algorithm - Importance of a rule

Can anyone tell me, how the Business íntelligence Studio calculates the importance of a rule. I can't find the formula. I know some formulas, but the result in SQL Server is completly different.

Thanks!

For rules, the importance is calculated using the following formula:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

An importance of 0 means there is no association between A and B. A positive

importance score means that the probability of B goes up when A is true. A

negative importance score means that the probability of B goes down when A

is true.

Below is an example of the correlation counts of donut and muffin derived

from a purchase database. Each cell value represents the number of

transactions. For example, 15 out of 100 transactions include a customer

purchasing both donuts and muffins.

Donut Not Donut Total

Muffin 15 5 20

Not muffin 75 5 80

Total 90 10 100

The support, probability, and importance of related itemsets and rules for

donut and muffin:

Support({Donut}) = 90

Support({Muffin}) = 20

Support ({Donut, Muffin}) = 15

Probability({Donut}) = 90/100 = 0.9

Probability({Muffin}) = 20/100 = 0.2

Probability({Donut, Muffin}) = 15/100 = 0.15

Probability(Donut|Muffin) = 15/20 = 0.75

Probability(Muffin|Donut) = 15/90 = 0.167

Importance({Donut, Muffin}) = 0.15/(0.2*0.9) = 0.833

Importance (Donut=>Muffin) = ln(Probability(Donut|Muffin)

/Probability(Donult|Not Muffin))= ln(0.8) = -0.223

Importance(Muffin=>Donut) = ln(Probability(Muffin|Donut)

/Probability(Muffin| Not Donut)) = ln(0.33) = -1.100

From the importance of the itemset {Donut, Muffin}, we can see Donut and

Muffin are negatively correlated; it is rather unlikely for someone who buys

a Muffin to also buy a Donut.

The Importance score is also known as Weight of Evidence (WOE).

|||

Hi,thanks a lot for your answer!

I recalculated the importance with your formulas and compared this with the results of the microsoft association algorithm.

Your formula for the importance is almost right, but it calculates the importance for

Muffin =>Donut and not Donut => Muffin

and it must be "log" and not "ln" !!

So at the end, this must be the right formula:

Importance(Muffin =>Donut) = log(Probability(Donut|Muffin) / Probability(Donut|Not Muffin) )

and for

Importance(Donut=> Muffin) = log(Probability(Muffin|Donut) / Probability(Muffin|Not Donut) )

UllaH

|||

Acutually at the beginning of Jamie's answer, the formular has been already there correctly:

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

Regards,

|||

Importance (A=>B) = log ( p(a|b) / p(a|not b) )

It makes more sense to me if a and b are switched in the log function

Can some one point me to a Microsoft Research Paper "With all due respect to all" not just odiscussion Onions that discusses the theoretical background for calculating Rule importance?

Musa

|||Dear all,

I try to run the "donuts and muffins" example by using SQL 2005 BI but I didnot have the results as the formula you instruct (Importance (A=>B) = log ( p(a|b) / p(a|not b) ) ). Please explain me more detail.

probability importance
0.938 0.105302438 F3 = NotMuffin -> F2 = Donut








0.833 0.218055761 F2 = Donut -> F3 = NotMuffin


0.75 -0.105302438 F3 = Muffin -> F2 = Donut


0.5 -0.218055761 F2 = NotDonut -> F3 = NotMuffin


0.5 0.458637849 F2 = NotDonut -> F3 = Muffin

Thank you very much.
Your truthly,
sql

Assertion failed error while resizing a vector in a plug-in algorithm

I got an Assertion failed error while resizing a vector in a plug-in algorithm.

In order to isolate the problem I created a simple model class in Navigator.h file as shown below:

//========================= begin code =======================

class CStateStats
{
public:
DOUBLE m_dblSum;
DOUBLE m_dblSqrSum;
public:
CStateStats()
{
m_dblSum = 0.0;
m_dblSqrSum = 0.0;
}
};

class CAttStats : public DMHALLOC
{
public:
dmh_vector<CStateStats> vstatestats;
public:
CAttStats() : vstatestats (*this)
{
}
};

//========================= end code =======================

The access to DMHALLOC is provided in that class and in Navigator class as shown below:

//========================= begin code =======================

class ATL_NO_VTABLE NAVIGATOR :

public DMHALLOC,

public CComObjectRootEx<CComMultiThreadModel>,

public CComCoClass<NAVIGATOR, &CLSID_NAVIGATOR>,

public ISupportErrorInfo,

public IDMAlgorithmNavigation

{

public:

NAVIGATOR() : _viAttributeOutput(*this), _vCAttStats(*this)

//========================= end code =======================

I succeded making room for _vCAttStats vector, but when I tried providing room for the vectors of the vector I got an Assertion failed error (file dmhallocator.h Line:56 Expression assert(_dmhalloc._spidmmemoryallocator != NULL)). Please, see the code below, included in NAVIGATOR::GetNodeArrayProperty function:

//========================= begin code =======================

_vCAttStats.resize (2); // <<<<< succeeded here!

// make space for the states

_vCAttStats[0].vstatestats.resize(ulStates); // <<<<<<< assertion failed here!

//========================= end code =======================

I tried using a vector-of-vector approach and I also succeeded.

But I have to use that kind of structure: a vector of class with a vector inside.

I think I must provide a similar approach of vector-of-vector existing in DmhVector.h but I don't know how to do it.

I would apreciate any help.

hello,Claudio

It looks like:

- the original DMHALLOC (containing the allocator pointer), NAVIGATOR is passed properly to the vector of CAttStats, _vCAttStats and used correctly in resizing it

- during resize, STL calls the default constructor for CAttStats , which does not take any argument. Consequently, the CAttStats DMHALLOC instance does not contain an allocator pointer

- _vCAttStats[0].vstatestats.resize(ulStates); attempts to resize the vstatestats vector, which does not have a properly initialized DMHALLOC , hence the assertion that fails

To confirm my hypothesis in your code, try to use _vCAttStats[0].vstatestats.get_allocator() right before calling resize. It is likely NULL or uninitialized (well, not the actual object which is a reference, but the IDMMemoryAllocator pointer it contains).

The simplest and most reliable solution is:

- do not derive CAttStats from DMHALLOC

- use, instead, an IDMMemoryAllocator member inside the CAttStats

- explicitly set that member to the current allocator before using vstatestats

- use IDMMemoryAllocator->Alloc( n*sizeof(CStateStats) ) to get a C-style buffer of state stats which can be freed in the destructor of CAttStats with IDMMemoryAllocator->Free

Hope this helps

|||

Hi Bogdan,

Thanks for you help.

I suceeded using your suggestions.

The drawbacks of this approach are that I have to explicitly initialize vstatestats because the class constructor is not called anymore when I provide room for the buffer and I don't have anymore the vector facilities. Am I correct?