Active Learning of Custering with Side Information Using $\eps$-Smooth Relative Regret Approximations

Details Active Learning of Custering with Side Information Using $\eps$-Smooth Relative Regret Approximations Active Learning of Custering with Side Information Using $\eps$-Smooth Relative Regret Approximations

2012-01-31

arxiv.org/abs/1201.6462v1

Computer Science

Learning

Scientific paper

Clustering is considered a non-supervised learning setting, in which the goal is to partition a collection of data points into disjoint clusters. Often a bound $k$ on the number of clusters is given or assumed by the practitioner. Many versions of this problem have been defined, most notably $k$-means and $k$-median. An underlying problem with the unsupervised nature of clustering it that of determining a similarity function. One approach for alleviating this difficulty is known as clustering with side information, alternatively, semi-supervised clustering. Here, the practitioner incorporates side information in the form of "must be clustered" or "must be separated" labels for data point pairs. Each such piece of information comes at a "query cost" (often involving human response solicitation). The collection of labels is then incorporated in the usual clustering algorithm as either strict or as soft constraints, possibly adding a pairwise constraint penalty function to the chosen clustering objective. Our work is mostly related to clustering with side information. We ask how to choose the pairs of data points. Our analysis gives rise to a method provably better than simply choosing them uniformly at random. Roughly speaking, we show that the distribution must be biased so as more weight is placed on pairs incident to elements in smaller clusters in some optimal solution. Of course we do not know the optimal solution, hence we don't know the bias. Using the recently introduced method of $\eps$-smooth relative regret approximations of Ailon, Begleiter and Ezra, we can show an iterative process that improves both the clustering and the bias in tandem. The process provably converges to the optimal solution faster (in terms of query cost) than an algorithm selecting pairs uniformly.

Affiliated with

Also associated with

No associations

Rating

Active Learning of Custering with Side Information Using $\eps$-Smooth Relative Regret Approximations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Active Learning of Custering with Side Information Using $\eps$-Smooth Relative Regret Approximations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Active Learning of Custering with Side Information Using $\eps$-Smooth Relative Regret Approximations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56553