Exploring classifier attribute interactions and time series using constrained randomisations

Abstract

Gaining insight into structures and properties in data is a central problem in data mining and knowledge discovery. This is essential when the data is to be used, e.g., in decision-making. In this thesis we consider investigating the structure of data in two cases: temporal structures in time series, and attribute interactions utilised by classifiers.

Time series are ubiquitous and represent an important type of data. We investigate temporal structures in time series, focusing on interval sequences. We seek explanations for observed properties by constructing and evaluating null hypotheses describing the internal properties of the time series. We approach this as a hypothesis testing problem where observed time series are compared to randomly generated instances. The properties being investigated are modelled in terms of constraints on the randomisations, allowing complex relationships to be examined and explained. Furthermore, we apply computational methods in the analysis of a sleep study to explain the relationship between time series representing heart rate variability and performance on a psychomotor vigilance test.

Classification has wide applicability in multiple domains, however, many high-performing classifiers are essentially opaque, black-box algorithms, making it difficult to gain insight into the basis for predictions. In classifier analysis we consider attribute interactions utilised by classifiers. An interaction means that two or more attributes jointly carry information with respect to, e.g., a class label. We study two different types of interactions. Firstly, we investigate relationships between attributes in a dataset and show how this is related to factorising the class-conditional joint data distribution, such that attributes in the same factor are interacting while attributes in different factors are independent, given the class. We devise a method for testing the hypothesis that a dataset originates from a generating distribution with a particular factorised form. Secondly, we investigate how classifiers exploit attribute interactions in making predictions and develop a novel framework based on constrained randomisations for partitioning the attributes of a dataset into groups based on how they are jointly exploited by the classifier. The methods developed here are useful in several data analysis applications, e.g., in enhancing the interpretability of opaque classifiers, detecting adverse drug interactions in pharmacovigilance, anonymising data and gaining insight into the structure of datasets.

Ett centralt problem inom data- och kunskapsutvinning är hur man skall få insikt i datans egenskaper och struktur. Detta är viktigt då datan används t.ex. för beslutsfattande. I denna avhandling granskas strukturer i data i två fall: temporala strukturer i tidsserier, samt hur klassificerare använder sig av samverkan mellan attribut i datan.

Tidsserier är typiskt förekommande och utgör en viktig typ av data. Vi undersöker temporala strukturer i tidsserier, med fokus på intervallsekvenser. Vi skapar nollhypoteser som beskriver tidsseriens interna egenskaper och söker med hjälp av dessa förklaringar för observerade egenskaper. Vi närmar oss detta som ett hypotestestningsproblem, där den observerade tidsserien jämförs mot slumpmässigt skapade instanser. Egenskaperna vi undersöker beskrivs genom begränsade randomiseringar, vilket gör det möjligt att undersöka och hitta förklaringar till komplexa förhållanden. Vidare använder vi beräkningsmetoder i analysen av data från en sömnstudie, för att förklara förhållandet mellan tidsserier beskrivande hjärtfrekvensvariabilitet och psykomotorisk vaksamhet.

Klassificering har ett brett tillämpningsområde inom olika områden, men ett problem är att många av de mest effektiva klassificerarna är opaka svarta lådor, vilket gör det är svårt att få inblick i hur förutsägelserna görs. Vi studerar här hur klassificerare utnyttjar attributinteraktioner i datan. En interaktion innebär att två eller fler attribut samverkar med avseende på t.ex. en klassvariabel. Vi betraktar två typer av interaktioner. Det första fallet utgörs av förhållandet mellan attribut i datamängden. Vi visar hur detta problem är relaterat till en faktorisering av attributens klassberoende simultanfördelning, så att attribut i samma faktor samverkar, medan attribut i olika faktorer är oberoende, med hänsyn till klassvariabeln. Vi presenterar en ny metod för att undersöka hypotesen att datan härstammar från en distribution med en särskild faktoriserad form. Det andra fallet gäller hur klassificerare utnyttjar attributinteraktioner för förutsägelser och vi presenterar en ny metod för att dela in attributen i grupper på basen av hur algoritmen utnyttjar deras samverkan. Metoden bygger på begränsad randomisering av datan. Metoderna vi utvecklat är generella och användbara inom analys av data och de möjliggör t.ex. förståelse av svårtolkade klassificerare, undersökning av samverkan mellan mediciner inom farmakovigilans, anonymisering av data samt bättre insikt i datans struktur.