Integrating Fuzzy c-Means Clustering with PostgreSQL

Abstract

Many data sets to be clustered are stored in relational databases. Having a clusterization algorithm implemented in SQL provides easier clusterization inside a relational DBMS than outside with some alternative tools. In this paper we propose Fuzzy c-Means clustering algorithm adapted for PostgreSQL open-source relational DBMS.

-

Integrating clustering algorithms is a topic/xplore/al issue for database programmers [ 11 ]. Such an approach, on the one hand, encapsulates DBMS internal details from application programmer. On the other hand, it allows to avoid overhead connected with export data outside a relational DBMS. The Fuzzy c-Means (FCM) [ 9, 6, 2 ] clustering algorithm provides a fuzzy clustering of data. Currently this algorithm have many implementations on a high-level programming languages [ 5, 7 ]. For implementation the FCM algorithm in SQL we choose an open-source PostgreSQL DBMS [ 15 ].

The paper is organized as follows. Section 2 introduces basic definitions and an overview of the FCM algorithm. Section 3 proposes implementation of the FCM in SQL called pgFCM. Section 4 briefly discusses related work. Section 5 contains conclusion remarks and directions for future work.

The Fuzzy c-Means Algorithm K-Means [ 10 ] is one of the most popular clustering algorithms, it is a simple and fairly fast [ 3 ]. The FCM algorithm generalizes K-Means to provide fuzzy clustering, where data vectors can belong to several partitions (clusters) at the same time with a given weight (membership degree). To describe FCM we use the following notation: • d ∈ N — dimensionality of a data vectors (or data items) space; • i ∈ N : 1 ⩽ i ⩽ n — vector subscript in a training set; • xi ∈ X — the i-th vector in the sample; • k ∈ N — number of clusters; • j ∈ N : 1 ⩽ j ⩽ k — cluster number; • C ⊂ Rk d — matrix with clusters’ centers (centroids); • cj ∈ Rd — center of cluster j, d-dimensional vector; • xil; cjl ∈ R — l-s coordinates of vectors xi and cj respectively; • U ⊂ Rn k — matrix with membership degrees, where uij ∈ R: 0 ⩽ uij ⩽ 1 is a membership degree between vector xi and cluster j; •

(xi; cj ) — distance function, defines a membership degree between vector xi and cluster j; • m ∈ R : m > 1 — the fuzzyfication degree of objective function; • JF CM

— objective function.

The FCM is based on minimization of the objective function JF CM :

N k JF CM (X; k; m) = ∑ ∑ uimj 2(xi; cj )

i=1 j=1

Fuzzy clusterization is carried out through an iterative optimization of the objective function (1). Membership matrix U and centroids cij are updated using the following formulas:

∀j; l uij = ∑k ( (xi; cj ) ) 1 2m t=1 (xi; ct) n ∑uimj · xil cjl = i=1n ∑uimj i=1 (1) (2) (3) degree of membership vector xi to a cluster cj on step s degree of membership vector xi to a cluster cj on step s+1 result of computation function (6) on step s i; x1; x2; : : : ; xd i; l; val j; l; val i; j; dist i; j; val i; j; val d; k; n; s; delta n n·d k·d n·k n·k n·k s

Let s is a number of iteration, ui(js) and ui(js+1) are elements of matrix U on steps s and s+1 respectively, and " ∈ (0; 1) ⊂ R is a termination criterion. Then the termination condition can be written as follows: miajx{|ui(js+1) − ui(js)|} < " (4) Objective function (1) converges to a local minimum (or a saddle point) [ 1 ].

Algorithm 1 The Fuzzy c-Means Algorithm Input: X; k; m; " Output: U 1: s := 0; U (0) := (uij ) {initialization} 2: repeat 3: {computation of new centroids’ coordinates} Compute C(s) := (cj ) using formula (3) where uij ∈ U (s) 4: {update matrixes values}

Compute U (s) and U (s+1) using formula (2) 5: s := s + 1 6: until miajx{|ui(js) − ui(js 1)|} ⩾ "

Algorithm 1 shows the basic FCM. The input of algorithm receives a set of data vectors X = (x1; x2; : : : ; xn), number of clusters k, fuzzyfication degree m, and termination criterion ". The output is a matrix of membership degrees U . 3

Implementation of Fuzzy c-Means Algorithm using PostgreSQL In this section we suggest pgFCM algorithm as a way to integrate FCM algorithm with PostgreSQL DBMS. 3.1

General Definitions

To integrate FCM algorithm with a relational DBMS it is necessary to perform matrixes U and X as relational tables. Subscripts for identification elements of relational tables are presented in Table 1 (numbers n; k; d a defined above in a section 2).

As a function of distance (xi; cj ), without loss of generality, we use the Euclidean metric: v u d (xi; cj ) = tu∑ (xil − cjl)2 l=1 (5) = miajx{|ui(js+1) − ui(js)|} (6) 3.2

Database Scheme

Table 2 summarizes database scheme of pgFCM algorithm (underlined columns are primary keys).

In order to store sample of a data vectors from set X it is necessary to define table SH (i; x1; x2; : : : ; xd). Each row of sample stores vector of data with dimension d and subscript i. Table SH has n rows and column i as a primary key.

FCM steps demand aggregation of vector coordinates (sum, maximum, etc.) from set X . However, because of its definition, table SH does not allow using SQL aggregation functions. To avoid this obstacle we define a table SV (i; l; val), which contains n·d rows and have a composite primary key (i; l). Table SV represents a data sample from table SH ans supports SQL aggregation functions max and sum.

Due to store coordinates of cluster centroids temporary table C(j; l; val) is defined. Table C has k·d rows and the composite primary key (j; l). Like the table SV , structure of table C allows to use aggregation functions.

In order to store distances (xi; cj ) table SD(i; j; dist) is used. This table has n·k rows and the composite primary key (i; j).

Table U (i; j; val) stores membership degrees, calculated on s-th step. To store membership degrees on s+1 step similar table U T (i; j; val) is used. Both tables have n·k rows and the composite primary key (i; j).

Finally, table P (d; k; n; s; delta) stores iteration number s and the result of computation function (6) delta for this iteration number. Number of rows in table P depends on the number of iterations. 3.3

The pgFCM Algorithm

The pgFCM algorithm is implemented by means of a stored function in PL/pgSQL language. Algorithm 2 shows the main steps of the pgFCM.

Algorithm 2 The pgFCM Algorithm Input: SH; k; m; eps Output: U 1: {initialization}

Create and initialize temporary tables (U; P; SV , etc.) 2: repeat 3: {computations} 4: Compute centroids coordinates. Update table C. 5: Compute distances (xi; cj). Update table SD. 6: Compute membership degrees U T = (utij).

Update table U T . 7: {update}

Update tables P and U . 8: {check for termination} 9: until P:delta ⩾ eps

The input set of data vectors X stored in table SH. Fuzzyfication degree m, termination criterion ", and number of clusters k are function parameters. The table U contains a result of pgFCM work.

3.4 Initialization

Initialization of tables SV , U , and P provided by SQLcode I1, I2, and I3 respectively. Table SV is formed by sampling records from the table SH.

I1: INSERT INTO SV

SELECT SH.i, 1, x1 FROM SH; ...

INSERT INTO SV

SELECT SH.i, d, xd FROM SH;

For table U a membership degree between data vector xi and cluster j takes 1 for all i = j.

I2: INSERT INTO U (i, j, val) VALUES (1, 1, 0); ...

INSERT INTO U (i, j, val) VALUES (j, j, 1); ...

INSERT INTO U (i, j, val) VALUES (n, k, 0);

In other words, as a start coordinates of centroids, first d data vectors from sample X are used.

∀ i = j uij = 1 ⇒ cj = xi

When initializing the table P , the number of points k is taken as a parameter of the function pgF CM . A data vectors space dimensionality d and a cardinal number of the training set n also provided by function pgF CM parameters. The iteration number s and delta initializes as zeros.

I3: INSERT INTO P(d, k, n, s, delta) VALUES (d, k, n, 0, 0);

3.5 Computations

According to Algorithm 2, the computation stage is splitted to the following three sub-steps: computation coordinates of centroids, computation of distances, and computation membership degrees, marked as C1, C2, and C3 respectively.

C1: INSERT INTO C

SELECT R1.j, l, R1.s1 / R2.s2 AS val

FROM (SELECT l, j, sum(U.val^2 * SV.val) AS s1

FROM U, SV

WHERE U.i = SV.i

GROUP BY l, j) AS R1,

(SELECT j, sum(U.val^2) AS s2

FROM U

GROUP BY j) AS R2 WHERE R1.j = R2.j;

C2: INSERT INTO SD

SELECT i, j,

sum((SV.val - C.val)^2)

AS dist

FROM SV, C

WHERE SV.l = C.l;

GROUP BY i, j;

Through the FCM, computations of the distances provide by formula (2). Let us notice that in formula (3) the fraction’s numerator does not depend on t, and rewrite this formula as follows: k uij = 1 2m (xi; cj) · ∑ m2 1 (xi; ct) (7) t=1

So, the computation of membership degrees can be written as follows:

C3: INSERT INTO UT

SELECT i, j,

SD.dist^(2.0^(1.0-m)) * SD1.den AS val

FROM (SELECT i, sum(dist^(2.0^(m-1.0))) AS den

FROM SD

GROUP BY i) AS SD1, SD WHERE SD.i = SD1.i;

3.6 Update

Update stage of the pgFCM modifies P and U tables as shown below in U1 and U2 respectively.

U1: INSERT INTO P

SELECT L.d, L.k, L.n, L.s + 1 AS s,

E.delta

FROM (SELECT i, j,

max(UT.val - U.val)

AS delta

FROM U, UT

GROUP BY i, j) AS E,

(SELECT d, k, n, max(s)

FROM P

GROUP BY d, k, n) AS L) AS R

Table U T stores temporary membership degrees to be inserted into table U . To provide the rapid removal all the table U rows, obtained at the previous iteration, we use the truncate operator.

U2: TRUNCATE U;

INSERT INTO U

SELECT * FROM UT;

This stage is the final for the algorithm pgFCM. On each iteration the termination condition (4) must be checked.

To implement the check, the result delta of the function (6) from table P is stored in the temporary variable tmp.

CH1: SELECT delta INTO tmp

FROM P, (SELECT d, k, n, max(s) AS max_s

FROM P

GROUP BY d, k, n) AS L WHERE P.s = L.max_s AND P.d = L.d AND P.k = L.k AND P.n = L.n;

After selecting the delta, we need to check the condition < ". Then if this condition is true we should stop, otherwise, work will be continued.

CH2: IF (tmp < eps) THEN

RETURN; END IF;

The final result of the algorithm pgFCM will be stored in table U . 4

Related Work

Research on integrating data mining algorithms with relational DBMS includes the following. Association rules mining is explored in [ 13 ]. General data mining primitives are suggested in [ 4 ]. Primitives for decision trees mining are proposed in [ 8 ].

Our research was inspired by papers [ 11, 12 ], where integrating K-Means clustering algorithm with relational DBMS, was carried out. The way we exploit is similar to mentioned above. The main contribution of the paper is an extension of results presented in [ 11, 12 ] for the case where data vectors may belong to several clusters. Such a case is very important in problems connected with medicine data analysis [ 14, 16 ]. To the best of our knowledge there are no papers devoted to implementing fuzzy clustering with relational DBMS. 5

Conclusion

In this paper we have proposed the pgFCM algorithm. pgFCM implements Fuzzy c-Means clustering algorithm and processes data stored in relational tables using PostgreSQL open-source DBMS. There are following issues to continue our research. Firstly, we plan to investigate pgFCM scalability using both synthetical and real data sets. The second direction of our research is developing a parallel version of pgFCM for distribution memory multiprocessors.

References

[1] J. Bezdek , R. Hathaway , M. Sobin , and W. Tucker . Convergence Theory for Fuzzy c-means: Counterexamples and Repairs . IEEE Trans. Syst. Man Cybern. , 17 : 873 - 877 , October 1987 .

[3] P. S. Bradley , U. M. Fayyad , and C. Reina . Scaling Clustering Algorithms to Large Databases. In KDD , pages 9 - 15 , 1998 .

[4] J. Clear , D. Dunn , B. Harvey , M. Heytens , P. Lohman , A. Mehta , M. Melton , L. Rohrberg , A. Savasere , R. Wehrmeister , and M. Xu . NonStop SQL/MX primitives for knowledge discovery . In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '99 , pages 425 - 429 , New York, NY, USA, 1999 . ACM.

[5] E. Dimitriadou , K. Hornik , F. Leisch , D. Meyer, and Weingessel A. Machine Learning Open-Source Package 'r-cran-e1071' , 2010 . http://cran.r-project. org/web/packages/e1071/index.html.

[6] J. C. Dunn . A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact WellSeparated Clusters . Journal of Cybernetics , 3 : 32 - 57 , 1973 .

[7] Apache Software Foundation , I. Drost, T. Dunning , J. Eastman , O. Gospodnetic , G. Ingersoll, J. Mannix , S. Owen , and K. Wettin. Apache Mahout , 2010 . https://cwiki.apache.org/confluence/display/ MAHOUT/Fuzzy+K-Means.

[8] G. Graefe , U. M. Fayyad , and S. Chaudhuri . On the Efficient Gathering of Sufficient Statistics for Classification from Large SQL Databases . In KDD , pages 204 - 208 , 1998 .

[9] A. K. Jain , M. N. Murty , and P. J. Flynn . Data clustering: a review . ACM Comput. Surv. , 31 : 264 - 323 , September 1999 .

[10] J. B. MacQueen. Some Methods for Classification and Analysis of MultiVariate Observations . In L. M. Le Cam and J. Neyman, editors, Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability , volume 1 , pages 281 - 297 . University of California Press, 1967 .

[11] C. Ordonez . Programming the K-means clustering algorithm in SQL . In W. Kim, R. Kohavi , J. Gehrke , and W. DuMouchel, editors, KDD , pages 823 - 828 . ACM, 2004 .

[12] C. Ordonez . Integrating K-Means Clustering with a Relational DBMS Using SQL . IEEE Trans. Knowl . Data Eng., 18 ( 2 ): 188 - 201 , 2006 .

[13] S. Sarawagi , S. Thomas, and R. Agrawal . Integrating association rule mining with relational database

[14] A. I. Shihab . Fuzzy Clustering Algorithms and their Applications to Medical Image Analysis . PhD thesis , University of London, 2000 .

[15] M. Stonebraker , L. A. Rowe , and M. Hirohama . The Implementation of POSTGRES . IEEE Trans. on Knowl. and Data Eng ., 2 : 125 - 142 , March 1990 .

[16] D. Zhang and S. Chen. A Novel Kernelized Fuzzy c -Means Algorithm with Application in Medical Image Segmentation . Artificial Intelligence in Medicine , 32 : 37 - 50 , 2004 .