7

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を使用するときに、これらの未知のスコアをどのように処理するのでしょうか。

これを実装する方法をまだ本当に理解していないので、私はコードを持っていません。

どんな助けでも大歓迎です！

4

3 に答える 3

10

不完全なデータポイントを持つ「未知の機能」はありません。

これは実際にはkNNでよく知られている問題であり、これに対処するための徹底的に検証されたパターンがあります。

この問題は実際には「不完全なデータ」の問題ですが、kNNのコンテキストでは、スパース性の問題と呼ばれることがよくあります（通常は？）。

実際には、knnモデルを構築する際のスパース性の問題は、モデルを構成するデータの効率的な保存/取得を除いて、kNNの核心です。

たとえば、Amazon.comのレコメンデーションエンジンを考えてみましょう。このエンジンでは、列を構成するユーザー機能と行を構成するユーザーとしての商品評価があり、このマトリックスが100％完全であるためには、Amazonのすべての顧客がAmazonが販売するすべての商品を購入して確認する必要があります。 。この行列の実際のスパース性は>95％でなければなりません。

最も一般的な手法（そして私が知る限り、これはまだ最先端です）は、NNMA、または非負行列近似として知られています。この手法は、誤ってNNMFとも呼ばれ、Fは因数分解を表します。（NNMAは因数分解手法に基づいていますが、結果は元のデータマトリックスの因数ではありません。）この代替用語は正しくないものの、広く使用されているため、検索エンジンのクエリに含めます。

本質的に、この手法を使用して、マトリックスからスパース性を削除するか、別の言い方をすれば、欠落しているセルにデータを入力できます（つまり、行Rの顧客は列Cの製品を再表示していません）。

付属のチュートリアル（python + numpy）を含むnnmaの完全な実装は、Albert AuYeungChing -manのブログにあります。

または、NNMAのパッケージコードを含むいくつかのPythonパッケージ（PyPI経由で入手可能）があります。私はこれらのうちの1つ、GoogleCodeで見つけることができるPyMFのみを使用しました。

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」を含む2D配列（行列）を渡すだけです（つまり、欠落している値ごとに「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です。

于 2012-05-07T10:52:40.530 に答える
4

あなたが見逃している部分は、距離を測定するための方法です。ピアソン相関は、最も広く使用されている方法の1つです。コサイン距離は別のものです。L1距離（差の絶対値の合計）は通常、良い結果をもたらしません。

グーグルで検索すると、使用する類似距離に基づいて欠落値を処理するための推奨される方法がわかります。たとえば、ピアソンでは、2人のユーザーによって一般的に評価された本のみが相関の測定に使用されるため、欠落している値は単に無視されます。これは理にかなっています。まるで、2人のユーザーが読んだ本のごく一部が共通しているかのように、それはおそらく異なる趣味を持っていることを意味します。コサイン距離では、欠落値はゼロと見なすことができます。

他の一般的に使用されるアプローチは、欠落値を代入することです。たとえば、最初にピアソンを使用して本間の類似性を見つけ、次に各人について欠落している評価を予測することができます。

于 2012-05-07T08:57:30.100 に答える
2

KNN is usually sensitive to #features. In real life, I expect you are going to have much more books.

I would try to change the features space: instead of having a feature for each document, maybe it worth investigating using lists of books as features.

Feature1 = { books with score 1 }
Feature2 = { books with score 2 }
...

Now, you can define distance for each feature - maybe by using recall and precision between each two lists of 2 users.

Another advantage of this method is you can easily give weight to features - maybe the list of books ranked as 5 is more informative then the one ranked with 3?

The disadvantage is clear, you will not gain any boost if users A,B ranked a book with 4,5 - however it can also be solved by adding another feature, comparing these lists between two users..

Disclaimer: I never tested this method, and I have no idea how it will behave - but I think it is an approach worth investigating. I think there is no good way to determine if this suggestion will give good results except empirical testing, which can be done using cross-validation from your training set.

于 2012-05-06T17:45:34.383 に答える