余弦距离作为k均值的向量距离函数

Question

我有一个N个顶点的图形,其中每个顶点代表一个地方.此外,我有一个向量,每个用户一个,N个系数中的每一个,其中系数的值是在相应位置花费的持续时间(秒),如果没有访问该位置,则为0.

例如图表:

向量:

v1 = {100, 50, 0 30, 0}

意味着我们花了:

100secs at vertex 1
50secs at vertex 2 and 
30secs at vertex 4 

(未访问的顶点3和5,因此为0).

我想运行k-means聚类,我选择cosine_distance = 1 - cosine_similarity了距离的度量,其公式为cosine_similarity:

作为描述在这里.

但我注意到以下情况.假设k=2其中一个向量是:

v1 = {90,0,0,0,0}

在解决最小化候选质心总距离的优化问题的过程中,假设在某一点上,2个候选质心是:

c1 = {90,90,90,90,90}
c2 = {1000, 1000, 1000, 1000, 1000}

运行cosine_distance(v1,c1)和(v1,c2)的公式,我们得到0.5527864045两者的距离完全相同.

我认为v1比c2更接近c1更接近(更接近).显然事实并非如此.

Q1.为什么这个假设错了？

Q2.在这种情况下,余弦距离是否是正确的距离函数？

Q3.考虑到问题的本质,什么会更好？

Answer 1

让我们将余弦相似度分成几部分,看看它是如何以及为什么起作用的.

2个向量之间的余弦 - a和b- 定义为:

cos(a, b) = sum(a .* b) / (length(a) * length(b))

哪里.*是元素乘法.分母在这里只是为了规范化,所以让我们简单地称之为L.有了它我们的功能变成:

cos(a, b) = sum(a .* b) / L

反过来,可以改写为:

cos(a, b) = (a[1]*b[1] + a[2]*b[2] + ... + a[k]*b[k]) / L = 
          = a[1]*b[1]/L + a[2]*b[2]/L + ... + a[k]*b[k]/L

让我们更抽象一点,x * y / L 用函数替换g(x, y)(L这里是常量,所以我们不把它作为函数参数).因此,我们的余弦函数变为:

cos(a, b) = g(a[1], b[1]) + g(a[2], b[2]) + ... + g(a[n], b[n]) 

也就是说,每对元素(a[i], b[i])都是分开处理的,结果只是所有处理的总和.这对你的情况有好处,因为你不希望不同的对(不同的顶点)相互混淆:如果user1只访问了vertex2和user2 - 只有vertex1,那么它们没有任何共同点,它们之间的相似性应该是零.你真正不喜欢的是如何g()计算各对之间的相似性 - 即函数.

使用余弦函数,各对之间的相似性如下所示:

g(x, y) = x * y / L

其中x和y表示用户在顶点上花费的时间.这里有一个主要问题:乘法是否代表各个对之间的相似性？我不这么认为.在某些顶点上花费90秒的用户应该接近在那里度过的用户,比如70或110秒,但远远超过花费1000或0秒的用户.乘法(甚至归一化L)在这里完全是误导.什么意味着乘以2个时间段？

好消息是,这是你设计相似功能的人.我们已经决定对对(顶点)的独立处理感到满意,并且我们只希望单独的相似函数g(x, y)使其参数合理.比较时间段的合理功能是什么？我会说减法是一个很好的候选人:

g(x, y) = abs(x - y)

这不是相似函数,而是距离函数 - 距离函数越近,值越小,结果越小g()- 但最终的想法是相同的,所以我们可以在需要时交换它们.

我们可能还想通过平衡差异来增加大错配的影响:

g(x, y) = (x - y)^2 

嘿! 我们刚刚重新发明(均值)平方误差!我们现在可以坚持使用MSE来计算距离,或者我们可以继续寻找好的g()功能.

有时我们可能不想增加,而是平滑差异.在这种情况下,我们可以使用log:

g(x, y) = log(abs(x - y))

我们可以使用这样的零特殊处理:

g(x, y) = sign(x)*sign(y)*abs(x - y)   # sign(0) will turn whole expression to 0

或者我们可以通过颠倒差异从远处回到相似性:

g(x, y) = 1 / abs(x - y)

请注意,在最近的选项中,我们没有使用归一化因子.事实上,你可以为每个案例提出一些良好的规范化,或者只是省略它 - 规范化并不总是需要或好的.例如,在余弦相似性公式中,如果将标准化常数更改L=length(a) * length(b)为L=1,则会得到不同但仍然合理的结果.例如

cos([90, 90, 90]) == cos(1000, 1000, 1000)  # measuring angle only
cos_no_norm([90, 90, 90]) < cos_no_norm([1000, 1000, 1000])  # measuring both - angle and magnitude

总结这个漫长且无聊的故事,我建议重写余弦相似度/距离,以便在两个向量中使用变量之间的某种差异.