13

我有一个 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 与 c1 比 c2 更相似(更接近)。显然情况并非如此。

Q1。为什么这个假设是错误的?

Q2。对于这种情况,余弦距离是正确的距离函数吗?

Q3。考虑到问题的性质,什么会更好?

4

3 回答 3

18

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

两个向量 -ab- 之间的余弦定义为:

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

wherexy表示用户在顶点上花费的时间。这是主要问题:乘法是否很好地代表了个体对之间的相似性?我不这么认为。在某个顶点上花费 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

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

于 2014-08-07T16:20:57.430 回答
4

余弦相似度适用于您不想考虑长度而只考虑角度的情况。如果您还想包括长度,请选择不同的距离函数。

余弦距离与平方欧几里得距离(唯一真正定义 k-means 的距离)密切相关这就是球形 k 均值有效的原因。

关系很简单:

平方欧几里得距离sum_i (x_i-y_i)^2可以分解为sum_i x_i^2 + sum_i y_i^2 - 2 * sum_i x_i*y_i. 如果两个向量都被归一化,即长度无关紧要,那么前两项是 1。在这种情况下,平方欧几里得距离是2 - 2 * cos(x,y)

换句话说:余弦距离是欧几里得距离的平方,数据归一化为单位长度

如果您不想标准化数据,请不要使用余弦。

于 2014-08-09T09:54:59.417 回答
0

Q1. Why is this assumption wrong?

正如我们从定义中看到的,余弦相似度测量了 2 个向量之间的角度。

在您的情况下,向量v1平放在第一个维度上,而c1两者c2都与轴对齐,因此,余弦相似度必须相同。

请注意,问题在于c1c2指向同一方向。Any v1将与它们具有相同的余弦相似度。举例说明:

在此处输入图像描述

Q2. Is the cosine distance a correct distance function for this case?

正如我们从手头的例子中看到的那样,可能不是。

Q3. What would be a better one given the nature of the problem?

考虑欧几里得距离

于 2014-08-07T11:52:37.230 回答