レコメンデーション発展　検索エンジンの作成3

[Aidemy](https://aidemy.net/)　2020/12/3
#はじめに
　こんにちは、んがょぺです！バリバリの文系ですが、AIの可能性に興味を持ったのがきっかけで、AI特化型スクール「Aidemy」に通い、勉強しています。ここで得られた知識を皆さんと共有したいと思い、Qiitaでまとめています。以前のまとめ記事も多くの方に読んでいただけてとても嬉しいです。ありがとうございます！
　今回は、レコメンデーション発展の3つ目の投稿になります。どうぞよろしくお願いします。

＊本記事は「Aidemy」での学習内容を「自分の言葉で」まとめたものになります。表現の間違いや勘違いを含む可能性があります。ご了承ください。

今回学ぶこと
・ページの重み付け
・ランキングの作成

#コンテンツベースフィルタリング
##Webページを重み付け
・Chapter2までで、__URLを取得することはできる__ようになったが、__表示される順番__はクローリングされた順番であった。ここでは、取得した情報をもとに__各Webページに重み付けを行う__。重みを評価する関数__「評価関数」__には様々なものがあり、基本的には__Webページの推薦度と相関のあるもの__を選べば良い。

##対象の単語の出現回数で重み付け
・重み付けの基準で最も単純なのが__「単語の出現回数」__である。出現回数は「0~1」に変換する、すなわち__正規化__して比較する。ここでは、正規化を行う関数__「normalizescores()」__と、単語の頻度を計算する関数__「frequeryscore()」__を作成する。
・まずは「normalizescores()」について、__値が小さい方と値が大きい方のどちらを推薦度の高いものと扱うか__を決めて、正規化を行う。値が小さい方である場合（small_flagが1である時）、値が0だと推薦度が無限になってしまうので、初めに__「vsmall」__として十分に小さい数値を__閾値__として設定する。関数に渡された「scores」のうち、最小のものを「minscore」とする。返り値は__{URL:正規化した出現回数}__という辞書にしたいので、「URL」部分は__「scores.items()」__の1つ目（url）とし、「出現回数部分」についてはminscoreを、__「vsmallかscores.items()の2つ目（l）の内大きい方」__で割る事で正規化を行い、格納する。値が大きい方を推薦度が高いものと見なすときも、これと同様に実装すれば良い。

・単語の出現回数を計算する関数「frequeryscore()」については、Chapter2で作成した「get_match_rows」関数により得られるURL「rows」のそれぞれ(row)について、__{row[0]:0}__というような辞書に変換し、countsという変数に格納する。このrow[0]の部分に、単語「row」が出てきたら「+1」とし、全て数え終わったら、「normalizescores」にこれを渡したものを返り値とする。

・コード![スクリーンショット 2020-12-02 0.08.07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/fc54d77d-c071-a1f1-bfc6-28e33aeac352.png)


##単語の位置による重み付け
・検索したい単語が__Webページの上部にあるほど__、それがトピックである可能性が高いと考えられる。ここでは、この観点から、__「単語の出現した位置の和」__で重みを算出する関数__「locationscore()」__を作成する。
・実装のアルゴリズムとしては、「locations」という__{単語：重み}__の辞書を作成し、引数で渡されたクエリrowsのそれぞれ（row）について、__1列目以降の合計値__についてを重みとみなして変数locationに格納し、これがrow[0]の重みよりも__小さければ__、位置がrow[0]よりも上に出現しているとみなせるので、これを新たなrow[0]として更新する。全てについて評価し終わったら、normalizascores()にlocationsを渡して正規化を行う。この時、推薦度は「値が小さい方」を大とするので、__small_flagは1__とする。

・コード![スクリーンショット 2020-12-02 0.17.15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/d24b3128-0a54-7e9b-bedb-d9f6e25f7008.png)

##単語間の距離による重み付け
・複数の単語を検索するとき、それらの__単語の距離が近いほど__求めている内容に近い可能性が高いと言える。今回は、単語間の距離で重みを算出する関数__「distancescore()」__を作成する。
・まず、そもそも単語が一つしかない時は、重みを算出できないので、その部分については重みを1として返す。また、前項と同じで、初期値（mindistance）は十分大きな値に設定しておく。
・あとは、実際に__単語間の距離（dist）__を計算する。「2~単語の数」の長さの「i」について、__「abs(row[i]-row[i-1])」__とすることで計算できる。この合計値をdistとする。そして、これがmindistanceのrow[0]より__小さければ__、前項と同じように単語間の距離がより近いということになるので、これに値を更新する。

・コード![スクリーンショット 2020-12-02 1.04.59.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/9ced9984-fc41-d635-e55c-4c5013d7dabe.png)

##インバウンドリンクによる重み付け
・他サイトから__自分のサイト内のページへのリンク__のことを__「インバウンドリンク」__という。価値のあるWebページほど、__多くのページからリンクされることが多い__ため、このリンクの数で重み付けを行う。ただし、この方法は__クエリの情報を使用しない__ので、他の評価方法と合わせて使用する必要がある。
・インバウンドリンクの数を数えるには、SQL文の中で__「select count(\*) from テーブル where 条件」__と記述すれば良い。
・以下は、この数を数える関数__「inboundlinkscore()」__を作成したものである。まずは引数で渡されたrowsのそれぞれから、__set()__で重複が無いようにURLを取得する（uniqueurls）。そして、__{URL:リンクの数}__となっている辞書を作成する。「URL」部分はuniqueurlのそれぞれ(url)を格納すればよく、「リンクの数」部分は「linkテーブルのうち、url_to(遷移先のURL)が'url'となっているものの数」を格納すれば良い。


・コード![スクリーンショット 2020-12-02 12.15.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/ea9c97f3-d1d1-9f56-58b1-d3a295ca7557.png)

#PageRank
##PageRankについて
・__PageRank__はGoogleの創設者によって作られたもので、「そのページが全ページからして__どの程度大切なのか__」を割り当てるアルゴリズムである。__他ページからのリンクが多いページのランキングを高くし__、また、__ランキングの高いページからのリンクは高く評価する__という特徴がある。
・PageRankは、学習率を$\gamma$とすると、__「$\gamma$×(リンク元のPageRank / リンク元のリンク先の数)」の和__で算出できる。以下の図について、$\gamma$=1とした時、AのPageRankを求める式は「(3.0/3)+(6.0/2)+(0.5/1)」で、値が「4.5」となる。


![スクリーンショット 2020-12-02 13.30.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/75d819c6-c224-985e-2341-3c9a0510a607.png)

##PageRankの計算
・ここでは実際にPageRankを計算していく。前項の方法では、__「リンク元のPageRank」が全て求まっていれば__例のように簡単に計算できたが、今回の場合はそうはいかないので、このような場合は__「初期値に任意の数を与え、PageRankの計算を何度か繰り返す」__事で、それぞれのPageRankが真の値に近づいていくので、これを利用する。
・このアルゴリズムは以下のようになる。
　1:pagerankテーブルがすでにあれば削除する
　2:pagerankテーブルを作成（カラムは「url」「score」）
　3:URLカラムにそれぞれのURL、scoreカラムに__初期値を与える__
　4:全てのURLで__PageRankを計算する__
　5:PageRankを__更新する__

・「1」について、テーブルの削除は__「drop table if exists テーブル」__のようにすれば良い。
・「2」について、テーブルの作成は__「create table テーブル(カラム)」__と記述する。
・「3」について、カラムの値の代入は__「insert into テーブル select 値」__で記述する。値部分に他のカラムの持つ値を入れるときは、文末に「from」を追加する。
・「4」について、PageRankの計算には__「リンク元のPageRank」__と__「リンク元のリンク先の数」__が必要なので、各URLについて(url)、linkテーブル内で、リンク先（url_to）がurlであるリンク元（url_from）を「linker」として、「select score from pagerank」で、urlカラムの値がlinkerであるもののscoreを取得する。また、__「select count(\*) from link」__でurl_fromがlinkerであるものの数を取得すれば良い。
・この二つについて、あらかじめ設定した$\gamma$と合わせて、前項のように計算すれば良い。
・「5」について、値の更新は__「update テーブル set カラム = 更新する値 where 条件式」__で行える。更新したら、「conn.commit()」を忘れないようにする。
・この更新までを、引数で与えられた「iterations」の回数分（デフォルト3）行うことで、真のPageRankの値に近づく。

・コード![スクリーンショット 2020-12-02 16.12.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/eb41cde9-7e7c-b294-2718-5aed5485e7d7.png)

##PageRankで重み付けを行う関数の作成
・前項で算出したPageRankを使って重み付けを行う関数__「pagerankscore()」__を作成する。具体的には、__{URL:PageRank}__の辞書を作成する。それぞれのrowについて、pagerankテーブルから、対応するurl（row[0]）のscoreを取得すれば良い。
・ちなみに、ここまでにconn.execute()についてきた__「fetchone()[0]」__は、値を取得するとき、selectメソッドのままではそれが__リスト形式__で取得されてしまうため、fetchone()でリストの一番最初（値）を指定し、__[0]で値のみ取得できるようにしている__。

・コード![スクリーンショット 2020-12-02 16.37.55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/8435a15d-c9c8-5af5-ee93-3a447c604b98.png)

#seacherをクラスにまとめる
##初期値の設定
・検索に関する物をまとめて__「seacher」__というクラスにまとめる。これが、__実際の検索エンジンとなる__。sercherクラスの実装は以下のようになる。
　1:クエリを受け取り、クエリの含まれるページの__URLを取得する__（Chapter2の__get_match_rows__関数）
　2:取得したURLを、評価関数によって__重み付けする__（このChapterで実装してきた関数）
　3:評価値の高いものから__レコメンドする__（これから実装する__query__関数）

・「2」について、ここまでで作成してきた評価関数について、get_match_rows関数によって得られるURL「rows」を渡して、最終的な評価値「totalscore」を返す関数__「weightlist()__」を作成する。
・まずは「totalscore」を定義する。これは__{URL:評価値}__とする。URLは今まで通りrow[0]で取得できる。評価値は__初期値0で定義する__。
・次に、それぞれの評価関数で重みから評価値を算出したもののリスト__「weights」__を作成する。評価関数自体の重みは1とする。
・最後に、__「重み×そのURLの評価値」__で__totalscores__を算出する。それぞれのURLについて、全ての評価関数の評価値の合計が最終的なtotalscoresとなる。

・「3」の__query__関数について、__get_match_rows()__と__weightlist()__を使って評価値(scores)を算出する。__scores.items()__は(url,score)となっているが、scoreについてランキングにしたいので(score,url)と__並び替え__、これについて__降順にsortする__ことでランキングとする。最後にランキング上位からいくつか（今回は10個）レコメンドの候補をリストにして返す。

・コード![スクリーンショット 2020-12-02 17.41.49.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/bb1c931d-d1aa-0f1f-f044-16981d5497aa.png)

・ここまで終わったら、あとはこれらの関数を全てsearcherクラスにまとめ、引数や関数について「self」をつけて完成となる。以下は、このクラスを使って実際に検索した結果である。クラスは「s」に格納し、クラスメソッドである「query」関数を__「s.query」__として呼び出している。

![スクリーンショット 2020-12-02 18.25.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/0786fffd-eab4-d238-e0e0-dd338151c85a.png)

#まとめ
・今回は、取得したURLを、__より推薦度の高いものから順に表示させる__ことを目標とした。推薦度の高さは、__単語の数や位置、単語間の距離、インバウンドリンクの数__で重み付けを行って算出するほか、__PageRank__を使ってリンクの関係から重み付けを行うこともできる。
・重み付けでは、__正規化__を行って算出する。また、PageRankのほうは、__初期値を与えて計算を繰り返す__ことで真の値に近づくようにしている。
・重み付けが終わったら、全ての手法で算出された重みの値が大きいものから順にランキングを作成し、上位からレコメンドしていけば良い。

今回は以上です。最後まで読んでいただき、ありがとうございました。