45
To compare the similarity of two hierarchical (tree-like) structures, measures based on cophenetic correlation idea are used. But is it correct to perform comparison of dendrograms in order to select the "right" method or distance measure in hierarchical clustering?
There are some points - hidden snags - regarding hierarchical cluster analysis that I would ...
32
As @Max indicated in the comments (+1) it would be simpler to "write your own" than to spend time looking for it somewhere else. As we know, the cosine similarity between two vectors $A,B$ of length $n$ is
$$
C = \frac{ \sum \limits_{i=1}^{n}A_{i} B_{i} }{ \sqrt{\sum \limits_{i=1}^{n} A_{i}^2} \cdot \sqrt{\sum \limits_{i=1}^{n} B_{i}^2} } $$
which is ...
30
According to cosine theorem, in euclidean space the (euclidean) squared distance between two points (vectors) 1 and 2 is $d_{12}^2 = h_1^2+h_2^2-2h_1h_2\cos\phi$. Squared lengths $h_1^2$ and $h_2^2$ are the sums of squared coordinates of points 1 and 2, respectively (they are the pythagorean hypotenuses). Quantity $h_1h_2\cos\phi$ is called scalar product (= ...
18
Technically to compute a dis(similarity) measure between individuals on nominal attributes most programs first recode each nominal variable into a set of dummy binary variables and then compute some measure for binary variables. Here is formulas of some frequently used binary similarity and dissimilarity measures.
What is dummy variables (also called one-...
16
If you have stumbled upon this question and are wondering what package to download for using Gower metric in R, the cluster package has a function named daisy(), which by default uses Gower's metric whenever mixed types of variables are used. Or you can manually set it to use Gower's metric.
daisy(x, metric = c("euclidean", "manhattan", "gower"),
...
16
There exist many such coefficients (most are expressed here). Just try to meditate on what are the consequences of the differences in formulas, especially when you compute a matrix of coefficients.
Imagine, for example, that objects 1 and 2 similar, as objects 3 and 4 are. But 1 and 2 have many of the attributes on the list while 3 and 4 have only few ...
14
The inverse is to change from distance to similarity.
The 1 in the denominator is to make it so that the maximum value is 1 (if the distance is 0).
The square root - I am not sure. If distance is usually larger than 1, the root will make large distances less important; if distance is less than 1, it will make large distances more important.
13
Seems like you're looking for either the Jaccard distance or the Dice dissimilarity.
Jaccard distance:
$1 - \frac{|A \cap B|}{|A \cup B|}$
Dice dissimilarity:
$1 - \frac{2|A \cap B|}{|A| + |B|}$
These both are equal to zero if $A$ and $B$ are exactly the same, and one if they are completely different. However, Jaccard will "punish" differences more ...
11
We know that Jaccard (computed between any two columns of binary data $\bf{X}$) is $\frac{a}{a+b+c}$, while Rogers-Tanimoto is $\frac{a+d}{a+d+2(b+c)}$, where
a - number of rows where both columns are 1
b - number of rows where this and not the other column is 1
c - number of rows where the other and not this column is 1
d - number of rows where both ...
11
Let me address this by describing the four maybe most common similarity metrics for bags of words and document (count) vectors in general, that is comparing collections of discrete variables.
Cosine similarity is used most frequently in general, but you should always measure first and make sure that no other similarity would produce better results for your ...
10
First of all, in many applications you do not need a distance metric, but a dissimilarity will be okay. So make sure that triangle inequality is needed.
In mathematics, triangle inequality is part of the definition of a metric, and distances in mathematics are synonymous to metrics. But in database literature, often distances are not required to be metric.
...
answered Dec 4 '14 at 9:53
Has QUIT--Anony-Mousse
36.8k6 gold badges46 silver badges87 bronze badges
9
The above solution is not very good if X is sparse. Because taking !X will make a dense matrix, taking huge amount of memory and computation.
A better solution is to use formula Jaccard[i,j] = #common / (#i + #j - #common). With sparse matrixes you can do it as follows (note the code also works for non-sparse matrices):
library(Matrix)
jaccard <- ...
9
There are various methods to define document similarity, but let me introduce the most easiest approach to start with, based on semantic vector space:
First build your term-document matrix
Then "Normalize" the entries in the matrix with tf-idf
From there, you can use your document-vectors columns of the matrix to calculate the similarity with the cosine ...
9
The answer is really right there in your linked articles. From the first, here are the formulae for cosine and correlation (lightly edited for brevity and clarity):
\begin{align}
{\rm CosSim}(x,y) &= \frac{\sum_i x_i y_i}{ \sqrt{ \sum_i x_i^2} \sqrt{ \sum_i y_i^2 } } \\
\ \\
\ \\
{\rm Corr}(x,y) &= \frac{ \sum_i (x_i-\bar{x}) (y_i-\bar{y}) }{
\...
answered May 10 '14 at 2:33
8
The function
$$ f\colon [0,1]\times[0,1]\to[0,1], \quad(x,y)\mapsto \frac{1}{4}x+\frac{1}{4}y+\frac{3}{4}(x-y)^2 $$
does what you want. Plus, it's positive, symmetric and definite ($x\neq y$ implies that $f(x,y)>0$).
Neither it nor its root is linearly homogeneous like a norm-derived distance function, though ($f(\lambda x, \lambda y)\neq\lambda f(x,y)$...
7
You can use the cosine function from the lsa package:
http://cran.r-project.org/web/packages/lsa
7
Some answers above are computationally inefficient, try this;
For cosine similarity matrix
Matrix <- as.matrix(DF)
sim <- Matrix / sqrt(rowSums(Matrix * Matrix))
sim <- sim %*% t(sim)
Convert to cosine dissimilarity matrix (distance matrix).
D_sim <- as.dist(1 - sim)
7
A good approach to this kind of problem can be found in section 4 of the paper The Bayesian Image Retrieval System, PicHunter by Cox et al (2000). The data is a set of integer outcomes $A_1, ..., A_N$ where $N$ is the number of trials. In your case, there are 3 possible outcomes per trial. I will let $A_i$ be the index of the face that was left out. The ...
7
For high-dimensional data, shared-nearest-neighbor distances have been reported to work in
Houle et al., Can Shared-Neighbor Distances Defeat the Curse of Dimensionality? Scientific and Statistical Database Management. Lecture Notes in Computer Science 6187. p. 482. doi:10.1007/978-3-642-13818-8_34
Fractional distances are known to be not metric. $L_p$ ...
answered Dec 4 '14 at 15:29
Has QUIT--Anony-Mousse
36.8k6 gold badges46 silver badges87 bronze badges
7
Area between 2 curves may give you the difference. Hence sum(nr-nf) (sum of all differences) will be an approximation of the area between 2 curves. If you want to make it relative, sum(nr-nf)/sum(nf) can be used. These will give you a single value indicating similarity between 2 curves for each graph.
Edit: Above method of sum of differences will be useful ...
7
From the wikipedia page:
$$J=\frac{D}{2-D} \;\; \text{and}\;\; D=\frac{2J}{J+1}$$
where $D$ is the Dice Coefficient and $J$ is the Jacard Index.
In my opinion, the Dice Coefficient is more intuitive because it can be seen as the percentage of overlap between the two sets, that is a number between 0 and 1.
As for the Overlap it represents the percentage of ...
6
There are two commonly seen approaches:
Add outliers to real data by randomization methods.
In order to obtain a rare class, downsample a class to desired sparsity (usually, this should be <<1%)
For 1 there are some variants - modifying single attributes, drawing each attribute, but from different instances etc.; personally, I'm not at all convinced ...
answered Nov 16 '12 at 13:59
Has QUIT--Anony-Mousse
36.8k6 gold badges46 silver badges87 bronze badges
6
It's more common to measure discrepancy than similarity, but some of them can be converted easily to your way around.
Possible measures of discrepancy in distribution include (but are not limited to):
Kolmogorov-Smirnov distance. This distance between cdfs (or emprical cdfs), $D$, is small when the distributions are the same and close to 1 when they're ...
6
This is a big issue in some areas of machine learning. I'm not as familiar with it as I'd like, but I think these should get you started.
Dimensionality Reduction by Learning an Invariant Mapping (DrLIM) seems to work very well on some data sets.
Neighborhood components analysis is a very nice linear algorithm, and nonlinear versions have been developed as ...
6
You might compute PMI using Wikipedia, as following:
1) Using Lucene to index a Wikipedia dump
2) Using Lucene API, it is straightforward to get:
The number (N1) of documents containing word1 and the number (N2) of documents containing word2. So, Prob(word1) = (N1 + 1) / N and Prob(word2) = (N2 + 1) / N, where N is the total number of documents in ...
6
Could your problem be restated as wanting to discover the regular expressions that will match the strings in each category? This is a "regex generation" problem, a subset of the grammar induction problem (see also Alexander Clark's website).
The regular expression problem is easier. I can point you to code frak and RegexGenerator. The online RegexGenerator++...
6
The simplest most common way to avoid a 0 probability in word frequencies is the Lidstone smoothing
Which is basically, instead of using
$$p(w_i)=\frac{\#(w_i)}{\sum{\#(w_j)}}$$
Use:
$$p(w_i)=\frac{\#(w_i)+\epsilon}{\sum{\#(w_j)}+N\epsilon}$$
Regarding information of $p=0-$ The motivation I know is taken from the entropy definition:
$$H(p)=p\log{p}$$
And ...
6
The definition of the cosine similarity is:
$$
\text{similarity} = \cos(\theta) = {\mathbf{A} \cdot \mathbf{B} \over \|\mathbf{A}\|_2 \|\mathbf{B}\|_2} = \frac{ \sum\limits_{i=1}^{n}{A_i B_i} }{ \sqrt{\sum\limits_{i=1}^{n}{A_i^2}} \sqrt{\sum\limits_{i=1}^{n}{B_i^2}} }
$$
It is sensitive to the mean of features. To see this, choose some $j \in \{1, \ldots,...
6
Does Mercer's theorem work in reverse?
Not in all cases.
Wikipedia: "In mathematics, specifically functional analysis, Mercer's theorem is a representation of a symmetric positive-definite function on a square as a sum of a convergent sequence of product functions. This theorem, presented in (Mercer 1909), is one of the most notable results of the work of ...
Only top voted, non community-wiki answers of a minimum length are eligible
