Questions tagged [clustering]
Clustering is an unsupervised learning problem. It deals with finding "clusters" or groups in a collection of unlabeled data. A cluster is therefore a collection of objects which are “similar” and are “dissimilar” to the objects belonging to other clusters.
72
questions
7
votes
1
answer
990
views
K-Clustering of a Graph maximizing intra-cluster weights?
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.
Input: A complete graph G with non-...
- 261
-1
votes
1
answer
197
views
Clustering without specifying the number of clusters apriori
Does anyone know of an algorithm that can perform the following tasks:
Unsupervised clustering without specifying the number of clusters apriori. For example if all the buildings in wide geographical ...
- 107
3
votes
0
answers
122
views
Finding most informative feature subsets given dataset, clustering algorithm and gold standard partition
I have an $n \times m$ matrix of data $\mathbf{D}$ as well as a $k$-partition $P$ of $n$ indices each representing a row in a dataset. Assuming an arbitrary clustering algorithm $A$, I would like to ...
- 61
1
vote
0
answers
130
views
Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D [closed]
I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
- 11
1
vote
0
answers
113
views
Techniques to get nodes in the best Markov Cluster?
I was using Markov Clustering to cluster nodes in my bidirectional graph, and overall the results were great. However, there were a couple instances where a weakly connected node would attract a node ...
- 111
1
vote
1
answer
893
views
Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?
An elaboration on this question, but with more constraints.
The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions. The bucketing grid seems to work ...
- 161
0
votes
0
answers
345
views
Divide-and-conquer approach for hierarchical clustering
I have a huge data set (33K), each represented as a bit-vector of 275-dimensions. Basically my data set can be represented as a $33000 \times 275$ matrix. I want to cluster these bit-vectors. I have ...
- 181
0
votes
0
answers
300
views
Fuzzy K-modes clustering how to find the cluster centers
I'm trying to understand [fuzzy k-modes][1] algorithm (look mainly at page 3) in order to implement it.
I'm stuck at the calculation of cluster centers they said as shown in the link
https://...
- 101
5
votes
1
answer
339
views
k-clustering problems
I'm interested in open questions from the book Approximation Algorithms for NP-Hard Problemss dedicated to k-clustering. They are:
Is Euclidean max cut solvable in polynomial time? If not, how well ...
0
votes
1
answer
214
views
K-means with centres outside the data?
Say we want to split a cube in $\mathbb{R}^{64}$ into 10 pieces.
NN, nearest-neighbor or Voronoi splits,
take 10 cluster centres $c_0, \ldots, c_9$ in the cube,
e.g. from K-means,
then classify a new ...
- 325
4
votes
1
answer
263
views
Higher-order and black-box clustering
As far as I understand a large number of clustering problems can be formulated as:
$\underset{\textbf{P}}{ \text{argmin}} \; \sum_{i,j} f \left(x_i, x_j\right)$
where $\textbf{P}$ is a partitioning ...
1
vote
1
answer
120
views
Scoring set of points based on clustering
I have a sparse set of points with unpredictable locations. I need a way of "scoring" each set of points such that clustering is rewarded. My working case is actually one dimensional, but a two ...
- 119
1
vote
1
answer
624
views
Clustering of letters - what approach would give the best results?
I am working on letter recognition program. I have a text and divide it into letters, every single letter is written to separate file.
Now I want to apply a clustering algorithm to these images to ...
- 111
0
votes
0
answers
149
views
A better way to cluster items
I am working on a text processer which gives out similarities between a set of strings. After weighted LCS, Levenshtein distance and double metaphone matching, I get buckets of strings such as
...
- 523
0
votes
3
answers
199
views
clustering (lat,lng) pairs, with clusters having the same number of elements
Imagine you have a list of (lat,lng) pairs. You have k employees. And you want each employee to visit roughly the same number of places, making the least distance possible.
I've tried to solve this ...
- 103
12
votes
2
answers
504
views
Euclidean-squared max-cut in low dimensions
Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that ...
- 121
9
votes
2
answers
5k
views
Computational complexity of clustering algorithms
My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space.
Suppose further that the pairwise dissimilarity ...
- 251
2
votes
1
answer
529
views
K-NN or matrix factorization for discovering correlated features?
I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature. "Similar" users should be clustered together ...
DanB
11
votes
2
answers
354
views
Clustering formalizations other than K-means for separable data
Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended ...
12
votes
5
answers
570
views
clustering algorithm for non-dimensional data
i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this ...
- 223
1
vote
0
answers
2k
views
DAG partitioning to subgraphs
Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes.
(Note: ...
9
votes
4
answers
456
views
Continuous Clustering
So I have an issue I'm facing in regards to clustering with live, continuously streaming data. Since I have an ever-growing data set I'm not sure what is the best way to run efficient and effective ...
brian