# A formal analysis of stability - lessons and open questions

Lecture slides:

- A formal analysis of stability - lessons and challenges
- What is a good clustering???
- In what sense is the leftmost clustering better than the middle one?
- Even if we commit to a fixed cost function
- Even harder questions
- Quest for a general theory
- A more modest approach
- Stability - the basic idea
- Stability - the formal definition
- (In)Stability detects non-clusterability:
- Stability distinguishes relevant from irrelevant clustering paradigms:
- Stability detects correct k
- Conclusions (as of Dec. 2005)
- Have we found a good answer?
- Some bothersome examples
- The bottom line of a formal analysis
- The formal results
- Proof Idea 1: Uniqueness implies stability
- Proof idea 2: Multiple solutions imply instability
- Proof idea (continued)
- Some Examples
- The bottom line
- Other notions of stability
- Two different topics for discussion
- Some thoughts on the ‘finite samples’ issue
- Alternative notions of clusterability

*Author: Shai Ben David, University Of Waterlo*