余弦距离作为k-means的向量距离函数

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}

对于 (v1, c1) 和 (v1, c2)，应用 cosine_distance 公式，我们得到了相同的距离，即 0.5527864045。

我认为 v1 与 c1 的相似度（距离）更高。但显然情况并非如此。

Q1. 为什么这个假设是错误的？

Q2. 对于这种情况，余弦距离是否正确？

Q3. 鉴于问题的性质，有哪些更好的距离函数可供选择？

- Thalis K.

Answer 1

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

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

让我们更加抽象化，用函数g(x, y)替换x * y / L（这里的L是常数，因此我们不将其作为函数参数）。因此，我们的余弦函数变为：

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

那就是说，每对元素 (a[i], b[i]) 都被单独处理，结果就是所有处理的简单总和。这对你的情况很有帮助，因为你不希望不同的对（不同的顶点）相互干扰：如果用户1只访问了顶点2而用户2只访问了顶点1，那么他们之间没有任何共同之处，他们之间的相似度应该为零。你实际上不喜欢的是如何计算个体对之间的相似度 - 即函数g()。

用余弦函数计算个体对之间的相似度如下：

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

其中x和y表示用户在顶点上花费的时间。这里的主要问题是：乘法是否能很好地表示个体对之间的相似性？我认为不行。在某个顶点上花费90秒的用户应该与在那里花费70或110秒的用户更接近，但距离在那里花费1000或0秒的用户更远。乘法（即使通过L进行归一化）在这里完全具有误导性。两个时间段相乘意味着什么？

好消息是，你将设计相似度函数。我们已经决定满足独立处理对（顶点），并且我们只想要个体相似度函数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

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

- ffriend

Answer 2

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

余弦距离与平方欧几里得距离（k-means真正定义的唯一距离）密切相关，这就是为什么球形k-means有效的原因。

它们之间的关系非常简单：

平方欧几里得距离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)！

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

如果您不想归一化您的数据，请不要使用余弦距离。

- Has QUIT--Anony-Mousse

Answer 3

Q1. 为什么这个假设是错误的？

从定义中我们可以看出，余弦相似度衡量的是两个向量之间的夹角。

在您的情况下，向量v1平放在第一维上，而c1和c2都与轴线等齐，因此，余弦相似度必须相同。

请注意，问题在于c1和c2指向相同的方向。任何v1都将与它们具有相同的余弦相似度。例如：

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

从手头的例子可以看出，可能不是。

Q3. 鉴于问题的性质，有更好的距离函数吗？

考虑欧几里得距离。

- axiom

---

考虑到这个问题的性质，我更倾向于使用非对称函数。 我的意思是，即使两个用户访问了一个顶点，即使他们停留的时间可能不完全相同，他们也应该被认为比那些根本没有访问过该顶点（即有匹配的0）的用户更接近。据我理解，欧几里得距离是对称的，对吗？ - Thalis K.

问题不在于向量中有很多零，而在于每个聚类中心都具有所有系数相等的问题。我将用户向量的所有系数都设为零，只是为了更清楚地显示它应该比另一个更接近一个中心。您可以用非零值替换用户向量的0，并且仍然从两个中心得到相同的距离。这就是为什么我并不完全相信余弦距离对于这个问题来说是不合适的。 - Thalis K.