处理kNN中的不完整数据(数据稀疏性)

Question

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

可以说我有一张桌子:

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"最接近".但在现实世界中,会有更多的？/未知分数.那么在使用knn时如何处理这些未知分数呢？

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

任何帮助表示赞赏!

Answer 1

您没有"未知功能",您的数据点不完整.

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

虽然问题实际上是一个"不完整的数据"问题,但在kNN环境中,它经常(通常是？)被称为稀疏性问题.

在实践中,构建knn模型中的稀疏性问题可能除了有效存储/检索构成模型的数据之外,kNN的关键.

例如,考虑Amazon.com的推荐引擎,其中产品评级为用户特征,包括列和用户组成的行,为此矩阵100%完成,每个亚马逊客户必须购买和审查亚马逊销售的每个产品. .该矩阵的实际稀疏度必须> 95%.

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

从本质上讲,这种技术可用于从矩阵中删除稀疏性,或换句话说,填充缺失的单元格(即,R行的客户尚未修改C列的产品).

您可以在Albert Au Yeung Ching-man的博客中找到nnma的完整实现,包括附带的教程(在python + numpy中).

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

因此,您可以看到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"的二维数组(矩阵)(换句话说,您的数据矩阵,每个缺失值插入一个"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.