# Tag Info

## Hot answers tagged dbscan

8

You take the last column of that matrix sort descending plot index, distance hope to see a knee (if the distance does not work well. there might be none)

5

In short, KMeans is a distance based clustering technique where depending on the distance between the data points your initialization(usually kmeans++) and clustering works. In kmeans, you initialize cluster centers and then find distance between each point and each of the cluster and then you cluster points to their nearest centers. Here the optimization ...

5

When I run the code you posted, I get three points on my plot: The "point" at (0, 4) corresponds to X[1] and the "point" at (0, 5) is actually three points, corresponding to X[0], X[2], and X[3]. The point at (5, 5) is the last point in your X array. The data at (0, 4) and (0, 5) belong to one cluster, and the point at (5, 5) is considered noise (plotted in ...

4

If you want to test whether your algorithm works as expected, I'd use sklearn datasets. They allow you to create simple synthetic 2D data with certain properties: circles, half moons, etc. If you want "real" datasets, here is an interesting resource found after a brief search: https://uni.hi.is/helmut/2019/06/20/datasets-for-dbscan-evaluation/ It seems to ...

3

Euclidean distances between l2-normalized word vectors is equivalent to the angular distance between the word vectors. This is not the same as cosine distance, but it is very similar. It is worth noting that cosine distance is not actually a metric, and that forces many algorithms, including the ones discussed here, to resort to more expensive O(n^2) ...

3

You can do DBSCAN, OPTICS, HDBSCAN with cosine similarity - they do not expect or require Euclidean distances. Yes, one version of cosine distance corresponds nicely to Euclidean distance of L2 normalized vectors. So there is some theoretical support to L2 normalize the vectors and try Euclidean then. Given how word2vec is trained, I don't think Euclidean ...

3

Write the DBSCAN code yourself. Run the code. Observe that your code likely will be a lot slower than the libraries code.

3

A cluster in DBSCAN consists of multiple core points. The radius is the area covered by a single core point, but together with neighbor core points the shape will be much more complex. In particular, they can be much larger than epsilon, so you should choose a small value, and rely on this "cover" functionality. Wikipedia has an example of a non-convex ...

2

DBSCAN does not guarantee a minimum cluster size. There are known situations, c.f. Wikipedia, where a cluster can have fewer than "minPts" points. Furthermore, it has the concept of noise: points that do not have enough neighbors. For epsilon, also see the Wikipedia article. As you don't specify the number of clusters, this parameter is what mostly controls ...

2

You don't want clustering. What you are looking for is near duplicate detection. Use minhash. Apparently that is what Google News uses for exactly this purpose.

2

As the algorithm should not change the order of the lists you could just add the clusters list cities["cluster"] = cluster If you are really paranoid you can add your input parameters a second time to the dataframe in the same way and compare the diff in values (should be 0).

2

If I remember correctly, non-negative matrix factorization (NMF) can be used as a clustering approach that can recover clusters that are along vectors, for example. It may work for your dataset. It factors a data matrix $D \in \mathbb{R}^{m * n}$ into two matrices $W \in \mathbb{R}^{m*k}$ and $H \in \mathbb{R}^{k * n}$. Effectively, $W$ contains the weights ...

2

No, it does not make sense to encore the data this way. You use Euclidean distance. You need to encode the variables in a way that Euclidean distance computes a similarity that is useful for your problem. It strictly is not enough to encode stuff somehow as numbers! Garbage in, garbage out is what you get this way.

2

In the scikit-learn implementation of Spectral clustering and DBSCAN you do not need to precompute the distances, you should input the sample coordinates for all id_1 ... id_n. Here is a simplification of the documented example comparison of clustering algorithms: import numpy as np from sklearn import cluster from sklearn.preprocessing import ...

2

Dont try to visually confirm it. You are plotting your clustering resutls in ONLY two dimensions and you expect that all of the information is in these two dimesnions. That is very unlikely. If you plot 3 dimensions you will see even more seperability and it will make a bit more sense. In any case you need a metric for example Silhouette that tells you how ...

2

Each of those selected clustering algorithms can be fit using cosine distances in scikit-learn: from sklearn.cluster import DBSCAN, MeanShift, OPTICS from sklearn.metrics.pairwise import cosine_distances # Define clustering algorithms algorithms = [DBSCAN, MeanShift, OPTICS] # Placeholder for results results = dict.fromkeys((a.__name__ for a in algorithms)...

1

Why do you recompute the distance matrix? Just compute the 1x5000 vector directly for all new points. You can even do this in batches, then feed one row at a time to the predictor.

1

Bilgin! Anony-Mousse puts right questions and gives good suggestions. Before you use the self-implemented DBSCAN code - write it on paper. Perhaps it is not the best algorithm at all for your database so try sci-kit learn implementation first to see the results. Here are the Python implementation https://github.com/chrisjmccormick/dbscan/blob/master/...

1

Define your own distance function. I suggest you simply use dist(x,y)=haversine(x[0],y[0])+haversine(x[1],y[1])

1

The main difference is that they work completely differently and solve different problems. Kmeans is a least-squares optimization, whereas DBSCAN finds density-connected regions. Which technique is appropriate to use depends on your data and objectives. If you want to minimize least squares, use k-means. If you want to find density-connected regions use ...

1

Don't blindly copy code from the internet. You copied code that scales data. Hence, the axis changed. But that wasn't DBSCAN, but that was you invoking StandardScaler. It is important that you understand what you are doing... You have a time axis and a value axis. These are completely different, and computing Euclidean distance does not make any sense... ...

1

The output from db_scan.labels_ is the assigned cluster value for each of the points that you provide as input to the algorithm. You provided 20 points, so there are 20 labels. As explained in the relevant documentation, you will see: labels_ : array, shape = [n_samples] Cluster labels for each point in the dataset given to fit(). Noisy samples are ...

1

Automatic weighting will likely not be enough. For examples standard scaler will assign twice as much weight to the one-hot encoded parts than to the other attributes. Plus, it is based on the assumption that all variables should have the same (assuming they are all normal distributed) weight. But should they all have the same weight? Does it even make ...

1

Don't use clustering at all. Define a threshold, and theshold the data. Done. Keep it simple and easy to understand.

1

You can run DBSCAN without storing the distances in a matrix. This has the drawback that each time you visit a point, you have to recalculate all the relevant distances, which requires more time. However, the space complexity stays $O(n)$, since the only things you have in memory at any single time are the positions of the n points, their various labels, the ...

1

As @Anony-Mousse pointed it, on DBSCAN index structures are often used in order to decrease execution times. K-d-trees are one example but this one works well just in small dimensions. You had right intuition about what slowing down, the computation of every distance from all point to one is O(n) time complexity but applied to every points it becomes O(n2) ...

1

Normalizing the vectors maps them all down to a unit sphere. That definitely changes their Euclidean distances (not cosine distances though), so, no I don't think that's valid, nor does it help the dimensionality. Clustering in high dimensions is indeed problematic and I agree with @Emre that t-SNE is an option to get more meaningful clusters out for ...

1

General speaking, you can assign the cluster to the new value using the method of that clustering method. For example, if you are using the DBSACAN algorithm, you can assign the cluster to the new value, if it is reachable from one core points of a cluster (in a tie situation, we can assign the more density cluster or many other methods).

1

DBSCAN is O(n) times the cost of a neighbor search. If you use an index like LSH that could answer neighborhood search in O(1) (assuming a very even data distribution, with O(1) neighbors per point) then DBSCAN can run in O(n) plus the time needed to build such an index. Yes, minHash indexes could be used if they are appropriate for your data and distance.

1

None of the internal evaluation metrics will work well on text in my experience. Probably because of the curse of dimensionality. Furthermore, DBSCAN does not cluster everything, but can also produce noise points. Few evaluation methods (and even fewer implementations...) handle it well that noise is not a cluster.

Only top voted, non community-wiki answers of a minimum length are eligible