Рекомендаційний алгоритм із використанням кластеризації даних
Date
2022-02-28
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Львівської політехніки
Lviv Politechnic Publishing House
Lviv Politechnic Publishing House
Abstract
Розроблено рекомендаційний алгоритм для підвищення якості надання рекомендацій та врахування проблем розрідженості
даних і холодного старту, який враховує удосконалення відомих методів колаборативної фільтрації із використанням
кластеризації. З'ясовано, що рекомендаційні системи створюють для швидкого знаходження товарів чи послуг в
мережі Інтернет, надаючи пропозиції, які точно відповідають інтересам користувачів. Незважаючи на інтенсивний розвиток
алгоритмів рекомендаційних систем та незалежно від доменів їх використання (електронна комерція, розваги, послуги,
новини, соціальні мережі тощо), актуальними залишаються питання підвищення якості наданих рекомендацій,
збільшення швидкодії їх вироблення, масштабованості, забезпечення стійкості в умовах розрідженості даних, холодного
старту. Модифіковано алгоритм колаборативної фільтрації, який можна використати для вироблення рекомендацій користувачам
системами закупівлі товарів чи надання послуг. Виявлено, що завдання пошуку схожих користувачів за вподобанням
вирішують з використанням кластеризації. Поділ користувачів на кластери відбувається за допомогою алгоритму
k-середніх із динамічним пошуком оптимальної кількості кластерів і початкових центроїдів. Запропонований рекомендаційний
алгоритм надає релевантні рекомендації та працює ефективно за різної кількості вхідних даних. Кластеризація
дає змогу алгоритму бути масштабованим і працювати із великою кількістю користувачів системи. Практична
реалізація модифікованого рекомендаційного алгоритму здійснена для системи підбору кінофільмів. Наукова новизна
отриманих результатів дослідження полягає у розвитку методу колаборативної фільтрації на підставі використання кластеризації
із динамічним визначенням кількості кластерів і початкових центроїдів для ідентифікації груп подібних користувачів.
Для верифікації результатів модифікований алгоритм було порівняно із іншими наявними імплементаціями – з
алгоритмом, заснованим на пам'яті, та алгоритмом, заснованим на сусідстві. Запропонований алгоритм має кращі результати
на 25-40 % для проведених тестів. Модифікований рекомендаційний алгоритм не є прив'язаним до певної предметної
області, тому його можна інтегрувати в програмні системи різних доменів.
Recommender systems play a vital role in the marketing of various goods and services. Despite the intensive growth of the theory of recommendation algorithms and a large number of their implementations, many issues remain unresolved; in particular, scalability, quality of recommendations in conditions of sparse data, and cold start. A modified collaborative filtering algorithm based on data clustering with the dynamic determination of the number of clusters and initial centroids has been developed. Data clustering is performed using the k-means method and is applied to group similar users aimed at increase of the quality of the recommendation results. The number of clusters is calculated dynamically using the silhouette method, the determination of the initial centroids is not random, but relies on the number of clusters. This approach increases the performance of the recommender system and increases the accuracy of recommendations since the search for recommendations will be carried out within one cluster where all elements are already similar. Recommendation algorithms are software-implemented for the movie recommendation system. The software implementation of various methods that allow the user to receive a recommendation for a movie meeting their preferences is carried out: a modified algorithm, memory and neighborhood-based collaborative filtering methods. The results obtained for input data of 100, 500 and 2500 users under typical conditions, data sparsity and cold start were analyzed. The modified algorithm shows the best results – from 35 to 80 percent of recommendations that meet the user's expectations. The drop in the quality of recommendations for the modified algorithm is less than 10 per cent when the number of users increases from 100 to 2500, which indicates a good level of scalability of the developed solution. In the case of sparse data (40 percent of information is missing), the quality of recommendations is 60 percent. A low quality (35 percent) of recommendations was obtained in the case of a cold start – this case needs further investigation. Constructed algorithms can be used in rating recommender systems with the ability to calculate averaged scores for certain attributes. The modified recommendation algorithm is not tied to this subject area and can be integrated into other software systems.
Recommender systems play a vital role in the marketing of various goods and services. Despite the intensive growth of the theory of recommendation algorithms and a large number of their implementations, many issues remain unresolved; in particular, scalability, quality of recommendations in conditions of sparse data, and cold start. A modified collaborative filtering algorithm based on data clustering with the dynamic determination of the number of clusters and initial centroids has been developed. Data clustering is performed using the k-means method and is applied to group similar users aimed at increase of the quality of the recommendation results. The number of clusters is calculated dynamically using the silhouette method, the determination of the initial centroids is not random, but relies on the number of clusters. This approach increases the performance of the recommender system and increases the accuracy of recommendations since the search for recommendations will be carried out within one cluster where all elements are already similar. Recommendation algorithms are software-implemented for the movie recommendation system. The software implementation of various methods that allow the user to receive a recommendation for a movie meeting their preferences is carried out: a modified algorithm, memory and neighborhood-based collaborative filtering methods. The results obtained for input data of 100, 500 and 2500 users under typical conditions, data sparsity and cold start were analyzed. The modified algorithm shows the best results – from 35 to 80 percent of recommendations that meet the user's expectations. The drop in the quality of recommendations for the modified algorithm is less than 10 per cent when the number of users increases from 100 to 2500, which indicates a good level of scalability of the developed solution. In the case of sparse data (40 percent of information is missing), the quality of recommendations is 60 percent. A low quality (35 percent) of recommendations was obtained in the case of a cold start – this case needs further investigation. Constructed algorithms can be used in rating recommender systems with the ability to calculate averaged scores for certain attributes. The modified recommendation algorithm is not tied to this subject area and can be integrated into other software systems.
Description
Keywords
центроїди, кластери, коефіцієнт подібності, розрідженість даних, холодний старт, similarity coefficient, centroid, cluster, data sparsity, cold start
Citation
Левус Є. В. Рекомендаційний алгоритм із використанням кластеризації даних / Є. В. Левус, Р. Б. Василюк // Український журнал інформаційних технологій. — Львів : Видавництво Львівської політехніки, 2022. — Том 4. — № 2. — С. 18–24.