Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Constraint-Based Clustering Methods (II):Handling Soft Constraints

  • Treated as an optimization problem: When a clustering violates a soft constraint, a penalty is imposed on the clustering
  • Overall objective: Optimizing the clustering quality, and minimizing the constraint violation penalty
  • Ex. CVQE (Constrained Vector Quantization Error) algorithm: Conduct k-means clustering while enforcing constraint violation penalties
  • Objective function: Sum of distance used in k-means, adjusted by the constraint violation penalties
    • Penalty of a must-link violation
      • If objects x and y must-be-linked but they are assigned to two different centers, c1 and c2, dist(c1, c2) is added to the objective function as the penalty
    • Penalty of a cannot-link violation
      • If objects x and y cannot-be-linked but they are assigned to a common center c, dist(c, c′), between c and c′ is added to the objective function as the penalty, where c′ is the closest cluster to c that can accommodate x or y


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.