48

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


21

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


17

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


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"), ...


15

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.


15

Many answers here 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)


15

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


14

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


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


9

You can use the cosine function from the lsa package: http://cran.r-project.org/web/packages/lsa


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

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


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}) }{ \...


9

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


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

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


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

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


7

There are some field-specific reasons to perform row normalization. In text analysis, it is quite common to represent a text with the histogram of the words it contains. Starting from the count of words for each line, raw standardization turns it into an histogram. And the computational reason. If you are working with a sparse matrix, you cannot center and ...


7

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


7

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


7

Yes, the Matrix Profile allows discord discovery, which is very competitive for anomaly detection (according to multiple independent test) And yes, while "finding similarities among time series" is a bit too vague to clearly respond to, the Matrix Profile does do that. If you write to the author of the tutorial (me) with some data samples, he will advise ...


6

The following function might be useful when working with matrices, instead of 1-d vectors: # input: row matrices 'ma' and 'mb' (with compatible dimensions) # output: cosine similarity matrix cos.sim=function(ma, mb){ mat=tcrossprod(ma, mb) t1=sqrt(apply(ma, 1, crossprod)) t2=sqrt(apply(mb, 1, crossprod)) mat / outer(t1,t2) }


6

To measure the distance and similarity (in the semantic sense) the first thing to check is if you are moving in a Euclidean space or not. An empirical way to verify this is to estimate the distance of a pair of values ​​for which you know the meaning.


6

Qualifications It so happens that in the Iris data set the rows (as is this data set is usually presented) are values on four variables, all with the same dimensions and units. However, I will not assume reference to this specific data set. For more on that data set, one starting point is What aspects of the Iris data set make it so successful ... ...


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

Your measure seems to resolve to a distance defined by Simpson. See A Survey of Binary Similarity and Distance Measures page 44, equation 45.


6

You could try recurrent neural networks, where your input is a sequence of the letters in the word, and your output is a category. This fits your requirement such that you don't hand code any features. However for this method to actually work you will require a fairly large training data set. You can refer Supervised Sequence Labelling with Recurrent ...


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