あなたにオススメの〜的なサービスを実装する（アルゴリズム改良版）

前回までは、数式通りにゴリゴリとレコメンド行列を作成していきましたが、前回のプログラムでは計算量がO(m^3)になってしまいます。(mはユーザーデータの量)

したがって、ユーザーが1000人、2000人と増えていくに連れて、一気にプログラムの速度が落ちます。
今回は、前回と同様の計算を行う上でより効率的なプログラムを紹介します。
このプログラムでは、理論的に計算量がC(mn)になります。(nはアイテムの個数)

ただし、今回はユーザーが2つのアイテムだけ購入する前提で作成しました。

まずは、前回のプログラムの実行時間を計測できるようにします。

import numpy as np
from random import randint
import time

def generateTable(m, n):
    a = np.zeros([m, n])
    for row in range(0, m):
        col1 = int(randint(0, n - 1))
        a[row][col1] = 1
        
        col2 = int(randint(0, n - 1))
        while col2 == col1:
            col2 = int(randint(0, n - 1))
        a[row][col2] = 1
    return a

start = time.clock()

m, n = 1000, 42
A = generateTable(m, n)

# create association table
fav_table = []
for i in range(len(A[0])):
	fav_row = []
	for j in range(len(A[0])):
		fav_row.append([])
		fav_row[j] = 0
		for k in range(len(A)):
			fav_row[j] += A[k][i] * A[k][j]
	fav_table.append(fav_row)

# calculate association rate from table
transposed = [[row[i] for row in fav_table] for i in range(len(A[0]))]
def add(x, y): return x + y
sum_table = [reduce(add, transposed[i]) for i in range(len(transposed))]

for i in range(len(fav_table)):
	for j in range(len(fav_table[0])):
		fav_table[i][j] /= float(sum_table[j])

end = time.clock()
time = end-start
time = str(round(time, 3))
print 'Older Process: ' + time + 'second'

今回は、ユーザーのアイテム購入データが1000件、アイテム数が42個として計算します。

これを実行した結果、4.3秒ほどの時間がかかりました。

続いて新しいプログラムを紹介します。

import numpy as np
from random import randint
import time

def generateTable(m, n):
    a = np.zeros([m, n])
    for row in range(0, m):
        col1 = int(randint(0, n - 1))
        a[row][col1] = 1
        
        col2 = int(randint(0, n - 1))
        while col2 == col1:
            col2 = int(randint(0, n - 1))
        a[row][col2] = 1
    return a

def createRawAssociate(a, m, n):
    b = np.zeros([n, n])
    for k in range(0, m):
        findAssociate(a, b, n, k)
    b_tran = np.transpose(b)
    return b + b_tran

def findAssociate(a, b, n, k):
    col1, col2 = 0, 0
    for j in range(0, n):
        if a[k][j]:
            col1 = j
            break
    for l in range(col1 + 1, n):
        if a[k][l]:
            col2 = l
            break
    b[col1][col2] += 1

def totalVector(b, n):
    c = np.zeros(n)
    for j in range(0, n):
        for k in range(0, n):
            c[j] += b[k][j]
    return c

def createAssociateTable(b, c, n):
    d = np.zeros([n, n])
    for i in range(0, n):
        for j in range(0, n):
            if c[j]: d[i][j] = round(b[i][j] / c[j], 2)
    return d

start = time.clock()

m, n = 1000, 42
A = generateTable(m, n)
B = createRawAssociate(A, m, n)
C = totalVector(B, n)
D = createAssociateTable(B, C, n)

end = time.clock()
time = end-start
time = str(round(time, 3))
print 'Process: ' + time + 'second'