@article{miettinen2008discrete,
  abstract = {Matrix decomposition methods represent a data matrix as a product of two factor matrices: one containing basis vectors that represent meaningful concepts in the data and another describing how the observed data can be expressed as combinations of the basis vectors. Decomposition methods have been studied extensively, but many methods return real-valued matrices. Interpreting real-valued factor matrices is hard if the original data is Boolean. In this paper, we describe a matrix decomposition formulation for vBoolean data, the Discrete Basis Problem. The problem seeks for a Boolean decomposition of a binary matrix, thus allowing the user to easily interpret the basis vectors. We also describe a variation of the problem, the Discrete Basis Partitioning Problem. We show that both problems are NP-hard. For the Discrete Basis Problem, we give a simple greedy algorithm for solving it; for the Discrete Basis Partitioning Problem, we show how it can be solved using existing methods. We present experimental results for the greedy algorithm and compare it against other well-known methods. Our algorithm gives intuitive basis vectors, but its reconstruction error is usually larger than with the real-valued methods. We discuss the reasons for this behavior.
},
  author = {Miettinen, Pauli and Mielikäinen, Taneli and Gionis, Aristides and Das, Gautam and Mannila, Heikki},
  doi = {10.1109/TKDE.2008.53},
  interhash = {1799269370f8bbb6860151b13145ad7f},
  intrahash = {b9e0638656d2fcd0c2965aff0ee0112e},
  journal = {IEEE Transactions on Knowledge and Data Engineering},
  month = oct,
  number = 10,
  pages = {1348--1362},
  publisher = {IEEE},
  title = {The Discrete Basis Problem},
  url = {http://dx.doi.org/10.1109/TKDE.2008.53},
  volume = 20,
  year = 2008
}

@inproceedings{tatti2006dimension,
  abstract = {Many 0/1 datasets have a very large number of variables; however, they are sparse and the dependency structure of the variables is simpler than the number of variables would suggest. Defining the effective dimensionality of such a dataset is a nontrivial problem. We consider the problem of defining a robust measure of dimension for 0/1 datasets, and show that the basic idea of fractal dimension can be adapted for binary data. However, as such the fractal dimension is difficult to interpret. Hence we introduce the concept of normalized fractal dimension. For a dataset D, its normalized fractal dimension counts the number of independent columns needed to achieve the unnormalized fractal dimension of D. The normalized fractal dimension measures the degree of dependency structure of the data. We study the properties of the normalized fractal dimension and discuss its computation. We give empirical results on the normalized fractal dimension, comparing it against PCA.},
  author = {Tatti, N. and Mielikainen, T. and Gionis, A. and Mannila, H.},
  booktitle = {Proceedings of the Sixth IEEE International Conference on Data Mining (ICDM 2006)},
  doi = {10.1109/ICDM.2006.167},
  interhash = {5164cd6a09b802d14dce6d3947df60cd},
  intrahash = {0a8ad03bc7d2d0d7d77ee73eede4ecc0},
  issn = {1550-4786},
  month = dec,
  organization = {IEEE},
  pages = {603--612},
  title = {What is the Dimension of Your Binary Data?},
  url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4053086},
  year = 2006
}

@mastersthesis{jaeschke2005struktur,
  author = {Jäschke, Robert},
  interhash = {e15113f443dfe1054256c34bd365a4ad},
  intrahash = {3cbe3059391ae0f543c448701949ddbc},
  school = {Technische Universität Dresden},
  title = {Die Struktur der Monoide binärer Relationen auf endlichen Mengen},
  type = {Diplomarbeit},
  url = {http://www.kde.cs.uni-kassel.de/pub/pdf/jaeschke2005struktur.pdf},
  year = 2005
}

@inproceedings{conf/pkdd/ReadPHF09,
  author = {Read, Jesse and Pfahringer, Bernhard and Holmes, Geoffrey and Frank, Eibe},
  booktitle = {ECML/PKDD (2)},
  crossref = {conf/pkdd/2009-2},
  date = {2009-08-31},
  editor = {Buntine, Wray L. and Grobelnik, Marko and Mladenic, Dunja and Shawe-Taylor, John},
  ee = {http://dx.doi.org/10.1007/978-3-642-04174-7_17},
  interhash = {d07ad188ba08d6931d30643b849de079},
  intrahash = {ab264cc42b2f1530ab6da09aaf5fa0fc},
  isbn = {978-3-642-04173-0},
  pages = {254-269},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Classifier Chains for Multi-label Classification.},
  url = {http://dblp.uni-trier.de/db/conf/pkdd/pkdd2009-2.html#ReadPHF09},
  volume = 5782,
  year = 2009
}

@article{yang69,
  author = {Yang, Jaw-Ching},
  interhash = {3091b16dcb62c8a3e7cbe0e7505d7331},
  intrahash = {0ba5eb63a0676e360e42c305a9297c4a},
  journal = {Proceedings of the American Mathematical Society},
  pages = {134-135},
  title = {A theorem on the semigroup of binary relations},
  volume = 22,
  year = 1969
}

@article{zaretski63,
  author = {Zarecki, K. A.},
  interhash = {430f0d7da2f2497b1e17285ea9540ae4},
  intrahash = {89cada18428af1a3bba8a6e4efd8be16},
  journal = {Matematiceskij Sbornik},
  note = {(russisch)},
  pages = {291-305},
  title = {Die {H}albgruppe der binären {R}elationen},
  volume = 61,
  year = 1963
}

@article{schein76,
  author = {Schein, Boris M.},
  interhash = {f569baaa08e9eab441e3786c088193dd},
  intrahash = {6790c6e1d10a6b12b5556342a9681413},
  journal = {Semigroup Forum},
  pages = {95-102},
  title = {Regular elements of the semigroup of all binary relations},
  volume = 13,
  year = 1976
}

@article{schein70,
  author = {Plemmons, R. J. and Schein, B. M.},
  interhash = {341ee2f65ff1940a18d395f2cf5eadd4},
  intrahash = {100395cf400ac7fa3109ce84ae9bcdb8},
  journal = {Semigroup Forum},
  pages = {267-271},
  title = {Groups of Binary Relations},
  volume = 1,
  year = 1970
}

@article{plemmons70,
  author = {Plemmons, R. J. and West, M. T.},
  interhash = {307a57a63944ca1e3db479bc0ebc1799},
  intrahash = {253e1239891456fa4c67c07b95e62ed3},
  journal = {Pacific Journal of Mathematics},
  number = 3,
  pages = {743-753},
  title = {On the semigroup of binary relations},
  volume = 35,
  year = 1970
}

@article{montague69,
  author = {Montague, J. S. and Plemmons, R. J.},
  interhash = {5c420ea16daeb1d8ac737a77bed3a51a},
  intrahash = {74a0526ce6e2a4fe8e2f0d17dc7caf5d},
  journal = {Journal of Algebra},
  pages = {575-587},
  title = {Maximal Subgroups of the Semigroup of Relations},
  volume = 13,
  year = 1969
}

@article{markowsky77,
  author = {Markowsky, George},
  interhash = {8492e269df9fd1cc3eb81c39154aecca},
  intrahash = {5150c38951d8b2512727c201197e6cdf},
  journal = {Semigroup Forum},
  pages = {253-259},
  title = {Bounds on the index and period of a binary relation on a finite set},
  volume = 13,
  year = 1977
}

@article{konieczny94,
  author = {Konieczny, Janusz},
  interhash = {2f0fc12a47ba98a11a2746376b118e48},
  intrahash = {133de67269c9bfa71bde2b7615f0c1b3},
  journal = {Semigroup Forum},
  pages = {235-252},
  title = {Green's Equivalences in Finite Semigroups of Binary Relations},
  volume = 48,
  year = 1994
}

@article{konieczny05,
  author = {Konieczny, Janusz},
  interhash = {b45742ab9ef8aa1421d9fd02db40dfa7},
  intrahash = {4092862e96f165222ba8beef4a6d461f},
  note = {to be published},
  title = {A Proof of {D}evadze's Theorem on Generators of the Semigroup of Boolean Matrices},
  year = 2005
}

@article{konieczny02,
  author = {Konieczny, Janusz},
  interhash = {68bc453b63e41a469f5c566e241986e0},
  intrahash = {78b8c939590dc5d30f4016126c693a46},
  journal = {Southeast Asian Bulletin of Mathematics},
  pages = {627-641},
  title = {The Semigroup Generated by Regular Boolean Matrices},
  volume = 25,
  year = 2002
}

@phdthesis{konieczny92,
  address = {University Park, PA},
  author = {Konieczny, Janusz},
  interhash = {60bdd44499692bb4fd980a3c056ca9a4},
  intrahash = {5b9baadb9546877d03df5fa7751433d3},
  school = {The Pennsylvania State University},
  title = {Semigroups of binary Relations},
  year = 1992
}

@article{devadze68-2,
  author = {Devadze, H. M.},
  interhash = {0b7e4d5d50bceba261c1143ee27c2b8f},
  intrahash = {ca97abe7105f15d09ab9983c54986538},
  journal = {Ucenye zapiski / Leningradskij Gosudarstvennyj Pedagogiceskij Institut Imeni A. I. Gercena},
  note = {(russisch)},
  pages = {92-100},
  title = {Erzeugende {M}engen bestimmter Unterhalbgruppen der {H}albgruppe aller binären {R}elationen auf einer endlichen {M}enge},
  volume = 387,
  year = 1968
}

@article{devadze68,
  author = {Devadze, H. M.},
  interhash = {ceae40797dbc8d58aea5d23f9a58af03},
  intrahash = {059e8c6458166d878c19dda553f2c6bc},
  journal = {Doklady Akademii Nauk BSSR},
  note = {(russisch)},
  number = 9,
  pages = {765-768},
  title = {Erzeugende {M}engen der {H}albgruppe aller binären {R}elationen auf einer endlichen {M}enge},
  volume = 12,
  year = 1968
}

@techreport{seminar,
  author = {Kriegel, Daniela and Hahn, Andreas and J{"a}schke, Robert},
  institution = {Technische Universit{"a}t Dresden},
  interhash = {ac48c0162b80b3afff5d099eea508961},
  intrahash = {101efca8c9368b56d680ce92329784e5},
  title = {Halbgruppen bin{"a}rer {R}elationen auf einer {$3$}-elementigen {M}enge},
  type = {Seminararbeit},
  year = 2004
}