Balanced similarity-graph clustering

Description

Segment customers by partitioning a similarity graph built with extended Jaccard similarity into clusters of equal size or equal revenue, avoiding k-means' degenerate clusters on sparse data.

On sparse, high-dimensional purchase or usage data, Euclidean k-means produces degenerate results: one giant cluster and singletons. OPOSSUM represents each customer as a vector of spend per product, computes extended Jaccard similarity (which respects amounts and ignores shared absences), and uses a balanced graph partitioner so each cluster has a similar number of customers or a similar share of revenue. Results are shown as a reordered similarity matrix with dark diagonal blocks, and each cluster is profiled by top-revenue products and products with the highest lift. On 2,466 drugstore customers by 762 products with k=20, k-means gave a singleton and a cluster of 1,645, while OPOSSUM gave 122-125 per cluster; one cluster showed smoking-cessation gum at 35 times lift. A text case study found graph partitioning with cosine or Jaccard similarity best by NMI. Balance is a design choice, not a property of the data.

Attributes

Loss type
Unmigrated
Effort
Days

Steps

  1. Represent each user or customer as a vector of spend or usage per product or feature.
  2. Compute pairwise extended Jaccard (or cosine) similarity.
  3. Choose the balance criterion: equal counts or equal revenue or usage share.
  4. Partition the similarity graph into k balanced parts with a graph partitioner such as Metis.
  5. Display the reordered similarity matrix to judge separation between clusters.
  6. Profile each cluster by top items and lift relative to the whole population, and name segments.

Sources

  • Handbook of Data Mining (Ye, 2003)

Also known as

  • OPOSSUM
  • Size-constrained clustering
  • Value-balanced segmentation
  • Graph partitioning with extended Jaccard

Categories

  • Analytics & Behaviour
  • Computational & Machine Learning