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

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

两个向量 -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

wherex和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

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

于 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都与轴对齐，因此，余弦相似度必须相同。

请注意，问题在于c1并c2指向同一方向。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 回答