# Tag Info

## Hot answers tagged clustering

Accepted

### Under what conditions is K-means clustering transformation-invariant?

The answer depends on your K-means algorithm, but what follows should work for standard algorithms. You will get the same result if your transformation $T$ satisfies two conditions: It preserves ...
• 278k

### Implement K-means clustering with Map-Reduce

You can run a loop over $j\in\{1..k\}$: Create a map that maps each point $x_i$ to itself if $x_i$ is nearest to the mean $m_j$, and to the zero vector otherwise: x_i \rightarrow \begin{cases}(x_i, ...

### What are the (efficient) algorithms to cluster squares into groups using a threshold such that the closest squares form groups?

Store the centers of the rectangles in a data structure that supports efficient nearest-neighbor queries, such as a quadtree. Now for each rectangle $R$, you can determine whether there exist any ...
• 163k
Accepted

### Group time series events into minimal amount of buckets

The first event at time $t_0$ needs to be in a bucket. We can safely choose the bucket $[t_0, t_0+30]$, as there is nothing to gain by making it start earlier. We then move on to the next event ...
• 2,542
Accepted

### clustering with uncertain number of clusters

Several algorithms allow doing this. First one is the hierarchical clustering. When creating your dendrogram, the key is to cut the "longest branches." DBSCAN is also a good alternative. Finally, you ...
Accepted

### 2 means clustering

Your proof makes no sense to me. I don't know what you mean by "each center is assigned to one of my centers". When writing a proof, you need to define all terms before first use, and use rigorous ...
• 163k
Accepted

### How to compare/cluster millions of strings?

The length of each string is at least 200, and you only consider two strings similar if their edit distance is less than 20. So if $S,T$ are similar, then there must exist $U$ such that (1) $U$ is a ...
• 163k

### Convolutional Neural Network with constant kernels

A fully connected layer is able to classify images better than random. If you make the kernels constant and there is still information in the result, the network is essentially only a FCN operating on ...
• 2,360

### The nearest points in a set

This problem does generalize the clique problem. One example of a metric is the shortest path distance in a connected, unweighted graph $G$, where the distance between vertices $u$ and $v$, $d(u,v)$, ...
• 126

### Cluster Edge Deletion on 2-trees

Let me first formalize the problem: Cluster edition Instance: A graph $G$ and an integer $k$. Question: Can $G$ be transformed into a cluster graph by deleting at most $k$ edges? It is not difficult ...
• 22.7k
Accepted

### Why does the BFR (Bradley, Fayyad and Reina) algorithm assume clusters to be normally distributed around its centroid?

Roughly, the algorithm needs to estimate the probability to assign a point the correct cluster. So the algorithm add P to a cluster if it is very unlikely that, after all the points have been ...
• 146
Accepted

### Efficient Network Clustering Algorithm for Million Node Networks

The Louvain algorithm does just this, and it easily handles graphs of this size. It is implemented in most, if not all, graph libraries. In particular, Networkit provides a fast parallel ...
Accepted

### K-Modes Clustering with Partially-Overlapping, Variable-Length Data?

I don't know how if there's a "proper" way to do this, but defining a similarity measure between two bags of "words" is a well-trodden path in information retrieval. Let $B$ be the ...
• 22.7k
Accepted

### What type of clustering would occur if one of the functions in double hashing is constant?

When $h_2$ is constant we have open adressing with linear probing. Usually the step size equals $1$, but here it is another constant. It has both primary and secundary clustering. For the primary ...
• 30.8k
Accepted

### Community detection in weighted directed graphs for fixed number of communities

There are lots of community detection algorithms that need the number of communities as input. For example, Bigclam [1], a matrix factorization approach, needs the number of communities as input. ...
• 1,944
Accepted

### sum of squared distances from mean equals all-pairs sum of square distances?

This can be easily seen by a change of coordinates that makes the average $\bar{x} = 0$. This can be done by translating the whole plane, preserving all distances. Since the equation depends only on ...
• 1,807
Accepted

### Least squares fit of a 1D lattice of points to a 2D dataset

Define an objective function $\Psi(m,c,d,i)$ that specifies how "bad" a particular choice of values for $m,c,d,i$ are. Then, use any standard black-box optimization algorithm (e.g., gradient descent) ...
• 163k
Accepted

### Convolutional Neural Network with constant kernels

No, probably not -- unless you happen to get lucky and the kernel weights you started with just happen to be good ones. But if you choose the kernel weights randomly, your procedure will probably ...
• 163k
Accepted

### CURE algorithm: what does moving the representative points towards the centroid do?

If I'm understanding your question correctly, you are interested in why the representative points are chosen as such, why they are merged and why this works. I'll first go over some background for ...
• 8,323
Accepted

### How to calculate the minimum number of groups, by grouping groups with capacity together?

The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem. If car A has a higher capacity than car B, and you get an optimal ...
• 31.2k

### What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)

In fact, MPI and PVM are very different. However, they have the same objective, that is achieving data/message exchange between processors, thus enabling distributed/parallel computation. MPI is the ...
Accepted

### what would be the time complexity of DBSCAN algorithm?

As the graph is sparse, if you have a data structure to query in $O(\log{n})$, you can reach to $O(n \log{n})$ for your case. More details in this link: DBSCAN visits each point of the database, ...
• 3,582

• 121
1 vote

### How to cluster images based on meta-information in tags

Yes, this has been studied, but the images seem to be completely irrelevant. What you have is a set of texts, and you want to cluster them based on similarities. You simply want to do text ...
• 16.7k

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