Representative Selection in Nonmetric Datasets

Figures & data

FIGURE 1 Clustering vs. representative selection. (a) When applying k-medoids, k = 77 clusters are required to satisfy the distance condition. (b) A better representative set does so with only 13 representatives.

Table

Algorithm 1. Extended Greedy K-Centers Approach (farthest first traversal)

1: Input: data sampleSet , required distance δ

2: choose random starting representative

3: representativeSet

4: sampleSet

5: maximalDist

6: while maximalDist > δ do

7:  maximalElement

8:  representativeSet

9:  sampleSet

10:  maximalDist

11: end while

Table

Algorithm 2. One-shot δ-representatives selection algorithm

1: Input: data , required distance δ

2: Initialize representatives .

3: Initialize clusters

4: representative assignment subroutine, RepAssign, lines 5–22:

5: for i = 0 to m do

6:  Initialize dist

7:  Initialize representative = null

8:  for rep in representatives do

9:   if d(xi, rep) ≤ dist then

10:    representative = rep

11:    dist = d (xi, rep)

12:   end if

13:  end for

14:  if dist ≤ δ then

15:   add xi to clusterrepresentative

16:  else

17:    representative = xi

18:    Initialize clusterrepresentative

19:    add xi to clusterrepresentative

20:    add clusterrepresentative to clusters

21:  end if

22: end for

Table

Algorithm 3. The δ-medoid representative selection algorithm.

1: Input: data required distance δ

2: t = 0

3: initialize .

4: initialize

5: repeat

6:

7:  call RepAssign subroutine, lines 5–22 of Algorithm 2

8:  initialize

9:  for cluster in clusters do

10:

11:   add representative to representativest

12:  end for

13: until representativest = representativest–1

FIGURE 2 Three musical segments as pitch (in MIDI format) over time, along with the musical notation of the first segment (1stViolinSeg).

FIGURE 3 Representative set size percentage from entire set and average representative set distance for three different composers, ten different pieces each, and five different distance criteria. Each column represents data for a different composer; δ-medoids yields the most compact representative set overall while still obtaining a smaller average distance than the k-centers heuristic.

FIGURE 4 The RoboCup 2D Simulation. Three potential movement trajectories for a specific agents are marked.

FIGURE 5 Representative set size percentage from entire set for four different teams, five different game logs each, and five distance criteria. Each column represents game data for a different team. Axes denoting distance are in log-scale.

FIGURE 6 The histograms (plotted as density functions, i.e., counts normalized as percentages) of the average overlap between representative sets found for each method for the same data under different permutations (overlap measured in %). For k-medoids, δ-medoids, and the k-centers heuristic, in more than 90% of the datasets, there was a > 90% average overlap. Spectral clustering yields drastically less consistent representation sets. The overlaps observed are almost exactly the same, implying that the expected extent of overlap depends more on the structure of the data than on the type of randomization the algorithm employs.

FIGURE 7 Representative set size percentage from entire set and average representative set distance for four different multivariate Gaussian distributions from which the samples are drawn, 20 different experiments each, and four different distribution values. Each column represents data for a different distribution; δ-medoids yields the most compact representative set overall while still obtaining a smaller average distance than the k-centers heuristic.

FIGURE 8 Two segments for example, in musical notation.

FIGURE 9 Same two segments, plotted as midi pitch over time.

FIGURE 10 Two movement segments. Each coordinate in the trajectory is labeled with its timestamp in the trajectory . Both segments begin with a long sprint toward one direction and then a sequence of small steps in the opposite direction (scales are × 10).