ユーザ行動分析に基づく推奨アルゴリズム

文書ディレクトリ

ユーザ行動分析に基づく推奨アルゴリズム

ユーザ行動データ概要

ユーザ行動分析

ユーザの活躍度と物品の流行度の分布

ユーザの活躍度と物品の流行度の関係

実験設計とアルゴリズム評価

データセット

実験設計

評価指標

レルムベースのアルゴリズム

ユーザによる協同フィルタリングアルゴリズム

ソースコード実装

ユーザ行動分析に基づく推奨アルゴリズム
このアルゴリズムは協同フィルタリングアルゴリズムと呼ばれ、協同フィルタリングとは、ユーザーが協力して、絶えずウェブサイトとやり取りすることで、自分の推薦リストが自分の興味のないものをフィルタリングし、ますます自分のニーズを満たすことができることを意味します.
ユーザ動作データの概要
ユーザーの動作データの最も簡単な存在形式はログです.多くのインターネットビジネスでは、元のログをユーザーの行動に従ってセッションログ(session log)にまとめ、各セッションは、ログを表示したり、ログをクリックしたりするユーザーの行動と対応するサービスを表します.ユーザ行動は、パーソナライズされた推奨システムにおいて、一般に、顕著なフィードバック行動(explicit feedback)と隠れたフィードバック行動(implicit feedback)に分けられる.explicit feedbackには、ユーザが物品の好みを明確に示す行為が含まれる.implicit feedbackとは、ユーザの好みに明確に反応できない行為を指す.explicit feedbackと比較して,暗黙的なフィードバックは明確ではないが,膨大な数である.
ゆうせいフィードバックデータ
隠性フィードバックデータ
ユーザーの興味
はっきりした
はっきりしない
数量
ごくわずか
膨大である
きおく
データベース#データベース#
分散ファイルシステム
リアルタイム読み取り
リアルタイム
遅延あり
正負フィードバック
すべてある
正のフィードバックのみ
ユーザ行動解析
ユーザー行動データを利用して推奨アルゴリズムを設計する前に、まずユーザー行動データを分析し、データに含まれる一般的な法則を理解しなければならない.そうすれば、アルゴリズムの設計に指導的な役割を果たすことができる.以下のユーザ行動データの一般的な法則.
ユーザーの活躍度とアイテムの流行度の分布
インターネット上の多くのデータ分布はpower Lawも長尾分布と呼ばれている.
f ( x ) = α x k f(x)=\alpha x^k f(x)=αxk研究により,ユーザ行動データもpower law分布,f i(k)f_を満たすことが分かった.i(k)fi(k)は、k個のユーザによって行動が生じるアイテム数であり、f u(k)f_u(k)fu(k)は、k個の物品に対して行動を起こすユーザ数である.すなわちf i(k)=α i k i β f_i(k)=\alpha_i k^\beta_i fi​(k)=αi​kiβ​ f u ( k ) = α u k u β f_u(k)=\alpha_u k^\beta_u fu​(k)=αu​kuβ​
ユーザーの活躍度とアイテムの流行度の関係
この法則によれば,ユーザが活発であればあるほど,冷たいものに傾いていることがわかる.ユーザ行動データのみに基づいて設計される推奨アルゴリズムは、一般に協同フィルタリングアルゴリズムと呼ばれる.学界は協同フィルタリングアルゴリズムに対して多くの方法を提案した.例えば、分野ベースの方法、隠語義モデル、図ベースのランダムウォークアルゴリズムなどである.最も広く使われているのは、
ユーザの協同フィルタリングアルゴリズムに基づいて、このアルゴリズムは、ユーザに、彼の興味と類似する他のユーザが好む物品を推薦する.
物品に基づく協同フィルタリングアルゴリズムこのアルゴリズムは、以前に好きだった物品に似た物品をユーザに推薦する.
実験設計とアルゴリズム評価
データセット
GroupLensが提供するMovieLensデータセットを採用し、このデータセットは3つの異なるバージョンを含み、中程度のサイズのデータセットを選択し、6000人以上のユーザーが4000本以上の映画に対する100万件のスコアを含む.このデータセットは、スコア付きデータセットです.ステルスフィードバックデータセットのTopN推奨問題を重点的に検討するため,データセットのスコア記録を無視する.TopNの推奨任務は、ユーザーが映画の採点を準備する前提で映画に何点を与えるかを予測するのではなく、ユーザーが映画の採点を予測することである.
じっけんせっけい
まず,ユーザ行動データセットを均一にランダムにM部(M=8)に分け,テストセットとして1部を選択し,残りをトレーニングセットとした.トレーニングセットにユーザー興味モデルを構築し、テストセットでユーザーの行動を予測し、対応する評価指標を統計する.評価指標がオーバーフィットした結果ではないことを保証するために、M回の試験を行い、毎回異なる試験セットを使用する必要がある.次にM回試験の評価指標の平均値を最終的な評価指標とした.次のコードは、ユーザスコアファイルのデータをトレーニングセットのテストセットに分割するプロセスです.

def get_datas(input_file,M,k,seed) : #                    
    """
    get rating information
    Args: 
        input_file:user rating file
        M：        
        k:         
        seed：     
    Return: two lists
       one:train datas
       another:test datas
    """
    if not os.path.exists(input_file) :
        return [],[]
    linenum = 0
    train_data = []
    test_data = []
    fp = open(input_file)
    random.seed(seed)
    for line in fp :
        if linenum == 0 :
            linenum += 1
            continue 
        item = line.strip().split(',')
        if len(item) < 4:
            continue
        if random.randint(0,M) == k :
            test_data.append([item[0],item[1],item[2]])
        else :
            train_data.append([item[0],item[1],item[2]])
    fp.close()
    return train_data,test_data

ここで,異なるkと同じランダム種子seedを選択するたびに,M回の実験を行うとM個の異なる訓練セットと試験セットが得られ,その後それぞれ実験を行い,M回の実験の平均値を最後の評価指標とした.このようにするのは,ある実験結果がオーバーフィットした結果であることを防止するためである.
評価指標

精度/リコール率ユーザuに対してN個の物品を推奨し、(R(u)R(u)R(u))と記載し、ユーザがテストセット上で好む物品の集合を(T(u)T(u)T(u)とする.次に,推奨アルゴリズムの精度:r e c a l l=Σu∣R(u)a n d T(u)Σu∣T(u)∣T(u)∣recall=frac{ sum_u|R(u)and T(u){sum_u|T(u)|}recall=Σu∣T(u)∣R(u)andT(u)p r e c i s i o n=Σu∣R(R(u)andT(u)p r e c i s i o n=Σu(R(u)R(u(u)andT(u)andT(u(u)p p r r r r r r r r e c i i s i u)a n d T(u)Σu∣R(u)∣precision=frac{sum_u|R(u)and T(u)}{sum_u|R(u)|}precision=Σu∣R(u)∣R(u)andT(u)リコール率は、最終的な推奨リストに含まれるユーザ−物品スコアレコードの割合の割合を記述し、精度は、最終的な推奨リストにおいて発生したユーザ−スコアレコードの割合を記述する.

カバー率カバー率は推薦アルゴリズムが長尾を発掘する能力を反映し、カバー率が高いほど、推薦アルゴリズムが長尾中の物品をユーザーに推薦できることを示している.C o v e r a g e = ⋃ u ∈ U R ( u ) I Coverage=\frac{\bigcup_{u\in U}R(u) }{I} Coverage=I⋃u∈U​R(u)​

新規度推薦リストの中の物品の平均流行度で推薦結果の新規度を測定し、推薦された物品がいずれも人気がある場合、推薦の新規度が低いことを説明し、そうでなければ推薦結果が比較的新規であることを説明する.

レルムベースのアルゴリズム
ユーザベースの協同フィルタリングアルゴリズム
ユーザーベースの協同フィルタリングアルゴリズムは、同じ趣味の人が好きなものをお勧めします.次の2つのステップがあります.

ターゲットユーザの関心と同じユーザセットを見つける

は、このセットのユーザが好むものを見つけ、ターゲットユーザが聞いたことのないものをターゲットユーザ

に推薦する.
ステップ1の鍵は,2人のユーザの興味類似度を計算することである.ここでは,主に行動の類似度を用いて興味の類似度を計算する.ユーザu u及びv v vが与えられ、N(u)N(u)N(u)をユーザu uがかつて正のフィードバックをした物品集合とし、N(v)N(v)N(v)をユーザv vがかつて正のフィードバックをした物品集合とする.計算方法は2つあります.

jaccard式:Wuv=∣N(u)⋂N(v)∣N(u)⋃N(v)∣W_{uv}=\frac{|N(u)\bigcap N(v)|}{|N(u)\bigcup N(v)|} Wuv​=∣N(u)⋃N(v)∣∣N(u)⋂N(v)∣​

余弦類似度計算:Wuv=∣N(u)⋂N(v)∣N(u)∣N(v)∣W_{uv}=\frac{|N(u)\bigcap N(v)|}{\sqrt{|N(u)||N(v)|}} Wuv​=∣N(u)∣∣N(v)∣ ​∣N(u)⋂N(v)∣​

ソース実装

import os
import math
import  numpy as np
import random
NumOfMovies = 9000
NumOfUsers = 700

def get_data(file):
    """
        
    """
    if not os.path.exists(file):
        return {}
    fp = open(file)
    data = {}
    linenum = 0
    for line in fp:
        if linenum == 0:
            linenum += 1
            continue
        line = line.split(',')
        userid,itemid = int(line[0]),int(line[1])
        if userid not in data:
            data[userid] = []
        data[userid].append(itemid)
    fp.close()
    return data

def split_data(data,M,k,seed):
    #              
    test = {}
    train = {}
    random.seed(seed)
    for user,items in data.items():
        for i in items:
            if random.randint(0,M) == k:
                if user not in test:
                    test[user] =[]
                test[user].append(i)
            else:
                if user not in train:
                    train[user] = []
                train[user].append(i)
    return train,test

def UserSimilarity(train):
    #        W
    #         
    item_user = {}
    for u,items in train.items():
        for i in items:
            if i not in item_user:
                item_user[i] = []
            item_user[i].append(u)
    #  C[u][v] u v        
    C = {}
    N = np.zeros([NumOfUsers],dtype = np.int32)
    user_related = {}
    for i,users in item_user.items():
        for u in users:
            N[u] += 1
            if u not in C:
                C[u] = {}
            for v in users:
                if u == v:
                    continue
                if v not in C[u]:
                    C[u][v] = 0
                C[u][v] += (1/math.log(1+len(users)))
                if u not in user_related:
                    user_related[u] = []
                user_related[u].append(v)
    #       W
    W = np.zeros([NumOfUsers,NumOfUsers],dtype = np.float)
    for u,users in C.items():
        for v in users:
            W[u][v] += C[u][v] / math.sqrt(N[u] * N[v])
    return W ,user_related

def recommend(User,train,K,N,W,user_related):
    #      W       record
    k_user = {}
    rank ={}
    
    for v in user_related[User]:
        k_user[v] = W[User][v]
    k_user = sorted(k_user.items(),key = lambda x:x[1],reverse = True)[:K]
    for v,w in k_user:
        for item in train[v] :
            if item in train[User]:
                continue
            if item not in rank:
                rank[item] = 0
            rank[item] += w
    rank = sorted(rank.items(),key = lambda x:x[1],reverse = True)[:N]
    return rank

def Recall(train,test,N,k,W,user_related):
    #     
    hit = 0
    totla = 0
    for user in train:
        tu =test[user]
        rank = recommend(user,train,k,N,W,user_related)
        for item in rank :
            if item[0] in tu :
                hit += 1
        totla += len(tu)
    return hit/(totla*1.0)
    
def Precision(train,test,N,k,W,user_related):
    #     
    hit = 0
    totla = 0
    for user in train:
        tu =test[user]
        rank = recommend(user,train,k,N,W,user_related)
        for item in rank :
            if item[0] in tu :
                hit += 1
        totla += len(rank)
    return hit/(totla*1.0)


if __name__ == "__main__":
    data = get_data(r"F:\       \UserCF\data\ratings.csv")
    train,test = split_data(data,2,1,1)
    del data
    W,user_relatde = UserSimilarity(train)
    recall = Recall(train,test,10,10,W,user_relatde)
    precision = Precision(train,test,10,10,W,user_relatde)
    print(recall,precision) 

注:以上は「推薦システム実践」という本を参考にする.