1
$\begingroup$

I am trying to self-learn more about different clustering methods. I think I understand the main idea of the algorithms, but perhaps their use-cases can shed light on something that puzzles me - namely, can two different data points have the same values? If dealing with macroscopic objects, then I think the answer is no. But if dealing with people's interests (example: users that like product A also like product B and product C), then I think the answer is yes. I'm not sure if this is correct, and I'm thinking that the answer to this question depends on the assumptions inherent to the clustering technique, so some details are below.

Agglomerative Hierarchical Clustering Context:

From this example, we are given a distance matrix that corresponds to the distances between several data points and want to run an agglomerative hierarchical clustering method. This distance matrix is given below:

 .. DISTANCE MATRIX (SHAPE=(6, 6)):
[[  0 662 877 255 412 996]
 [662   0 295 468 268 400]
 [877 295   0 754 564 138]
 [255 468 754   0 219 869]
 [412 268 564 219   0 669]
 [996 400 138 869 669   0]]

Say we apply single-linkage (aka minimum linkage). Since no two cities can be at the same location, each iteration produces a pair consisting of the row and column that correspond to the two closest cities; then the distance matrix loses that row and that column at each iteration. Now, suppose we had a different distance matrix that contais non-unique distances, either because data points can share the same location or because it is possible to have a subset of multiple non-overlappng cities at different locations that are equally distant from each other. As an example, this distance matrix could look something like this:

 .. DISTANCE MATRIX (SHAPE=(6, 6)):
[[  0 138 877 255 412 996]
 [138   0 295 468 268 400]
 [877 295   0 754 564 138]
 [255 468 754   0 219 869]
 [412 268 564 219   0 669]
 [996 400 138 869 669   0]]

(Notice that the non-zero minimum distance of 138 exists at (row, col) = (1, 0), (0, 1), (2, 5), (5, 2) not along the diagonal.) Then it follows that this linkage criteria may find more than one row and column that correspond to the minimum distance between data points. Is this allowed? If so, suppose we find from our distance matrix that two pairs of rows/columns (as opposed to one pair in the unique case) satisfy the linkage criteria at some iteration; would these rows/columns contained in the dendrogram have 4 (2 rows + 2 columns) legs instead of 2 (one row + one column)?

To complicate matters further, what if any of the non-diagonal elements of the distance matrix are zero? Is this allowed?

Density-Based DBSCAN Clustering Context:

One way to run the DBSCAN algorithm is to check if a point has been visited (for all points); if this original point has not been visited, check the number of points contained in the neighborhood of the original point and repeat this technique recursively to the neighborhood points. One can classify each neighborhood as a cluster or as noise based off of minimum number of points required to form a cluster.

The simplest case is that of unique data points. Suppose our data set is not so simple because it contains duplicates, and suppose our condition is that a minimum of 4 points are needed to classify a group as a cluster (else the group is noise). Suppose we find 4 points ([0, 0], [1, 0], [0, 1], [0, 1]) that can potentially form a cluster, but only 3 of the points are unique. In one sense, the duplicate point [0, 1] has already been visited and not counting it means the 3 unique data points are noise; if we consider duplicate points as non-visited, then the 4 points will form a cluster. How does one choose whether or not to consider the (non-)unique data points? Maybe it has to do with what the data points represent, but maybe it has something to do with the assumptions required for DBSCAN?

$\endgroup$
1
$\begingroup$

When working with real data, it makes little sense to discard points just because they have the same attributes.

The reason is simple: you only have incomplete data. There usually is some attribute (such as the row number, user id, etc.) that makes them different. But it is an attribute that you don't want to include in your analysis. Or: just because two persons have the same name does not mean they are the same person.

If you have many duplicates it can be beneficial to transform the data into a weighted data set though. But then you'll have to implement everything yourself because standard tools such as sklearn, ELKI, R all don't seem to support instance weighting in clustering.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.