A hubness based sampling approach for PAM algorithm

Hub is the data instance that appears frequently in other instances´ nearest neighbour lists. Hubness, the emergence of hubs, is an important property of high-dimensional datasets. An instance with a large hubness score is usually close to the centre of a cluster, whereas that with a small score is often an outlier or a boundary instance. In this paper, a hubness score based sampling approach is proposed for PAM algorithm. It selects some of the high hubness score instances to reduce redundancy, and at the same time, guarantees that every instance from original dataset will have some of its K nearest neighbours being selected. Experimental results on six UCI datasets and two synthetic datasets suggests: when K is set to 10, the approach removes more than 80% instances and increases clustering accuracy.