狠狠撸

「これを買っている人はこれも買っています」
実装してみた
デジタルサーカス（株）長谷川智希
side

長谷川智希
ともき
@tomzoh?
とむぞう
趣味 Webサイト開発, iOSアプリ開発
レンタルカートレース, ビール, 電子工作 (mbed), …
TOMZOH
デジタルサーカス（株）?
副団長CTO
Facebook CakePHP iOS

デジタルサーカス（株）
? Webサイト開発
? スマホアプリ開発
? 自社サービス
（）
（iOS, Android)
（http://appbuilder.jp）
Twitter: @tomzoh

今日のテーマ:
「これを買っている人はこれも買っています」
実装してみた
side

Toby Segaran?著
當山仁健、鴨澤眞夫?訳
出版社: オライリージャパン
2008年07月発行
392ページ
ISBN978-4-87311-364-7
http://www.amazon.co.jp/dp/4873113644

2章
推薦を行う
「この映画に高い評価をした人は、こんな
映画にも高い評価をしています。」のアルゴ
リズム。
?自分に似ている人は誰か
?この映画に似ている映画は何か

# 映画の評者といくつかの映画に対する彼らの評点のディクショナリ?
critics={
'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'Superman Returns': 3.5,
'You, Me and Dupree': 2.5, 'The Night Listener': 3.0},
'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5, 'Just My Luck': 1.5, 'Superman Returns':
5.0, 'The Night Listener': 3.0, 'You, Me and Dupree': 3.5},
'Michael Phillips': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0, 'Superman Returns': 3.5, 'The Night
Listener': 4.0},
'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'The Night Listener': 4.5, 'Superman Returns': 4.0,
'You, Me and Dupree': 2.5},
'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 'Just My Luck': 2.0, 'Superman Returns': 3.0,
'The Night Listener': 3.0, 'You, Me and Dupree': 2.0},
'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 'The Night Listener': 3.0, 'Superman
Returns': 5.0, 'You, Me and Dupree': 3.5},
'Toby': {'Snakes on a Plane':4.5,'You, Me and Dupree':1.0,'Superman Returns’:4.0}
}

「これを买っている人はこれも买っています」実装してみた PHP side

やりたいこと
? 「このリポジトリにスターした?はこんなリポジ
トリにもスターしています」
? ?ると嬉しいであろうリポジトリをお勧めして
くれるシステム！

推薦: 2つの?法
（1）?分に似たユーザを探して、そのユーザが
スターしているリポジトリを推薦する。
（2）?分がスターしているリポジトリについて、
似たリポジトリを探して推薦する。

「似ている」
どうやって「似ている」と判断するか。

「似ている」
どうやって「似ている」と判断するか。
「似ている」 = 「近い」

ユークリッド距離
63
2
3

sqrt((6-3)^2 + (2-3)^2) = 3.16…
63
2
3 3.16…

John Steve Tim Philip
The Shawshank Redemption 1 1 2 2
The Man in the Iron Mask 2 1 4 1
ID4 2 3
The Devil Wears Prada 3 5 4

ID4 2 3
JohnとSteveの距離:

ID4 2 3
sqrt((1-1)^2 + (2-1)^2 + (2-0)^2 + (3-5)^2))

ID4 2 3
sqrt((1-1)^2 + (2-1)^2 + (2-0)^2 + (3-5)^2))
( - )^2 +
( - )^2 +
( - )^2 +
( - )^2

John - 3 4.2 2
Steve * - 5.9 3.3
Tim * * - 5.8
Philip * * * -

John - 3 4.2 2
Steve * - 5.9 3.3
Tim * * - 5.8
Philip * * * -
John - 3 4.2 2
Steve * - 5.9 3.3
Tim * * - 5.8
Philip * * * -
TimにはJohnが?た映画を推薦すれば良さそう

ID4 2 3

ID4 2 3
ID4 2 3

http://www.amazon.co.jp/dp/B0083RQI0S
BUY NOW

? Repo
88,811 twbs/bootstrap
45,137 vhf/free-programming-books
44,106 angular/angular.js
43,279 mbostock/d3
37,667 nodejs/node-v0.x-archive
36,648 jquery/jquery
31,681 h5bp/html5-boilerplate
31,461 FreeCodeCamp/FreeCodeCamp
31,080 facebook/react
29,881 robbyrussell/oh-my-zsh
29,651 meteor/meteor
29,413 github/gitignore
28,336 rails/rails
27,248 torvalds/linux
27,111 Homebrew/homebrew

User
mvied
dcwatson
christophwille
rpoisel
victoriafrench
runcom
brynary
marceloemanoel
ysrb
Caged
anotherjesse
kevwil
rsanheim
BrianTheCoder
lancecarlson
kvnsmth
josh
? Repo
88,811 twbs/bootstrap
45,137 vhf/free-programming-books
44,106 angular/angular.js
43,279 mbostock/d3
37,667 nodejs/node-v0.x-archive
36,648 jquery/jquery
31,681 h5bp/html5-boilerplate
31,461 FreeCodeCamp/FreeCodeCamp
31,080 facebook/react
29,881 robbyrussell/oh-my-zsh
29,651 meteor/meteor
29,413 github/gitignore
28,336 rails/rails
27,248 torvalds/linux
27,111 Homebrew/homebrew

骋颈迟贬耻产のデータ数

リポジトリ約1千400万ユーザ约1千600万

mvied dcwatson rpoisel ysrb
twbs/bootstrap
vhf/free-programming-books
angular/angular.js
:
?
?
? ?
? ??
?

twbs/bootstrap
angular/angular.js
:
ユーザ约1千600万
?
?
? ?
? ??
?

twbs/bootstrap
angular/angular.js
:
ユーザ约1千600万リポジトリ約1千400万
?
?
? ?
? ??
?

リポジトリとリポジトリの距離を計算
(14,000,000 x 14,000,000 - 14,000,000) / 2 = 100兆回の組合せ計算
計算1回あたり
16,000,000回の2乗計算
twbs/bootstrap
angular/angular.js
:
?
?
? ?
? ??
?

リポジトリとリポジトリの距離を計算
(14,000,000 x 14,000,000 - 14,000,000) / 2 = 100兆回の組合せ計算
計算1回あたり
16,000,000回の2乗計算
twbs/bootstrap
angular/angular.js
:
?
?
? ?
? ?
?つらい
?
?

リポジトリ ? スターを付けたユーザの一覧
twbs/bootstrap 88,811 mvied dcwatson ysrb …
vhf/free-programming-books 45,137 mvied dcwatson rpoisel …
angular/angular.js 44,106 dcwatson ysrb …
:

:
リポジトリ350件☆6,700以上ぐらい

:
リポジトリ350件☆6,700以上ぐらい
ユーザ最?88,811

? スターを付けている: 1 付けていない: 0
? リポジトリ間のユークリッド距離を計算

twbs/bootstrap
vhf/free-
programming-books
angular/angular.js …
twbs/bootstrap - 0.01904850 0.00492629
vhf/free-
programming-books * - 0.00492461
angular/angular.js * * -
:

GitHub recommender
http://ghrec.hasegawa-tomoki.com
? 骋颈迟贬耻产のユーザ名を??すると?
おすすめリポジトリを表?
? APIで?を付けているリポジトリ取得 →
そのリポジトリに似ているリポジトリを推薦

骋颈迟贬耻产のユーザ名

GitHub recommender

GitHub recommender
? 取得: ?数上位6,800リポジトリ

GitHub recommender
? 計算: ?数上位350リポジトリ

GitHub recommender
? 計算量ナメてて間に合わなかった

GitHub recommender
? これが O(n^2) というやつか…
? 計算量ナメてて間に合わなかった

わかったこと
? APIでデータを取るのにすごく時間がかかる。
? リポジトリ間の距離を計算するのにすごく時間がかかる。
? このクラスの計算量になると最初からまじめにプログラム
をチューニングしないといつまでたっても終わらない。
? memcachedの圧縮は素晴らしい。
? 超簡単な割にそれなりにそれっぽい結果が出るので楽
しい。

どの程度「それらしい」か

GitHub API
? 時間あたりの利?可能数が制限されている。
? レイテンシは1秒ぐらい。
? 全てのレコードが取得できる訳では無い。
? ページ数を指定して取得することになるけど「これ以上は取れないよ」とレ
スポンスが帰ってくる。
? 「リポジトリをスター数の降順で」は結構?倒。
? 検索条件にリポジトリ作成?時、スター数を?れて複数回コール。

?を取得するAPI
https://api.github.com/repos/twbs/bootstrap/stargazers

こういうのを作って
計算状況がわかる様にすると
精神衛?上良い。

2次会やります！
この近くのシャレオツな（？）
お店で終電前まで

ありがとうございました
@tomzoh
デジタルサーカス（株）
Drupal & スマホエンジニア
絶賛募集中！

狠狠撸

「これを买っている人はこれも买っています」実装してみた PHP side

Recommended

More Related Content

Similar to 「これを买っている人はこれも买っています」実装してみた PHP side (20)

More from Tomoki Hasegawa (20)

「これを买っている人はこれも买っています」実装してみた PHP side