Scalable CLOPE algorithm for clustering categorical data

Introduction and Main Concepts

Clustering of large arrays of categorical data is very important for data analysis systems. Categorical data can be found in any field: manufacturing, commerce, marketing, medicine… Categorical data also includes so-called transactional data: receipts in supermarkets, logs of visits to web resources. This also includes the analysis and classification of text documents (Text Mining).

Here and further, the "categorical data" refers to the qualitative attributes of objects measured using the name scale. We remind that when using the name scale, it is only indicated whether the objects are the same or not relative to the measured feature.

It is inefficient and often impossible to use traditional algorithms for clustering of objects with categorical features (for more information, see the article "Clustering Algorithms in Data Mining"). The main difficulties are related to the high size and huge volume that often characterize such databases.

Algorithms based on pairwise distance calculation (k-means and analogs) are effective mainly for numerical data. Their performance when working with arrays of records with a large number of non-numeric factors is unsatisfactory. And it's mostly not due to the complexity of setting up a metric for calculating the distance between the categorical attributes, but the fact that each iteration of the algorithm requires pairwise comparison of objects with each other, and there can be a lot of iterations. it is not applicable for tables with millions of records and thousands of fields.

Therefore, there are ongoing studies in the field of development of scalable clustering algorithms for categorical and transactional data. These have special requirements, namely as follows:

• minimum possible number of "scans" of the database table;
• operation with a limited amount of RAM;
• ability to interrupt the algorithm and save the intermediate results so that you can continue the calculations later;
• the algorithm should operate when the objects from the database can be retrieved only in the unidirectional cursor mode (i.e., in the record navigation mode).

Nowadays, more than a dozen methods have been proposed for working with categorical data, for example, a family of hierarchical cluster algorithms. However, they do not always meet the requirements listed above. One of the most effective algorithms is LargeItem algorithm, which is based on optimization of a certain global criterion. This global criterion uses a support parameter (the terminology here has a lot in common with algorithms for generation of association rules).

In general, calculation of the global criterion makes the clustering algorithm many times faster than using the local criterion for pairwise comparison of objects; so "globalization" of the evaluation function is one of the ways to obtain scalable algorithms.

The CLOPE algorithm that we discuss in this article is very similar to LargeItem algorithm but faster and easier in terms of programm implementation. CLOPE was proposed in 2002 by a group of Chinese scientists. At the same time, it provides higher performance and better clustering quality compared to LargeItem algorithm and many other hierarchical algorithms.

To begin with, we will describe the clustering problem under consideration for categorical data. The entire presentation will go as if we have a database of transactional data, and at the end of the article we will show how to use CLOPE to partition any categorical arrays into clusters by working with them as with transactional ones.

The term "transaction" here refers to some arbitrary set of objects, whether it is a list of keywords in an article, products purchased in a supermarket, a set of patient symptoms, outstanding image fragments, etc. The task of transactional data clustering is to split the entire set of transactions in such a way that similar transactions end up in the same cluster, and different transactions end up in different clusters.

The CLOPE clustering algorithm is based on the idea of maximization of the global cost function, which increases the proximity of transactions inside the clusters due to an increase in the cluster histogram parameter. Let's consider a simple example of 5 transactions: \{ (a,b), (a,b,c), (a,c,d), (d,e), (d,e,f) \}. Let's assume that we want to compare the following two partitions into clusters:

\{ \{ ab,abc,acd \}, \{ de,def \} \} , (1)

\{ \{ ab,abc \}, \{ acd,de,def \} \}, (2)

For the first and second partitioning options in each cluster, let's calculate the number of occurrences of each transaction item in them, and then calculate the height of (H) and width of W of the cluster. For example, the cluster \{ ab,abc,acd \} has occurrences of a : 3, b : 2, c : 2 with H=2 and W=4. To facilitate understanding, Figure 1 shows these results geometrically as histograms.

We can evaluate the quality of two partitions by analyzing their height of H and width of W. The clusters \{ de,def \} and \{ ab,abc \} have the same histograms, so they are equivalent. The histogram for the cluster \{ ab,abc,acd \} contains 4 different items and has an area of 8 blocks (H=2.0,H/W=0.5), and the cluster\{ acd,de,def \} contains 5 different items with the same area of (H=1.6,H/W=0.32). Obviously, splitting (1) is better, since it provides a greater overlap of transactions (respectively, the H parameter is higher there).

The CLOPE algorithm operates based on this obvious and simple concept of geometric histograms (Clustering with sLOPE). Let's look at its more detailed formal description.

CLOPE algorithm

Let us assume that there is a D transaction database consisting of a set of transactions \{ t_1,t_2,…,t_n \}. Each transaction has a set of objects \{ i_1,…,i_m \}. The cluster set \{ C_1,…,C_k \} is a partition of the set \{ t_1,…,t_n \}, such that C_1…C_k = \{ t_1,…,t_n \} and C_i\neq \varnothing \wedge C_i \bigcap C_j = \varnothing is true for 1<=i, j<=k. Each item C_i is called a cluster n, m, k are the number of transactions, the number of objects in the transaction database, and the number of clusters, respectively.

Each C cluster has the following attributes:

• D(C) — set of unique objects;
• Occ(i,C) — number of occurrences (frequency) of an object i in cluster C;
• S(C)=\sum_{i\in\ D(C)}\ Occ\ (i, C)=\sum_{t_i\in C}\mid t_i \mid;
• W (C) = | D (C) |;
• H(C)=S(C)/W(C).

The histogram of the cluster C is called a graphical image of its current attributes: the objects in the cluster are laid off along the OX axis in the order of descending of the values of Occ(i,C), and the value of Occ(i,C) is laid off along the OY axis (Fig. 2).

In Figure 2, S(C)=8 corresponds to the area of the rectangle bounded by the coordinate axes and the dotted line. Obviously, the higher the H value, the more "similar" the two transactions are. Therefore, the algorithm must choose partitions that maximize H.

However, it is not enough to take into account the H height value alone. Let's take a database consisting of 2 transactions: \{ abc,def \}. They do not contain common objects, but the partition \{ \{abc,def \} \} and the partition \{ \{ abc \}, \{ def \} \} are characterized by the same height of H=1. It turns out that both splitting options are equivalent. But if we use the gradient G(C)=H(C)/W(C)=S(C)/W(C)^2 instead of H(C), then the partition option \{ \{ abc \}, \{ def \} \} will be better (the gradient of each cluster is 1/3 versus 1/6 for the partition \{ \{ abc,def \} \}).

Summarizing the above, we write a formula for calculation of the global criterion — the cost function Profit(C):

Profit (C) = \frac {\sum \limits_{i=1}^{k} G(C_i)\times\mid C_i\mid}{\sum \limits_{i=1}^{k} \mid C_i\mid}=\frac {\sum \limits_{i=1}^{k} \frac{S(C_i)}{W(C_i)^r}\times\mid C_i\mid}{\sum \limits_{i=1}^{k} \mid C_i\mid}

where:

• |Ci| — number of transactions in the i-th cluster
• k — number of clusters
• r — positive real number greater than 1.

The r parameter, called the repulsion coefficient (repulsion) by the authors of CLOPE, regulates the level of similarity of transactions within the cluster, and, as a result, the final number of clusters. This coefficient is selected by the user. The higher the r, the lower the similarity level and the more clusters will be generated.

The formal statement of the clustering problem by the CLOPE algorithm looks as follows: for given D and r, find the partition C: Profit(C,r) -> max.

Algorithm Implementation

Let's assume that the transactions are stored in a database table. The best solution is searched for during a sequential iterative search of the database records. Since the optimization criterion is global in nature, based only on the calculation H and W, the performance and speed of the algorithm will be significantly higher than that during the pairwise comparison.

The implementation of the algorithm requires the first pass through the transaction table to perform the initial split defined by the following function Profit(C,r). After that, a small (1-3) number of additional table scans is required to improve the clustering quality and optimize the cost function. If there are no changes in the current pass through the table, the algorithm stops. The pseudocode of the algorithm looks as follows.