# Tag Info

6

The answer depends on your K-means algorithm, but what follows should work for standard algorithms. You will get the same result if your transformation $T$ satisfies two conditions: It preserves distances: $d(z,w) = d(T(z),T(w))$, where $d$ is your metric, say $d(z,w) = \|z-w\|$. It preserves averages: if $\sum_i p_i z_i$ is a convex combination that $T(\... 5 You can run a loop over$j\in\{1..k\}$: Create a map that maps each point$x_i$to itself if$x_i$is nearest to the mean$m_j$, and to the zero vector otherwise: $$x_i \rightarrow \begin{cases}(x_i, 1) & d(x_i, m_j) \le d(x_i, m_l),\ l\neq j \\ (0,0) & \text{otherwise} \end{cases}$$ In the reduce stage, you would find the sums and counts:$$(x_{i1}... 4 Store the centers of the rectangles in a data structure that supports efficient nearest-neighbor queries, such as a quadtree. Now for each rectangle$R$, you can determine whether there exist any other rectangles within the prescribed distance, and if so, list them all. Then you can merge all such rectangles into the same group by using a union-find data ... 4 The first event at time$t_0$needs to be in a bucket. We can safely choose the bucket$[t_0, t_0+30]$, as there is nothing to gain by making it start earlier. We then move on to the next event starting at$t>t_0+30$(earlier events fall into the bucket we chose). We once again choose the latest bucket containing that event. It is not hard to prove that ... 3 Several algorithms allow doing this. First one is the hierarchical clustering. When creating your dendrogram, the key is to cut the "longest branches." DBSCAN is also a good alternative. Finally, you can use K-means or GMM and optimize your number of cluster against a metrics (see sklearn pages on the subject) (be aware of overfitting) 3 Your proof makes no sense to me. I don't know what you mean by "each center is assigned to one of my centers". When writing a proof, you need to define all terms before first use, and use rigorous logic, where each step is logically implied by the prior step. You can't just write down some intuition that feels right; that's not a proof. The claim is ... 3 The length of each string is at least 200, and you only consider two strings similar if their edit distance is less than 20. So if$S,T$are similar, then there must exist$U$such that (1)$U$is a substring of$S$, (2)$U$is a substring of$T$, and (3) the length of$U$is at least 10. This suggests that one heuristic is to find all length-10 substrings ... 3 A fully connected layer is able to classify images better than random. If you make the kernels constant and there is still information in the result, the network is essentially only a FCN operating on a preprocessed image. Of course it will learn how to classify the image. But it will certainly be worse than a similar network where the convolutional weights ... 3 How to get the optimal value for$k$? You have to define a measure for optimiality. The problem with that is that with bigger$k$most measures become smaller (better). One measure which is independent from$k$is the silhouette coefficient: Let$C = (C_1, \dots, C_k)$be the clusters. Then: Average distance between an object$o$and other objects in the ... 3$C$is a cluster,$c$is centroid,$d$is provided distance function,$\delta$is Dirac measure,$x$is element.$IV = \sum \limits_C \sum \limits_{x \in C} d(x, c)$meaning for each cluster calculate the sum of distances from it's centroid, and sum the results.$EV = \frac{1}{N} \sum \limits_i \sum \limits_j\delta(C(x_i) \ne C(x_j))d(x_i, x_j)$meaning ... 3 If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters. When it comes to community detection or clustering, you need to make a formal definition of a community or cluster (in this case it is a clique). There are two types of definitions: Non-... 3 This problem does generalize the clique problem. One example of a metric is the shortest path distance in a connected, unweighted graph$G$, where the distance between vertices$u$and$v$,$d(u,v)$, is the length of the shortest path between them. There exists a clique of size$K$in this graph if and only if we can find$K$points whose distances sum to${...

3

Let me first formalize the problem: Cluster edition Instance: A graph $G$ and an integer $k$. Question: Can $G$ be transformed into a cluster graph by deleting at most $k$ edges? It is not difficult to see that the problem is, already for general graphs, fixed-parameter tractable (FPT) parameterized by the number of edge deletions $k$. Being FPT means the ...

3

Roughly, the algorithm needs to estimate the probability to assign a point the correct cluster. So the algorithm add P to a cluster if it is very unlikely that, after all the points have been processed, some other cluster centroid will be found to be nearer to P. So the algorithm measure the probability that, if P belongs to a cluster, it would be found as ...

2

There are lots of community detection algorithms that need the number of communities as input. For example, Bigclam [1], a matrix factorization approach, needs the number of communities as input. Another example is the seed expansion [2] method that needs the number of communities as input. I'm sure there are many algorithms that take the number of ...

2

No, probably not -- unless you happen to get lucky and the kernel weights you started with just happen to be good ones. But if you choose the kernel weights randomly, your procedure will probably work very poorly. You can always try it out yourself and see what happens. That said, you might be thinking of "fine-tuning". In fine-tuning, we first train a ...

2

This can be easily seen by a change of coordinates that makes the average $\bar{x} = 0$. This can be done by translating the whole plane, preserving all distances. Since the equation depends only on distances, its validity does not change. Let us denote $|S|$ by $n$. The left hand side becomes $n \sum_{i \in S} ||x_i||^2$. The right hand side can be ...

2

Define an objective function $\Psi(m,c,d,i)$ that specifies how "bad" a particular choice of values for $m,c,d,i$ are. Then, use any standard black-box optimization algorithm (e.g., gradient descent) to find $m,c,d,i$ that minimize the objective function. You might choose the initial values of $m,c$ based on a least-squares fit, and choose the initial ...

2

If I'm understanding your question correctly, you are interested in why the representative points are chosen as such, why they are merged and why this works. I'll first go over some background for CURE, then I focus on this particular question. Background: why CURE? I think we should start with the intention of CURE. To see that, we look at slide 14: ...

2

The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem. If car A has a higher capacity than car B, and you get an optimal solution (smallest number of cars) containing B but not A, then you can swap cars A and B, you won't need more cars, and because A has more empty capacity, you ...

2

Of course not. Otherwise the construction would be "pick an arbitrary set of centers". You can follows the proof and see that the size of the coreset depends polynomially on $\beta$ and $\alpha$. If they are $O(1)$ they can be hidden in the $O()$ notation. Otherwise, someone needs to pay. See more details in Section 6 here: https://arxiv.org/abs/...

2

If $(P_1, P_2)$ is a partition of $P$, that means that $P_2 = P\setminus P_1$. That means that is suffices to count the number of possible choices of $P_1$, which is the cardinal of the powerset of $P$, $|\mathcal{P}(P)| = 2^{|P|}$. If $P_1$ and $P_2$ have symmetrical roles, you can divide the result by $2$ (but it does not change the asymptotical complexity)...

2

Partial Answer: Let us construct an instance where k-means++ initialization performs better than the Gonzalez initialization. Consider the real line. Place $n$ points at the origin, i.e., position $0$. Place $n$ points at the position $1$. Lastly, place $1$ point at the position $n^{1/4}$. Let us cluster this pointset with $2$ clusters, i.e., $k = 2$. In the ...

2

From what I understand, the problem the paper is trying to solve is a gap problem of deciding whether $X$ is $(k,b)$-clusterable, or at least $\epsilon$-far from being $(k,2b)$-clusterable. Since they explained why the algorithm always accepts when $X$ is $(k,b)$-clusterable, now they move on to explain what happens when $X$ is at least $\epsilon$-far from ...

2

If you split along each dimension into two parts, then in two dimensions you have $2\cdot 2 = 4$ children (that's why it's called a quadtree), in three dimensions you have $2\cdot 2\cdot 2 = 8$ children (that's why three-dimensional quadtrees are called octtrees), and for $k$ dimensions you have $2^k$ children. That's independent of the numbers of points in ...

2

Let $P$ be the given set of points. Declare a variable $x_p$ for every point $p \in P$ in the plane. Set $x_p = 1$ if point $p$ belongs to cluster $1$ and $x_p = -1$ if point $p$ belongs to cluster $2$. Then, the integer linear program would be as follows: Objective function: minimize $d_1+d_2$ Constraints: $\frac{(x_p + x_{p'})}{2} \cdot d(p,p') \leq d_1$ ...

2

The Louvain algorithm does just this, and it easily handles graphs of this size. It is implemented in most, if not all, graph libraries. In particular, Networkit provides a fast parallel implementation. If you are interested in clusters only, you may use a dedicated implementation like the generalized version documented in this paper.

1

There are many possible approaches. One approach that I would suggest investigating is finding all pairs of similar strings, and then applying a standard algorithm for clustering of sparse graphs. There are multiple possible approaches for finding similar strings, depending on how you plan to measure similarity. One approach is to measure similarity using ...

1

The stable roommates problem is to find a perfect matching in a non bipartite graph which is "stable". "Perfect" means that every one is assigned to a pair. "Stable" means that it does not exist 2 persons which would prefer to be together instead of their assignement. Note that the stable roommates may have no solution. Now about your problem, the point is ...

1

Here's what my search has come up with: There's a straightforward dynamic programming solution of the problem in this case, which requires $\mathop{\Omega}\left( k \cdot n^3 \right)$ time; and with some thought one can avoid redundant computation of sums-of-squares by this algorithm, reducing the complexity to $\mathop{\Omega}\left( k \cdot n^2 \right)$. ...

Only top voted, non community-wiki answers of a minimum length are eligible