IBM Research

K-means Clustering of Proportional Data
Using L1 DistanceHisashi Kashima
IBM Research, Tokyo Research Laboratory

Jianying Hu
Bonnie Ray
Moninder Singh
IBM Research, T.J. Watson Research Center© Copyright IBM Corporation 2008-2009

IBM Research

We propose a new clustering method for
proportional data with the L1 distance K-means clustering K-means clustering of proportional data with the L1-distance Motivation of L1-proportional data clustering: Workforce management
 An efficient sequential optimization algorithm
 Experimental results with real world data sets

K-means Clustering of Proportional Data Using L1 DistanceIBM Research

Review of K-means clustering K-means clusteringpartitions N data points
obtain K centers Iteration:
1. Assign each data point

into K groups

to its closest cluster

2. Estimate the j-th new centroid by
set of data points assigned
to the j-th cluster

whereis a distance measure between two vectors

K-means Clustering of Proportional Data Using L1 DistanceIBM Research

K-means clustering of proportional data
 K-means clustering of proportional data partitions N proportional data points

into K groups obtain K centers A proportional data is a M-dimensional vector
where each element is non-negative
 elements are summed to be one, i.e.

 Cluster center also must satisfy the constraints

andclustering

1

job role distributions

2345678910

cluster centroids (= templates)

K-means Clustering of Proportional Data Using L1 DistanceIBM Research

We use the L1 distance, but why ?
Application to Skill Allocation-Based Project Clustering We concentrate on the L1-distance as the distance measure Our motivation: Workforce management

We want staffing templates for assigning skilled people to various projects
A template indicates how much % of the whole project time is charged to a particular
job role
e.g. “software installation” template = (consultant=0.1, engineer=0.9, architect=0.0)• used for efficient assignment of appropriate people to appropriate project• used as bases of skill demand forecasting
The L1 distance from templates can be directly translated into cost differences.
• Also allows different skills associated with different costs

 L1-distance is known to be robust to noise
K-means Clustering of Proportional Data Using L1 DistanceIBM Research

Challenge of using L1 distance for K-mean clustering ofproportional data For L2 distance, the closed form solution is obtained as the meanregardless whether the proportional constraints apply

 For L1 distance,the median is the closed form solution for the unconstrained caseWith proportional constraints, no closed form solution exists

 There are two fast approximations for constrained L1 K-means:
1. Use the mean (just like L2 K-means)
2. Median followed by normalization

 Challenge: can we find an efficient way to compute accurate solutions ?

K-means Clustering of Proportional Data Using L1 DistanceIBM Research

Algorithm for K-means clustering with proportional data
 K-means clustering of proportional datapartitions N data points
obtain K centers

into K groups

 Iteration:
1. Assign each data point

to one of K clusters

2. For the j-th cluster, estimate a new centroid bys.t.
whereis the L1-distance:

K-means Clustering of Proportional Data Using L1 DistanceandIBM Research

The key point is how to solve step 2 efficiently The optimization problem involved in Step 2 iss.t.

and The equivalent linear programming problem has O( #data points ×#dimensions )-variables
 But we want a more efficient method tailored for our problem using
the equality constraint explicitly

K-means Clustering of Proportional Data Using L1 DistanceIBM Research

Our approach: sequential optimization w.r.t. 2 variables
 Key observation: we have only one equality constraints.t.

and We employ sequential optimization borrowing the idea of SMO
algorithm for SVM (QP)Picks up two variables at a time and optimizes w.r.t. the two variables Iteration:
1. find a pair of variables
andwhich improves the solution the most
2. Optimize the objective function with respect only to them (while keeping theequality constraint satisfied)K-means Clustering of Proportional Data Using L1 Distancea piecewise
linear function

IBM Research

How to select the two variables ?
 Key observation: The objective function is decomposed into
piecewise linear convex functions with only one parameter,piecewise linear
and with only oneparameter If we decrease,
will be increased Find a pair of variables
andwhich has the steepest gradient Found in O(log M) time by efficient implementations

gradient wrt the change

left gradient of

K-means Clustering of Proportional Data Using L1 Distanceright gradient of

IBM Research

How much do we update the two variables ?
 Update
andwhile keeping the constraint
 If we decrease
by,increases by Move the two variables until either of them reaches a corner point
minimum distance to thenext corner of the two
objective functions
 The number of updates is boundedby the number of corners

fdfd’

∆d∆d’

decrease ofincrease of

K-means Clustering of Proportional Data Using L1 DistanceIBM ResearchExperiments
 Two real world datasets representing skill allocations for past
projects in two service areas in IBM
1,604 project with 16 skill categories
302 projects with 67 skill categories

 We compared three algorithms


The proposed algorithm“Normalized median”
1. Computes dimension-wise medians
2. Normalizes them to make the sum to be one“Mean”• Uses sample means as cluster centroids(The equality constraint is automatically satisfied)K-means Clustering of Proportional Data Using L1 DistanceIBM Research

The proposed method achieves low L1 errors

2206020055
Total L1 distortion

Total L1 distortion

 10-fold cross validation × 10 runs with different initial clusters Performances are evaluated by sum of L1 distances to nearest clusters
 The proposed algorithm consistently outperforms both alternative
approaches at all values of K

180
160
140
120

50
Proposed
45

Proposed

Normalized Median

Normalized Median

40
Mean

Mean

35

100

30

80

25
1

23

4

5678

923

Number of clusters

K-means Clustering of Proportional Data Using L1 Distance4567

Number of clusters

8910

IBM Research

The proposed method produces moderately sparse clusters
 The proposed method leads to more interpretable cluster centroids
 “Normalized Median” produces many cluster centroids with only asingle non-zero dimension
Moderately sparse

Too sparse

Proposed
Proposed

Not sparse

NormalizedNormalizedMedianMedian
Unspecified
Project Management
Principal
PSIC
OtherMissing
Knowledge and Learning
Developer-Other
Data Related
Consultant-Other
Business Transformation Consultant
Business Strategy Consultant
Business Development Executive
Architect-Other
Application Developer
Application Architect

cluster 1cluster 2cluster 3

cluster 4cluster 5cluster 6cluster 1cluster 2cluster 3

Mean MeanUnspecified
Project Manage
Principal
PSIC
Other
Missing
Knowledge andDeveloper-Othe
Data Related
Consultant-Oth
Business Trans
Business Strat
Business Deve
Architect-Othe
Application Dev
Application Arc

Unspecified
Project Management
Principal
PSIC
Other
Missing
Knowledge and Learning
Developer-Other
Data Related
Consultant-Other
Business Transformation Consultant
Business Strategy Consultant
Business Development Executive
Architect-Other
Application Developer
Application Architect

cluster 4cluster 5

K-means Clustering of Proportional Data Using L1 Distancecluster 6cluster 1cluster 2cluster 3

cluster 4cluster 5cluster 6

IBM ResearchConclusion
 We proposed a new algorithm for clustering proportional data using
L1 distance measureThe proposed algorithm explicitly uses the equality constraint Other applications include


document clustering based on topic distributions
video analysis based on color distributions

K-means Clustering of Proportional Data Using L1 Distance