Multi-Assignment Clustering for Boolean Data Andreas P. Streich Mario Frank David Basin Joachim M. Buhmann andreas.streich@inf.ethz.ch mario.frank@inf.ethz.ch basin@inf.ethz.ch jbuhmann@inf.ethz.ch Department of Computer Science, ETH Zurich, Universit¨tsstrasse 6, CH-8006 Zurich, Switzerland a equally contributing corresponding author Abstract Conventional clustering methods typically assume that each data item belongs to a single cluster. This assumption does not hold in general. In order to overcome this limitation, we propose a generative method for clustering vectorial data, where each object can be assigned to multiple clusters. Using a deterministic annealing scheme, our method decomposes the observed data into the contributions of individual clusters and infers their parameters. Experiments on synthetic Boolean data show that our method achieves higher accuracy in the source parameter estimation and superior cluster stability compared to stateof-the-art approaches. We also apply our method to an important problem in computer security known as role mining. Experiments on real-world access control data show performance gains in generalization to new employees against other multi-assignment methods. In challenging situations with high noise levels, our approach maintains its good performance, while alternative state-of-the-art techniques lack robustness. This assumption is appropriate if membership in one group excludes membership in other groups and thus the dataset can be partitioned into homogeneous and disjoint subsets. However, the assumption of mutually exclusive cluster memberships fails for many domains. The properties of many data sets can be better explained in the more general setting, where data items can belong to multiple clusters. Speaking in generative terms, a data item is interpreted as a combination of emissions of all the sources it belongs to -- an interpretation similar to the one presented in (Streich & Buhmann, 2008). Consider, for instance, clustering the preferences of children: Being a chocolate addict does not exclude being fond of dinosaurs and thus being part of the reptile-lovers cluster. This point of view goes far beyond fuzzy clustering, where the exclusivity constraint is just weakened: an object belongs to a given number of clusters each with some percentage (this necessitates less preference for chocolate if the preference for reptiles rises -- explain this to your children!). If cluster memberships are represented as vectors of binary indicator variables, fuzzy clustering allows indicator values between 0 and 1. In ordinary clustering and fuzzy clustering, the membership indicators of each object sum to 1, whereas in Multi-Assignment Clustering, this sum can be any integer greater than or equal to 1. In this paper, we present a novel approach, called Multi-Assignment Clustering (MAC), for clustering Boolean vectorial data that can simultaneously belong to multiple clusters. In our generative model, each component of each data vector is either drawn from a signal distribution (given by the clusters the data item belongs to) or from an independent global noise distribution. We present an expectation-maximization (EM-)algorithm where the source prototypes of the clusters and the cluster memberships of each data item are simultaneously estimated as well as the mixture 1. Introduction Data clustering is the unsupervised learning task of dividing data into groups. If the goal is not only to group data, but also to infer the hidden structure responsible for generating the data, a source is associated with each cluster. Conventional clustering methods assume that each data item belongs to a single cluster. Appearing in Proceedings of the 26 th International Conference on Machine Learning, Montreal, Canada, 2009. Copyright 2009 by the author(s)/owner(s). Multi-Assignment Clustering for Boolean Data weight of the global noise source. In experiments with synthetic data, our method recovers the cluster prototypes with significantly higher accuracy than alternative methods (see Section 2), especially for datasets with high noise level. Furthermore, the assignment of data items to clusters has superior stability under resampling. We apply our model to an important problem arising in computer security: the automated engineering of roles for role-based access control (RBAC) or "role mining". An RBAC system is defined by assignments from users to roles and from roles to permissions. Roles can thus be interpreted as sets of permissions. A user is granted a permission if he is assigned to a role that contains this permission. The goal of role mining is to identify roles in an access-control system consisting of direct assignments of users to permissions. The assignment of users to multiple roles is a property of RBAC, which is explicitly permitted by the NIST standard for role-based access control (Ferraiolo et al., 2001). This design decision simplifies the structure of the roles. Users can be equipped with a set of basic permissions (check e-mail, change desktop background, etc.) by a common role. Specialized permissions can then be granted by assigning users to additional roles that are not shared by all users. As users can be assigned to multiple roles, one can equip the users with needed permissions using only a small total number of roles. In contrast, if users could be only assigned to single roles, then each user would require a role specially tailored to his job. As a result, the total number of roles needed in the system would be much higher. For enterprize systems with tens of thousands of users and permissions, manual role engineering is timeconsuming, costly, and error-prone. Therefore, automated approaches that find meaningful roles are highly desirable. We report on experimental results on access-control data showing that our approach finds good solutions even under difficult conditions. The remainder of the paper is organized as follows. We review related work in Section 2 before we introduce our model in Section 3 and derive the inference steps of the model parameters for a deterministic annealing algorithm. In Section 4, we report on experimental results with synthetic and real-world data. We conclude with a theoretical discussion of our method in Section 5 and an outlook in Section 6. our method and from each other. Binary independent component analysis (BICA) is a linear factor model for binary data proposed by Kab´n a and Bingham in (2008). As in standard ICA, the cluster prototypes are assumed to be orthogonal. BICA employs non-negative mixing coefficients for the assignment to multiple clusters, which sum up to 1. A Bayesian framework for inference in the Noisy-OR model (Pearl, 1988) is presented by Wood (2006). The Noisy-OR model combines emissions of multiple hidden sources by Boolean disjunction and adds a global drift towards 1. The Indian Buffet Process (IBP) (Griffiths & Ghahramani, 2005) is used as a prior for the cluster assignments. IBP assumes an infinite number of clusters of which only a finite set is responsible to explain the observed data. Wood (2006) proposes a Gibbs sampling scheme to infer the Noisy-OR parameters. We will refer to this model as the Infinite Noisy-OR (INO) throughout this article. The Discrete Basis Problem solver (DBPs) (Miettinen et al., 2006) is a greedy algorithm that picks the cluster centroids from a candidate set. Candidates are computed using association rule mining (Agrawal et al., 1993). A predefined number of centroids is then chosen and assigned to the objects such that the data set is optimally approximated. DBPs has no underlying probabilistic model. The role-mining problem (RMP) is presented in (Vaidya et al., 2007). The problem of automated engineering of roles, or role mining, goes back to (Kuhlmann et al., 2003). Since then, a number of combinatorial methods have been proposed that approximate a direct user-permission assignment matrix with roles as best possible, e.g. (Colantonio et al., 2008; Ene et al., 2008). Even though not originally designed for this application, we consider the DBPsolver as the best representative for these combinatorial methods. In (Frank et al., 2008) a probabilistic model corresponding to RMP is derived and its exclusive clustering variant is tested using the Gibbs sampling algorithm of Kemp et al. (2006). We did not find any probabilistic role-mining method that supports multicluster (multi-role) solutions. 3. Generative Data Model In this section, we propose a model for clustering binary vectorial data. Let N be the number of objects, D the number of dimensions, and K the number of clusters. We are given a binary data matrix x {0, 1}N ×D . Row i is denoted by xi· and column j by x·j . This notation will be used for all matrices. We aim to explain each xi· as the disjunction of the 2. Related Work We present here three state-of-the-art methods for clustering binary data and explain how they differ from Multi-Assignment Clustering for Boolean Data prototypes of all clusters the data item i belongs to. The matrix of Boolean prototypes is denoted by u {0, 1}K×D , where uk· denotes the prototype of the cluster k. The cluster memberships are coded by the binary assignment matrix z {0, 1}N ×K , where zik states whether object i belongs to cluster k. With these entities, the decomposition of x can be formalized by the Boolean matrix product x = z u, where is defined such that xij = k [zik ukj ] . 3.1. Probabilistic Model Finding optimal matrices z and u for the decomposition of x is NP-hard (Vaidya et al., 2007). A probabilistic representation allows us to drastically simplify the optimization problem. Therefore, we introduce independent random variables1 kj := p(ukj = 0) for the deterministic centroids u. The matrix of all Bernoulli parameters is denoted by [0, 1]K×D . We propose a mixture model where xij is either drawn from a signal or a noise component. The probability of xij under the signal model is K xij zik kj k=1 k=1 K zik kj 1-xij Alternatively, xij can be sampled from a global noise source with independent Bernoulli distribution parameterized by r (indicating the probability of a 1), i.e. pN (xij | r) = rxij (1 - r) 1-xij . (3) Unlike the Noisy-OR model, this noise process is symmetric and can produce both 0s and 1s. The indicator variable ij defines whether xij is sampled from the signal distribution (ij =0) or the noise distribution (ij =1). The combined distribution of xij is thus pM (xij | Li , , r, ij ) = pN (xij | r) ij pS (xij | Li , ) 1-ij . We assume that the elements of the matrix x are conditionally independent given the model parameters. Furthermore, we consider ij to be Bernoulli distributed with the parameter := p(ij = 1) called bit randomization probability. Thus we have pM (x | z, , r, ) = i,j pM (xij | Li , , r, ) ij i,j pM (x, | z, , r, ) = pM (x | z, , r, ) . (1) (1 - ) 1-ij . pS (xij | z, ) = 1- Marginalizing out , we get the data likelihood as pM (x | z, , r, ) = {} Note that some xij might be 1 because any of the sources to which the data item i belongs emits a 1 in dimension j. Conversely, xij is 0 only if all contributing sources emit a 0 in dimension j. This is reflected in (1) by the product over k. To simplify notation, we modify this expression: We replace the indicator vector zi· by the assignment set Li , containing the indices of all clusters that xi· belongs to, i.e. Li := {k {1, .., K} |zik = 1}. L denotes the set of all possible assignment sets which, if no constraints are imposed, is the power set of the set of clusters. Accordingly, we define Li j := kLi kj . As the conjunction of two Bernoulli distributed binary random variables is again Bernoulli distributed, Li j can be interpreted as the parameter of the Bernoulli-distribution describing the data with label set Li . However, we emphasize that Li j is only used for notational convenience. In all computations, it will be computed based on the parameters of single clusters, which are the only source parameters of the model. With this notation, the probability distribution of xij given the parameters of the signal model is pS (xij | Li , ) = [1 - Li j ] 1 pM (x, | z, , r, ) = i,j ( · pN (xij ) + (1 - ) · pS (xij )) . The costs of assigning a data item i to a label set L is defined as the negative logarithm of the likelihood of the data item, given its assignment to the label set L: Ri,L = - j log [ · pN (xij |r) + (1 - ) · pS (xij |L, )] . The normalized responsibilities i,L and the Lagrange functional F are defined as: i,L = ci,L L ci,L F = -T i log L ci,L , (4) with the auxiliary variable ci,L := exp (-Ri,L /T ). The expected risk over all data items and label sets is then R := E [Ri,L ] = i L i,L Ri,L . (5) xij [Li j ] 1-xij . (2) 3.2. Inference The model parameters pq (for p {1, . . . , K} and q {1, . . . , D}) as well as the expected bit randomization probability and the noise parameter r Defining kj as the probability of ukj being zero simplifies computations as compared to standard Bernoulli parameters, which indicate the probability for a 1. Multi-Assignment Clustering for Boolean Data are inferred by deterministic annealing (DA) (Rose et al., 1992; Buhmann & K¨hnel, 1993). DA is a u gradient descent optimization method that provides a smooth transition from the uniform distribution (having maximum entropy H) to a solution with minimal expected risk R. The Lagrange functional is F = R - T H, where the Lagrange parameter T (the computational temperature) controls the trade-off. Minimizing F at a given temperature T is thus equivalent to maximizing the entropy H under a constraint on the expected risk R. By gradually decreasing the temperature T , we obtain a homotopy method, which keeps the gradient-based expectation maximization scheme from getting trapped in local minima. In the estimation step, for each i and L, the risk Ri,L of assigning data item i to the label set L and the resulting responsibility i,L is computed given the current centroids . In the maximization step, we first determine the optimal values for and r and then use these values in the equations to determine the optimal source parameters . The individual steps are described below. We choose an initial temperature and a constant rate cooling scheme (T · T , with < 1) as described in (Rose et al., 1992). The optimization algorithm terminates if the responsibilities i,L have converged to one of the cluster sets L, for all objects i. Bit-Randomization Probability : The extremality condition of the free energy with respect to , the expected ratio of noisy elements in the matrix x, is given by F =- i,L i L j ij ij gL,j,1 · gL,j,0 Source Parameters : We derive the optimality condition for F with respect to pq as F = (1 - ) pq iq fL,j,1 ·fL,j,0iq ·i,L = 0 , (8) x 1-x i LLp with fL,j,1 := -L\p,q / ( r + (1 - ) (1 - L,q )) fL,q,0 := L\p,q / ( (1 - r) + (1 - )L,j ) L\p,j := kL,k=p k,j , with Lp := {L L|p L}. Equation 8 determines the value pq that minimizes F . The corresponding bisection search typically needs less than a dozen iterations to determine these values. and r are fixed to the value computed in the first part of the maximization step. i,L is also kept fix while both L,q and L\p,q are computed based on the source parameters . We use the values of the previous iterations for all p q , with p = p or q = q. Only at the end of the maximization step are the previous values of overwritten. These updates for the -parameters are done independently for all p and q. Namely, the independence assumption for different cluster parameters in the same dimension is a simplification. However, it drastically reduces the computational costs, keeps the results independent of the order in which the computations are done, and distorts the results only negligibly. The Matlab implementation of Multi-Assignment Clustering is available from the authors. 4. Experiments and Results In this section, we first introduce performance measures and then present experimental results on synthetic data. Afterwards, we report on our findings for role mining on a user-permission assignment dataset from a large enterprize. 4.1. Evaluation criteria The lack of a general formal objective function in clustering implies the absence of a unique general evaluation criterion for clustering solutions. We evaluate our experimental results using the measures that we intro^ ^ duce in this section. We denote by u and z the esti^ mated decomposition of the data matrix x. x denotes ^ ^ ^ the reconstruction of x, i.e. x := u z. Furthermore, in tests on synthetic data, we make comparisons between the noise-free data matrix xS := z u and the noisy data matrix x. Coverage Rate: This is the ratio of the number of ^ matrix elements that are 1 in both x and x to the x 1-x =0, (6) with gL,j,1 := gL,j,0 r - (1 - L,j ) r + (1 - ) (1 - L,j ) (1 - r) - L,j := . (1 - r) + (1 - )L,j The values of the source parameters and the responsibilities are kept fixed in this part of the algorithm. The value of with F ( ) = 0 is determined using bisection search. Noise Parameter r: The extremality condition for the probability r to emit a 1 by the noise process is F = r ij ij iL · hL,j,1 · hL,j,0 = 0 , x 1-x (7) i,j L with hL,j,1 := -1/ ( r + (1 - ) (1 - Lj )) hL,j,0 := 1/ ( (1 - r) + (1 - )Lj ) . Multi-Assignment Clustering for Boolean Data number of elements equal to 1 in x, i.e. cov := |{(i, j)|xij = xij = 1}| / |{(i, j)|xij = 1}| . ^ Coverage is a standard evaluation criterion in the rolemining literature. Instability: The notion of stability captures the requirement of stable clustering. Namely, a clustering solution based on a dataset should be reproducible for a different data set drawn from the same distribution (Lange et al., 2004). Training a classifier using the cluster solution of one data set and applying it to a second data set gives the desired measure. The instability of the clustering solution is the minimum disagreement under all permutations between the classification solution and the clustering result on the second dataset. Formally, let x(1) (x(2) ) be the first (second) data set, ^ each containing N samples and let z(1) (^(2) ) be the z cluster assignments inferred on the first (second) data ^ set. Let (1) be the classifier trained on x(1) , with z(1) used as label sets. Note that we need a classifier capable of handing multi-labels. Finally, let |L| be a permutation on |L| objects. Then, the instability is computed as |L| 1 min |L| - 1 N |L| n Source 1 Source 2 Source 3 5 10 15 20 25 Figure 1. Prototypes of the three sources used to generate the synthetic data. Black indicates a 1, white a 0. sources. A data item that is assigned to none of the sources is explained solely by the noise process. Afterwards, we sampled equally many data items from single sources and from the disjunction of multiple sources. Furthermore, some data items were generated by the noise distribution only. We ran experiments with different noise levels from 0% to 90%, for a total number of 500 data items. The results for MAC as well as for Infinite Noisy-OR (INO), Discrete Basis Problem solver (DBPs), and Binary Independent Component Analysis (BICA) are illustrated in Fig. 2. The average Hamming distance between the true and estimated centroids is shown in the upper graph (this magnitude equals the percentage of differing bits). The MAC algorithm outperforms its three competitors on all noise levels below 80%. Since the orthogonality assumption of BICA is not fulfilled by the data, its estimated centroids have a high deviation from the true ones. INO usually chooses a higher number of sources than the number K used to generate the data. In order to compare with the true centroids, we took the K sources that agreed the best, thereby granting this method a slight advantage. In terms of stability (lower graph), all methods are affected by increasing noise. BICA is relatively instable also on noise-free data but seems to be a bit more robust to noise than DBPs and INO. Except for very high noise levels (> 70%), MAC achieves higher stability than the other three methods. 4.3. Experiments on Real-World Data In this section, we evaluate our algorithm on the rolemining problem. The dataset we use for our experiments comes from the IT system of a bank from which we were given a user-permission assignment matrix with 4900 users and 1300 permissions. Before explaining the results, we first describe the properties of a good set of roles. A role-based access control system should generalize well to new users. The existing set of roles should suffice to endow a new employee with all permissions he needs to accomplish his tasks. In contrast, a role system that 1 i=1 |L| " " (2) (2) (1) (xi ) =^i· z , where equality means equality of the complete assignment vector zi· , i.e. the data item is assigned to the ^ same set of clusters. We use a nearest neighbor classifier with Hamming distance for (1) . As a random assignment to one of |L| cluster sets achieves a stabil|L| 1 ity measure of 1 - |L| , the factor |L|-1 allows us to compare clustering solutions with different numbers of clusters. Average Hamming Distance: This measure states how accurately the centroids of the underlying clusters are estimated. hamm := 1 min K K dH (uS , uK (k)· ) , k· ^ k where K is a permutation of K elements and dH (·, ·) is the Hamming distance between two binary vectors. 4.2. Experiments on Synthetic Data We ran experiments with artificially generated data in order to compare the estimators of the source prototypes obtained by different clustering techniques. For the results presented in this section, we first chose a set of three source prototypes as illustrated in Fig. 1. An object can be assigned to any combination of these Multi-Assignment Clustering for Boolean Data P[estimated centroid bit wrong] [%] 50 MAC (with Noise) BICA INO DBP tation of INO (Matlab) provided by the authors of (Wood, 2006) ran for roughly two weeks. The original dataset has a relatively simple structure and does not suffice to assess the capabilities of the algorithms to deal with noisy, complicated data. In order to simulate a more complex scenario, we produced artificial users by Boolean addition of the first and second 500 permissions of each user. The resulting user-permission matrix exhibited substantially more structure. Additionally, 33% of the matrix entries were replaced by random bits to increase the noise level. To evaluate the generalization performance, we again took the unused set of users of the modified userpermission matrix, but without the artificial noise. The results are shown in the right column of Fig. 3. Compared with the results on the original data set, MAC is clearly more robust with respect to the additional noise and still recovers roles that allow one to accurately describe the permissions of new users. Both DBPs and BICA are significantly worse in both coverage and prediction error. INO seems to be more robust against this additional noise, but is also clearly outperformed by MAC. 40 30 20 10 0 0 0.9 10 20 30 40 50 60 70 80 90 Noise Level [%] MAC (with Noise) 0.8 0.7 BICA INO DBP Instability 0.6 0.5 0.4 0.3 0.2 0.1 0 0 10 20 30 40 50 60 70 80 90 Noise Level [%] Figure 2. Average Hamming distance between true and estimated source prototypes (upper graph) and cluster instability (lower graph) on synthetic data. Solid lines indicate the average over 10 data sets with random noise, the dashed lines standard deviation. For INO, we only plotted instability results of experiments where the same number of clusters was inferred in both data sets. To improve readability, sample standard deviation (around 0.1) is not plotted in the lower graph. 5. Theoretical Considerations In this section, we describe some of our model's theoretical properties. Recall that L is the set of admissible cluster assignments. Let L := |L| be the cardinality of L and M the maximal number of clusters an object can belong to. L can be encoded as a binary membership matrix zL {0, 1}L×K . We denote a row in zL as a cluster set. The lth row indicates the clusters contained in the cluster set l (we assume an arbitrary, but fixed numbering of the cluster sets). We can now decompose the assignment matrix z as z = zL zL , with zL {0, 1}N ×L encoding the exclusive assignment of data items to cluster sets. With this notation, the decomposition xS = z u can be extended to xS = zL zL u, which in turn is equivalent to xS = zL zL u . The inflated matrix uSAC := zL u can be interpreted as the cluster centroids in the corresponding clustering problem with mutually exclusive memberships (Single-Assignment Clustering). While such a scenario is asymptotically equivalent to the model presented in this paper, it ignores the high dependency between centroids associated with different cluster sets and must estimate a much larger number of parameters. This explains why, for finite sample size, the proposed model yields more accurate parameter estimates, at the price of a more involved optimization problem. Details will be provided in a forthcoming publication. generalizes poorly may well replace the existing direct user-permission assignments but will require the construction of new roles when new users are added. Given the above, our emphasis in these experiments is on the ability of the model to generalize to new data. In order to quantify this ability, we split the given data in two disjoint sets. The first 2000 users are used to infer the roles. We randomly chose a ratio of permissions from the remaining users in order to decide which roles to give them. The generalization ability of the role system is determined by how accurately the permissions of the remaining users are predicted by these roles. In the left column of Fig. 3, we plot the coverage (upper graph) and the prediction error (lower graph) for this generalization experiment. Our algorithm took roughly 2 hours (Matlab) to compute these results. Both DBPs (C++) and BICA (Matlab) finished within 15 minutes. The implemen- Multi-Assignment Clustering for Boolean Data 90 90 Coverage [%] 70 60 50 40 MAC 30 0 0.1 0.2 DBPs 0.3 BICA 0.4 INO 0.5 Coverage [%] 80 80 70 60 50 40 MAC 30 0 0.1 0.2 DBPs 0.3 BICA 0.4 INO 0.5 (Fraction of Total Permissions Taken) MAC DBPs BICA (Fraction of Total Permissions Taken) MAC DBPs BICA INO 11 9 INO 11 9 Prediction Error [%] Prediction Error [%] 7 5 3 7 5 3 1 0 (Fraction of Total Permissions Taken) 0.1 0.2 0.3 0.4 0.5 1 0 (Fraction of Total Permissions Taken) 0.1 0.2 0.3 0.4 0.5 Figure 3. Generalization error of roles inferred from the original data set (left column) and from the modified data set with higher complexity and 33% noise (right column). 30 sources are used for the methods MAC, DBPs, and BICA. Both data sets consist of 2000 users and 500 permissions. The estimated bit randomization probability is 3% on the original data, and 38% on the modified data. r is estimated to be around 50%. We use a logarithmic scale in the plots for the prediction error in order to improve the resolution in the low-error part. The plots show that the proposed MAC method is competitive on the original data and clearly outperforms DBPs, BICA, and INO under conditions with high noise. The formulation introduced above highlights a possible challenge of the proposed model, namely the large number of possible cluster sets, which can make the computations for parameter estimation, (6), (7) and (8), very time-consuming. Note that in general, we M K have L = 2K or L = m=0 M if the number of clusters an object can be assigned to is bounded by M . However, we emphasize that the large complexity is due to the data itself and not by the model that tries to explain it. Using a smaller number of clusters or cluster sets than in the generative process necessarily leads to a mismatch between the real underlying distribution and the distribution inferred by the clustering algorithm. The proposed formalism allows one to control the model complexity in a transparent way. Using prior knowledge on the complexity from the application, we can thus drastically reduce the running time compared to nonparametric methods, which do not offer such a mechanism. Finally, we point out that the described model has an inherent preference for a sparse centroid matrix u: Since the disjunction has no inverse, the number of 1s in the matrix row xi· is non-decreasing in the number of 1s in row zi· of the assignment matrix. Probabilistically speaking, the probability Li ,j of xij = 0 is the product of the factors k,j [0, 1] and thus decreases with the number of factors |L|. In order to explain matrix rows with few entries 1, the prototypes are to be chosen sparsely, while data rows containing a larger number of 1s are explained as the superposition of several sparse prototypes. Conversely, in a setting where the sources are likely to emit 1s in many dimensions, sparse rows of the data matrix are explained by the overall noise process. Such a configuration is thus less likely than a setting with sparse sources. Hence, it will be dropped in favor of a configuration with sparse source prototypes. We believe that this preference for sparse prototypes pushes the learning algorithm away from a large number of local optima. We assume that this mechanism is the reason for the superior stability and source parameter retrieval observed in the experiments, as presented in Section 4. In the application of role engineering, roles with a min- Multi-Assignment Clustering for Boolean Data imal number of permission, which suffice to grant the users needed permissions, correspond to an important security design principle, termed least privilege: Users should have as few permissions as possible, since assigning superfluous permissions to a user constitutes an unnecessary security risk. Our results obtained for the coverage and the prediction error show that MAC outperforms competing methods in prediction accuracy (see Fig. 2, upper graph) and thus minimizes security risks. Ferraiolo, D. F., Sandhu, R., Gavrila, S., Kuhn, D. R., & Chandramouli, R. (2001). Proposed NIST standard for role-based access control. ACM Trans Inf Syst Secur, 4, 224­274. Frank, M., Basin, D., & Buhmann, J. M. (2008). A class of probabilistic models for role engineering. Conf on Computer and Communications Security (pp. 299­310). Griffiths, T. L., & Ghahramani, Z. (2005). Infinite latent feature models and the indian buffet process. Conf on Neural Information Processing Systems (pp. 475­482). Kab´n, A., & Bingham, E. (2008). Factorisation and a denoising of 0-1 data: A variational approach. Neurocomputing, 71, 2291 ­ 2308. Kemp, C., Tenenbaum, J. B., Griffths, T. L., Yamada, T., & Ueda, N. (2006). Learning systems of concepts with an infinite relational model. Nat Conf on Artificial Intelligence (pp. 763­770). Kuhlmann, M., Shohat, D., & Schimpf, G. (2003). Role mining - revealing business roles for security administration using data mining technology. Symp on Access Control Models and Technologies (pp. 179­186). Lange, T., Roth, V., Braun, M. L., & Buhmann, J. M. (2004). Stability-based validation of clustering solutions. Neural Computation, 16, 1299­1323. Miettinen, P., Mielik¨inen, T., Gionis, A., Das, G., & a Mannila, H. (2006). The Discrete Basis Problem. Proc of Principles and Practice of Knowledge Discovery in Databases (pp. 335­346). Pearl, J. (1988). Probabilistic reasoning in intelligent systems : Networks of plausible inference. Morgan Kaufmann. Rose, K., Gurewitz, E., & Fox, G. (1992). Vector quantization by deterministic annealing. IEEE Trans on Information Theory (pp. 2210­2239). Streich, A. P., & Buhmann, J. M. (2008). Classification of multi-labeled data: A generative approach. Europ Conf on Machine Learning (pp. 390­405). Vaidya, J., Atluri, V., & Guo, Q. (2007). The Role Mining Problem: Finding a minimal descriptive set of roles. Symp on Access Control Models and Technologies (pp. 175­184). Wood, F. (2006). A non-parametric bayesian method for inferring hidden causes. Conf on Uncertainty in Artificial Intelligence (pp. 536­543). 6. Conclusion We have presented a new approach to clustering complex Boolean data where data items can be assigned to multiple clusters. We carried out comparative studies on synthetic Boolean data sampled from a generative model. These experiments demonstrate that our approach produces cluster assignments of superior stability and more accurate cluster parameter estimates compared to state-of-the-art approaches. Moreover, the generalization performance of our approach is substantially more robust with respect to the addition of noise than competing models. Our experimental results on access-control data show an analogous behavior. Our method outperforms the state-of-the-art approaches and the most pronounced improvements are in scenarios with complex and noisy user-permission assignments. Acknowledgements: The work of AS was in part funded by CTI grant Nr. 8539.2;2 EPSS-ES. This work was partially supported by the Zurich Information Security Center. It represents the views of the authors. References Agrawal, R., Imieli´ski, T., & Swami, A. (1993). Minn ing association rules between sets of items in large databases. Int Conf on Mngm of Data, 22, 207­216. Buhmann, J., & K¨hnel, H. (1993). Vector quantizau tion with complexity costs. IEEE Trans on Information Theory (pp. 1133­1145). Colantonio, A., Di Pietro, R., & Ocello, A. (2008). A cost-driven approach to role engineering. Symp on Appl Comp (pp. 2129­2136). Ene, A., Horne, W., Milosavljevic, N., Rao, P., Schreiber, R., & Tarjan, R. E. (2008). Fast exact and heuristic methods for role minimization problems. Symp on Access Control Models and Technologies (pp. 1­10).