In this paper we show the results of the experimental comparison of five triclustering algorithms on real-world and synthetic data wrt. resource efficiency and 4 quality measures. One of the algorithms, the OAC-triclustering based on prime operators, is presented first time in this paper. Interpretation of results for real-world datasets is provided.
Recently analysis of triadic data attracts more and more attention in Data
Mining community [
In this paper we compare the following triclustering methods:
object-attributecondition triclustering (2 modifications including new one) [
The rest of the paper is organised as follows. In section 2 we give main definitions and describe the triclustering methods selected for the comparison. Section 3 describes all the experiments and their results on real and synthetic data along with specially introduced quality measures. Section 4 concludes the paper and indicates some further research direction. 2
Object-attribute-condition triclustering (OAC-triclustering) is based on Formal
Concept Analysis [
First, we recall some basic notions of Formal Concept Analysis (FCA) [
A0 = {m ∈ M | gIm for all g ∈ A}, B0 = {g ∈ G | gIm for all m ∈ B}. (1)
The pair (A, B), where A ⊆ G, B ⊆ M , A0 = B, and B0 = A is called a (formal) concept (of the context K) with extent A and intent B (in this case we have also A00 = A and B00 = B).
The concepts, ordered by (A1, B1) ≥ (A2, B2) ⇐⇒ A1 ⊇ A2 form a complete lattice, called the concept lattice B(G, M, I). 2.1
Object-attribute-condition triclustering Here let us define the box operators and describe box OAC-triclustering. We use a slightly different introduction of the main TCA notions because of their further technical usage.
Let K = (G, M, B, I) be a triadic context, where G, M , and B are sets, and I is a ternary relation: I ⊆ G × M × B. In addition to set of objects, G, and set of attributes, M , we have B, a set of conditions.
Derivation (prime) operators for a triple (ge, me, eb) ∈ I from triadic context K can be defined as follows: g0 := { (m, b) | (ge, m, b) ∈ I} e (2) (3) are (4) (5) (ge, me)0 := { b | (ge, me, b) ∈ I} m0, eb0, (ge, eb)0, (m, eb)0 prime operators can be defined the same way. e e
Now for a triple (ge, me, eb) ∈ I let us define box operator ge ( me and eb introduced in the same way): g := { g | ∃m(g, m) ∈ eb0 ∨ ∃b(g, b) ∈ me0} e Definition 1. Suppose K = (G, M, B, I) is a triadic context. For a triple (g, m, b) ∈ I a triple T = (g , m , b ) is called a box operator based OAC-tricluster. Traditionally, its components are respectively called extent, intent, and modus.
The density of a tricluster T = (X, Y, Z) is defined as the fraction of all triples of I in X × Y × Z: ρ(T ) := |I ∩ (X × Y × Z)|
|X||Y ||Z| Definition 2. The tricluster T is called dense iff its density is not less than some predefined threshold, i.e. ρ(T ) ≥ ρmin.
Let us elaborate on the structure of box operator based triclusters. Suppose K = (G, M, B, I) is a triadic context, and the triple (g, m, eb) ∈ I is considered. e e Then object g will be added to ge iff {(g, me, b) | b ∈ B ∧ (g, me, b) ∈ I} 6= ∅ ∨ {(g, m, eb) | m ∈ M ∧ (g, m, eb) ∈ I} 6= ∅. It is clear that this condition is equivalent to the one in eq. (4), and can be easily illustrated (Fig. 1): if at list one of the elements from “grey” cells is an element of I, then g is added to ge .
The idea of box OAC-triclustering is to enumerate all triples of the ternary relation I for a context K generating a box operator based tricluster for each. If generated tricluster T was not added to the set of all triclusters T on previous steps, then T is added to T . It is possible to implement hash-fuctions for triclusters in order to significantly optimize computational time by simplifying the comparison of triclusters. Also a minimal density threshold can be used.
Prime OAC-triclustering extends the biclustering method from [
Prime based OAC-triclusters are more dense than box operator based ones. Their structure is illustrated on Fig. 2: every element corresponding to the “grey” cell is an element of I. Thus, prime operator based OAC-triclusters in a threedimensional matrix form contain a cross-like structure of ones.
It may also be useful to implement hash functions for triclusters.
TriBox method
The TriBox method [
f (T ) = ρ(T )2|X||Y ||Z|
Once again, hash-functions for triclusters may be used for optimizations. 2.3
Spectral triclustering method
Spectral triclustering method [
Let us elaborate on this technique. Suppose K = (G, M, B, I) is a triadic context First we need to transform K into tripartite graph Γ = hV, Ei. Since I is a ternary relation it is only possible to represent K as a tripartite hypergraph without the loss of information. The following transformation technique is considered: V := G t M t B, for each triple (g, m, b) ∈ I edges (g, m), (g, b) and (m, b) are added to E to form an undirected non-weighted graph. As the result some additional triples will be added to I after inverse transformation. Still it is clear that these triples will be added only in ,,dense“ areas of I thus possibly filling missing values and “optimizing” tricontext for methods aiming at finding formal concepts. Thus this technique is acceptable for solving the problem.
After the transformation Laplacian matrix is built for Γ : degree(vi), if i = j Lij =
−1, 0, if i 6= j and ∃ edge (vi, vj ) otherwise (6) (7) (8) where vi is the ith vertex of V.
The second minimal eigenvector of L is an optimal solution of the continuous variant of the optimal partition problem for Γ (finding the minimal set E˜ ⊆ E so that the graph Γ˜ = (V, E \ E˜) is not connected). The sign of each component of this vector indicates one of the 2 new connected components. For convenience we find the optimal partition vector as the approximation of the obtained vector by setting its components to ±1 values.
In order to avoid partitioning of dangling vertices or small subgraphs the
generalized eigenvalue problem must be considered ([
Lv = λDv where D is a diagonal matrix containing vertices’ degrees on the main diagonal.
Also, some minimum size constraint can be used to avoid too deep partitioning. Since spectral triclustering is not able to generate the same tricluster more than once, it is not necessary to use hash functions to speed up the calculations. 2.4
Trias method
Formally, Trias [
Trias is based on the NextClosure algorithm that enumerates all formal concepts of the dyadic context in lexicographical order. In Trias this approach is extended to the triadic case and minimal support constraints are added (triclusters with too small extent, intent or modus are skipped).
As well as spectral triclustering, Trias is not able to generate the same tricluster more than once. 3 3.1
Noise-tolerance.
In order to test noise-tolerance of the algorithms 26 triadic contexts have been generated. The initial context contains 30 objects, 30 attributes, 30 conditions, and 3 non-overlapping 10 × 10 × 10 cuboids of ones on the main diagonal in its three-dimensional matrix form. Then this context has been sequentially noised by the inversions with the probability of an inversion of a triple varying from 0.1 to 0.5 with 0.1 interval (the latter context can be called uniform context, because probability of (g, m, b) ∈ I is equal for every triple). There have been 5 such series of context. Table 1 contains the average number of triples and total density for these sets of contexts.
The noise tolerance of an algorithm has been defined as the ability to build triclusters similar to initial cuboids. We used the Jaccard similarity coefficient to find the most similar tricluster t for the given cuboid c and their similarity. Total similarity has been defined as follows (C is a number of cuboids): (9) (10) sim(c) = 1 XcC C
max |Gc ∩ Gt| |Mc ∩ Mt| |Bc ∩ Bt| c=c1 t=t1,...,tT |Gc ∪ Gt| |Mc ∪ Mt| |Bc ∪ Bt| Following size measure for spectral triclustering has been chosen: Size(X, Y, Z) = |X| + |Y | + |Z|
|G| + |M | + |B| smin has been set to 0.34 to stop at the triclusters of correct size.
All of the methods have been implemented by authors and incorporated in a single triclustering toolbox in order to make the comparison more accurate. The toolbox has been implemented in C# using MS Visual Studio 2010/2012. All the experiments have been performed on Windows 7 SP1 x64 system equipped with an Intel Core i7-2600 @ 3.40GHz processor and 8 GB of RAM. AlgLib1 library was used for eigenvalue decomposition.
The results of the experiments are represented on Figure 3. It is clear that every method has managed to successfully find initial cuboids, but the results quickly deteriorate for most of methods with the growth of inversion probability. TriBox has shown the best results as it tries to optimize the density-volume trade-off (which most probably is the best for the areas of the former cuboids for small error probability). Though prime OAC-triclustering has been also rather noise-tolerant, it generated significantly more triclusters (most likely the high number of triclusters is the reason for these results). All the other methods have been unable to provide significant results for noisy contexts. Moreover, as it was expected, no adequate triclusters were generated by any of the methods for the contexts with inversion probability 0.5. 3.2
Time, quantity, coverage, density and diversity.
The experiments on the computation time, triclusters count, coverage, density, and diversity were conducted on the following contexts (Table 2): 1. Uniform context (∀(g, m, b) P ((g, m, b) ∈ I) = 0.1) 2. Top 250 movies context from www.imdb.com, objects — movie titles, attributes — tags, conditions — genres 3. Random sample of 3000 of the first 100000 triples of the www.bibsonomy.org dataset, objects — users, attributes — tags, conditions – bookmark names Parallel versions of OAC-triclustering algorithms and TriBox have also been implemented via parallelization of their outer loops and the computation time for them has been compared. Coverage and diversity measures were introduced as additional quality measures. Coverage is defined simply as a fraction of the triples of the context (alternatively, objects, attributes or conditions) included 1 http://www.alglib.net/ in at least one of the triclusters of the resulting set. To define diversity we will use a binary function of 2 triclusters intersect(Ti, Tj ) that equals to 1 if both triclusters Ti and Tj have nonempty intersection of the sets of contained triples, and 0 otherwise.
It is also possible to define intersect for the sets of objects, attributes and conditions. For instance, intersectG(Ti, Tj ) is equal to 1 if triclusters Ti and Tj have nonempty intersection of their extents, and 0 otherwise.
Now we can define diversity of the tricluster set T : diversity(T ) = 1 −
Pj Pi<j intersect(Ti, Tj ) |T |(|T |−1) 2 (11)
The diversity for the sets of objects, attributes or conditions is similarly defined.
Table 3 contains the results for the experiments. The following values for parameters were selected: 1. OAC-triclustering: ρmin = 0 2. SpecTric: smin = 0 3. Trias: τG = τM = τB = 0 Trias is one of the most time consuming algorithms compared in the paper along with TriBox and SpecTric for large contexts. Though the resulting triclusters (triconcepts) can easily be interpreted their number and small size make it impossible to understand the general structure of the context. Since all triconcepts have been generated and thus every triple has been covered, the coverage is equal to 1. Since the concepts are small general diversity is rather high. Still, the set diversity depends on the size of the corresponding set: the smaller the set — the greater the chance of intersection and the lower the diversity.
Examples of the triconcepts for the IMDB context: SpecTric has displayed rather good computation time only for small contexts. Most of this time is used for the eigenvalue decomposition of Laplacian matrix. Thus we intend to test some alternative linear algebra libraries in the toolbox and compare the results as well. The resulting triclusters can be reasonably interpreted, though their average density is low. Their small number makes this method good for dividing the context into several non-overlapping parts. Also the diversities for SpecTric are always equal to 1 because the method generates partitions of the initial context. High diversity though leads to low coverage.
Examples of the triclusters for the IMDB context: TriBox in this study generates the best triclusters. The only drawback of this method is high computation time, though the use of the parallel version of TriBox can significantly lower it for multi-core processors. Average density of the resulting triclusters is rather high, they have good interpretability. Coverage and diversities are also high in most of the cases. The only exception is set diversity in the situation when some of the sets are small, just as for Trias.
Examples of the triclusters for the IMDB context: Box OAC-triclustering has been not that successful. Despite being rather fast (only OAC-triclustering based on prime operators and SpecTric for small contexts are faster) and having good parallel version the resulting triclusters are quite large, have relatively low density and many intersections. It leads to the high coverage (1 for rhomin = 0) and rather low diversities. Also these triclusters are difficult to interpret (unlike SpecTric’s triclusters that also have large size and low density). In many cases extent sizes are small. Examples are given below: Prime OAC-triclustering showed rather good results. It is one of the fastest algorithms (though some additional optimizations specified for unparallel version made parallelization inefficient for small contexts). The number of triclusters is high, but they are easily interpreted. Once again for ρmin = 0 coverage is equal to 1, but remains high for different ρmin. At the same time diversities are also rather high. Examples of the triclusters for the IMDB context are given below:
We compared several different triclustering approaches and showed that there is no algorithm-winner with respect to the considered criteria. Also, we can conclude that either (dense) prime OAC-triclustering or TriBox is a good alternative for TCA approach because the total number of triclusers for real data example is drastically less than the number of triconcepts. The proposed algorithm has a good scalability on real-world data and shows acceptable noise-tolerance level. Probably investigated spectral hierarchical partitioning of ternary relations can be a good alternative of concept-based triclustering as a tool for fast exploratory (preliminary) analysis.
Our further work on triclustering will go in the following directions: – developing a unified theoretical framework for n-clustering, – mixing several constraint-based approaches to triclustering (e.g., mining dense triclusters first and then frequent tri-sets in them), – finding better approaches for estimating tricluster’s density, – taking into account the nature of real-world data for optimization (their sparsity, value distribution, etc.). – investigation of the existing approaches and developing their extensions to triadic numerical data for comparison purposes, – applying triclustering in recommender systems and social network analysis. Acknowledgements. We would like to thank our colleagues Boris Mirkin, Jonas Poelmans, Leonid Zhukov, Andrey Kramarenko, Svetlana Vasyukova for helpful comments, and Ruslan Magizov (box OAC-triclustering) and Zarina Sekinaeva (SpecTric) for their programming support. This research was carried out in 2013 within a project of the Basic Research Program of the National Research University Higher School of Economics (Moscow) and affiliated Laboratory of Intelligent Systems and Structural Analysis.