Skip to main content

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
Filter by
Sorted by
Tagged with
16 votes
0 answers
501 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 ...
Neal Young's user avatar
  • 10.8k
6 votes
0 answers
246 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....
Inuyasha Yagami's user avatar
5 votes
0 answers
161 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 $...
Andrea's user avatar
  • 319
4 votes
0 answers
123 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 ...
aaronsteven's user avatar
3 votes
0 answers
89 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$ ...
Inuyasha Yagami's user avatar
3 votes
0 answers
167 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 (...
Inuyasha Yagami's user avatar
2 votes
0 answers
107 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) = \...
Inuyasha Yagami's user avatar
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 ...
user3660112's user avatar
2 votes
0 answers
155 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 (...
donnyton's user avatar
  • 161
2 votes
0 answers
244 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 ...
rivu's user avatar
  • 131
1 vote
0 answers
284 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 ...
axizzt's user avatar
  • 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. ...
Sudipta Roy's user avatar
1 vote
0 answers
49 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)...
Sudipta Roy's user avatar
1 vote
0 answers
40 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 ...
Romans Pancs's user avatar
1 vote
0 answers
86 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 ...
Karagounis Z's user avatar
1 vote
0 answers
113 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 ...
DavidDLewis's user avatar
1 vote
0 answers
56 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 ...
kelin's user avatar
  • 111
1 vote
0 answers
767 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 ...
CCguy's user avatar
  • 11
1 vote
0 answers
538 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 ...
Fatime's user avatar
  • 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 ...
Newtang's user avatar
  • 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
75 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 ...
Inuyasha Yagami's user avatar
0 votes
0 answers
113 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 ...
Inuyasha Yagami's user avatar
0 votes
0 answers
46 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 ...
Matt.W's user avatar
  • 11
0 votes
0 answers
35 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-...
Sudipta Roy's user avatar
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 ...
Ram's user avatar
  • 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 ...
Maggie's user avatar
  • 181
0 votes
0 answers
305 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://...
Mariya's user avatar
  • 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 ...
Stattrav's user avatar
  • 523
-1 votes
1 answer
84 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 ...
AzLimbiate's user avatar
-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 ...
Eric Nunes's user avatar
-1 votes
1 answer
201 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 ...
Olumide's user avatar
  • 107
-1 votes
1 answer
445 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?
ihadanny's user avatar
  • 197