Human-supervised clustering of multidimensional data using crowdsourcing

Abstract

Clustering is a central task in many data analysis applications. However, there is no universally accepted metric to decide the occurrence of clusters. Ultimately, we have to resort to a consensus between experts. The problem is amplified with high-dimensional datasets where classical distances become uninformative and the ability of humans to fully apprehend the distribution of the data is challenged. In this paper, we design a mobile human-computing game as a tool to query human perception for the multidimensional data clustering problem. We propose two clustering algorithms that partially or entirely rely on aggregated human answers and report the results of two experiments conducted on synthetic and real-world datasets. We show that our methods perform on par or better than the most popular automated clustering algorithms. Our results suggest that hybrid systems leveraging annotations of partial datasets collected through crowdsourcing platforms can be an efficient strategy to capture the collective wisdom for solving abstract computational problems.

Keywords: crowdsourcing; data clustering; games; human-computing.

Figure 1.

Illustration of multiple scenes of Colony B. (a) Clustering panel with stage/total scores and puzzle progress, (b) end-game screen showing the progress towards a new badge discovery, (c) list of available thematic badges, (d) educational information related to a badge, and (e) leaderboard with multiple leagues.

Figure 2.

Game flow showing the first two stages and the process of puzzle solving. The player: (a) is presented with initial stage data; (b) makes a selection of the most representative group of dots on the mobile screen; (c) receives feedback from the game (score); and (d) is presented with the next stage data. It also shows in blue the points selected by the player on the previous stage. The player selects a group of dots for this stage and (e) receives feedback from the game.

Figure 3.

Performance comparison of the human-based algorithms with automated clustering approaches applied to the synthetic dataset for (a) all clusters; (b) low-dimensional clusters; and (c) high-dimensional clusters. The colour scheme is used to separate groups of algorithms: hubCLIQUE (red), automated CLIQUE (orange), CloCworks (purple), algorithms that require a known number of clusters/components (green), and algorithms that do not require it (cyan). For GMM, the average value over 1000 runs is reported. For algorithms requiring a known number of clusters, we report their performance with the number of clusters estimated by the elbow heuristic (four).

Figure 4.

Analysis of the performance of CloCworks applied to a series of Colony B-simulated networks using the stochastic block models (SBM) network generator. CloCworks was applied to every set of networks.

Figure 5.

Performance comparison of the human-based algorithms with automated clustering approaches applied to the voice recognition dataset (VRD). The figure notations and chosen colour scheme are described in figure 3.