Privacy preserving neighbourhood-based collaborative filtering recommendation algorithms

Recommender systems, which recommend users the potentially preferred items by aggregating similar interest neighbours’ history data, show an increasing importance in various Internet applications. As a well-known method in recommender systems, neighbourhood-based collaborative filtering has received considerable attention recently because of its easy implementation and high recommendation accuracy. However, the risks of revealing customers’ privacy during the process of filtering have attracted noticeable public concern. Specifically, the kNN attack discloses the target user’s sensitive information by creating k fake nearest neighbours by non-sensitive information. Among the current solutions against the kNN attack, probabilistic methods showed a powerful privacy preserving effect. However, the existing probabilistic methods neither guarantee enough prediction accuracy due to the global randomness, nor provide assured security enforcement against the kNN attack. To overcome the problem of recommendation accuracy loss, we propose a novel approach called Partitioned Probabilistic Neighbour Selection. In this thesis, we define the sum of k neighbours’ similarity as the accuracy metric α, the number of user partitions, across which we select the k neighbours, as the security metric β. We consider two versions of the Partitioned Probabilistic Neighbour Selection schemes. Firstly, to ensure a required prediction accuracy while maintaining high security against the kNN attack, we propose an accuracy-assured Partitioned Probabilistic Neighbour Selection algorithm. We select neighbours from each exclusive partition of size k with a decreasing probability. Theoretical and experimental analysis show that to provide an accuracy-assured recommendation, our method yields a suitable trade-off between the recommendation accuracy and system security. Secondly, to ensure a required security guarantee while achieving the optimal prediction accuracy against the kNN attack, we propose a security-assured accuracy-maximised Partitioned Probabilistic Neighbour Selection algorithm. We select neighbours from each partition with exponential differential privacy to reduce the magnitude of noise. Theoretical and experimental analyses show that to achieve the same security guarantee against the kNN attack, our approach ensures an optimal prediction accuracy. In addition, as the core of neighbourhood-based CF, the task of dynamically maintaining users’ similarity list is challenged by the cold-start problem and the scalability problem. Recently, several methods have been proposed for solving the two problems. However, these methods require mn steps to compute the similarity list against the kNN attack, where n and m are number of users and items respectively. Observing that the k new users from the kNN attack, with enough recommendation data, share the same rating list, we present a faster algorithm, TwinSearch, to avoid computing and sorting the similarity list for each new user repeatedly to save the time complexity. The computation cost of our algorithm is 1/125 of the existing methods. Both theoretical and experimental results show that the TwinSearch Algorithm achieves better running time than the traditional method.Thesis (M.Phil.) -- University of Adelaide, School of Computer Science, 2015