Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Adaptive Graph-Based Algorithms for Conditional Anomaly Detection and Semi-Supervised Learning

Valko, Michal (2011) Adaptive Graph-Based Algorithms for Conditional Anomaly Detection and Semi-Supervised Learning. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Primary Text

Download (2MB) | Preview


We develop graph-based methods for conditional anomaly detection and semi-supervised learning based on label propagation on a data similarity graph. When data is abundant or arrive in a stream, the problems of computation and data storage arise for any graph-based method. We propose a fast approximate online algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local representative points that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties. Anomaly detection techniques are used to identify anomalous (unusual) patterns in data. In clinical settings, these may concern identifications of unusual patient--state outcomes or unusual patient-management decisions. Therefore, we also present graph-based methods for detecting conditional anomalies and apply it to the identification of unusual clinical actions in hospitals. Our hypothesis is that patient-management actions that are unusual with respect to the past patients may be due to errors and that it is worthwhile to raise an alert if such a condition is encountered. Conditional anomaly detection extends standard unconditional anomaly framework but also faces new problems known as fringe and isolated points. We devise novel nonparametric graph-based methods to tackle these problems. Our methods rely on graph connectivity analysis and soft harmonic solution. Finally, we conduct an extensive human evaluation study of our conditional anomaly methods by 15 experts in critical care.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairHauskrecht, Milosmilos@pitt.eduMILOS
Committee MemberLitman, Dianelitman@cs.pitt.eduDLITMAN
Committee MemberMarai, G. Elisabetamarai@cs.pitt.eduMARAI
Committee MemberLafferty,
Date: 30 September 2011
Date Type: Completion
Defense Date: 1 August 2011
Approval Date: 30 September 2011
Submission Date: 22 June 2011
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Institution: University of Pittsburgh
Schools and Programs: Dietrich School of Arts and Sciences > Computer Science
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Anomaly Detection; Graph-Based Learning; Online Learning; Semi-Supervised Learning; Adaptive Learning; Machine Learning
Other ID:, etd-06222011-175928
Date Deposited: 10 Nov 2011 19:48
Last Modified: 19 Dec 2016 14:36


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item