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.
33
questions with no upvoted or accepted answers
16
votes
0
answers
481
views
a geometric variant of k-medians. NP-hard or in P?
The following problem is a special case of k-medians. Is it NP-hard? Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set ...
- 9,595
6
votes
0
answers
235
views
Does k-Median problem become any easier when L = C?
In the $k$-median problem, $L$ defines as set of feasible facility locations and $C$ defines a set of client locations in a metric space.
The current best approximation guarantee for the problem is $2....
- 1,471
5
votes
0
answers
158
views
Exact algorithms for $k$-means
Lets recall the definition of $k$-means clustering for euclidean spaces.
Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $...
- 189
3
votes
0
answers
86
views
Exact FPT Algorithm for Continuous Euclidean $k$-Means
The continuous Euclidean $k$-means problem is defined as follows:
Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
- 1,471
3
votes
0
answers
153
views
Incorrect Lower Bound of k-Means++ Algorithm
The $k$-means++ algorithm is composed of two parts:
Initialization part: the initial $k$ centers are chosen based on $D^2$ sampling.
Expectation maximization part: the standard $k$-means algorithm (...
- 1,471
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
2
votes
0
answers
92
views
NP-hardness of Euclidean k-Median for k = 2
In the Euclidean $k$-median problem, we are given a set $C$ of clients in $\mathbb{R}^d$. The task is to open a set $F \subset \mathbb{R}^d$ of $k$ facilities such that the cost function $\Phi(F) = \...
- 1,471
2
votes
0
answers
40
views
Concept of 'shape' in clustering
Is there any abstract definition for 'shapes' of a cluster?
I am currently working on providing for a set of axioms to study clustering. In my work, I have found a need for an abstract definition for ...
- 61
2
votes
0
answers
154
views
Quality measure for clusters of a metric space embedding of a graph?
When evaluating clustering algorithms for networks, we have well-established metrics like Modularity and Surprise for evaluating the quality of the resulting partition.
If we then embed our graph (...
- 161
2
votes
0
answers
242
views
Grouping a set of rectangles in larger rectangular regions
I have a set of rectangles, which I want to cluster (group) as shown here(I can not post images yet, so please bear with me).
The approach I took was to consider central points of each rectangle as a ...
- 131
1
vote
1
answer
198
views
Graph partitioning to minimize sum of intra-partition edge weights
I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
- 11
1
vote
0
answers
52
views
Failing to understand a lemma regarding Robust Low Rank Approximation
I am reading Low Rank Approximation in the Presence of
Outliers by Bhaskara and Kumar and kind of stuck at the proof of Lemma 9. The paper studies robust (to outliers) low rank approximation problem. ...
- 265
1
vote
0
answers
47
views
A variant of k-median clustering
Suppose $\mathcal{P} =\{P_1,\cdots,P_n\}$ is a family of $n$ finite sets in $\mathbb{R}^d$. Given set $C=\{c_1,\cdots,c_k\}$ of $k$ points, consider the follwoing objective funtion
$cost(\mathcal{P},C)...
- 265
1
vote
0
answers
37
views
A continuum version of the 1D k-means clustering problem: constant factor approximations
Modify the k-means clustering problem in 1D by assuming that, instead of a finite number of observations, we must classify into $K$ clusters a continuum of observations, distributed on the unit ...
- 33
1
vote
0
answers
85
views
k-center 2.0: A stronger k-center condition
Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$.
Note that ...
- 607
1
vote
0
answers
112
views
algorithms for a large submatrix / general factor / quasi-biclique problem?
Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
- 145
1
vote
0
answers
55
views
Clustering algorithm for image metric
Im working on image clustering (finding duplicates). I have a metric for images, it uses histogram features (mean, dispersion, skewnewss) for each color channel. So there are 9 dimensions. It is quite ...
- 111
1
vote
0
answers
718
views
Splitting a graph into size constrained clusters
I ran across a problem while working on an algorithm for a game I'm making on the side. It's basically a clustering problem where we have a graph G and want to split it into clusters of equal size ...
- 11
1
vote
0
answers
536
views
Time complexity of clustering based on random walk
What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph?
Can I use the complexity of eigen vector computation for this purpose?
The ...
- 11
1
vote
0
answers
114
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
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: ...
0
votes
0
answers
68
views
k-Median Problem With Restricted Centers
The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...
- 1,471
0
votes
0
answers
106
views
How general cost function for $p = \log n$ is the $k$-center cost function?
The $k$-clustering problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...
- 1,471
0
votes
0
answers
45
views
What is the meaning of an Oracle in data clustering?
I am not sure whether this is the best place to ask this question. I am in the process of researching the area in data clustering as well as the algorithms that are associated with it and the term ...
- 11
0
votes
0
answers
33
views
Does optimal fitting flat must pass through the mean of the point set?
I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line.
Project clustering is a natural generalization of k-...
- 265
0
votes
0
answers
215
views
Clustering in sublinear time/query
Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy:
1) Minimizing the number of balls that are required to cover all ...
- 639
0
votes
0
answers
346
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
301
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
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
-1
votes
1
answer
82
views
Al-Mubaid's Similarity Measure for Ontological Concepts
Al-Mubaid et al. proposed a semantic similarity measure in their research paper [1]. They see ontologies as connected graphs but refer to clusters within ontology graphs without ever defining what ...
- 11
-1
votes
1
answer
2k
views
Time complexity analysis of random forest and k-means?
I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where
$n$ is the number of points,
$K$ is ...
-1
votes
1
answer
198
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
-1
votes
1
answer
444
views
Canopy clustering: what should we do with samples in overlapping canopies?
In canopy clustering http://www.kamalnigam.com/papers/canopy-kdd00.pdf, if a sample falls in an overlap of 2 canopies, how do we choose its cluster?
- 197