Efficient search for statistically significant dependency rules in binary data

Abstract

Analyzing statistical dependencies is a fundamental problem in all empirical science. Dependencies help us understand causes and effects, create new scientific theories, and invent cures to problems. Nowadays, large amounts of data is available, but efficient computational tools for analyzing the data are missing.

In this research, we develop efficient algorithms for a commonly occurring search problem - searching for the statistically most significant dependency rules in binary data. We consider dependency rules of the form X->A or X->not A, where X is a set of positive-valued attributes and A is a single attribute. Such rules describe which factors either increase or decrease the probability of the consequent A. A classical example are genetic and environmental factors, which can either cause or prevent a disease.

The emphasis in this research is that the discovered dependencies should be genuine - i.e. they should also hold in future data. This is an important distinction from the traditional association rules, which - in spite of their name and a similar appearance to dependency rules - do not necessarily represent statistical dependencies at all or represent only spurious connections, which occur by chance. Therefore, the principal objective is to search for the rules with statistical significance measures. Another important objective is to search for only non-redundant rules, which express the real causes of dependence, without any occasional extra factors. The extra factors do not add any new information on the dependence, but can only blur it and make it less accurate in future data.

The problem is computationally very demanding, because the number of all possible rules increases exponentially with the number of attributes. In addition, neither the statistical dependency nor the statistical significance are monotonic properties, which means that the traditional pruning techniques do not work. As a solution, we first derive the mathematical basis for pruning the search space with any well-behaving statistical significance measures. The mathematical theory is complemented by a new algorithmic invention, which enables an efficient search without any heuristic restrictions. The resulting algorithm can be used to search for both positive and negative dependencies with any commonly used statistical measures, like Fisher's exact test, the chi-squared measure, mutual information, and z scores.

According to our experiments, the algorithm is well-scalable, especially with Fisher's exact test. It can easily handle even the densest data sets with 10000-20000 attributes. Still, the results are globally optimal, which is a remarkable improvement over the existing solutions. In practice, this means that the user does not have to worry whether the dependencies hold in future data or if the data still contains better, but undiscovered dependencies.

Tilastollisten riippuvuuksien etsintä ja analysointi on empiiristen tieteiden keskeisimpiä tehtäviä. Tilastolliset riippuvuudet auttavat ymmärtämään asioiden syy- ja seuraussuhteita, kuten esimerkiksi mitkä geenit tai elämäntavat altistavat tietyille sairauksille ja mitkä puolestaan suojelevat niiltä. Tällaiset riipuvuudet voidaan esittää havainnollisesti riippuvuussääntöinä muotoa ABCD->E, missä A,B,C ja D vastaavat havaittuja tekijöitä ja E on niistä tilastollisesti riippuva seuraus.

Analysoitavaa dataa on nykyaikana valtavasti saatavilla lähes miltätahansa elämän alueelta. Ongelmana on, ettei kaikkia mahdollisia riippuvuuksia voida tutkia tavallisilla tilastollisilla työkaluilla tai tietokoneohjelmilla. Esimerkiksi jos datassa esiintyy 20 muuttujaa ja kukin niistä voi saada vain kaksi arvoa (esimerkiksi geeni esiintyy tai ei esiiny näytteessä), erilaisia mahdollisia riippuvuussääntöjä on jo yli 20 miljoonaa kappaletta. Usein data kuitenkin sisältää vähintään satoja tai jopa kymmeniä tuhansia muuttujia, eikä kaikkien mahdollisten riippuvuussääntöjen tutkiminen ole laskennallisesti mahdollista.

Tässä tutkimuksessa on kehitetty tarvittavia tehokkaita laskentamenetelmiä tilastollisesti kaikkein merkitsevimpien riippuvuussääntöjen etsintään binääridatasta, jossa kukin muuttuja voi saada vain kaksi arvoa. Geenitutkimuksen lisäksi tällaista dataa esiintyy luonnostaan mm. biologiassa (eri havaintopaikoilla esiintyvät kasvi- ja eläinlajit) sekä markkinointitutkimuksessa (ns. ostoskoridata eli mitä tuotteita kukin asiakas on ostanut). Mikäli datassa on kuitenkin useampiarvoisia muuttujia, ne voidaan aina tarvittaessa esittää binäärimuodossa.

Aiempiin tiedonlouhintamenetelmiin verrattuna tutkimuksessa kehitetyt menetelmät ovat sekä tehokkaampia että luotettavampia. Perinteisesti suurien datajoukkojen riippuvuuksia on yritetty analysoida assosiaatiosäännöillä, mutta assosiaatiosäännöt eivät välttämättä esitä mitään tilastollista riippuvuutta tai riippuvuus voi olla tilastollisesti merkityksetön (sattuman tuotetta). Lisäksi assosiaatiosääntöjen hakumenetelmät ovat tehottomia löytämään kaikkia merkityksellisiä riippuvuuksia. Tämän tutkimuksen tuloksena kehitetyllä tietokoneohjelmalla on kuitenkin mahdollista hakea kaikkein merkityksellisimmät riippuvuudet jopa kymmeniä tuhansia muuttujia sisältävistä datajoukoista tavallisella pöytätietokoneella. Hakukriteerinä, jolla riippuvuuden tilastollinen merkityksevyys arvioidaan, voidaan käyttää melkein mitätahansa tilastollista mittaa kuten Fisherin eksaktia testiä tai chi2-mittaa.