algorithm - 按属性查找相似产品

Question

我听说过 K 最近邻可以找到元素所属的类别，但我想知道是否有一种算法可以根据属性返回元素列表。

例如给定一部电影

[director: "Hill Thompson", starring-actor: "Will Smith", release-date: "Dec 1776"]

结果会返回

[director: "Hill Thompson", starring-actor: "Will Smith", release-date: "Jan 1996"]

代替

[director: "Hill Thompson", starring-actor: "Poop Jenkins", release-date: "Sept 1822"]

因为前一个结果匹配更多属性“Hill Thompson”和“Will Smith”，而前者只有一个匹配 - Hill Thompson。

余弦相似度是解决这个问题的好方法吗？

Answer 1

余弦相似度是解决这个问题的好方法吗？

是的。这会很好，但是有 TF-IDF

最常用的相似性度量是Jaccard Similarity 和Cosine similarity。 在给定的场景下，可以直接使用Jaccard Similarity，得到想要的结果。

说，

A = {director: "Hill Thompson", starring-actor: "Will Smith", release-date: "Dec 1776"}
B = {director: "Hill Thompson", starring-actor: "Will Smith", release-date: "Jan 1996"}
C = {director: "Hill Thompson", starring-actor: "Poop Jenkins", release-date: "Sept 1822"}
D = {director: "Foo Bar", starring-actor: "Poop Jenkins", release-date: "Some date"}

Jaccard 相似度 将是:

J(A,B) = 2 / 4 = 0.5
J(A,C) = 1 / 5 = 0.2
J(C,D) = 1 / 5 = 0.2

当 J(A,B) > J(A,C) 时，K 最近邻 方法会先选择 B，然后再选择C。 在这种情况下，Jaccard 相似度 很好地捕捉了直觉。

为了演示 Cosine Similarity 如何更好，再添加一个属性:

A = {place filmed : "A", director: "Hill Thompson", starring-actor: "Will Smith", release-date: "Dec 1776"}
B = {place filmed : "A", director: "Hill Thompson", starring-actor: "Will Smith", release-date: "Jan 1996"}
C = {place filmed : "A", director: "Hill Thompson", starring-actor: "Poop Jenkins", release-date: "Sept 1822"}
D = {place filmed : "A", director: "Foo Bar", starring-actor: "Poop Jenkins", release-date: "Some date"}


J(A,B) = 3 / 5 = 0.6
J(A,C) = 2 / 6 = 0.33
J(C,D) = 2 / 6 = 0.33

注意 J(C,A) = J(C,D)

这是错误的直觉。

为什么？ 因为A地方好像是经常拍电影的地方。仅仅因为两部电影是在同一个地方录制的，我们不能断定它们是相似的。所以理想情况下它应该是 Sim(C,D) > Sim(C,A)。在这种情况下，Jaccard Similarity 无法捕捉直觉，而 Cosine similarity 与 TF-IDF 的表现更胜一筹。

在这种情况下，Cosine Similarity 的问题在于实现。 余弦相似度 是在向量上定义的。当数据不是数字时，很难创建向量。

创建向量的一种方法是使用 boolean 向量。

例如， 向量将形成为:

vector = [A,HillThompson,FooBar,WillSmith,Poop Jenkins,Dec 1776,Jan 1996, Sept 1822, Some date]

向量将是:

A = {1,1,0,1,0,1,0,0,0}
C = {1,1,0,0,1,0,0,1,0}
D = {1,0,1,0,1,0,0,0,1}

J(C,A) = 5 / 12
J(C,D) = 5 / 12

请注意，Jaccard Similarity 仍然捕捉到了错误的直觉。如果未完成 TF-IDF，余弦相似度也会如此。

现在计算 TF-IDF :

IDF(A)              = log( 1 + 4 / 4) = 0.30

IDF(HillThompson)   = log( 1 + 4 / 3) = 0.37
IDF(FooBar)         = log( 1 + 4 / 1) = 0.70

IDF(WillSmith)      = log( 1 + 4 / 2) = 0.48
IDF(Poop Jenkins)   = log( 1 + 4 / 2) = 0.48

IDF(Dec 1776)       = log( 1 + 4 / 1) = 0.70
IDF(Jan 1996)       = log( 1 + 4 / 1) = 0.70
IDF(Sept 1822)      = log( 1 + 4 / 1) = 0.70
IDF(Some date)      = log( 1 + 4 / 1) = 0.70

IF-IDF 向量现在是:

A = {0.30/4, 0.37/4, 0,      0.48/4, 0,       0.70/4, 0, 0,      0}
C = {0.30/4, 0.37/4, 0,      0,      0.48/4,  0,      0, 0.70/4, 0}
D = {0.30/4,      0, 0.70/4, 0,      0.48/4,  0,      0, 0,      0.70/4}

A = {0.075,  0.0925, 0,      0.12,   0,       0.175,  0, 0,     0 } 
C = {0.075,  0.0925, 0,      0,      0.12,    0,      0, 0.175, 0 }
D = {0.075,  0,      0.175,  0,      0.12,    0,      0, 0,     0.175 }

|A| = 0.2433
|C| = 0.2433
|D| = 0.2850

计算余弦相似度:

Cosine(A,C) = 0.01418 / ( 0.2433 * 0.2433 ) = 0.2395
Cosine(C,D) = 0.0200  / ( 0.2492 * 0.2850 ) = 0.2816

因此，余弦相似度与TF-IDF 的直觉是D 与C 更相似A 比 C。因此它优于 Jaccard similarity

请注意 我已经展示了计算结果，因为我是在 PC 上而不是在科学计算器上完成的。可能会有错误的机会。万一你找到了，请纠正它。