0
$\begingroup$

I'm taking a class on data mining and of course, we went over the Apriori algorithm (Fast Algorithms for Mining Association Rules).

Something that I want to know is how do apriori based algorithms avoid finding spurious relationships when generating association rules?

Is this a case of being aware of the difference between predictive vs. causal analysis? Meaning there could be some hidden third factor causing the association but as long as the relationship holds we don't care what that third factor is. Association rules don't say that A causes B, they just say that A and B happen together often.

Is it because these algorithms are often run on VERY large data sets so the probability of having an excessive number of false positives is very low. Meaning, if you only have a sample size of 50 you could get a associations that complete a low support just by change but that is unlikely to happen when you have 500,000 or 5,000,000 samples.

$\endgroup$
1
$\begingroup$

A short answer is that you can't avoid spurious rules if you use only Apriori.

The traditional approach for association rule mining uses only two search criteria: minimum frequency and minimum "confidence" (precision). So, the dependence (association in the statistical sense) is not necessarily positive even in the sample. In addition, you may find a lot of rules that express statistically insignificant positive dependence (are not likely to hold in the population). Usually, only the latter are called "spurious" but obviously the independence rules and those expressing negative dependence are also false discoveries.

It is possible to search for only statistically significant positive associations (in the statistical sense, i.e. dependencies) but it is more difficult. A simple approach is to search first for traditional association rules but with so small minimum frequency and confidence thresholds that no true associations are missed. This may be computationally impossible, but if you succeed, you can afterwards select only the significant positive associations with other goodness measures and/or statistical tests. A more feasible approach is to search directly statistical associations (also called dependency rules and classification rules) with statistical goodness measures but without any minimum frequency requirements (or at most minimal). For a short review of such approaches, see e.g. Hämäläinen: Kingfisher: an efficient algorithm for searching for both positive and negative dependency rules with statistical significance measures, Knowledge and Information Systems August 2012, Volume 32, Issue 2, pp 383–414 (also https://pdfs.semanticscholar.org/59ff/5cda9bfefa3b188b5302be36e956b717e28e.pdf).

Another problem in association rule mining (and pattern discovery, in general) is the multiple testing problem. Even if you check that each pattern is statistically significant (not likely due to chance), you may end up with many spurious associations. The problem is that each test can make an error (declare a spurious pattern significant) and when many patterns are tested, the errors cumulate. As a solution, you should adjust the p-values or significance levels so that the overall probability of errors is sufficiently small.

The large data size affects the problem but the effects can be unpredictable. In large data Apriori usually requires large minimum frequency thresholds (the search is often otherwise infeasible) and frequent patterns tend to be also significant (if they just express positive dependence). However, in large data even weakest dependencies may appear statistically significant (see discussion here Statistical significance versus sample size), while in the same time you may miss the most significant (but less frequent) associations altogether.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.