algorithm - 在 kNN 中处理不完整数据(数据稀疏性)

Question

我正在尝试使用 knn 创建一个简单的推荐系统。

假设我有一张 table :

User | Book1 | Book2 | Book3 | Book4 | Book5 | Book6 | Book7 |
1    | 5     | ?     | 3     | ?     | 4     | 3     | 2     |
2    | 3     | 4     | ?     | 2     | 3     | 4     | 2     |
3    | 4     | 2     | 1     | ?     | ?     | 3     | 3     |
4    | 2     | 5     | 3     | ?     | 4     | 1     | 1     |
5    | 1     | 1     | 4     | 3     | 1     | ?     | 1     |
6    | 5     | 2     | 5     | 4     | 4     | 2     | ?     |

因此，如果要找到用户 1 的可能分数，我想只需取用户 1 阅读的书籍与其他用户阅读的书籍的绝对差异即可。然后我将使用该差异找出该列表中的哪个用户与用户 1“最接近”。但在现实世界的情况下，会有更多 ?/unknown 分数。那么在使用 knn 时如何处理那些未知的分数？

我没有任何代码，因为我还没有真正理解如何实现它。

感谢任何帮助!

Answer 1

您没有“未知特征”，您的数据点不完整。

这实际上是 kNN 中众所周知的问题，并且有一个经过彻底验证的模式来处理它。

尽管该问题实际上是一个“不完整数据”问题，但在 kNN 上下文中，它通常(通常？)被称为稀疏性问题。

在实践中，构建 knn 模型时的稀疏性问题是 kNN 的症结所在，但构成模型的数据的高效存储/检索可能除外。

例如，考虑 Amazon.com 的推荐引擎，其中产品评分作为用户特征构成列，用户构成行，为了让这个矩阵 100% 完整，每个亚马逊客户都必须购买并评论亚马逊销售的每一种产品。这个矩阵的实际稀疏度必须>95%。

最常用的技术(据我所知仍然是最先进的)被称为 NNMA，或非-负矩阵近似。这种技术也经常被错误地称为 NNMF，其中 F 代表因式分解。 (NNMA 基于分解技术，但结果不是原始数据矩阵的因子。)我提到这个是因为这个替代术语虽然不正确但被广泛使用，所以我会把它包含在我的搜索引擎查询中。

本质上，这种技术可用于消除矩阵的稀疏性，或者换句话说，填充缺失的单元格(即，R 行的客户尚未审查 C 列的产品)。

您可以在 Albert Au Yeung Ching-man's blog 中找到 nnma 的完整实现，包括附带的教程(使用 python + numpy) .

或者，有几个 python 包(可通过 PyPI 获得)包含 NNMA 的打包代码。我只用过其中一个，PyMF ，您可以在 Google 代码中找到它。

为了让您了解 NNMA 是如何发挥其魔力的，这里是我在 python + NumPy 中简单但完整的 NNMA 实现:

import numpy as NP

def cf(q, v):
    """ the cost function """
    qv = (q - v)**2
    return NP.sum(NP.sum(qv, axis=0))


def nnma(d, max_iter=100):
    x, y = d.shape
    z = y
    w = NP.random.rand(x, y)
    h = NP.random.rand(y, z)
    for i in range(max_iter):
        wh = NP.dot(w, h)
        cost = cf(d, wh)
        if cost == 0: 
            break
        hn = NP.dot(w.T, d)
        hd = NP.dot(NP.dot(w.T, w), h)
        h *= hn/hd
        wn = NP.dot(d, h.T)
        wd = NP.dot(NP.dot(w, h), h.T)
        w *= wn/wd
    return NP.dot(w, h)

要使用这个NNMA 函数，只需传入一个二维数组(矩阵)，每个缺失的单元格(换句话说，您的数据矩阵，为每个缺失值插入“0”):

>>> d    # the original (sparse) data matrix with missing cells denoted by "0"s

  array([[ 7.,  0.,  4.,  7.,  0.,  1.],
         [ 3.,  9.,  7.,  3.,  1.,  7.],
         [ 4.,  4.,  3.,  7.,  3.,  9.],
         [ 4.,  8.,  0.,  9.,  2.,  1.],
         [ 6.,  3.,  9.,  5.,  9.,  3.],
         [ 6.,  1.,  4.,  4.,  1.,  0.],
         [ 0.,  4.,  8.,  6.,  0.,  5.],
         [ 9.,  0.,  6.,  0.,  5.,  2.],
         [ 6.,  8.,  4.,  6.,  3.,  7.],
         [ 3.,  6.,  3.,  8.,  7.,  2.]])

>>> d1 = nnma(d)     # call nnma, passing in the original data matrix

>>> d1    # the approximated data matrix with all missing values populated

   array([[ 6.998,  0.29 ,  3.987,  7.008,  0.292,  0.796],
          [ 2.989,  8.92 ,  6.994,  3.02 ,  1.277,  7.053],
          [ 4.007,  4.496,  2.999,  7.01 ,  3.107,  8.695],
          [ 4.005,  8.019,  0.254,  9.002,  1.917,  0.89 ],
          [ 5.998,  3.014,  9.001,  4.991,  8.983,  3.052],
          [ 5.992,  1.077,  4.007,  3.976,  0.753,  0.464],
          [ 0.346,  3.436,  7.993,  5.988,  0.194,  5.355],
          [ 9.001,  0.124,  5.997,  0.375,  5.02 ,  1.867],
          [ 6.   ,  7.994,  3.998,  6.   ,  2.999,  7.009],
          [ 2.995,  6.022,  3.001,  7.987,  6.939,  2.185]])

如您所见，结果还不错，特别是对于非常简单的实现。所有缺失的项目都被填充，其余的值非常接近原始数据矩阵中的相应值，例如，原始数据矩阵中的第 0 列、第 0 行为 7.0，而近似值中为 6.998。