5
$\begingroup$

In terms of input -> [process] -> output what are features that distinguish clustering, blind signal separation and dimensionality reduction?

From this Wikipedia article, the implication is that there are two types of unsupervised learning:

  • clustering; and
  • blind signal separation

I have never heard of the term blind signal separation before. How does it differ from clustering and how does dimensionality reduction underpin this?

$\endgroup$
4
$\begingroup$

Short Answer: Clustering and blind signal separation (BSS) are often used together in an application, and when this is the case, the BSS algorithm comes first as a pre-processing step in order to "reduce the dimension of the problem". The original inputs can then be accordingly "cut down" before being fed into a clustering algorithm to optimally segment the now lower order problem. Because the dimensions have been reduced, the result of clustering can now be readily visualised in 2 or 3 dimensions.

In "input-[process]-output" form, we have a linked, three-step filter:

 input (high dimensional, mixed source) -> [Blind signal separation] ...
      -> ranking of features -> [Dimension reduction] -> lower dimensional inputs ...
            -> [Clustering] -> optimal segmentation.


To elaborate:

Suppose that your inputs are vectors, i.e. each of your data points / samples has a number of attributes, say $n$ of them.

Clustering:

In simple terms, clustering takes the inputs, considers them in an $n$-dimensional space, and, given a target number of clusters, runs a mathematical algorithm to decide what should be the centre of each cluster and which points should be assigned to belong to which cluster.

So clustering is essentially mathematical segmentation of your data into groups (optimal segmentation if you will).

But the challenge with using clustering on your raw vector inputs is that the algorithm is having to work in $n$ dimensional space -- which means its difficult to visualise, and, if many of the attributes are correlated, then those extra dimensions are not adding much value in the problem of identifying the best clusters.

Enter blind source separation...

Blind Source Separation:

Blind signal separation (BSS), on the other hand, is about separating a mixture into individual components.

Again, in simple terms, suppose that you have a process that "mixes" or confounds a number of pure signals into an aggregate whole. As an example, think of taking a recording from a number of microphones situated in an orchestra hall where there are a number of instruments all playing the same melody but where there is also quite a bit of local chattering among the audience. The resulting recording is a mixture of all of this.

The question in this case is, from the mixed input, and without knowing how the mixture is composed, can you take the output (recording) and separate out the individual input vectors?

So BSS is essentially an inverse problem in which you start with a mixed input and attempt to separate out the individual elements that went into the mixing process.

BSS, Dimension Reduction, and Clustering:

I mentioned at the start that clustering and BSS are often used together. The reason for that brings in the concept of dimensionality reduction.

The input into BSS consists of mixed signals plus noise (uncorrelated, white noise for example, or low correlated sources of little interest).

BSS works by identifying, from a number of 'features' about the signals (mathematical expressions involving the individual attributes of each vector), those features that 'explain' the greatest variation in the data.

These features can then be ranked in descending order. By taking the top three features, for example, one arrives at a much more manageable number of dimensions in which to perform clustering.

A typical example and real-world application:

So in a typical example, one might first apply PCA (principal components analysis) -- which is a type of BSS algorithm -- to a data set to "discover" the top 3 features that are most useful in explaining the variation in the data set, and then use mathematical clustering on just those 3 features to identify the segments into which the data can be split.

I've seen this combination approach used very successfully in the problem of classification (unsupervised learning) of bottom-oriented sonar signals to determine automatically the type of sea bottom that a vessel is travelling over: is it muddy, sandy, rocky, without having to send a diver down to check.

So, when used in combination, these techniques can become quite powerful tools.

$\endgroup$
3
$\begingroup$

That Wikipedia article is a mess. No wonder it has been tagged as "cleanup" for more than two years.

If you want to learn about clustering, do not approach it from the learning side.

To the machine learning side, unsupervised learning is the ugly duckling they resort to when they don't have any labeled training data. But they do not really like or understand it. Because actually it is doing something very different. Note that most of the clustering work is done outside of the machine learning community (but in the knowledge discovery community), and they would not call it unsupervised learning.

In learning, you have an objective. You want e.g. to be able to predict the value of future observations. The clear objective in particular helps with evaluation, but also narrows down the search space a lot.

In cluster analysis, you don't have a strict objective. It is an explorative method, with unfortunately a very big search space, so you need a lot of heuristics and assumptions. You want to explore your data, and learn something new - discover some new structure in this case. If you had a clustering method that gives your the structure you already know, it actually failed the objective to some kind. Yet, this is how cluster analysis is often approached and evaluated: can it discover the structure that I already knew?

Dimensionality reduction is a technique one would prefer to be able to avoid (as it means dropping some of your data), but higher data complexity usually means much worse processing time. And if there is redundancy in your data, it is very reasonable to reduce the dimensionality first.

Reducing the number of dimensions makes data tractable that was not tractable before. It also helps with finding an appropriate distance function, because the popular distances such as Euclidean distance don't work well in high-dimensional data due to what is known as the "curse of dimensionality". With increasing dimensionality, the distances in your dataset concentrate and become more similar. As most clustering algorithms are based on distances, they fail to find clusters then, as the difference between objects blurs. There are various aspects involved (I remember having just seen an article discussing like ~9 different views of it!), but naively you can see it as a consequence of the central limit theorem. Given enough dimensions, the distances become normally distributed around some mean, and the variance is largely the amount of noise you have across the dimensions. If there is too much noise, the distances are only determined by the noise (not the signal) and your algorithms fail.

BSS I can't tell you much about. It has not been on my radar much. I remember having seen the basic idea in a purely audio analysis domain (isolating 4 voices from an 5-channel audio signal, I remember something about needing n+1 microphones to isolate n voices based on the delay alone?) It definitely is not the essential technique of unsupervised learning...

$\endgroup$
  • $\begingroup$ I liked your nice philosophical discourse of clustering. Regarding dimensionality reduction, I'd better used words "tecnique one should get reasons for" instead of technique one would like to avoid. Also, I think you ought to expand your notice about Euclidean distance don't work well since you touched that. $\endgroup$ – ttnphns Oct 7 '12 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.