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
- Discipline
- Computational & Machine Learning
- Loss type
- Unmigrated
- Goal
- Segment users, Synthesise data
- Stage
- Discovery, Post-launch
- Data
- Quantitative
- Effort
- Days
Steps
- Represent each user or customer as a vector of spend or usage per product or feature.
- Compute pairwise extended Jaccard (or cosine) similarity.
- Choose the balance criterion: equal counts or equal revenue or usage share.
- Partition the similarity graph into k balanced parts with a graph partitioner such as Metis.
- Display the reordered similarity matrix to judge separation between clusters.
- 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