Advanced search
Add to list

Maximum entropy models and subjective interestingness: an application to tiles in binary databases

Tijl De Bie (UGent)
Author
Organization
Abstract
Recent research has highlighted the practical benefits of subjective interestingness measures, which quantify the novelty or unexpectedness of a pattern when contrasted with any prior information of the data miner (Silberschatz and Tuzhilin, Proceedings of the 1st ACM SIGKDD international conference on Knowledge discovery and data mining (KDD95), 1995; Geng and Hamilton, ACM Comput Surv 38(3):9, 2006). A key challenge here is the formalization of this prior information in a way that lends itself to the definition of a subjective interestingness measure that is both meaningful and practical. In this paper, we outline a general strategy of how this could be achieved, before working out the details for a use case that is important in its own right. Our general strategy is based on considering prior information as constraints on a probabilistic model representing the uncertainty about the data. More specifically, we represent the prior information by the maximum entropy (MaxEnt) distribution subject to these constraints. We briefly outline various measures that could subsequently be used to contrast patterns with this MaxEnt model, thus quantifying their subjective interestingness. We demonstrate this strategy for rectangular databases with knowledge of the row and column sums. This situation has been considered before using computation intensive approaches based on swap randomizations, allowing for the computation of empirical p-values as interestingness measures (Gionis et al., ACM Trans Knowl Discov Data 1(3):14, 2007). We show how the MaxEnt model can be computed remarkably efficiently in this situation, and how it can be used for the same purpose as swap randomizations but computationally more efficiently. More importantly, being an explicitly represented distribution, the MaxEnt model can additionally be used to define analytically computable interestingness measures, as we demonstrate for tiles (Geerts et al., Proceedings of the 7th international conference on Discovery science (DS04), 2004) in binary databases.
Keywords
Swap randomizations, Rectangular databases, Prior information, Subjective interestingness measures, COMPLEX NETWORKS, Maximum entropy principle

Citation

Please use this url to cite or link to this publication:

MLA
De Bie, Tijl. “Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases.” DATA MINING AND KNOWLEDGE DISCOVERY 23.3 (2011): 407–446. Print.
APA
De Bie, T. (2011). Maximum entropy models and subjective interestingness: an application to tiles in binary databases. DATA MINING AND KNOWLEDGE DISCOVERY, 23(3), 407–446.
Chicago author-date
De Bie, Tijl. 2011. “Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases.” Data Mining and Knowledge Discovery 23 (3): 407–446.
Chicago author-date (all authors)
De Bie, Tijl. 2011. “Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases.” Data Mining and Knowledge Discovery 23 (3): 407–446.
Vancouver
1.
De Bie T. Maximum entropy models and subjective interestingness: an application to tiles in binary databases. DATA MINING AND KNOWLEDGE DISCOVERY. 2011;23(3):407–46.
IEEE
[1]
T. De Bie, “Maximum entropy models and subjective interestingness: an application to tiles in binary databases,” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 23, no. 3, pp. 407–446, 2011.
@article{6936406,
  abstract     = {Recent research has highlighted the practical benefits of subjective interestingness measures, which quantify the novelty or unexpectedness of a pattern when contrasted with any prior information of the data miner (Silberschatz and Tuzhilin, Proceedings of the 1st ACM SIGKDD international conference on Knowledge discovery and data mining (KDD95), 1995; Geng and Hamilton, ACM Comput Surv 38(3):9, 2006). A key challenge here is the formalization of this prior information in a way that lends itself to the definition of a subjective interestingness measure that is both meaningful and practical. In this paper, we outline a general strategy of how this could be achieved, before working out the details for a use case that is important in its own right. Our general strategy is based on considering prior information as constraints on a probabilistic model representing the uncertainty about the data. More specifically, we represent the prior information by the maximum entropy (MaxEnt) distribution subject to these constraints. We briefly outline various measures that could subsequently be used to contrast patterns with this MaxEnt model, thus quantifying their subjective interestingness. We demonstrate this strategy for rectangular databases with knowledge of the row and column sums. This situation has been considered before using computation intensive approaches based on swap randomizations, allowing for the computation of empirical p-values as interestingness measures (Gionis et al., ACM Trans Knowl Discov Data 1(3):14, 2007). We show how the MaxEnt model can be computed remarkably efficiently in this situation, and how it can be used for the same purpose as swap randomizations but computationally more efficiently. More importantly, being an explicitly represented distribution, the MaxEnt model can additionally be used to define analytically computable interestingness measures, as we demonstrate for tiles (Geerts et al., Proceedings of the 7th international conference on Discovery science (DS04), 2004) in binary databases.},
  author       = {De Bie, Tijl},
  issn         = {1384-5810},
  journal      = {DATA MINING AND KNOWLEDGE DISCOVERY},
  keywords     = {Swap randomizations,Rectangular databases,Prior information,Subjective interestingness measures,COMPLEX NETWORKS,Maximum entropy principle},
  language     = {eng},
  number       = {3},
  pages        = {407--446},
  title        = {Maximum entropy models and subjective interestingness: an application to tiles in binary databases},
  url          = {http://dx.doi.org/10.1007/s10618-010-0209-3},
  volume       = {23},
  year         = {2011},
}

Altmetric
View in Altmetric
Web of Science
Times cited: