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.

learn more… | top users | synonyms

0
votes
1answer
7 views

Explanation of Information double summation within Normalized Mutual Information

The Normalized Mutual Information NMI calculation is described in deflation-PIC paper with the applicable formula copied to the screenshot shown below. My question is specifically about the double ...
0
votes
0answers
4 views

Meaning of coherence measure $\frac{n}{s}\max_{1 \le i \le n}\sum_{j=1}^n U_{ij}^2$

In the paper Extracting Certainty from Uncertainty: Transductive Pairwise Classification from Pairwise Similarities, the authors use a coherence measure defined as $$ \mu_s=\frac{n}{s}\max_{1 \le i ...
0
votes
0answers
29 views

Find the radius of a cluster, given that its center is the average of the centers of two other clusters

I do not know if it is possible to find it, but I am using Kmeans clustering with Mahout, and I am stuck to the following. In my implementation, I create with two different threads the following ...
-2
votes
3answers
41 views

Is every point in $\mathbb R$ a cluster point of $\mathbb R$? [closed]

Could someone please tell me if all of the points in $\mathbb R$ are cluster points for $\mathbb R$ or not?
-1
votes
1answer
37 views

What is the meaning of |⋯| notation for an index subset?

I am currently working on a research project. In the attached image what does the capital $|I|$ and $|J|$ mean ?
1
vote
1answer
24 views

What is the definition of “convex” and “relaxation” concepts in clustering?

I have following text from a paper i am trying to understand: I don't understand what does below sentence refers to as being convex/non-convex The problem is that even though the objectives ...
0
votes
1answer
21 views

Measure for presence of several poorly interconnected components in undirected graph

Is there a measure to classify networks regarding whether or not they are composed of several (internally closely connected) groups which are poorly connected (i.e. few links between groups). That ...
0
votes
0answers
53 views

Proving symmetry of metric (single linkage between clusters using arbitrary dissimilarity measure)

I am told to assume that our dissimilarity measure $d$ satisfies the properties required of it, what seems to be the definition of a metric: $d(x,y) \geq0 $ and $d(x,y)=0 \Longleftrightarrow x=y$ ...
1
vote
0answers
58 views

Calculating Euclidean dissimilarity for a given cluster with itself

Suppose I have clusters $$A= \{(1,1)^T, (1,2)^T\} $$ $$B=\{(2,3)^T, (3,4)^T\} $$ $$C= \{(4,5)^T, (5,6)^T, (1,2)^T\} $$ I wish to use the Euclidean dissimilarity and Average linkage to calculate a ...
0
votes
1answer
49 views

Is k-means clustering guaranteed to converge if using Manhattan distance?

The k-means algorithm is an iterative clustering algorithm that partitions the data points into K clusters (with centroids {$\mu_1, ... , \mu_k$}, minimizing the Sum-of-Squared-Error: $$ SSE = ...
0
votes
0answers
7 views

How the quality of clusters made in SPSS can be evaluated?

How the quality of clusters made in SPSS with the method "Two-step clustering" can be evaluated? Which test should be applied to be sure that the quality is good.
0
votes
1answer
21 views

finding clusters in a network from eigengaps

I have a usual Laplacian matrix, which describes a network. From the matrix I get the eigenvalues and from these I can compute a metric of modularity in my network based on the largest eigengap. Let's ...
4
votes
1answer
48 views

Measure of the clusters quality in a graph

Suppose we have a graph $G=(V,E)$ with $n$ non-overlapping subgraphs, the clusters $C_1, C_2, \dots, C_n$ which covers the graph $C_1 \cup \dots \cup C_n = G$. I'm looking for a good metric to ...
1
vote
0answers
17 views

UPGMA: Distance between clusters for multi-dimensional data

How would you calculate the distance for multi-dimensional data? From wikipedia: ...
2
votes
0answers
22 views

probability of clusters for iid points

Consider that $X_1^{(n)},...,X_n^{(n)}$ are iid uniform random variables on $[0,n]$. For $T >0$, let $N_n(T) = \sup_{t \in [0,n]} \# \{ i: |X_i^{(n)} - t| \leq T \}$ be the maximum number of points ...
2
votes
1answer
24 views

Identifying the k points in 2D geographic space which are 'most distant' from each other

I have a set of DNA samples from Y plants in a given geographic area. I'm going to be doing DNA sequencing on individuals in this population (and a number of other, separate populations), however due ...
3
votes
0answers
25 views

Looking for an algo to “sorta” diagonalize a similarity matrix.

I've got a big fat similarity matrix. The rows and columns represent people, and the values represent some positive measure of their closeness (0 meaning no connection at all). The n-th row and n-th ...
0
votes
0answers
11 views

Reinforcement Clustering algorithm

I am trying to implement Reinforcement Clustering algorithm for one of my homework assignments for clustering documents. I have implemented K-means algorithm that will be used as one of the building ...
0
votes
0answers
29 views

Clustering Coefficient of A Transitive Graph/Network

Whats the difference of a transitive network's clustering coefficient and a non-transitive networks coefficient? more precisely is the clustering coefficient of a transitive network is as high as ...
0
votes
1answer
49 views

Are minimum cut communities maximal?

I am looking at the paper Graph Clustering and Minimum Cut Trees by Flake et al. Let $G(V, E)$ be some undirected weighted graph. Definition. Let $s, t\in V$ be given. Let $(S, T)$ be the minimum ...
1
vote
1answer
22 views

Cluster points so that within each cluster holds a certain maximum distance between points

Currently I'm struggling with a (for me) new field, namely clustering. I would really appreciate any help I could get! The starting situation is that a data set $(x_k)_{k\in\{1,\dots,n\}} \subseteq ...
2
votes
0answers
18 views

Sampling with an “oversampling” factor, in K-Means||

I'm trying to understand K-Means||, a scalable version of K-Means++, which itself is an "improved" version of the clustering algorithm K-Means. Please find here the link to K-Means|| paper ...
1
vote
2answers
50 views

Finding similarity between elements using statistics

I have a dataset of DJs in which I'm trying to find DJs similar to a specific DJ. Each DJ has a set of a genres with a certain percentage. How can I find the similarity between 2 DJs? The following is ...
1
vote
1answer
59 views

Clustering analysis of a weighted graph

My data consists of a large weighted undirected graph of $n$ nodes. I need to group the nodes into $m$ clusters ($m < n$), such that nodes in a cluster are connected with heavy weights. What ...
0
votes
0answers
57 views

Percolation Theory Basics: Open cluster size decay (Square Lattice)

I am trying to learn some stuff about percolation. On wiki (http://en.wikipedia.org/wiki/Percolation_theory) it says: "when $p<p_{c}$, the probability that a specific point (for example, the ...
1
vote
0answers
85 views

Triangulation of clusters of points

I am trying to solve a triangulation problem, but I am not really sure what is the best way to tackle it. I have a series of points $P$ in an $n$-dimensional space. These points are clustered in $k$ ...
1
vote
0answers
28 views

Machine learning algorithm for relative similarity

I'm trying to find a good starting place (or existing algorithm) to determine the similarity of various items to one another based on subjective assessments of two items' relative similarity to a ...
0
votes
1answer
58 views

In Cluster Analysis, how do we calculate Purity?

In cluster analysis how do we calculate purity? What's the equation? I'm not looking for a code to do it for me. Let $\omega_k$ be cluster k, and $c_j$ be class j. So is purity practically ...
0
votes
0answers
20 views

Which cut-off for collapsing this tree?

I have a Newick tree that is built by comparing similarity (euclidean distance) of Position Weight Matrices (PWMs or PSSMs) of DNA regulatory motifs that are ~5-9 bp long sequences. An interactive ...
0
votes
0answers
26 views

mean number of links in adjacency matrix

I have converted from an individual-level adjacency matrix to one for clusters and I am trying to show mathematically how I programmed up determining the mean number of inter-cluster links. I am not ...
2
votes
0answers
24 views

voronoi graph generated by $k$-means clustering

assume I correctly find the optimal centroids $c_i$ in the kmeans clustering problem, which finds $k$ centroids that minimizes: $$ \min \sum_i \sum_{x_j\in C_i } \|x_j - \mu_i\|^2 $$where $\mu_i, \ ...
0
votes
0answers
11 views

compare different quantization methods on a line.

assuming we have $n$ points ${x_1,x_2,...,x_n }$ uniformly distributed (or any other distribution that's convenient, or even distribution-free) over an interval $[a,b]$. Now I quantize the interval ...
0
votes
0answers
16 views

Graph partitioning with constraints

Consider having $n$ data points ${{x}_{1}},..,{{x}_{N}}\in {{R}^{D}}$. Given an affinity matrix of the data, $W=[{{w}_{ij}}]$ where ${{w}_{ij}}$ is the affinity measure for data points ${{x}_{i}}$ and ...
0
votes
0answers
53 views

Need explanation for clustering coefficient formula

I need some explanation for clustering coefficient formula itsef firstly and why it can be used for detecting communities in a social network! Also I would like to know why it is not a good method for ...
1
vote
1answer
87 views

Normalized Mutual Information results in log(0) with non-overlapping clusters - how to deal with that?

I want to evaluate how well my flat soft clustering method works, compared to a gold standard. After some research I found that Normalized Mutual Information would most likely be a good measure, for ...
0
votes
0answers
79 views

K-means convergence to local maxima

I study K-means clustering algorithm. It's known that K-means algorithm converges to the local maximum, the problem is I cannot come up with the examples that shows this. If you know the simple ...
6
votes
0answers
574 views

Optimization / personalization within clusters

I have the following optimization problem: I have a (random and very noisy) objective function f(A, P), where A is a vector of "observable" parameters of the input and P is the parameters that I can ...
0
votes
1answer
137 views

how do I compute the eigenvectors for spectral clustering from a singular value decomposition?

I am implementing spectral clustering following A tutorial on spectral clustering. After preparing the Laplacian matrix $L^{n \times n}$, I compute the Singular Value Decomposition $U \Sigma V^{*}$. ...
11
votes
0answers
120 views

Size of connected regions on a randomly-colored infinite chessboard

Consider an infinite chessboard where each square is colored white with probability $p$ and black with probability $1-p$. Suppose without loss of generality that the square at $(0,0)$ is white. We ...
0
votes
1answer
36 views

Ensemble of Classifiers Method (Bagging)

I am reading a book about classification systems. They tell me that Bagging is a technique where "we perform sampling with replacement, building the classifier on each bootstrap sample. Each sample ...
0
votes
0answers
75 views

How to find “approximate most common” value from a list of RGB values

I have about 50 equally sized photos of magazine covers, which I'm attempting to blend into one composite image that shows the "average" cover. Each of the covers has a single face on it, so the ...
0
votes
1answer
262 views

Uncountable subset of $\mathbb{R}$ clusters at some point of $\mathbb{R}$ [duplicate]

It seems very intuitive and simple, but how would I go about proving something like this? Thanks.
1
vote
1answer
92 views

cluster validation and determining number of clusters

I want to find number of cluster in the real world data set. So, I validate the spectral clustering by using some indexes as shown in figures below? But as you seen in figures the results are very ...
3
votes
1answer
66 views

Unsupervised clustering in $10$ dimensions

I have a set of $\sim1000$ feature vectors in $\sim10$ dimensions and would like to cluster them in an unsupervised manner. I am expecting some of the vectors to bunch together in groups, but quite a ...
0
votes
1answer
175 views

Clusteranalyse bei Zeitreihen / Cluster analysis of time series

ich habe eine Frage zur Anwendung der Clusteranalyse bei Zeitreihen. Ich kenne mich grundsätzlich mit statischer Clusteranalyse aus. Jedoch soll ich eine grössere Anzahl von Firmen ($n=3000$) anhand ...
2
votes
1answer
51 views

Optimize database indexes, the sequel

Background For those not familiar with databases. Indices help to speed up database searches, but they come at the cost of memory. Since you like your database to be fast, they are best cached in RAM ...
0
votes
2answers
48 views

Optimize database indexes

Q: I have 14 columns, how many indexes do i need to create to cover all possibilities? Examples of possibilities: col1 col12 col5, col3, col4 col7, col2, col12, col1 all 14 columns -- Order can ...
2
votes
1answer
508 views

Mutual Information for clustering

I'm working on a document clustering application and decided to use Normalized Mutual Information as one of the measures of effectivenes. But I don't really understand how to implement this in that ...
4
votes
1answer
51 views

How can I geometrically (or geographically) group items together?

I'm a programmer, and I'm working on a project that takes a bunch of photos and separates them into groups by their gps coordinates. I have no experience in things like geometric group theory so I'm ...
2
votes
1answer
147 views

How would you quantify the closeness between sets.

How would you represent the closeness (distance?) between sets? For example: how close are the sets: {8,4,5} and {9,8,2}? Could it be a percentage? If there is no way to do this, would you need two ...