Managing large and confusing sets of increasing data is a well-known problem in Data Mining. Since compromises in many use cases like Recommender Systems or preferencebased applications are becoming more and more usual, it is very useful to cluster sets of promising results in order to get an overview and present them properly. In this paper we present the Pareto-dominance as a very suitable and promising approach to cluster objects over better than relationships. In order to meet someones desires, one can tip the balance of the nal results to the more favored dimension if no decision for allocating objects is possible.
Suggestions in Recommender Systems sometimes are confusing, because there are often too many results presented to the user. Clustering these results is a very promising opportunity to present less but representative results to the user. For example, in a Recommender System which addresses people with a similar taste of music, the regional distance to users which represents possible matches, similar to other applications, e.g., Tinder1, is considered almost as important as the music-matching score.
Assuming user Bob is searching for users, who have a high music-matching score and live in the neighborhood. There are users which are better than other users regarding one 1http://www.gotinder.com/ 2017, Copyright is with the authors. Published in the Workshop Proceedings of the EDBT/ICDT 2017 Joint Conference (March 21, 2017, Venice, Italy) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0 dimension, e.g., the music-matching score, but are worse at the same time than other users regarding the other dimension, e.g., the distance to Bob. In Figure 1 user P1 has a very close distance to Bob, and dominates due to that all other users. But P1 is dominated by all other users w.r.t. the very low music-matching score to Bob at the same time. This exposition, where only non-dominated users are shown is called Pareto-frontier or Skyline.
Now, the aim is to organize a large set of objects in a Paretofrontier clearly. One method is to compress this set and express it with a smaller appropriate set of representatives. Another approach is to mask out undesirable results, e.g., users like P9 and P10 who have a higher music-matching score, but unfortunately a very high distance. These two attempts can only be reached with some kind of clustering.
However we have two dimensions with di erent domains, e.g., distance in kilometers and music-matching as a score value. Therefore it is hardly possible to achieve an useful outcome without great a ord, because the dimensions should be set into relation to each other. In our example it is very circumstantial to set this wide range of distances in relation to only a small range of music-matching scores. Since every user has diverse requirements in such a Recommender System, it is by far not su cient to use the basic k-means clustering algorithm along with the typical Euclidean distance.
The approach presented in this paper uses the Paretodominance in order to cluster over better than relationships unlike mapped Euclidean distances, which have to be adjusted inconveniently for each use case.
The rest of the paper is organized as follows: We present related work in Section 2 and explain the basic background knowledge in Section 3. Our Pareto-dominance clustering approach is described in Section 4. After that, we discuss experiments, where runtime, number of iterations and quality of the nal clusters are considered and compared to the basic k-means clustering algorithm in Section 5. Finally Section 6 summarizes results and gives an outlook on future work.
A very early approach considering a Pareto-e cient
clustering was published in [
In [
In order to prevent a large set of Pareto-optimal objects
in highdimensional space in [
Another approach to handle with Skylines was presented
in [
Before explaining the Pareto-dominance clustering framework, we describe some important concepts. One basic point is the preference framework in order to shape desire-based queries. The other basic point mentioned in this section is the k-means clustering algorithm. 3.1
Preferences represent wishes which should be ful lled. In database systems a preference P = (A; <P ) is modeled as a strict partial order on the domain of A, dom(A). The term x <P y can be described as \I like y more than x". The most important preference is the well-known Pareto preference which models equal importance.
A Pareto preference P := P1 P2 = (A1 A2; <P ) with preferences Pi = (Ai; <Pi ) and tuples x = (x1; x2); y = (y1; y2) 2 dom(A1) dom(A2) is de ned as follows: (x1; x2) <P (y1; y2) , (x1 <P1 y1 ^ (x2 <P2 y2 _ x2 = y2)) _ (x2 <P2 y2 ^ (x1 <P1 y1 _ x1 = y1))
In order to construct Pareto preferences there are several
preference constructors published in [
k-means Clustering
The k-means clustering algorithm is the point of origin for
the clustering approach presented in our paper. Therefore
the base k-means clustering is brie y described here, as it is
presented in [
Given a set X = fxi j i = 1; :::; ng of d-dimensional points xi = (xi1; :::; xid) of size n and a set of k Clusters C = fcj j j = 1; :::; kg the algorithm works as follows: Algorithm 1
(k-means-clustering). 1. Choose an initial partition for the centroids of k clusters and repeat the following steps 2 and 3 until two succeeding clusterings are stable. Two clusterings are stable, if the points of the particular clusters are equal. 2. Allocate each point to the closest cluster based on the Euclidean norm to the cluster-centroids.
s d d(x1; x2) = jj x1 x2 jj2= P (x1i x2i)2 i=1 3. Recalculate the cluster-centroids of each cluster by averaging the contained points.
Consider the users in Figure 1, shown as points on a Pareto-frontier. Now we want to get three clusters. First, initialize the centroids of the three desired clusters randomly with P2; P5 and P8 for C1; C2 and C3.
Now for each user P1; :::; P10 the Euclidean distance to all three centroids, determined in step 1, are calculated. P1; P3 and P4 are allocated to C1, while the users P6 and P7 are assigned to C2. Finally C3 receives the users P9 and P10.
In the last step of each iteration, the new centroids W1; W2 and W3 of each cluster are averaged based on the points contained in the clusters. The result is shown in Figure 2.
In this section we describe the Pareto-dominance framework in detail. While a Pareto preference is used to determine the importance of preferences, the Pareto-dominance in our approach is used to allocate an object to the possibly best cluster, which is not dominated by other clusters w.r.t. the distances of the individual objects, by using the Euclidean norm for one-dimensional distances. Moreover the Paretodominance can additionally be used to nd the centroids closest point on the Pareto-frontier as new centroid in each cluster. 4.1
Consider the Pareto-frontier in Figure 1, presenting users w.r.t. a possibly high music-matching score and a possibly close distance. We want to get three promising clusters C1; C2 and C3. In this case assume the cluster-centroids are represented by the points P2; P5 and P8 (Step 1 in Algorithm 1). After that, for each point P1; :::; P10 the particular distances of the x- and the y-dimension to the cluster centroids are calculated as it can be seen in Table 1. In our approach this replaces step 2 in Algorithm 1. Furthermore the y-dimension, which represents the music-matching score is chosen as more important than the x-dimension at the appearance of Pareto-optimal cluster-centroids. Thus a onedimensional clustering is realized. The allocation of each user to a cluster can be seen in Figure 3.
Figure 4 shows a snippet of the Pareto-frontier of Figure 2 respectively Figure 3. While P4 is assigned to C1 regarding the smaller Euclidean distance of 41.27 unlike a distance of 52.00 to C2, the Pareto-dominance approach shows its versatility. The user Bob now can in uence on the clustering by choosing one dimension as the more important at the appearance of Pareto-optima. If he chooses the x-dimension, as more important P4 will be assigned to C1. This ensures that each user will be allocated to one and only one cluster, to avoid overlapping and imprecise clusters. This example shows, that a Pareto-dominant clustering combined with a one-dimensional clustering at the appearance of Paretooptima tends to a hierarchical clustering. Users with similar scoring values w.r.t. the music matching score are clustered together, unlike in the basic k-means clustering. In particular cluster C1 and C2 contain users with very similar musicmatching scores, where the range between the two boundary points is very small unlike the k-means clustering approach. So if P7 is allocated to C2 and P4 to C1 the users contained in the clusters are not as similar as in our approach.
After the allocation of each user to a cluster, the clustercentroids are recalculated regarding the contained users. For each cluster all values for the x- and y-dimension are averaged, which can be seen in Figure 3 as W1; W2 and W3.
After that for each cluster-centroid W1; W2 and W3 the closest Pareto-dominant user in each cluster can be optionally selected as the new cluster-centroid for the next iteration. In order to nd these users, the particular distances regarding the two dimensions are calculated, which can be seen in Table 2. Figure 3 shows the calculated centroids before assigning and the new centroids aswell.
P2 is the new cluster centroid of C1, because of the closest distance of each x- and y-dimension to W1. For cluster C2 P5 is allocated as new centroid because of the closer distances in both dimensions, too.
P8 and P9 both are Pareto-optima for the allocation of the cluster centroid of C3, because P9 is closer to W3 regarding the y-dimension and P8 regarding the xdimension. The one-dimensional clustering determined by Bob tips the balance to P9 as new cluster centroid.
In this section we describe the implemented frameworks for Java and PG/PL-SQL brie y and present results of experiments regarding runtime, number of iterations and quality of the clustering approaches compared to the basic k-means approach. 5.1
The rst implementation of our Pareto-dominant clustering was realized as a Java program with a complexity of O(n c m) where n is the number of points that should be clustered in c clusters in m iterations. We also implemented a database internal approach based on PG/PL-SQL in PostgreSQL2, because we want to show the bene ts of clustering in relational databases.
For both approaches we varied the number of points and the number of desired clusters. To compare the runtimes, we created several synthetic anticorrelated sets of two-dimensional Pareto-optimal points. In order to gain averaged reliable data, clusterings were performed in test rows with varying numbers of repeats w.r.t. the number of points. 5.2
The benchmarks of the Java implementation in Figure 5 show that the approach using the Pareto-dominance are mostly similar regarding the runtime compared to the basic k-means approach using the Euclidean distance. For constant numbers of clusters and growing number of points the runtime of the averaged clustering is growing for both approaches. Whereas for constant numbers of points and growing clusterings there are some aberations at k = 7 for 15000 for both approaches. Especially if points at the border of the cluster switch between two clusters, the runtime is growing. All in all the clustering approach using the Pareto-dominance is nearly e cient as using the Euclidean distance.
The benchmarks for the database approach in Figure 6 shows di erent behavior. The Pareto-dominance approach is of factor 2 slower than the approach using the Euclidean distance, because of the use of expensive database operations like Joins or Group by operations, which are not needed using the Euclidean distance. Especially the tests with k = 5; 7 and sets with 15000 points show aberations for the Pareto-dominance. But all in all for growing number of points and growing number of clusters the runtime is growing, too. Finally our approach is slower than the basic k-means clustering. But the e ort of normalizing the users w.r.t. the two dimensions should be considered as a time-consuming process in each use case.
The number of iterations w.r.t. the number of desired clusters and the number of points can be seen in Figure 7. For both frameworks, the number of iterations is similar. For growing number of desired clusters, the number of iterations is growing for both approaches aswell, except for the sets of k = 5; 7 with 15000 points using the Pareto-dominance. In contrary to our expectations for this experiment the number of points in the sets has no in uence on the number of necessary iterations to achieve a stable clustering, i.e. two succeeding clustering-iterations are equal. 5.3
In this subsection we want to compare the quality of clusters between the basic k-means clustering algorithm and our approach in order to show that the stable clusters are quite similar and not completely di erent and thus useful for clustering objects of Pareto-frontiers.
Considering the example from Figure 2 and 3, which show both the most occurent stable clusterings after the second iteration. We performed a test-series based on the k-means clustering, which were compared to a testrow with 100 clusterings of our approach. In order to compare these Clusters we use Precision and Recall. Precision represents all desired and delivered objects (correct alarms) in relation to all delivered objects (correct alarms & false alarms), whereas Recall represents the desired and delivered objects (correct alarms) in relation to all desired objects (correct alarms & false dismissals).
false alarms (fa) false dismissals (fd) correct alarms (ca) Precision: cac+afa
ca Recall: ca+fd
C1 C2 C3 fg fP4g fP7g fP4g fP7g fg fP1; P2; P3g fP5; P6g fP8; P9; P10g
1 0.66 0.75 0.75 0.66 1
In Table 4 the test series show the Precision and Recall scores for two more clusterings and the frequency in the test series of 100 clusterings, which get averaged. Finally in this case there is one very present clustering (1), which is a very satisfying clustering as mentioned in Section 4. Both other clusterings have very high scores for Precision. The scores for Recall especially for the third cluster for the clustering 2 and 3 are very low, which shows that only a few users based on the k-means approach were assigned to this cluster.
We presented a novel Pareto-dominance based clustering framework on Pareto-frontiers. Our framework provides several reasons for using this to manage large confusing sets of tuples with explicitly di erent domains. First, one can in uence the result of the clustering by attaching weight to a more important dimension in order to cluster at least over one dimension at the appearance of Pareto-optima. Second, tuples can now be clustered over better-than relationships in order to avoid adjustments for utilization in di erent uses cases. Third, our preliminary benchmarks show that a Pareto-dominant clustering can be realized in adequate time. The quality of our approach is satisfying, because the stable clusters distinguish from them of the basic k-means clustering, but are still as similar as possible, especially regarding the a liation of similar points w.r.t. the onedimensional clustering.
Future work includes the integration of multi-dimensional clusters using Borda count. For more comprehensive benchmarks, we want to investigate experiments on higher dimensions. Furthermore experiments with ground truth data sets and comparisons to other types of clusterings, e.g., agglomerative and density-based clusterings are scheduled aswell.
This work has been partially funded by the German Federal Ministry for Economic A airs and Energy according to a decision by the German Bundestag, grant no. ZF4034402LF5.