Question

Question: In MATLAB, Implement a hybrid clustering algorithm which combines hierarchical clustering and k-means clustering. The hybrid algorithm will use hierarchical clustering to produce stable clusters and k-means clustering will initialize seeds based on the centroids of the produced stable clusters (instead of randomly initialized seeds)

Background Information: Both hierarchal clustering and k-means clustering group similar data objects into clusters. However, the two algorithms have their pros and cons. For example, hierarchical clustering produces stable clusters while k-means clustering generates instable clusters due to random initial centroids(seeds). In hierarchal clustering once data objects are wrongfully merged, the data objects cannot be moved to another group while k-means clustering can re-assign data objects to a different group.

Answer 1

hierarchical clustering identifies groups in a tree-like structure but suffers from computational complexity in large datasets while K-means clustering is efficient but designed to identify homogeneous spherically-shaped clusters a hybrid non-parametric clustering approach that amalgamates the two methods to identify general-shaped clusters and that can be applied to larger datasets. Specifically, we first partition the dataset into spherical groups using K-means.next merge these groups using hierarchical methods with a data-driven distance measure as a stopping criterion.

The algorithm has the following steps:

1. Removing scatter from the dataset: The algorithm first removes scatter from the dataset from consideration.

   
   Outliers or scatter can greatly influence clustering performance . Although many methods exist, we adopt the following straightforward approach to eliminating scatter. We use K-means with the largest of our candidate group sizes (G) and multiple initializations ( Knp) to obtain a G-means partition. Observations in any of the G groups that have less than 0.1% of the size of the dataset are labeled as scatter and eliminated from further consideration. This leaves us with n_* observations X₁,X₂, …,X_n^* (say) which we proceed with clustering using K − mH.

2. Finding a partition: Our algorithm has two phases. The first focuses on finding a (potentially) large number (K₀) of homogeneous spherical groups while the next merges these groups according to some criterion. We call these phases the K-means and hierarchical phases. The exact details of these phases are as follows:

   1. The K-means phase: For a given K₀ and initialization, the K-means phase uses its namesake algorithm with multiple (m) initializations to identify K₀ homogeneous spherically-distributed groups. This phase yields K₀ groups {?₁, ?₂, …, ?_K0} with means μ₁,μ₂, …,μ_K0. Each obtained cluster ?_k is now considered to be one entity. Therefore, we now have K₀ entities labeled as ?₁, ?₂, …, ?_K0 for consideration.

   2. Hierarchical phase: For given K_* and distance d(·, ·), we successively merge the K-means groups as follows:

      1. Set i^* = 1 and d1∗=1. Define ?̃_j⁽¹⁾ = ?_j for all j.

      2. For j ∈ 1…(K₀ − i^*) C∼j(i∗+1)=C∼j(i∗). Find k, l such that k < l and d(C∼ki∗,C∼li∗)=min1≤m<q≤(K0-i∗+1)d(C∼mi∗,C∼qi∗). Set C∼k(i∗+1)=C∼k(i∗)∪C∼l(i∗) and if l <K₀ − i^* + 1 then C∼l(i∗+1)=C∼K0-i∗+1(i∗), define di∗∗=d(C∼ki∗,C∼li∗). Set i^* = i^* + 1.

      3. If i^* = K₀ or i^* = K₀ − K_* + 1 terminate, else return to Step 2(b)

For the hierarchical phase of Step 2, we calculate the distance between two clusters obtained from the K-means step by assuming (non-homogeneous) spherically-dispersed Gaussian-distributed groups in the dataset. Specifically, we let X₁,X₂, …,X_n^* be independent p-variate observations with Xi~Np(μζi,σζi2I), where ζ_i ∈ {1, 2, …, K} for i = 1, 2, …, n^*. Here we assume that μ_k’s are all distinct and that n_k is the number of observations in cluster k. Then the density for the X_i’s is given by f(X)=∑k=1KI(X∈Ck)ϕ(X;μk,σk2I), where ?_k is a cluster indexed by the Np(μk,σk2I) density and I(X ∈ ?_k ) is an indicator function specifying whether observation X belongs to the kth group having a p-dimensional multivariate normal density ϕ(X;μk,σk2I)∝σk-pexp[-12σk2(X-μk)′(X-μk)], k = 1, …, K. Define the distance measure

Dk(Xi)=(Xi-μk)′(Xi-μk)σk2

(1)

and the variable

Y^j,l(X) = ?_j(X) - ?_l(X), where X ∈ ?_l,

(2)

and Y^l,j (X) similarly. Using the spherically-dispersed Gaussian models formulated above, Y^j,l (X) is a random variable which represents the difference in squared distances of X ∈ ?_l to the center of ?_j and to the center of ?_l. Then plj=Pr[Yj,l(X)<0] is the probability that an observation from ?_l is classified into ?_j and is calculated as follows.

Theorem 1

Let X ~ N_p(μ_l, Σ_l), with Σ_l a positive-definite matrix. Further, let Y^j,l (X) = ?_j (X)−?_l (X), where Dk(X)=(X-μk)′∑k-1(X-μk) for k ∈ {j, l}. Let λ₁, λ₂, …, λ_p be the eigenvalues of ∑j∣l≡∑l12∑j-1∑l12 with corresponding eigenvectors γ₁, γ₂, … γ_p. Then Y^j,l (X) is distributed as ∑i=1pI(λi≠1)[(λi-1)Ui-λiδi2/(λi-1)]+∑i=1pI(λi=1)δi(2Zi+δi), where Ui′s are independent non-central χ²random variables with one degree of freedom and non-centrality parameter λi2δi2/(λi-1)2 with δi=γi′∑l-12(μl-μj) for i ∈ {1, 2, …, p} ∩ {i : λ_l ≠ 1}, independent of Z_i’s, which are independent standard normal random  variables, for i ∈ {1, 2, …, p} ∩ {i : λ_i = 1}.

1. Forming multiple partitions and choosing the optimal P_*: Repeat Step 2 N = ML times with M different K₀s and L different K_*s to form multiple partitions. Determine the optimal hierarchical partition P_*.