Some Applications Of Graph Theoretic Approach In Clustering Analysis

In this paper, we discuss hierarchical clustering methods, fuzzy clustering methods and grey clustering methods in cluster analysis, especially graph theoretic approach.Chapter one introduces the basic knowledge of cluster analysis.In Chapter two we discuss the hierarchical clustering analysis and the famous minimum distance method, and suggest that the method is a transformation of the Kruskal algorithm for the minimum spanning tree of a weighted connected graph in graph theory, obtain a good property of minimum distance method:Theorem 2.1 for minimum distance method and k = n-1,n-2,...,1.It implies that any Pm for m=n~1, n-2,...,2 in the system H = (Pn,Pn-1,...,P1)obtained by the minimum distance method is not only a separation best m -partition, but also a similarity best m -partition.In Chapter three we discuss fuzzy clustering analysis and the well-known transitive closure method, indicate the complexity of the method, define theconnected intensity S(u,v) between vertices u,v in the fuzzy relation graph G = (X,E,R), prove that S is a fuzzy equivalence relation and the maximumspanning tree of G=(X,E, R) has the following properties:Theorem 3. 2 If Tis a spanning tree of fuzzy relation graph G = (X,E,R),then the following statements are equivalent:(1) T is a maximum spanning tree of G;(2) For any e' ∈ E(T), let T1, T2 be the two components of T - e', then(3) For any u,v∈(u≠v), the unique path L between u,v in T is an optimal (u,v) path of G.and develop the relation between the connected intensity in G = (X,E,R) and the transitive closure t(R) of R :Theorem 3.3 If X = {X1,X2,...,Xn} , R = (rij)n×n is a fuzzy resembling relation of X, the transitive closure of R is t(R) = Rn =(rij(n))n×n,G=(X,E,R) is the responding fuzzy relation graph of (X, R), thenFrom above we imitate the Dijkstra algorithm for the minimum spanning tree of a weighted connected graph, give an algorithm of the fuzzy clustering with maximum spanning tree:If is a fuzzy resembling matrix and X is the clustering level, letting Ak be a set of vertices in the tree and rij = r(xi ,xj), then(1) Choose a vertex v1∈X, let A1 = {v1}, l(v1) = 0, p(v1) = , l(v):=r(v1,v),(2) Calculate max for any ifr(v*,v)>l(v), then l(v):=r(v*,v) and p(v):=v*.(3) If k=n-1, use the point function p(·) to find out back tracking a maximum spanning tree T of G; each connected component of T with all edges e of w(e) < λ removed is a cluster of X on the level λ, stop.Otherwise, let k := k +1 and return to (2). The complexity of the algorithm is only O(n2). We check the algorithm by anexample finally.In Chapter four we discuss grey correlation clustering analysis and the traditional line-by-line check-up method, point out that the complexity of the methodis O(m4), by imitating the definitions of the connected intensity and related results in the maximum spanning tree algorithm of fuzzy clustering analysis, we give the definition of connected intensity in a weighted graph G = (V, E, D) and property of its maximum spanning tree. Furthermore we define the λ - cross graph Gλ and the connected closure G of G = (V,E, D), obtain a property of Gλand G:Theorem 4. 2 If G = (V,E,D) is a weighted graph, then for any λ∈[0,l],-By which we indicate that vertices u and v in X clustered together in level λ, if and only if they are connected in the λ- cross graph Tλ of a maximumspanning tree T of the correlation graph G = (X, E, A). From this we develop the maximum spanning tree algorithm of grey correlation clustering analysis with the complexity is only O(m), which reduce the amount of operation effectively. Finally we check the algorithm by an example.