A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

7

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

When I run the code you posted, I get three points on my plot: The "point" at (0, 4) corresponds to X and the "point" at (0, 5) is actually three points, corresponding to X, X, and X. 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 ...

3

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

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

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

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

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 ...

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 ...

1

Start with what the parameters mean. $\varepsilon$ is the search radius around each point. You need this search radius to be small enough that it can't fully "bridge the gap" between the clusters. If the gap width is variable, $\varepsilon$ needs to be small enough to accommodate the narrowest gap. Note that we can exclude the occasional straying point from ...

1

Just to point out a minor confusion that there seems to be in the wording: there is mixed use of the the words temporarily and temporally. [OP has since corrected this] We really only care about the final word, temporally i.e. relating to time, or the timestamps of the points in a cluster. Temporarily means only for a short period of time, which is a ...

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,y)+haversine(x,y)

1

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.

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

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

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.

1

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).

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.

1

https://github.com/alitouka/spark_dbscan is n-dimensional. you can try also WEKA, SPMF library

1

DBSCAN is not limited to 2d (apparently you only found very bad implementations) and can be used with correlation distance, too. But mostly, you need to focus on preprocessing. If you intend to do correlation anyway, you should consider to z normalize your input data, I.e. x'= (x - mean(x))/stddev(x)

1

In short PCA, returns an orthogonal set of basis features that best represent the variance in the data. Intuitively, imagine you want to identify whether we are talking about a dog or a cat. Your features are: size, weight, color, fur type, etc... but you also have features like weather, owner name, etc... It should be evident that the first set of ...

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