# Clustering with hierarchical data dependencies

I am currently looking into how to cluster data with hierarchical dependencies. An example of a problem that I want to cluster: we would like to cluster cities to identify similar characteristics with respect to inhabitants. As input data, I have some characteristics such as the age, weight, height and sex of the inhabitants. Each city will therefore be modeled by a vector :

 ______________                                          _      _
number of people aged 20 years old     |  x_1   |
number of people aged 21 years old     |  x_2   |
age                                                 |        |
|        |
|        |
______________  number of people aged 79 years old     |  x_k   |
number of people of weight of 55kg     |        |
number of people of weight of 56kg     |        |
|        |
weight                                              |        |
number of people of weight of 100kg     |        |
______________ number of people of weight of 111kg     |        |
number of people of height of 1.55m     |        |
number of people of height of 1.56m     |        |
height                                              |        |
|        |
number of people of height of 2.02m     |        |
______________ number of people of height of 2.03m     |        |
sexe        number of male inhabitant               |        |
______________ number of female inhabitant             |_ x_n  _|


If I want to use k-means the input data are not independent, there is a strong correlation between different ages, different heights, etc ... Moreover, it seems illogical to me to have different dimensions for variables representing the same thing.

I'm not sure if there are any methods to deal with this kind of problem or if it's just a way to write it differently.

## 1 Answer

You can either use k-means or Hierarchical clustering for your use case.

Hierarchical clustering method works via grouping data into a tree of clusters

TYPES of Hierarchical Clustering

• Agglomerative : An agglomerative approach begins with each observation in a distinct (singleton) cluster, and successively merges clusters together until a stopping criterion is satisfied.
• Divisive : A divisive method begins with all patterns in a single cluster and performs splitting until a stopping criterion is met.

STEPS

1. Scaling: Normalize the data to bring it to same scale

2. On the scaled data using a linkage method, draw the dendogram to help determine the number of clusters. Domain knowledge also helps in choosing the number of clusters

• Dendogram: Dendogram looks like a tree-like diagram

There are several ways to measure the distance between clusters in order to decide the rules for clustering, and they are often called Linkage Methods. Some of the common linkage methods are:

• Linkage Methods

• Complete-linkage: calculates the maximum distance between clusters before merging.

• Single-linkage: calculates the minimum distance between the clusters before merging. This linkage may be used to detect high values in your dataset which may be outliers as they will be merged at the end.

• Average-linkage: calculates the average distance between clusters before merging.

• Centroid-linkage: finds centroid of cluster 1 and centroid of cluster 2, and then calculates the distance between the two before merging.

3. appropriate hierarchical clustering algorithm is applied with no of clusters, distance metric and linkage method.

4. Measuring goodness of clusters: Dunn's index is the ratio between the minimum inter-cluster distances to the maximum intra-cluster diameter.

Do take below points into consideration if you plan to opt for k-means or Hierarchical clustering |Deciding Factor|k-means clustering|Hierarchical clustering| |-|-|-| |Distance metric used|rely only on Euclidean distance|can handle any distance metric| |Stability of results| Requires a random step at its initialization that may yield different results if the process is re-run.| Not so in hierarchical clustering.| |Number of Clusters|right number of clusters figured out using elbow plots, Silhouette plot| hierarchical too can use all of those but with the added benefit of leveraging the dendrogram for the same| |Computation Complexity| K-means is less computationally expensive|more computationally expensive| |Large Dataset| can be run on large datasets within a reasonable time frame|not suitable for large dataset|

Note: For the above reasons k-means is more popular

Reference Links

• Thank you for your reply but these methods don't take into account the multimodality of the input. Another way of writing the problem is to define the vector as [x_1, x_2, ..., x_n] where x_i is a vector of size N_i whatever i (with N_i different from N_j). I considered these approaches: - For each mode, we replace the data with the parameters of a probability law of their distribution, but this is only possible if the distribution for each city follows the same law. - we can use auto-encoders to find the parameters characterizing the modes, but i don't know if it's efficient. Oct 21 at 7:02