Jason (jcreed) wrote,

Kleinberg's class was interesting today: he claimed the following result. If by an n-clustering function is meant a map from sets of n points with pairwise distances supplied between all of them (subject to only symmetry I think, not the triangle inequality) to a partition of those points, then one of the following three desirable properties of a hypothetical clustering algorithm must be violated:

  1. Scale Invariance: If all the distances are multiplied by a constant, the same partition arises.
  2. Richness: All possible partitions of the n points are achievable by some distance matrix. (This is ostensibly to avoid a clustering function always giving some constant clustering)
  3. Consistency: Take some distance matrix and consider the partition the clustering function outputs. If we change the distance matrix in such a way that
    • the distances between pairs of points that are separated by the partitioning do not decrease
    • the distances between pairs of points that fall into the same partition do not increase
    then the partition the clustering algorithm outputs on the new distance matrix must be the same

Went to the talk rweba mentioned on "dark energy". Cosmologists have an odd set of constraints on how they have to think about their subject. Somehow exactly the gap in how we think the universe behaves and how it does behave can have any of like three or four explanations that all come out identically in the math of it, but have different consequences in terms of the mechanism of what's going on.

Went climbing with christina. I didn't manage any V1s (and I'm not certain I even did any V0+s come to think) but I did top out on one side of one structure that I hadn't before, on a V0 course. Quite fun.
Tags: climbing, math, science

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded