네트워크가 작을때는 노드들간의 관계가 눈에 보이지만, 노드가 만약 수천 수만개라면? 하나의 헤어볼처럼 보이기 쉽상이다.
노드들이 복잡하게 엣지들과 연결되어 있을때 어떻게 중요한 노드를 알아볼 수 있을까?
이때 사용되는 중심성지수라는 것을 살펴보려한다.
중심성지수의 종류와 예제
위세 중심성(Eigenvector Centrality)
예제를 살펴보자, 만약 BTS콘서트가 열리고 콘서트 티켓을 어떤 사람에게 주어야 다른 사람들에게 충분히 홍보가 될까?
이는 중요한 노드가 무엇인지 찾는 과정이다.
가장 간단한 방법으로는 가장 많은 친구가 있는 사람을 찾는 것이다. 가장 엣지가 많이 연결된 노드를 찾으면 된다.
degree of node는 그 노드에 연결되어있는 엣지 개수이다. 이를 adjacency matrix에서 찾으려면 해당하는 노드의 행을 모두 더해주면 된다. 왜냐하면 adjacency matrix는 행과 열이 각각 node들이 연결되어 있는지 아닌지에 대한 행렬이기 때문이다.
하지만, 이걸로 그 사람이 가장 중요하다고 따질 수 없다. 그 사람이 연결된 사람이 많을 뿐이지, 그 사람의 친구, 또 그 사람의 친구가
계속 영향력 있는 사람일지는 모르기 때문이다.
그렇다면 수학적으로 영향력이 계속 많은 친구의 중심은 어떻게 구할까?
eigenvector centrality로 구한다. 이 방법은 해당하는 노드에 주변 모든 이웃들의 점수를 합산한 값을 내준다.
또 다른 방법으로는 Page Rank가 있다. 이런 경우에는 indirected network에서 사용한다. 예를 들면, World Wide Web.
근접 중심성(Clossness Centrality)
근접 중심성(Closeness Centrality)은 특정 노드가 다른 노드까지 도달하는 경로가 얼마나 짧은지를 나타낸다.
근접 중심성을 계산하는 수식은 노드 I에서 I를 제외한 다른 노드까지 도달하는 최소 경로의 평균을 구한 다음, 그 평균을 역수 취하면 된다.
매개 중심성(Betweenness Centrality)
Bottleneck of network는 정보의 흐름을 유지하는데 가장 중요한 node를 말한다. 병목현상이 일어나는 지점이다. 정보의 양은 그 노드가 몇개의 경로를 통과하는지에 비례한다. 가장 많은 정보가 지나가는 노드를 발견하는데 사용되는 지표는매개 중심성(Betweenness Centrality)이다.매개 중심성은 한 노드가 다른 노드들과의 연결망을 구축하는데 얼마나 도움을 주는지 측정하는 지표로 두가지 가정을 한다. (1) 정보의 흐름은 일정한 속도를 갖는다. (2) 정보는 가장 짧은 경로로 다닌다.
이때, 모든 짝의 노드들을 지나는 가장 짧은 경로를 찾는 알고리즘으로 Floyd-Warshall algorithm을 사용한다.
노드 I의 중요성이 아닌 임의의 X, Y 노드에 대해서 X-Y의 최단 경로에 노드 I가 포함되어 있는 횟수를 의미한다.
기존에 collaborative filtering은 추천시스템을 만드는데 유용한 알고리즘이지만, 몇가지 가정이 신경쓰인다.
첫째, 유저들의 관계가 simple하다고 가정하는 것과 둘째, 유저의 preference가 static하다는 가정이다. 실제로는 관계가 간단하지도 그리고 선호도가 계속 변하기때문에 일정한 선호도를 갖지도 않는다. 그래서 이런문제를 반영하여 해결하려는 노력으로 Graphical Model이 도입되었다.
Graphical Model로 무엇을 할 수 있는가?
Graphical Model을 사용하면 1) 유저 선호도간의 복잡한 관계를 잡아낼 수 있고, 2) 마코비안 스트럭쳐를 사용하여 그래피컬 모델을 사용한 경우 추천시스템에서 유저 선호도의 일시적인 면을 잡아낼 수도 있다. 모든 유저들의 선호도 관계를 모르고 부족한 데이터로도 모델을 만들 수 있다는 장점이 있다.
Graphical Model의 구동방식
아래처럼 Neflix에서 제공된 영화가 있다고해보자.
영화는 노드 그리고 이를 잇는 엣지들이 있다. 엣지들은 두 영화간의 관계를 나타낼 수 있고 한명의 유저가 그 영화를 좋아하면 +1, 아니면 -1로 표기를 한다. 그리고 다른 유저들도 하나씩 표기를 한다고 한다. 이때, Graphical Model은 적절한 age structure와 assocciated parameters를 이용해 관계를 잡아낼 수 있다. 그렇다면 그 그래프에 관계된 파라미터들은 뭘까? 이를 설명하기 위해 특별한 파라미터화가 필요한데 이런 모델을 pairwise graphical model이라고 한다.
아래 그림에서 보듯이 시그마와 각 시그마간의 관계를 나타내는 파라미터 쎄타가 존재한다.
그리고 4개의 변수가 이런 특정 파라미터를 갖을 확률을 공식으로 나타낼 수 있다.
그렇다면, 정확하게 파라메터를 예측하는 방법이 있을까? 그 방법중 하나가 moment matching이다. 간단히 설명하면, 우선 파라메터를 주고 경험적으로 얻은 순간과 비교한다. 이때 발생한 mismatch를 줄이는 방향으로 node와 edge paramater를 학습한다. 그리고 good match를 찾을때까지 이를 반복한다. 간단하다! 그렇다면 이걸 하기 위한 방법은? belief propagation algorithm이다. 이 계산 간단하지 않지만 한 여성이 단지 하나의 영화에 대한 평가를 내린것에도 다른 영화를 추천할 수 있을만큼의 대단한 모델을 만드는 graphical model을 구현하는데 사용된다.
앞에서 언급했듯이 일시적인 면을 잡아낼 수 있다고 했다. 이게 무슨 뜻이냐면, 예를 들어 아이언맨 1, 2, 3 영화가 있다면 무슨 영화를 먼저 추천해줄 것이냐에 대한 문제를 해결하기 위한 관점이다. 아이언맨 3가 가장 인기가 많아서 3를 추천해주는것이 맞겠지만, 어떤 유저는 1을 먼저 봤다면 그 다음에는 2를 볼것이라고 예상하고 2를 제안해줄 수 있다. 이런 문제를 해결하는데 Graphical Model이 유용하고 이 문제를 해결하기 위한 알고리즘으로 Hidden Markov Model이 있다. 이는 시간의 흐름을 반영하였다.
사용자의 성향을 알아보고 아이템을 추천해줄 수 있으며 사용자가 해당상품을 구매할 확률을 고려하고 친사용자에 가까운 서비스를 만들어낼 수 있는 시스템을 얘기합니다. 개인 맞춤화 시스템을 만드는 것이 대부분의 연구 목적입니다. 최근에 사람을 매칭해주는 어플에서도 사람과 사람을 매칭시키고 혹은 물건을 사는 시스템이나 영화, 노래를 듣는 어플같은데서는 사람과 물품 혹은 원하는 컨텐츠을 매칭하는데 추천시스템이 주로 사용됩니다.
추천시스템 분류
기본적으로콘텐츠기반(Content based filtering)과 협업필터링(Collaborative filtering), 최근접이웃기반필터링(nearest neighbor collaborative filtering), 잠재요인 기반 필터링(latent factor collaborative filtering)으로 나뉘어져 있습니다. 초기에는 콘텐츠기반 필터링을 주로 사용하다가 넷플릭스의 영화추천알고리즘에 협업필터링이 사용되면서 대부분 협업필터링을 사용하는 추세입니다.
예를 들어, 사용자가 여드름성 화장품과 아모레퍼시픽 화장품에 높은 평점을 주었을 경우 다음에는 아모레퍼시픽에 여드름성 다른 관련 화장품을 추천해주는 것입니다.
2. 협업필터링
사용자와 아이템간의 rating을 이용해 사용자사이의 '유사도'를 찾는 방식
한 사용자와 비슷한 사용자의 구매목록이나 평점등을 이용해서 해당 사용자가 어떤 상품을 좋아할지 수치적으로 예측하는 방식입니다. 유사도를 계산할때는 유클리디안 거리, 코사인유사도기반, 피어슨유사도기반 등의 수학적 유사도를 계산합니다. 유사도가 높은 사용자 집단(이를 'TOP-N'이라고 명칭함) 안에서 각 사용자들이 남긴 평점을 weighted sum을 계산해서 평점을 예측합니다. 예를 들어, 유사도가 높은 사용자들이 구매했던 상품에 대한 평점의 가중치의 합을 구해서 사용자 집단안에 속한 사용자의 평점을 예측하는 방식입니다. 하지만, 처음 방문한 사용자는 유사한 사용자를 알기 어렵기에 추천이 잘 될 수 없는 문제점이 있습니다. 이를 cold start problem이라고 말합니다. 이런 이유로 넷플릭스를 사용시 처음 방문자는 좋아하는 영화를 선택하는 설문조사를 진행하고 있습니다.
2-1. 최근접 이웃기반 협업 필터링
사용자-아이템 행렬에서 사용자가 아직 평가하지 않은 아이템을 예측하는 것입니다. row는 users, column은 items로 구성되어 있어야 합니다. 또한, 사용자기반 협업 필터링과 아이템 기반 협업 필터링으로 나뉩니다. 사용자 기반은 '비슷한 사용자들이 A아이템을 구매하더라~ '이고 아이템 기반은 'A아이템을 구매한 사용자가 다음과 같은 물품도 구매하더라~'라고 이해하시면 편합니다.
따라서, 사용자 기반 협업 시스템의 경우 row가 사용자, 아이테템 기반 협업 시스템의 경우 아이템이 row가 됩니다. 일반적으로 아이템기반 협업필터링이 정확도가 좋고 더 많이 사용됩니다.
사용자-아이템 평점 행렬에서 '잠재요인' 있다는 가정하에 행렬분해 방식을 사용하여 잠재요인을 구체적으로 정의하는 방식입니다. 예를 들어, 어떤 사용자의 영화평가에 대한 잠재요인이 장르라는 것을 가정한다면, 그 사용자가 판타지를 선호할때 다른 영화도 판타지를 추천해주는것이 가장 합리적이라고 판단되고 이를 추천해주는 것입니다.
2009년까지는 앞선 추천시스템방식이 주목을 받았다면 2009년 이후에는 넷플릭스 컴피티션에서 우승을 하면서 '행렬분해'(Matrix Factorization)을 이용한 잠재요인 필터링이 주목을 받고 많이 사용하고있는 추세입니다.
Let’s start with an example: Suppose you're given a dataset that contains thesize (in terms of area) of different houses and their market price. Your goal is to come up with an algorithm that will take thesize of the house as its inputandreturn its market price as the output.
In this example, the input variable i.e the size of the house, is called the independent variable (X), the output variable i.e house price is called the dependent variable (Y), and this algorithm is an example ofsupervised learning.
In supervised learning,algorithms are trained using "labeled"data (in this example, the dependent variable - house price, is considered a label for each house), and trained on that basis, the algorithm can predict an output for instances where this label (house price) is not known. "Labeled data" in this context simply means that the data is alreadytaggedwith the correct output. So in the above example, we already know the correct market price for each house, and that data is used to teach the algorithm so that it can correctly predict the house price for any future house for which the price may not be known.
The reason this paradigm of machine learning is known as supervised learning, is because it is similar to the process of supervision that a teacher would conduct on the test results of a student on an examination, for example. The answers the student gives (predictions) are evaluated against the correct answers (the labels) that the teacher knows for those questions, and the difference (error) is what the student would need to minimize to score perfectly on the exam. This is exactly how machine learning algorithms of this category learn, and that is why the class of techniques is known as supervised learning.
There are mainly 2 types of supervised learning algorithms:
Regression,where your output variable is acontinuousvariable, for example, the price of a house.
Classification, where your output variable iscategorical, for example, approve the loan or not i.e. yes or no categories.
In this lecture, we will be learning about regression algorithms, which obviously find great use in the machine learning prediction of several numerical variables we would be interested in estimating, such as price, income, age, etc.
Linear Regression
Linear Regression is useful for finding thelinear relationshipbetween theindependent and dependentvariables of a dataset. In the previous example, the independent variable was the size of the house and the dependent variable its market price.
This relationship is given by the linear equation:
Where
is theconstantterm in the equation,
is thecoefficientof the variable
,
is the difference between the actual value
and the predicted value(
).
and
are called the parameters of the linear equation, while
and
are the independent and dependent variables respectively.
What is an error?
With given
and
in the training data, the aim is to estimate
and
in such a way that the given equationfitsthe training datathe best. Thedifferencebetween theactual value and the predicted valueis called theerror or residual. Mathematically, it can be given as follows:
In order to estimate the best fit line, we need to estimate the values of
and
which requires minimizing themean squared error. To calculate the mean squared error, we add the square of each error term and divide the sum with the total number of records:
The equation of that best fit line can be given as follows:
Where
is the predicted value,
are the estimated parameters.
This equation is called thelinear regression model. The above explanation is demonstrated in the below picture:
Before applying the model over unseen data, it is important to check its performance to make it reliable. There are a few metrics to measure the performance of a regression model.
R-squared:R-squared is a useful performance metric to understandhow wellthe regression model hasfitted over the training data. For example, an R-squared of80%reveals that 80% of thetraining datafit the regression model.A higher R-squaredvaluegenerallyindicates abetter fit for the model.
Adjusted R-squared: The adjusted R-squared is amodifiedversion of R-squared that takes into account thenumber of independent variables present in the model. When a new variable is added, adjusted R-squaredincreasesif that variableadds valueto the model, anddecreasesif itdoes not. Hence, adjusted R-squared is a better choice of metric than R-squared to evaluate the quality of a regression model with multiple independent variables, because adjusted R-squared only remains high when all those independent variables are required to predict the value of the dependent variable well; it decreases if there are any independent variables which don't have a significant effect on the predicted variable.
RMSE: RMSE stands forRoot Mean Squared Error. It is calculated as the square root of the mean of the squared differences between actual outputs and predictions. The lower the RMSE the better the performance of the model. Mathematically it can be given as follows:
