# Tag Info

23

The difference is that in supervised learning the "categories", "classes" or "labels" are known. In unsupervised learning, they are not, and the learning process attempts to find appropriate "categories". In both kinds of learning all parameters are considered to determine which are most appropriate to perform the classification. Whether you chose ...

13

Note that there are more than 2 degrees of supervision. For example, see the pages 24-25 (6-7) in the PhD thesis of Christian Biemann, Unsupervised and Knowledge-free Natural Language Processing in the Structure Discovery Paradigm, 2007. The thesis identifies 4 degrees: supervised, semi-supervised, weakly-supervised, and unsupervised, and explains the ...

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 ... 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 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${...

2

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 ...

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

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

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

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 ...

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: ...

1

Strongly regular graphs fit the bill, i.e., one property is that adjacent vertices have (exactly) $\lambda$ common neighbors. Paley graphs should give you an infinite family and an explicit construction.

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)$. ...

1

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 ...

1

Algorithm 1 takes non-annotated data as input, so it is agnostic to the labels (shapes). In line 1, algorithm 1 computes clusters on the non-annotated data. The cluster assignments do not necessarily correspond exactly to the labels. The output of algorithm 1 will be a set of edges between data in different clusters, but the data need not have different ...

1

There are several standard clustering algorithms you could try, including k-means and hierarchical clustering. The additional restrictions you have should make both implementable in a reasonably efficient way. In particular, build a graph with one vertex per image, and an edge between each pair of images that meet all the thresholds. Note that this can be ...

1

You can use Cluster Edge Deletion, however, the problem is NP-hard. Create a graph where the vertex set is the set of your objects, and you create an edge between two objects if the distance is at most the threshold. Now, the Cluster Edge Deletion problem is to find the set with fewest edges to delete such that the remaining graph is a cluster graph (a ...

1

Have the app record the GPS location once per second, save it, and once every 30 seconds, update that trace of the locations over the past 30 seconds. Or, just upload the location every second. The bandwidth requirements for that are small. Then, if you have multiple users in the same location (within a fixed radius, say within 100 ft of each other), and ...

1

The constraints you have are not very clear (why should you start with "central items" ?). You should maybe try to come up with a well defined problem by precisely defining the clustering(s) you are looking for. For example, if the clustering you want is such that the maximum number of clusters is $k_{max}$ and the maximum distance between two elements in ...

1

Instead of the classical $k$-means algorithm where you classify all points and then update the center of each cluster to be the average of all points of that cluster, you could use the sequential variant of $k$-means: centers = random(k) while True: p = next_point(points) c = find_center(centers, p) c = c + a * (p - c) next_point iterates all ...

1

The one-nearest neighbor classifier is very competitive for time series. http://www.cs.ucr.edu/~eamonn/ICML2006.pdf If you want code or data, I have lots of both. eamonn

1

While you can modify any algorithm as you see fit, in its pure form UPGMA has the following underlying assumptions at work: UPGMA (Unweighted Pair-Group Method with Averages), arithmetic average - the average distance between elements of each cluster (weighted by the number of elements). For example, (AB) and C+(DE) = (55+3x45)/3 = 63.33 Additional ...

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