Coverage for hopwise/model/general_recommender/itemknn.py: 77%

1# @Time : 2020/8/18 

2# @Author : Zihan Lin 

3# @Email : linzihan.super@foxmail.com 

4 

5r"""ItemKNN 

6################################################ 

7Reference: 

8 Aiolli,F et al. Efficient top-n recommendation for very large scale binary rated datasets. 

9 In Proceedings of the 7th ACM conference on Recommender systems (pp. 273-280). ACM. 

10""" 

11 

12import numpy as np 

13import scipy.sparse as sp 

14import torch 

15 

16from hopwise.model.abstract_recommender import GeneralRecommender 

17from hopwise.utils import InputType, ModelType 

18 

19 

20class ComputeSimilarity: 

21 def __init__(self, dataMatrix, topk=100, shrink=0, normalize=True): 

22 r"""Computes the cosine similarity of dataMatrix 

23 

24 If it is computed on :math:`URM=|users| \times |items|`, pass the URM. 

25 

26 If it is computed on :math:`ICM=|items| \times |features|`, pass the ICM transposed. 

27 

28 Args: 

29 dataMatrix (scipy.sparse.csr_matrix): The sparse data matrix. 

30 topk (int) : The k value in KNN. 

31 shrink (int) : hyper-parameter in calculate cosine distance. 

32 normalize (bool): If True divide the dot product by the product of the norms. 

33 """ 

34 super().__init__() 

35 

36 self.shrink = shrink 

37 self.normalize = normalize 

38 

39 self.n_rows, self.n_columns = dataMatrix.shape 

40 self.TopK = min(topk, self.n_columns) 

41 

42 self.dataMatrix = dataMatrix.copy() 

43 

44 def compute_similarity(self, method, block_size=100): 

45 r"""Compute the similarity for the given dataset 

46 

47 Args: 

48 method (str) : Caculate the similarity of users if method is 'user', otherwise, calculate the similarity of items. 

49 block_size (int): divide matrix to :math:`n\_rows \div block\_size` to calculate cosine_distance if method is 'user', 

50 otherwise, divide matrix to :math:`n\_columns \div block\_size`. 

51 

52 Returns: 

53 list: The similar nodes, if method is 'user', the shape is [number of users, neigh_num], 

54 else, the shape is [number of items, neigh_num]. 

55 scipy.sparse.csr_matrix: sparse matrix W, if method is 'user', the shape is [self.n_rows, self.n_rows], 

56 else, the shape is [self.n_columns, self.n_columns]. 

57 """ # noqa: E501 

58 values = [] 

59 rows = [] 

60 cols = [] 

61 neigh = [] 

62 

63 self.dataMatrix = self.dataMatrix.astype(np.float32) 

64 

65 # Compute sum of squared values to be used in normalization 

66 if method == "user": 

67 sumOfSquared = np.array(self.dataMatrix.power(2).sum(axis=1)).ravel() 

68 end_local = self.n_rows 

69 elif method == "item": 

70 sumOfSquared = np.array(self.dataMatrix.power(2).sum(axis=0)).ravel() 

71 end_local = self.n_columns 

72 else: 

73 raise NotImplementedError("Make sure 'method' in ['user', 'item']!") 

74 sumOfSquared = np.sqrt(sumOfSquared) 

75 

76 start_block = 0 

77 

78 # Compute all similarities using vectorization 

79 while start_block < end_local: 

80 end_block = min(start_block + block_size, end_local) 

81 this_block_size = end_block - start_block 

82 

83 # All data points for a given user or item 

84 if method == "user": 

85 data = self.dataMatrix[start_block:end_block, :] 

86 else: 

87 data = self.dataMatrix[:, start_block:end_block] 

88 data = data.toarray() 

89 

90 # Compute similarities 

91 

92 if method == "user": 

93 this_block_weights = self.dataMatrix.dot(data.T) 

94 else: 

95 this_block_weights = self.dataMatrix.T.dot(data) 

96 

97 for index_in_block in range(this_block_size): 

98 this_line_weights = this_block_weights[:, index_in_block] 

99 

100 Index = index_in_block + start_block 

101 this_line_weights[Index] = 0.0 

102 

103 # Apply normalization and shrinkage, ensure denominator != 0 

104 if self.normalize: 

105 denominator = sumOfSquared[Index] * sumOfSquared + self.shrink + 1e-6 

106 this_line_weights = np.multiply(this_line_weights, 1 / denominator) 

107 

108 elif self.shrink != 0: 

109 this_line_weights = this_line_weights / self.shrink 

110 

111 # Sort indices and select TopK 

112 # Sorting is done in three steps. Faster then plain np.argsort for higher number of users or items 

113 # - Partition the data to extract the set of relevant users or items 

114 # - Sort only the relevant users or items 

115 # - Get the original index 

116 relevant_partition = (-this_line_weights).argpartition(self.TopK - 1)[0 : self.TopK] 

117 relevant_partition_sorting = np.argsort(-this_line_weights[relevant_partition]) 

118 top_k_idx = relevant_partition[relevant_partition_sorting] 

119 neigh.append(top_k_idx) 

120 

121 # Incrementally build sparse matrix, do not add zeros 

122 notZerosMask = this_line_weights[top_k_idx] != 0.0 

123 numNotZeros = np.sum(notZerosMask) 

124 

125 values.extend(this_line_weights[top_k_idx][notZerosMask]) 

126 if method == "user": 

127 rows.extend(np.ones(numNotZeros) * Index) 

128 cols.extend(top_k_idx[notZerosMask]) 

129 else: 

130 rows.extend(top_k_idx[notZerosMask]) 

131 cols.extend(np.ones(numNotZeros) * Index) 

132 

133 start_block += block_size 

134 

135 # End while 

136 if method == "user": 

137 W_sparse = sp.csr_matrix( 

138 (values, (rows, cols)), 

139 shape=(self.n_rows, self.n_rows), 

140 dtype=np.float32, 

141 ) 

142 else: 

143 W_sparse = sp.csr_matrix( 

144 (values, (rows, cols)), 

145 shape=(self.n_columns, self.n_columns), 

146 dtype=np.float32, 

147 ) 

148 return neigh, W_sparse.tocsc() 

149 

150 

151class ItemKNN(GeneralRecommender): 

152 r"""ItemKNN is a basic model that compute item similarity with the interaction matrix.""" 

153 

154 input_type = InputType.POINTWISE 

155 type = ModelType.TRADITIONAL 

156 

157 def __init__(self, config, dataset): 

158 super().__init__(config, dataset) 

159 

160 # load parameters info 

161 self.k = config["k"] 

162 self.shrink = config["shrink"] if "shrink" in config else 0.0 

163 

164 self.interaction_matrix = dataset.inter_matrix(form="csr").astype(np.float32) 

165 shape = self.interaction_matrix.shape 

166 assert self.n_users == shape[0] and self.n_items == shape[1] 

167 _, self.w = ComputeSimilarity(self.interaction_matrix, topk=self.k, shrink=self.shrink).compute_similarity( 

168 "item" 

169 ) 

170 self.pred_mat = self.interaction_matrix.dot(self.w).tolil() 

171 

172 self.fake_loss = torch.nn.Parameter(torch.zeros(1)) 

173 self.other_parameter_name = ["w", "pred_mat"] 

174 

175 def forward(self, user, item): 

176 pass 

177 

178 def calculate_loss(self, interaction): 

179 return torch.nn.Parameter(torch.zeros(1)) 

180 

181 def predict(self, interaction): 

182 user = interaction[self.USER_ID] 

183 item = interaction[self.ITEM_ID] 

184 user = user.cpu().numpy().astype(int) 

185 item = item.cpu().numpy().astype(int) 

186 result = [] 

187 

188 for index in range(len(user)): 

189 uid = user[index] 

190 iid = item[index] 

191 score = self.pred_mat[uid, iid] 

192 result.append(score) 

193 result = torch.from_numpy(np.array(result)).to(self.device) 

194 return result 

195 

196 def full_sort_predict(self, interaction): 

197 user = interaction[self.USER_ID] 

198 user = user.cpu().numpy() 

199 

200 score = self.pred_mat[user, :].toarray().flatten() 

201 result = torch.from_numpy(score).to(self.device) 

202 

203 return result