추천 알고리즘 구현하기 (User-based Collaborative Filtering)

추천 시스템은 보유하고 있는 데이터에 따라 다양한 방법으로 접근하여 구현이 가능하다. 아마존, 넷플릭스와 같이 사용자의 행위 데이터를 분석하여 맞춤형 추천이 가능하고, 뉴스 데이터 등의 텍스트 데이터의 내용을 분석하여 유사도 계산을 통해 추천하는 것도 가능하다. 이 글에서는 추천 시스템의 종류에 대한 소개와 협업 필터링을 통해 간단한 추천 알고리즘을 소개한다.

관련 키워드: 협업 필터링, Collaborative Filtering, Content-based Recommendation, Item-based Recommendation, User-based Recommendation, Inner Product Matrix Similarity


추천 시스템 종류 및 장단점

User-based CF (Collaborative Filtering)

사용자간의 유사도를 계산하여 다른 사용자의 리스트를 추천해주는 방식이다. 아이템에 대한 사용자의 평가 데이터가 존재할 때 행렬을 구성하여 사용자간 유사도 계산이 가능하다. 따라서 서비스 초창기 데이터가 별로 없거나 신규 사용자에 대해서는 추천 정확도가 떨어진다.

사용 예시

Watcha의 영화 추천

장점
– 아이템 자체의 정보 없이 추천이 가능
– 알고리즘이 간단하여 구축하기가 쉬움

단점
– 유저-아이템의 양이 많아질 수록 연산이 복잡해지고 컴퓨팅 자원 소모가 많아짐
– 신규 가입자의 경우 선택된 아이템이 없어 유저간 유사도를 구할 수 없음

Item-based CF

User-based CF와 달리 아이템 간의 유사도를 측정하여 사용자가 아이템을 조회했을 때 유사 상품을 보여주는 방식이다.

Usage Example

아마존의 유사 상품 추천

장점
– 아이템 자체의 정보 없이 추천이 가능
– 아이템에 대한 평가를 가지고있지 않은 신규 사용자에 대해서 추천이 가능

단점
– 유저-아이템의 양이 많아질 수록 연산이 복잡해지고 컴퓨팅 자원 소모가 많아짐
– 초기 서비스시 데이터 양이 적을 때 추천 정확도가 떨어짐

Content-based Filtering

Item-based CF와 마찬가지로 아이템간 연관성을 분석하여 연관 아이템을 찾아 보여주는 방법이다. CF 방식과 달리 아이템의 정보를 바탕으로 아이템의 유사도를 분석하여 추천해준다. 주로 텍스트 정보를 바탕으로 형태소분석, 키워드 추출, 연관단어 검색의 과정을 거쳐 아이템을 추천하고, Word2Vec 등을 사용하여 콘텐츠를 분석할 수 있다.

Usage Example
– 뉴스 추천

장점
– 사용자의 정보 없이 보유한 데이터만 가지고 추천 정확도를 높일 수 있음

단점
– 과정이 복잡하고 학습 시간이 오래걸림

Evaluation

추천 시스템의 성능 평가는 분류 등 다른 작업과는 평가 방식이 다르다. 실험 데이터에서 정답은 존재하지만 단순히 Precision, Recall을 통해 평가하기에는 정확도 비교가 어렵다. 따라서 사용자의 만족도 등을 고려한 지표를 만들어 사용하는데 이 글에서는 Normalized Discounted Cumulative Gain (NDCG) 지표를 사용하여 평가하는 방식을 소개한다.


CF 추천 알고리즘 구현

이 글에서는 CF를 통해 간단한 추천 시스템을 만들어 볼 것이다. Content-based 방식은 추후 다른 글에서 다룰 예정이다.

nodeml 라이브러리

nodeml은 요즘 기계학습 실험을 진행하면서 관련 알고리즘을 정리하며 만든 node.js용 기계학습 라이브러리이다. 현재 Bayes, CNN 등의 분류 알고리즘과 User-based CF 알고리즘을 라이브러리 형태로 구현해 놓았고, Yeast, bbc의 공개된 데이터셋과 개인적으로 수집해놓았던 사용자별 영화 평가 데이터 220만건을 샘플 데이터로 이용 할 수 있게 해놓았다.

라이브러리 설치는 node.js 프로젝트 경로에서 아래의 명령어를 통해 설치가 가능하다.

npm install --save nodeml

nodeml을 이용한 추천 시스템 코드

아래의 코드는 영화 데이터를 nodeml을 사용하여 사용자별 40개씩 추천한 후 ndcg를 계산한 코드이다.

const {sample, CF, evaluation} = require('nodeml');

const movie = sample.movie(); // 영화 데이터셋 {movie_id: no, user_id: no, rating: num, like: num}

let train = [], test = [];
for (let i = 0; i < movie.length; i++) {
    if (Math.random() > 0.8) test.push(movie[i]);
    else train.push(movie[i]);
}

const cf = new CF();

cf.maxRelatedItem = 40;
cf.maxRelatedUser = 40;

cf.train(train, 'user_id', 'movie_id', 'rating');

let gt = cf.gt(test, 'user_id', 'movie_id', 'rating');
let result = cf.recommendGT(gt, 40);
let ndcg = evaluation.ndcg(gtr, result);
console.log(ndcg);

영화 데이터셋

nodeml에 있는 영화 데이터는 총 220만건의 유저-아이템 평가 데이터이다. 데이터는 아래의 형태와 같이 구성되어있다.

[ { movie_id: '1', user_id: '1', rating: '3', like: '1011' } , ... ]

아래의 코드는 영화 데이터셋을 불러온 후 8:2 비율의 트레이닝, 테스트 집합으로 분할한다.

let movie = nodeml.sample.movie();

let train = [], test = [];
for (let i = 0; i < movie.length; i++) {
    if (Math.random() > 0.8) test.push(movie[i]);
    else train.push(movie[i]);
}

추천 알고리즘

nodeml의 추천 알고리즘은 유저 기반(User-based) CF 알고리즘이다. 알고리즘은 아래의 순서로 동작한다.

  1. 특정 사용자가 본 영화 목록을 불러온다
  2. 1의 영화 목록을 본 다른 사용자를 불러온다
  3. 2에서 검색된 사용자가 본 영화 목록을 바탕으로 사용자간 유사도를 Inner Product를 통해 구한다.
  4. 3에서 계산된 사용자들의 영화 목록을 불러온 후 사용자 유사도 점수를 바탕으로 해당 영화들의 점수를 구한다.
  5. 4에서 계산된 점수를 바탕으로 내림차순으로 정렬하여 높은 점수의 영화 n개를 추천한다.

아래의 코드는 nodeml에 구현되어있는 CF 알고리즘의 설명이다.

let trained = {};

let train = (data, x, y, val)=> {
            if (!x) x = 0;
            if (!y) y = 1;
            if (!val) val = 2;
            let userBase = {}, itemBase = {}, itemRank = {};

            for (let i = 0; i < data.length; i++) {
                    let userId = data[i][x];
                    let itemId = data[i][y];
                    let feature = data[i][val] * 1;

                    if (!userBase[userId]) userBase[userId] = [];
                    userBase[userId].push({itemId: itemId, feature: feature});

                    if (!itemBase[itemId]) itemBase[itemId] = [];
                    itemBase[itemId].push({userId: userId, feature: feature});

                    if (!itemRank[itemId]) itemRank[itemId] = 0;
                    itemRank[itemId] += feature;
            }

            let ranking = [];
            for (let itemId in itemRank)
                    ranking.push({itemId: itemId, play: itemRank[itemId]});
            ranking.sort((a, b)=> b.play - a.play);

            trained.userBase = userBase;
            trained.itemBase = itemBase;
            trained.ranking = ranking;
    };

학습 함수는 아래와 같이 구성된다. 학습이라기보다는 추천에 필요한 데이터를 사용하기 편리하게 재구성하는 과정이다. userBase에 유저별로 영화 및 평가 데이터가 저장되고, itemBase에는 영화별로 해당 영화를 본 사용자의 정보가 들어가게된다. ranking은 전체 받은 평가를 바탕으로 영화의 순위를 저장하는데, 이 데이터는 신규 사용자의 경우 평가한 아이템 데이터가 없기 때문에 전체 랭킹으로 추천을 해주기 위해 저장하였다.

let recommendToUser = (userId, count) => {
        let userList = trained.userBase[userId];
        if (userList)
                return recommendByArray(userList, count);
        else
                return JSON.parse(JSON.stringify(trained.ranking)).splice(0, count);
};

recommendToUser 함수는 특정 유저에 대해 n개의 추천 목록을 반환해주는 함수이다. 선택된 유저가 평가한 아이템이 없을 경우 전체 랭킹에서 n개를 추천해주고, 평가한 아이템이 존재할 경우 recommendByArray 함수를 통해 아이템을 추천해준다.

let recommendByArray = (listenList, count)=> {
        let alreadyIn = {};
        let similarUsers = {};
        for (let i = 0; i < listenList.length; i++) {
                alreadyIn[listenList[i].itemId] = true;
                let similarUserList = trained.itemBase[listenList[i].itemId];
                for (let j = 0; j < similarUserList.length; j++) {
                        if (!similarUsers[similarUserList[j].userId])
                                similarUsers[similarUserList[j].userId] = 0;
                        similarUsers[similarUserList[j].userId] += similarUserList[j].feature * listenList[i].feature;
                }
        }

        let relatedUsers = [];
        for (let userId in similarUsers)
                relatedUsers.push({id: userId, score: similarUsers[userId]});
        relatedUsers.sort((a, b)=> b.score - a.score);

        let playlist = {};
        let playlistCount = 0;
        for (let i = 0; i < relatedUsers.length; i++) {
                if (app.maxRelatedUser !== 0 && i > app.maxRelatedUser)
                        break;
                let userId = relatedUsers[i].id;
                let userScore = relatedUsers[i].score;
                let userList = trained.userBase[userId];

                for (let j = 0; j < userList.length; j++) {
                        if (alreadyIn[userList[j].itemId]) continue;
                        if (app.maxRelatedItem !== 0 && j > app.maxRelatedItem)
                                break;
                        if (!playlist[userList[j].itemId]) {
                                playlist[userList[j].itemId] = 0;
                                playlistCount++;
                        }

                        playlist[userList[j].itemId] += userScore;
                }
        }

        let result = [];
        for (let itemId in playlist)
                result.push({itemId: itemId, score: Math.round(Math.log(playlist[itemId] + 1) * 100) / 100});
        result.sort((a, b)=> b.score - a.score);
        result.splice(count);

        for (let i = 0; i < trained.ranking.length; i++) {
                if (result.length >= count) break;
                if (!playlist[trained.ranking[i].itemId])
                        result.push(trained.ranking[i]);
        }

        return result;
};

recommendByArray 함수는 지정된 사용자와 타 사용자의 점수를 계산하여 아이템을 추천해준다. 앞에서 알고리즘에 대해 설명한 순서로 코드가 진행되는데, 데이터가 많을 경우 속도가 느려지기 때문에 maxRelatedUsermaxRelatedItem를 설정하여 속도 개선이 가능하다. 기본적으로 설정은 모든 데이터를 활용하지만 해당 값이 설정되어 있을경우 일정양에 도달하면 멈추도록 되어있다.

NDCG 평가

const cf = new nodeml.CF();

cf.maxRelatedItem = 40;
cf.maxRelatedUser = 40;

cf.train(train, 'user_id', 'movie_id', 'rating');

let gt = cf.gt(test, 'user_id', 'movie_id', 'rating');
let result = cf.recommendGT(gt, 40);
let ndcg = evaluation.ndcg(gtr, result);
console.log(ndcg);

위의 코드는 Threshold 설정을 각각 40으로 설정한 후 test 데이터에 사용자별로 40개씩 추천을 한 후 ndcg 지표로 성능을 평가하는 코드이다.

time node nodeml.cf.js 

js파일을 위의 명령어로 실행하면 ndcg 값과 수행 시간을 확인 할 수 있다. 현재 코드를 수행할 경우 초당 68명의 사용자를 평가가 가능하고 정확도 및 전체 수행시간은 아래와 같다. (컴퓨팅 성능별로 차이가 있을 수 있음)

0.14899252729622794

real    9m2.662s
user    8m33.283s
sys     0m46.914s

아래는 동일한 환경에서 전체 랭킹에서 상위 40개의 아이템을 모든 유저에게 추천했을 경우와 비교를 한 자료이다. 빠른 실험을 위해 유저 100명에 대해 각각 추천하는 방식으로 비교하였다. CF알고리즘을 사용할 경우 수행시간은 2배정도 증가하고 정확도는 2배정도 향상되었다.

항목 CF 상위일괄추천
ndcg 0.20 ~ 0.24 0.10 ~ 0.12
초당사용자평가 68명 160명

마치며

이 글에서는 nodeml을 통한 추천 기술 구현과 평가 방법에 대해서 언급했는데, 알고리즘 자체가 복잡하지 않기 때문에 필요에 따라서 직접 구현할 수 있다고 생각한다. Inner Product 계산으로 유사도를 구했지만, k-NN 등 다른 알고리즘을 사용하여 유사도를 구하거나 추천시 아이템에 가중치를 변경하면 추가적인 성능 개선도 가능하다.

이 글에서는 CF만 다루었지만 추후에 Word2Vec를 사용한 텍스트 데이터에 대한 Content-based 추천 방식을 다루어 볼 예정이다.

댓글 남기기