Questions tagged [clustering]

Clustering is grouping (partitioning) a set of objects so that items in the same group are more similar to each other than to items in different groups, where the notion of similarity may be variously defined.

Filter by
Sorted by
Tagged with
0 votes
0 answers
9 views

Clustering of directed graphs satisfying priority constraints

I recently ran into a problem related to directed graph clustering, but don't know how to solve it. There is a directed acyclic graph $G = (V,E)$, where $V$ is the set of vertices, and $E$ is the set ...
user avatar
  • 431
0 votes
0 answers
20 views

Understanding academic paper methodology (clustering trajectories with Bezier curves)

I'm currently doing my Master's dissertation project using football (soccer) tracking data, and am looking to cluster player run paths of various lengths in Python. I have found a relevant paper ...
user avatar
  • 1
0 votes
1 answer
36 views

Get Maximum value of a cluster as a constraint in a MILP

I am facing the following problem: I have same kind of a clustering Problem \begin{alignat}{4} \text{min }\quad& \sum_{c \in C} \sum_{s \in S} - y_{c,s}\\[2ex] \text{s.t. }\quad& \sum_{c \in ...
user avatar
  • 3
3 votes
1 answer
52 views

Why does spectral clustering work?

Relevant Background I've recently learnt about the spectral clustering algorithm and had a hard time understanding why we do what we do. Trying to undetstand, I stumbled upon this great post, that ...
user avatar
0 votes
0 answers
39 views

Find in which face lie a point on a hyper polytope, inscribed in an hyper unit-sphere (and how to generate this hyper polytope)

I am working on clustering normalized point in a k dimension space. At first i used Spherical LSH strategy where i used random planes to cut the hyper-sphere but it induces a lot of random (because i ...
user avatar
0 votes
0 answers
16 views

Clustering when data is represented by multiple functional forms, all at once.

I wish to cluster similar data where I have a collection of many $y$ vs $x$ data. A third variable $z$ also exists, but z doesn't always affect $y$ whereas $x$ always affects $z$. In terms of $x$ and $...
user avatar
0 votes
0 answers
3 views

High dimensional behavior of Dirichlet Process-based clustering?

I have a problem stemming from Dirichlet Process Gaussian Mixture Models (DP-GMMs) in high dimension. I'll write this question so that no knowledge of DP-GMMs is needed. Let $D$ be the dimensionality ...
user avatar
2 votes
0 answers
24 views

How to learn data points by minimizing a loss function given their pairwise distance matrix?

Suppose $x_i \in\mathbb{R}^2$ for $i=1,2,...9$ are unknown. I'm given the pair-wise distance matrix between these points $D$ which is a $9*9$ symmetric matrix. I want to learn these data points by ...
user avatar
  • 2,265
0 votes
0 answers
9 views

How can I select K value of K-means from eigengap?

I have studied perturbation theory and spectral graph theory to calculate the optimal number of clusters .Eigengap heuristic suggests the number of clusters k is usually given by the value of k that ...
user avatar
  • 333
0 votes
0 answers
31 views

Maximum distance based clustering in metric spaces

I want to cluster a set of points $S$ in a general metric space with metric $d$, so that all points in a cluster can be connected by a path where the distance between two points is at most $D$. This ...
user avatar
2 votes
1 answer
78 views

what are the benefits of using Spectral K-means over Simple K-means ? and how Spectral K-means overcomes the local minimum problem of K-means?

I have understood why K-means get stuck in local minima Now I am curious to know how spectral k-means helps to avoid this local minima problem? According to this paper A tutorial on Spectral, ...
user avatar
  • 333
0 votes
1 answer
122 views

How to prove that the residual sum of squares is a non-convex Function?

The $K$-means algorithm uses a residual sum of squares (RSS) where $$ \mbox{RSS}_{K} = \sum_{d \in s}|{d-c(s)}|^2 $$ $\mbox{RSS} = \sum_{k= 1}^K \mbox{RSS}_{K}$ is the convergence criterion. $\mbox{...
user avatar
  • 333
0 votes
0 answers
5 views

Grouping/Clustering surface mesh triangles by function values

I have the following problem. I have triangular surface meshs of three dimensional bodies. For each triangle exists an associated function value. This value varies over the whole mesh, but there are ...
user avatar
1 vote
1 answer
42 views

Calculating Mahalanobis distance

I am slightly confused as to how you calculate Mahalanobis distance given a set of data. I have tried asking my tutor for help but he does not seem interested in helping what so ever and I am ...
user avatar
  • 147
0 votes
0 answers
16 views

Selecting N evenly spaced nodes in the plane

Given a set of nodes $P$, making up a completely disconnected graph, I am looking for a method of selecting $N$ of them such that the graph can be partitioned into approximately equally sized clusters ...
user avatar
0 votes
0 answers
26 views

Sampling vertices from a graph to maximize the spread

Given a graph with N vertices, I want to sample K of them such that I have the maximum possible spread. A possible application of this is to build shelters in a road network so that they cover the ...
user avatar
0 votes
0 answers
15 views

How RatioCut leads to unnormalized spectral clustering?

I have understood the underlying concepts of spectral clustering and how inter cluster distance equation is mapped to a matrix form and how it is optimized using lagrange multiplier. But unable to ...
user avatar
  • 333
0 votes
0 answers
35 views

Best order to allocate services in graph using custom comparator

Good day! I have a lot of graphs with different properties: structure, number of nodes & edges, etc. All of them are undirected, "weighted" (edges have width, in other words capacity). ...
user avatar
0 votes
0 answers
47 views

Colorblind test -- finding and classifying lines in 3-D space

I am creating a color blind test that uses RGB colors. RGB ranges [0-255] in all three colors to determine the final color. I would like to test the user to find which colors they struggle with. For ...
user avatar
  • 1
0 votes
0 answers
8 views

Clustering Similarity Measurement Based on Mutual Information

I have a question when learning the measures based on mutual information to the similarity between two clusterings. See this paper. Say the labels can be permuted. For example, "both a and b ...
user avatar
  • 1,526
0 votes
0 answers
18 views

Approximate maximization of a function

I am trying to find $s$ and $\eta=(\eta_0,\eta_1)$, that maximizes the following function. $$\max_{s,\eta} <x, \eta(s)>-n_0(s)log(1+e^{\eta_0})-n_1(s)log(1+e^{\eta_1})$$ where $x$ is a vector ...
user avatar
0 votes
0 answers
37 views

How to mathematically formulate this clustering optimization problem?

I need to perform clustering of two different entities (as seen in the attached image, red square and blue balls are two different entities) under the following constraints Lets say, red square: ...
user avatar
2 votes
0 answers
72 views

How to prove that trangle inequality is satisfied in Hausdorff distance

I'm working on a problem my teacher asked me to check if I was interested, which is 'how to prove that Hausdorff Distance is strictly a distance function'. More specifically, how to prove that $$D_H(A,...
user avatar
  • 29
0 votes
0 answers
17 views

Relation between two cost functions

I'm having a problem with an issue. Is the following statement true? If it is true, why? Be $X$ a set in $\mathbb{R}^m$. Given two clusterizations of it, ie, $C=\{C_1,...,C_k\}$ which each subset ...
user avatar
1 vote
0 answers
14 views

Cover all 2D points given a 2D template with minimum distance between them

I am looking for an algorithm that gets a binary image similar to the below image and given a circle(as a template) with radius R, returns the location of instances of this circle needed to cover all ...
user avatar
  • 177
1 vote
1 answer
14 views

intra cluster sampling

Apologize for the longish context setting but we are working on a recommender system which needs to let users know which erroneous files need attention. These erroneous files have been generated via ...
user avatar
0 votes
1 answer
35 views

Generalization of Marchenko-Pastur law to nonzero mean random matrices with unknown variance

I have an application where rectangular, $m \times n$ matrices appear, where every row represents a data point with noise in all of its components, except for some components which are part of a "...
user avatar
  • 325
0 votes
0 answers
18 views

How to design a clustering metric or cluster algorithm to seperate tow intersected circles?

In some classical books about pattern recognition, the clustering algorithm reveals the similarity among samples, while not considering the "global pattern" of grouped samples. So, I think ...
user avatar
  • 271
2 votes
1 answer
17 views

Sampling from a particular region of a Voronoi diagram

We are given a finite set of points $\{p_1, ..., p_n\}$ in $\mathbb{R}^d$ which induce a Voronoi partitioning of the space into $n$ regions under, say, Euclidean metric. What is an efficient way of ...
user avatar
  • 2,390
0 votes
1 answer
53 views

Clustering data using mixed integer linear programming

I am trying to understand if it is possible to use mixed integer linear programming (MILP) in order to perform a basic clustering operation to a dataset $D$. I know there exists standard algorithms ...
user avatar
  • 2,119
1 vote
0 answers
46 views

Spectral partitioning and Fiedler Vector

As we know, the Fiedler vector is the eigenvector corresponding to the second smallest eigenvalue and this vector can be used for graph partitioning. We also know that this vector comes from a relaxed ...
user avatar
  • 43
2 votes
0 answers
44 views

Can clustering be implemented as Linear Programming?

When considering Gaussian mixture models (GMM) one efficient algorithm is the Expectation-Minimization (EM) algorithm. The E-step famously determines the degree of membership. For example, given a GMM ...
user avatar
  • 2,119
0 votes
0 answers
13 views

K-Means-Algorithm: After 4 consecutive Iterations a Cluster has assumed three different sets

I am currently reading an analysis for the $k$-means algorithm. It states as a side note following lemma without a proof: Assume we are given four consecutive Iterations of the $k$-means algorithm. ...
user avatar
  • 155
0 votes
0 answers
24 views

Partition With Ranking to Solve A Clustering Problem

I have r restaurants and f friend where no of f >> no of r. Basically this is a clustering problem. I want to find the nature of clusters(i.e which restaurant consists how much no of friends) ...
user avatar
  • 333
2 votes
0 answers
92 views

Is this implementation use HBOS mathematic?

I'm experimenting with an unsupervised statistical-based outlier detection so-called XBOS on top of the KMeans clustering algorithm. It is claimed that XBOS generates outlier scores as HBOS does. I'm ...
user avatar
  • 73
0 votes
0 answers
53 views

Matching the labels of a clustering with ground truth labels for performance analysis

I'm working on clustering a dataset for which I have ground-truth labels. I want to evaluate the confusion matrix between the predicted and ground truth labels, but the labels assigned by my ...
user avatar
  • 61
0 votes
0 answers
21 views

Clustering with Matrix norm

Hello I am trying to learn some numerical linear algebra and I need some help. my problem: we have $225$ freshmen students in $15$ groups of $15$ students in each. for each student $3$-vector is ...
user avatar
  • 383
1 vote
0 answers
36 views

Error rate in comparing clusterings or partitions

Given $n,k \in \mathbb{N}, \ k < n$, we assume that there is an optimal partition $P$ of $n$ elements into $k$ bins. Given a random partition $Q$, what is the expectation value $E(r)$ of $r$, the ...
user avatar
  • 61
0 votes
0 answers
20 views

How to solve the following clustering problem with special constraints and imperfect information?

Given a set of nodes $[v_1, v_2, ... v_n]$ in order, I want to do a clustering task that assign all the nodes into a variable number of groups. I tried to do this by finding the parent node for each ...
user avatar
  • 1
0 votes
0 answers
52 views

Measuring cluster-ness in graph by operation on the adhjacency matrix

We have a weighted graph G=(V,E). Each vertex represents a d dimensional node embedding. the feature matrix $H\in \mathbb{R}^{|V|...
user avatar
  • 153
0 votes
0 answers
16 views

One-sided clustering in 3D space

Suppose we have some 3D observations of the form $a_i = {x_i, y_i, z_i}$ where all coordinates are non-negative. Is there then a way to cluster them according to the "outermost" point of a ...
user avatar
  • 1
0 votes
0 answers
20 views

how to calculate the variance between some observations when each observation is an n*m matrix

I have a cluster of 250 observations. each observation is a 4 by 9 matrix. 4 is number of variable parameters observed and 9 is number of days, observations were collected. I want to know the ...
user avatar
  • 15
1 vote
0 answers
18 views

Expectation Maximization : Show that the E step is the folowing

Given that $X_1,X_2 \dots X_n$ random variables distributed $exp(\theta)$. let $T>0$ constant , and we define instead of $X_i$ , $(Z_i,\delta_i)$ such as : $$Z_i = min\{Z_i,T\}$$ $$\delta_i = \...
user avatar
  • 119
0 votes
0 answers
31 views

Maximize colors within a circle

I have a set of $m$ points $P$ over a large bidimensional space, each point having a color. Every color belongs to one of $n$ disjunct sets $S_i$ of colors. Given a circle $c$ we define $C_c$ as the ...
user avatar
0 votes
0 answers
20 views

Indexing The Nodes of a Dendrogram

Suppose I have a dataset $\{x_i\}_{i=1}^n$ that I have implemented some hierarchical clustering algorithm (e.g., Single-Linkage Clustering) on. This gives me a dendrogram, which we can use to ...
user avatar
  • 61
0 votes
0 answers
18 views

Is vector quantization belonging to the extention of K-means clustering

In unsupervised learning, vector quantization belongs to the extension of K-means clustering? since K-means tries to develop clusters with corresponding chose optimized centers to represent and find ...
user avatar
1 vote
0 answers
41 views

Normalize an adjacency matrix twice

I am working on a graph clustering problem and i've seen that applying two consecutive normalizations on the adjacency matrix gives much better performance than when applying a single one. I first ...
user avatar
  • 55
0 votes
0 answers
35 views

A "straightfoward" statement about eigenvalues

I'm reading a paper about clustering techniques and I found the following easy construction Let $S = \{s_1,\dots , s_n\}$ be a ser of $n$ points where each $s_i \in \mathbb{R}^2$. Suppose that $S = ...
user avatar
  • 501
1 vote
0 answers
17 views

label a set of data points

I have a set of data points in a 3-dimensional space. Points are approximately in two rows, like this (with 3 in secondary row and 7 in primary row): I need to label both rows separately. For example,...
user avatar
  • 153
0 votes
0 answers
41 views

Am I interpreting this notation correctly?

I'm trying to parse a paper about a new (to me) clustering algorithm into code, and I want to make sure I understand the math correctly... but the notation is holding me up. From page 3 , equation 2: $...
user avatar

1
2 3 4 5
7