Abstract
We present an exact and highly scalable sampling algorithm that can be used as an alternative to exhaustive local pattern discovery methods. It samples patterns according to their frequency of occurrence and can substantially improve efficiency and controllability of the pattern discovery processes. While previous sampling approaches mainly rely on the Markov chain Monte Carlo method, our procedure is direct, i.e. a non process-simulating sampling algorithm. The advantages of this direct method are an almost optimal time complexity per pattern as well as an exactly controlled distribution of the produced patterns. In addition we present experimental results which demonstrate that these procedures can improve the accuracy of pattern-based models similar to frequent sets and often also lead to substantial gains in terms of scalability. An extended version of this paper shows modifications of the here presented algorithm to sample by other frequency related distributions. Namely, area, squared frequency and a class discriminativity measure.
Original language | English |
---|---|
Title of host publication | LWA 2011 |
Subtitle of host publication | Technical Report of the Symposium "Lernen, Wissen, Adaptivitat - Learning, Knowledge, and Adaptivity 2011" of the GI Special Interest Groups KDML, IR and WM 2011 |
Place of Publication | Germany |
Publisher | Fakultät für Informatik |
Pages | 114-121 |
Number of pages | 8 |
Publication status | Published - 2011 |
Externally published | Yes |
Event | Symposium on Learning, Knowledge, and Adaptivity 2011, LWA 2011 - Magdeburg, Germany Duration: 28 Sep 2011 → 30 Sep 2011 |
Conference
Conference | Symposium on Learning, Knowledge, and Adaptivity 2011, LWA 2011 |
---|---|
Country/Territory | Germany |
City | Magdeburg |
Period | 28/09/11 → 30/09/11 |