Semi-supervised clustering high-dimensional data

I have a data set with 20% labelled samples and 80% unlabelled samples. I have $C$ classes. More than $C$ classes may exist in the data. Each sample is a $70$-dim vector. The size of the dataset is N. That is:

$\chi$: subset of samples = $\{x_1, ... x_N\}$ where $x_i \in \mathbb{R}^{70}$

$Y:$ subset of labels = $\{y_1,...,y_N\}$ where $y_i \in \{0,1,...,C\}$ where 0 means that the class is unknown and $1,...,C$ is the class to which sample belongs. As I said before 20% of the samples are labelled and 80% are unlabelled.

A class can create different patterns, that is, a class can be explained by different clusters in the space. Example: maybe the class 2 can be explained by a Gaussian distribution in a certain part of the space and another Gaussian distribution in another part of the space. Better said, all the samples that should be labelled under the same class $i$ can be explained by different clusters in the space. I am assuming that if a clusters has labelled samples, the class that will represent that cluster will be based on the dominant label class of the samples inside that cluster. Besides, there is the possibility to find in the space clusters formed exclusively by unlabelled samples. That is, not all the classes are known.

How can I tackle a problem like this? I would like to find clusters with labelled samples and clusters with unlabelled samples (new patterns). I would like to use the information provided by the labelled samples to find the best clusters (I mean I can assume that I dont have samples and find the clsusters). Any help can be useful.

Thanks

• I hope that the edition clarifies the problem now
– user45299
Sep 26 '14 at 21:31

Your final goal is classification, if not mistaken your point, so don't think in the way to classify it cluster by cluster. Cluster itself can possess many class or many nonlinear decision boundaries too.

You can use cluster-then-labeling method. It is easy and intuitive and flexible. As the following:

1. Clustering
2. Within each cluster, taking the labeled data, train a easy classifier and label the unlabeled within that cluster .
3. Finally, you have a full labeled data, happy taking it to train a powerful classifier you prefered.

There may be problem arised at step 3 if there are clusters with all the unlabeled data. You can classify it to unknown or if you use hierarchical clustering, you can find along the hierarchy the higher level group which has labeled data.

If you know what's those features means and two set of features are strongly independent , you can also consider combining co-training. it is also an easy wrapper method. For more and friendly resources of co-training , Tom Mitchell is an option, his book is very friendly I think.

• Thanks for your answer. Part 2 of the technique will help. My first idea was to label them with the dominant label inside the cluster, however using a classifier might improve accuracy.
– user45299
Sep 27 '14 at 21:29
• However, how can I cluster the samples? I dont know the real number of clusters and the dimensionality is very high. I do not know either parameters that might help for density based approaches like the number of neighbours or $\varepsilon$. I have thought about two posibilities: Reducing dimensionality with semi-supervised learning and then applying subspace clustering with RESCU trying different $\varepsilon$ and k parameters or going or using EM clustering for high dimensionality using labelled samples as a place to start for searching. I need help for choosing a high-dim clustering alg.
– user45299
Sep 27 '14 at 21:35
• If I have some knowledge of data, I would go method with more visualization of data, eg. Agglomerative clustering. And from which the generated Hierarchy/Dendrogram to choose right number of cluster by your "EYES" and your knowledges. Sep 29 '14 at 3:56
• Which could be a good metric for high dimensional clustering?
– user45299
Oct 3 '14 at 15:48