As of May 31, 2023, we have updated our Code of Conduct.

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.

Filter by
Sorted by
Tagged with
7 votes
1 answer

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-...
Steven's user avatar
  • 261
-1 votes
1 answer

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 ...
Olumide's user avatar
  • 107
3 votes
0 answers

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 ...
aaronsteven's user avatar
1 vote
0 answers

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 ...
Duc Trung's user avatar
1 vote
0 answers

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 ...
Newtang's user avatar
  • 111
1 vote
1 answer

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 ...
donnyton's user avatar
  • 161
0 votes
0 answers

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 ...
Maggie's user avatar
  • 181
0 votes
0 answers

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://...
Mariya's user avatar
  • 101
5 votes
1 answer

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 ...
Kostia Antoniuk's user avatar
0 votes
1 answer

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 ...
Denis's user avatar
  • 325
4 votes
1 answer

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 ...
Amelio Vazquez-Reina's user avatar
1 vote
1 answer

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 ...
Eric Pruitt's user avatar
1 vote
1 answer

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 ...
pajton's user avatar
  • 111
0 votes
0 answers

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 ...
Stattrav's user avatar
  • 523
0 votes
3 answers

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 ...
rubenfonseca's user avatar
12 votes
2 answers

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 ...
Milos Hasan's user avatar
9 votes
2 answers

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 ...
Lan's user avatar
  • 251
2 votes
1 answer

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 ...
user avatar
11 votes
2 answers

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 ...
Aleksandr Levchuk's user avatar
12 votes
5 answers

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 ...
paintcan's user avatar
  • 223
1 vote
0 answers

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

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