Contents
Notes from class
Instructor: Mimi Boutin
Good/bad news
(Not necessarily in that order...)
- There will not be a final homework assignment
- Peer Review is coming along...
Peer Review
Double blind review.
What should the review contain?
- Constructive comments. Do this for each question
- Summarize what they did
- Say what is good
- Say what could be improved
- Grading. Grade the whole assignment.
- OK (B)
- Good (A)
- Excellent/Very Good (A+)
- OK- or NOT OK (B-/Fail)
Due April 25 11:59:59 pm (will accept it until April 28 if you handed in hw2 on time.)
Clustering
- There are no best criterion for obtaining a partition of $ \mathbb{D} $
- Each criterion imposes a certain structure on the data.
- If the data conforms to this structure, the true clusters can be discovered.
- There are very few criteria which can be both handled mathematically and understood intuitively. If you can develope a useful intuitive criterion and describe and optimize it mathematically, you can make big contributions to this field.
- Some criteria can be written in different ways, for example minimizing the square error, as in the following section.
Minimizing
same as minimizing trace of the within class variation matrix,
Comment about decision surfaces
This sub-section is a stub. You can help by adding what Mimi said about this topic.
Statistical Clustering Methods
Clustering by mixture decomposition works best with Gaussians. What are examples of gaussians? Circles, ellipses. However, if you have banana-like data, that won't work so well.
Article idea, with links to earlier discussion of this concept?_Old Kiwi
If you are in higher dimensions, do not even think of using statistical clustering methods! There is simply too much space through which the data is spread, so they won't be lumped together very closely.
- Assume each pattern $ x_{i}\in D $ was drawn from a mixture $ c $ underlying populations. ($ c $ is the number of classes)
- Assume the form for each population is known
- Define the mixture density
- Use pattern's $ x_{i}'s $ to estimate $ \theta $ and the priors $ P(\omega_{i}) $
Then the separation between the clusters is given by the separation surface between the classes (which is defined as ...)\\
Example: Model the data as a Gaussian Mixture
$ p(x|\mu_{i},\ldots,\mu_)=\sum_{i=1}^cP(\omega_{i})\frac{e^{(x_{1}-\mu_{1})^{T}\Sigma_{1}^{-1}(x_{1}-\mu_{1})}}{2\pi|\Sigma_{i}|^{n/2}} $
Note: the Maximum Likelihood approach to estimating $ \theta $is the same as minimizing the cost function $ J $ of the between-class scatter matrices.
Sub-example
If $ \Sigma_{1}=\Sigma_{2}=\ldots=\Sigma_{c} $, then this is the same as minimizing $ |S_{w}| $
Sub-example 2
If $ \Sigma_{1},\Sigma_{2},\ldots,\Sigma_{c} $ are not all equal, this
is the same as minimizingProfessor Bouman's "Cluster" Software
The "CLUSTER" software, developed by Purdue University's own Professor Charles Bouman, can be found, along with all supporting documentation, here: Cluster Homepage. The algorithm takes an iterative bottom-up (or agglomerative) approach to clustering. Different from many clustering algorithms, this one uses a so-called "Rissaren criterion" or "minimum description length" (MDL) as the best fit criterion. In short, MDL favors density estimates with parameters that may be encoded (along with the data) with very few bits. i.e. The simpler it is to represent both the density parameters and data in some binary form, the better the estimate is considered.
Note: there is a typo in the manual that comes with "CLUSTER." In the overview figure, two of the blocks have been exchanged. The figure below hopefully corrects this typo.
Below is the block diagram from the software manual (with misplaced blocks corrected) describing the function of the software.
(Fig.2)
Clustering by finding valleys of densities
Idea: Cluster boundaries correspond to local minima of density fct (=valleys)
in 2D
Advantages
- no presumptions about the shape of the data
- no presumptions about the number of clusters
Approach 1: "bump hunting"
Reference: CLIQUE98 Agrawal et al.
- Approximate the density fct p(x), (Using Parzen window)
- Approximate the density fct p(x), (Using K-Nearest Neighbor)
References
- CLIQUE98 Agrawal et al.