Clustering algorithms for high dimensional binary sparse data

Question

I have a dataset with 10,000 genes like below

person gene1 gene2 ... gene10000  ethnic
  1       0      1         1       asian
  2       1      0         1       European

Each row means, whether a person has a gene in their DNA or not. We are trying to classify different ethnic groups based on the data above. But first we want to use some clustering algorithms to visualize how the cluster would look like for different ethnic groups. We are not going to use this clustering algorithms to classify groups, it will be used just to visualize how it would look like, if we have nice separate clusters or overlapping clusters etc.

Please recommend some clustering algorithms for this type of dataset. Also, the dimension is 10000. Is this going to be a problem for clustering? Should I use some dimensionality reduction algorithms first? If so please give your recommendations. Thanks in advance.

Answer 1

How many ethnic groups did you identify?

If I had to visualize your problem, I'd determine the key influencers for each of the ethnic groups in a Naive Bayes like approach. These genes (gene combinations?!) (including their values) may strongly correlate to some ethnic group, while not (or inverse) correlate to another.

Place them on top of a pyramid graph. Place bars to the left and right for the correlation values.

Answer 2

'Clustering different ethnic groups for visualization' seems more like you are trying to do supervised dimensionality reduction since you already know the target variables in this case.

Since you will be using it for classification later, I assume you already know the number of ethnic groups. This can be done using Linear Discriminant Analysis (LDA). Check out this post: https://stats.stackexchange.com/questions/161362/supervised-dimensionality-reduction

Answer 3

Procedure-1 :

I think it would be better if you can try combining some geners, it is most likely that some follow similar trend, once you identify them try combining them.

You can use some Dimensionality reduction, then you can make more sense out of the data, as of now even if you give directly also it might take time for the model to understand and give some useful results.

Once you get the outcome of Dimensionality reduction you can directly apply multi class classification algorithms like SVM, RF and many more.

Procedure-2:

Another thing which you can try is, You can concatenate all the features(Gener's) into 1 single feature and try try understanding and see if does makes any sense/ get some good insights(Exploratory Analysis).

Do let me know if you have questions.

SVM : Support Vector Machine

RF : Random Forest

Answer 4

I suspect the number of ethnic groups is large and you are given a large enough sample of random people from different ethnic background to work with. So I propose the following:

Rather than using clustering (unsupervised segmentation) you could use an existing less granular ethnic grouping. Let's say your unique ethnic groups in your raw dataset is like that in https://en.wikipedia.org/wiki/List_of_contemporary_ethnic_groups then you could use a high level grouping with smaller groups such as that in https://www.google.com/search?q=ethnic+grouping+in+the+world&rlz=1C1CHBF_enUS810US810&oq=ethnic+grouping+in+the+world&aqs=chrome..69i57.10445j0j8&sourceid=chrome&ie=UTF-8 for the purpose of understanding the high level group profiles: for example by analysing the descending rank of frequency count of gene features that are more prevalent in each group. Technically you can do the same using the original more granular ethnic groups.

Normally you cannot apply traditional principal component analysis on the gene features since they are categorical with values 0 or 1, but you could apply a more appropriate method that does not require continuous variables inputs, such us the method used in this R package: https://cran.r-project.org/web/packages/FactoMineR/index.html

Clustering and recommendation in one shot:

You could also try explicit collaborative filtering which requires data to be in the format of user by item, in the following way:

1. since the gene features are all binary you could use your ethnic group numeric id as the rating but you have to convert it to numeric from 1 to N distinct ethnic groups
2. define person as the user dimension and the id of each gene feature as the item dimension
3. re-organize the data as [Person, genes,group], where genes=[1,2,...,N_genes] and group=[1,2,...,N_ethnic] keeping rows where gene feature=1 only in this format, the zero value assumed where the combination does not exist, separate the data in training and validation datasets
4. Apply Alternative Least Square (https://spark.apache.org/docs/2.2.0/ml-collaborative-filtering.html) on the training data then use the validation data to validate how well ALS predicts the ethnic group, may use the number of elements in the smaller ethnic grouping above as the an initial number of components in the ALS process
5. if the number of correct predictions of each ethnic group given gene features for all persons is reasonably higher than incorrect predictions then use the model to predict ethnic group membership, you can also look at the mix of gene features that are characteristic to each ethnic group from this result.

Answer 5

If you know the ground truth of data, the ethnic here. You can visualize your binary cluster as follow. Compute prototypes of each cluster using majority vote per feature which has a linear complexity in number of observations and in number of features. Then visualize each binary prototype as a binary grid of size $100\times100$ for your $10000$ features. Select two of your favorite colors and enjoy. You will see if centroids are overlapping with others when they share same color at same pixels. If you desire to cluster your data rapidly i will advice you to start with $K$-$Modes$ which is the binary equivalent of $K$-$Means$, both are in $O(n)$, set $K$ accordingly to your number of ethnic and once you have clusters apply again majority vote to extract prototypes, visualize them and observe if it has similitude with ground truth. You can find an easy to use version of the algorithm here with a practical bootstrap example, with visualization, on this SparkNotebook.

Answer 6

You already know to which cluster each person belongs, so you need to run a clustering algorithm that makes this prediction for you. Your question is about data exploration: You're trying to understand your data. Your actual problem is a supervised (multi-class) classification problem, and clustering algorithms are not suited for that, because they are unsupervised.

I would recommend to do two things: First, reduce the dimensionality to be able to visualize. Second, calculate metrics on the original high-dimensional dataset to gain more understanding.

To visualize the data, I recommend to use t-SNE to visualize in two dimensions and color with the ethnic group. This will give you an idea if your data forms clusters in the 10k-dimensional space.

Then, if you want to improve your feeling or intuition about your data further, by thinking about it in terms of clusters in the 10k-dimensional space, then you can calculate cluster metrics such as the Silhouette score, cluster compactness (average distance to the centre), or display the distance between clusters in a heatmap. You can merge two clusters by giving them the same label, and see how your results change.

I can't anticipate the results that you may get, so it could be very enlightening, meaning that you can tell that certain clusters are very compact, others very extensive, some are very similar to others and so on. But perhaps, using the above methods, you cannot make sense of your data at all. If that happens, then I would say it's time to stop thinking about your data as points in "gene space", with differences between people indicating a "distance", etc. In this case, it can be that the mapping from genes to ethnic grouping is more complex (non-linear) than a spatial clustering, so you need to use a classification algorithm that is capable of encoding this non-linearity.

Deep learning doesn't have many prerequisites but one of them is that it can only encode continuous functions. Neural networks also require numerical, real-valued input features. Since your problem has binary data and there is no reason to think that the gene to ethnicity mapping is a smooth function, perhaps algorithms based on decision trees are a good place to start.

Good luck! :-)