en>DavidCary: mention data scrubbing

2013-07-11T05:05:03Z

mention data scrubbing

New page

'''Cosine similarity''' is a measure of similarity between two vectors of an [[inner product space]] that measures the [[cosine]] of the angle between them. The cosine of 0° is 1, and it is less than 1 for any other angle. It is thus a judgement of orientation and not magnitude: two vectors with the same orientation have a Cosine similarity of 1, two vectors at 90° have a similarity of 0, and two vectors diametrically opposed have a similarity of -1, independent of their magnitude. Cosine similarity is particularly used in positive space, where the outcome is neatly bounded in [0,1].

Note that these bounds apply for any number of dimensions, and Cosine similarity is most commonly used in high-dimensional positive spaces. For example, in [[Information Retrieval]] and [[text mining]], each term is notionally assigned a different dimension and a document is characterised by a vector where the value of each dimension corresponds to the number of times that term appears in the document. Cosine similarity then gives a useful measure of how similar two documents are likely to be in terms of their subject matter.<ref>Singhal, Amit (2001). "Modern Information Retrieval: A Brief Overview". Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 24 (4): 35–43.</ref>

The technique is also used to measure cohesion within [[cluster]]s in the field of [[data mining]].<ref>P.-N. Tan, M. Steinbach & V. Kumar, "Introduction to Data Mining", , Addison-Wesley (2005), ISBN 0-321-32136-7, chapter 8; page 500.</ref>

''Cosine distance'' is a term often used for the complement in positive space, that is: <math>D_C(A,B) = 1 - S_C(A,B)</math>. It is important to note, however, that this is not a proper [[distance metric]] as it does not have the triangle inequality property and it violates the coincidence axiom; to repair the triangle inequality property whilst maintaining the same ordering, it is necessary to convert to Angular distance (see below.)

One of the reasons for the popularity of Cosine similarity is that it is very efficient to evaluate, especially for sparse vectors, as only the non-zero dimensions need to be considered.

==Definition==

The cosine of two vectors can be derived by using the [[Euclidean vector#Dot product|Euclidean dot product]] formula:

:<math>\mathbf{a}\cdot\mathbf{b}
=\left\|\mathbf{a}\right\|\left\|\mathbf{b}\right\|\cos\theta</math>

Given two [[Vector (geometric)|vectors]] of attributes, ''A'' and ''B'', the cosine similarity, ''cos(θ)'', is represented using a [[dot product]] and [[Magnitude (mathematics)#Euclidean vectors|magnitude]] as

:<math>\text{similarity} = \cos(\theta) = {A \cdot B \over \|A\| \|B\|} = \frac{ \sum\limits_{i=1}^{n}{A_i \times B_i} }{ \sqrt{\sum\limits_{i=1}^{n}{(A_i)^2}} \times \sqrt{\sum\limits_{i=1}^{n}{(B_i)^2}} }</math>

The resulting similarity ranges from −1 meaning exactly opposite, to 1 meaning exactly the same, with 0 usually indicating independence, and in-between values indicating intermediate similarity or dissimilarity.

For text matching, the attribute vectors ''A'' and ''B'' are usually the [[tf-idf|term frequency]] vectors of the documents. The cosine similarity can be seen as a method of normalizing document length during comparison.

In the case of [[information retrieval]], the cosine similarity of two documents will range from 0 to 1, since the term frequencies ([[tf-idf]] weights) cannot be negative. The angle between two term frequency vectors cannot be greater than 90°.

=== Angular similarity ===

The term "cosine similarity" has also been used on occasion to express a different coefficient, although the most common use is as defined above. Using the same calculation of similarity, the normalised angle between the vectors can be used as a bounded similarity function within [0,1], calculated from the above definition of similarity by:
:<math>1 - \frac{ \cos^{-1}( \text{similarity} )}{ \pi} </math>
in a domain where vector coefficients may be positive or negative, or
:<math>1 - \frac{ 2 \cdot \cos^{-1}( \text{similarity} ) }{ \pi }</math>
in a domain where the vector coefficients are always positive.

Although the term "cosine similarity" has been used for this angular distance, the term is oddly used as the cosine of the angle is used only as a convenient mechanism for calculating the angle itself and is no part of the meaning. Anyway this coefficient can not be used as a proper [[distance metric]] (by subtracting it from 1), consider 2 vectors with angle 0 but different l2-norms. A proper [[distance metric]] would expect these 2 vectors are the same, but this is not the case.
However for most uses this is not an important property. For any use where only the relative ordering of similarity or distance within a set of vectors is important, then which function is used is immaterial as the resulting order will be unaffected by the choice.

=== Confusion with "Tanimoto" coefficient ===

On occasion, cosine similarity has been confused{{citation needed|date=August 2013}} as a specialised form of a similarity coefficient with a similar algebraic form:

:<math>T(A,B) = {A \cdot B \over \|A\|^2 +\|B\|^2 - A \cdot B}</math>

In fact, this algebraic form [[Jaccard index#Tanimoto_Similarity_and_Distance|was first defined by Tanimoto]] as a mechanism for calculating the [[Jaccard coefficient]] in the case where the sets being compared are represented as [[bit vector]]s. While the formula extends to vectors in general, it has quite different properties from cosine similarity and bears little relation other than its superficial appearance.

=== Ochiai coefficient ===
This coefficient is also known in biology as Ochiai coefficient, or Ochiai-Barkman coefficient, or Otsuka-Ochiai coefficient:<ref>''Ochiai A.'' Zoogeographical studies on the soleoid fishes found Japan and its neighboring regions. II // Bull. Jap. Soc. sci. Fish. 1957. V. 22. № 9. P. 526-530.</ref><ref>''Barkman J.J.'' Phytosociology and ecology of cryptogamic epiphytes, including a taxonomic survey and description of their vegetation units in Europe. – Assen. Van Gorcum. 1958. 628 p.</ref>
:<math>K =\frac{n(A \cap B)}{\sqrt{n(A) \times n(B)}}</math>
Here, <math>A</math> and <math>B</math> are sets, and <math>n(A)</math> is the number of elements in <math>A</math>. If sets are represented as [[bit vector]]s, the Ochiai coefficient can be seen to be the same as the cosine similarity.

== Properties ==
Cosine similarity is related to [[Euclidean distance]] as follows. Denote Euclidean distance by the usual |''A'' - ''B''|, and observe that

:<math>|A - B|^2 = (A - B)^\top (A - B) = |A| + |B| - 2 A^\top B</math>

by [[Polynomial expansion|expansion]]. When ''A'' and ''B'' are normalized to unit length, |''A''| = |''B''| = 1 so the previous is equal to

:<math>2 (1 - \cos(A, B))</math>

== See also ==
* [[Sørensen similarity index|Sørensen's quotient of similarity]]
* [[Hamming distance]]
* [[Correlation]]
* [[Dice's coefficient]]
* [[Jaccard index]]
* [[SimRank]]
* [[Information retrieval]]

==References==
{{reflist}}

== External links ==
* [http://www.appliedsoftwaredesign.com/archives/cosine-similarity-calculator/ Online Cosine Similarity Calculator]
* [http://mathforum.org/kb/message.jspa?messageID=5658016&tstart=0 Weighted cosine measure]
* [http://pyevolve.sourceforge.net/wordpress/?p=2497 A tutorial on cosine similarity using Python]

{{DEFAULTSORT:Cosine Similarity}}
[[Category:Information retrieval]]

Triple modular redundancy - Revision history

en>DavidCary: mention data scrubbing