반응형
블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
솔웅

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

카테고리

Elements of AI - The nearest neighbor classifier

2018. 6. 21. 03:46 | Posted by 솔웅


반응형


Elements of AI




II.The nearest neighbor classifier




The nearest neighbor classifier is among the simplest possible classifiers. When given a item to classify, it finds the training data item that is most similar to the new item, and outputs its label. An example is given in the following diagram.


가장 가까운 neighbor classifier는 가장 단순한 possible classifiers 중 하나이다. 분류 할 항목이 주어지면 그 새 항목과 가장 유사한 training data item을 찾고 해당 레이블을 출력합니다. 다음 다이어그램에 예제가 나와 있습니다.







In the above diagram, we show a collection of training data items, some of which belong to one class (green) and other to another class (blue). In addition, there are two test data items, the stars, which we are going to classify using the nearest neighbor method.




위의 다이어그램에서 우리는 하나의 클래스 (녹색)와 다른 클래스 (파란색)에 속하는 training data items의 모음을 보여줍니다. 또한 가장 가까운 neighbor method을 사용하여 분류 할 2 개의 테스트 데이터 항목 (별)이 있습니다.



The two test items are both classified in the “green” class because their nearest neighbors are both green (see diagram (b) above).



두 test items은 가장 가까운 이웃이 모두 녹색이기 때문에 "녹색"등급으로 분류됩니다 (위 그림 (b) 참조).



The position of the points in the plot represents in some way the properties of the items. Since we draw the diagram on a flat two-dimensional surface — you can move in two independent directions: up-down or left-right — the items have two properties that we can use for comparison. Imagine for example representing patients at a clinic in terms of their age and blood-sugar level. But the above diagram should be taken just as a visual tool to illustrate the general idea, which is to relate the class values to similarity or proximity (nearness). The general idea is by no means restricted to two dimensions and the nearest neighbor classifier can easily be applied to items that are characterized by many more properties than two.



플롯에서 점의 위치는 항목의 속성을 어떤 식 으로든 나타냅니다. 다이어그램을 평평한 2 차원 표면에 그림으로서 두 가지 독립적 인 방향 (상하 또는 좌우)으로 이동할 수 있습니다. 이 항목에는 비교를 위해 사용할 수있는 두 가지 속성이 있습니다. 예를 들어 클리닉의 환자를 연령과 혈당치로 대표한다고 상상해보십시오.  위의 다이어그램은 클래스 값을 유사성 또는 근접성과 관련시키는 일반적인 아이디어를 설명하기위한 시각적 도구로서 사용되어집니다. 일반적인 개념은 결코 2 차원으로 제한되지 않으며 가장 가까운 이웃 분류자는 2보다 많은 특성을 특징으로하는 항목에 쉽게 적용될 수 있습니다.






What do we mean by nearest?



An interesting question related to (among other things) the nearest neighbor classifier is the definition of distance or similarity between instances. In the illustration above, we tacitly assumed that the standard geometric distance, technically called the Euclidean distance, is used. This simply means that if the points are drawn on a piece of paper (or displayed on your screen), you can measure the distance between any two items by pulling a piece of thread straight from one to the other and measuring the length.



가장 가까운 neighbor classifier (다른 것들 중에서)와 관련된 흥미로운 질문은 인스턴스 간의 거리 또는 유사성의 정의입니다. 위의 그림에서 우리는 기술적으로 Euclidean 거리라고 불리는 표준 기하학적 거리를 암묵적으로 가정했습니다. 이것은 단순히 포인트가 종이에 그려 지거나 (또는 화면에 표시되는 경우) 하나의 선을 다른 것으로 똑바로 잡아 당겨 길이를 측정함으로써 두 아이템 간의 거리를 측정 할 수 있음을 의미합니다.




Note

Defining ‘nearest’

Using the geometric distance to decide which is the nearest item may not always be reasonable or even possible: the type of the input may, for example, be text, where it is not clear how the items are drawn in a geometric representation and how distances should be measured. You should therefore choose the distance metric on a case-by-case basis.


어떤 항목이 가장 가까운 항목인지를 결정하기 위해 기하학적 거리를 사용하는 것은 항상 합리적이지는 않습니다. 그리고 심지어 가능하지 않을 수도 있습니다. 예를 들어, 입력 유형은 텍스트 일 수 있으며, 항목이 기하학적 표현으로 어떻게 그려지는지 명확하지 않고 어떻게 거리가 측정되어야 하는지도 명확하지 않습니다. 그러므로 여러분은 케이스 바이 케이스를 기반으로 거리 측정을 해야 합니다.




In the MNIST digit recognition case, one common way to measure image similarity is to count pixel-by-pixel matches. In other words, we compare the pixels in the top-left corner of each image to one another and if the more similar color (shade of gray) they are, the more similar the two images are. We also compare the pixels in the bottom-right corner of each image, and all pixels inbetween. This technique is quite sensitive to shifting or scaling the images: if we take an image of a '1' and shift it ever so slightly either left or right, the outcome is that the two images (before and after the shift) are very different because the black pixels are in different positions in the two images. Fortunately, the MNIST data has been preprocessed by centering the images so that this problem is alleviated.



MNIST 숫자 인식 케이스의 경우 이미지 유사성을 측정하는 일반적인 방법 중 하나는 픽셀 별 매치를 계산하는 것입니다. 즉, 각 이미지의 왼쪽 위 모서리에있는 픽셀을 서로 비교하고 더 비슷한 색 (회색 음영) 일수록 두 이미지가 더 유사하다고 판단합니다. 이렇게 각 이미지의 오른쪽 하단에있는 픽셀과 그 사이에있는 모든 픽셀을 비교합니다. 이 기술은 이미지를 이동하거나 크기를 조정하게 되면 민감하게 영향을 미칩니다. '1'이미지를 가져 와서 왼쪽 또는 오른쪽으로 조금씩 이동하면 결과적으로 두 이미지 (이동 전후)가 매우 다르게 됩니다. 검은 색 픽셀은 두 이미지에서 서로 다른 위치에 있기 때문입니다. 다행히도, MNIST 데이터는 이미지를 센터링하여 사전 처리되어 이 문제가 완화되었습니다.




Using nearest neighbors to predict user behavior


A typical example of an application of the nearest neighbor method is predicting user behavior in AI applications such as recommendation systems.


가장 nearest neighbor 방법의 전형적인 적용 예는 추천 시스템과 같은 AI 어플리케이션에서의 사용자 행동을 예측하는 것입니다.



The idea is to use the very simple principle that users with similar past behavior tend to have similar future behavior. Imagine a music recommendation system that collects data about users’ listening behavior. Let’s say you have listened to 1980s disco music (just for the sake of argument). One day, the service provider gets their hands on a hard-to-find 1980 disco classic, and add it into the music library. The system now needs to predict whether you will like it or not. One way of doing this is to use information about the genre, the artist, and other metadata, entered by the good people of the service provider. However, this information is relatively scarce and coarse and it will only be able to give rough predictions.



이 아이디어는 유사한 과거 행동을 하는 사용자가 비슷한 미래 행동을하는 경향이 있다는 아주 단순한 원칙을 사용하는 것입니다. 사용자의 청취 행동에 관한 데이터를 수집하는 음악 추천 시스템을 상상해보십시오. 1980 년대 디스코 음악을 들어 봤다고합시다. 어느 날, 서비스 제공 업체는 찾기 힘든 1980 디스코 클래식을 음악 라이브러리에 추가합니다. 시스템은 이제 당신이 좋아할 것인지 아닌지 예측할 필요가 있습니다. 이렇게하는 한 가지 방법은 서비스 제공 업체의 좋은 사람들이 입력 한 장르, 아티스트 및 기타 메타 데이터에 대한 정보를 사용하는 것입니다. 그러나 이 정보는 상대적으로 부족하고 거친 것이며 예측할 수 없을 것입니다.



What current recommendation systems use instead of the manually entered metadata, is something called collaborative filtering. The collaborative aspect of it is that it uses other users’ data to predict your preferences. The word “filter” refers to the fact that you will be only recommended content that passes through a filter: content that you are likely to enjoy will pass, other content will not. (This kind of filters may lead to the so called filter bubbles, which we mentioned in Chapter 1. We will return to them later.)



현재 추천 시스템이 사용하는 것은 수동으로 입력 한 메타 데이터 대신에 사용하는 collaborative filtering 이라고 하는 것입니다. collaborative라는 것은 여러분의 preferences를 예측하기 위해 다른 사용자들의 데이터를 사용한다는 겁니다.  'filter'라는 단어는 필터를 통과하는 콘텐츠만 추천된다는 것을 의미합니다. 여러분이 선호하는 콘텐츠들이 통과하고 그렇지 않은 것들은 통과하지 않을 겁니다.  (이런 종류의 필터는 1 장에서 언급 한 소위 말하는 필터 버블을 유발할 수 있습니다. 나중에 이부분은 다시 다루게 될 것입니다. )



Now let’s say that other users who have listened to 80s disco music enjoy the new release and keep listening to it again and again. The system will identify the similar past behavior that you and other 80s disco fanatics share, and since other users like you enjoy the new release, the system will predict that you will too. Hence it will show up at the top of your recommendation list. In an alternative reality, maybe the added song is not so great and other users with similar past behavior as yours don't really like it. In that case, the system wouldn't bother recommending it to you, or at least it wouldn't be at the top of the list of recommendations to you.



이제 80 년대 디스코 음악을 들었던 다른 사용자가 새 릴리스를 즐기고 이것을 계속해서 다시 듣는다고 가정 해 봅시다. 이 시스템은 귀하와 다른 80 년대 디스코 광신자들이 공유 한 유사한 과거 행동을 식별하고, 당신 같은 다른 사용자가 새로운 릴리스를 즐기기 때문에 시스템은 귀하도 그렇게 할 것이라고 예측할 것입니다. 따라서 추천 목록 상단에 표시됩니다. 현실에서는, 추가 된 노래가 그리 좋지 않을 수도 있고 당신과 비슷한 과거 행동을하는 다른 사용자가 이것을 좋아하지 않을 수도 있습니다. 이 경우 시스템에서 권장하지 않거나 최소한 추천 목록 맨 위에 올 수 없습니다.



The following exercise will illustrate this idea.



다음 연습문제에서 이 부분을 다루고 있습니다.





AWS DeepLens - Deep learning enabled video camera for developers




Exercise 14: Customers who bought similar products


In this exercise, we will build a simple recommendation system for an online shopping application where the users' purchase history is recorded and used to predict which products the user is likely to buy next.



이 연습문제 에서는 사용자의 구매 내역이 기록되고 사용자가 다음에 구매할 제품을 예측하는 데 사용되는 온라인 쇼핑 응용 프로그램을 위한 간단한 추천 시스템을 구축 할 것입니다.



We have data from six users. For each user, we have recorded their recent shopping history of four items and the item they bought after buying these four items:



우리는 6 명의 사용자 데이터를 가지고 있습니다. 각 사용자별로 4 가지 항목에 대한 최근 구매 내역과 4 가지 항목을 구입 한 후 구입 한 항목을 기록했습니다.






The most recent purchase is the one in the rightmost column, so for example, after buying a t-shirt, flip flops, sunglasses, and Moby Dick (novel), Ville bought sunscreen. Our hypothesis is that after buying similar items, other users are also likely to buy sunscreen.



맨 오른쪽에 있는 것들이 가장 최근에 구입한 목록들입니다. 예를 들어, Ville은 티셔츠, 플립 플롭, 선글라스 및 Moby Dick (소설)을 구입 한 후, 썬 스크린을 샀습니다. 우리의 가설은 비슷한 품목을 구입 한 다른 사용자들도 선 스크린을 사기 쉽다는 것입니다.



To apply the nearest neighbor method, we need to define what we mean by nearest. This can be done in many different ways, some of which work better than others. Let’s use the shopping history to define the similarity (“nearness”) by counting how many of the items have been purchased by both users.



nearest neighbor method을 적용하려면 nearest의 의미를 정해야 합니다. 이것은 여러 가지 방법으로 수행 할 수 있으며 그 중 일부는 다른 것보다 효과적일 겁니다. shopping history을 사용하여 두 사용자가 구매 한 항목 수를 계산하여 유사성 ( "nearness")을 정의합시다.



For example, users Ville and Henrik have both bought a t-shirt, so their similarity is 1. Note that flip flops doesn't count because we don't include the most recent purchase when calculating the similarity — it is reserved for another purpose.


예를 들어, Ville과 Henrik user는 모두 티셔츠를 구입했기 때문에 유사도는 1입니다. 유사도를 계산할 때 가장 최근의 구매가 포함되어 있지 않으므로 플립 플립은 포함되지 않습니다. 그것은 다른 용도로 사용될 겁니다.



Our task is to predict the next purchase of customer Travis who has bought the following products:



이제 아래 상품들을 구매한 Travis라는 고객의 다음 구매를 예측하는 겁니다.





You can think of Travis being our test data, and the above six users make our training data.



Travis가 우리의 테스트 데이터라고 생각하세요.  위의 6 명의 사용자가 우리의 training data를 만듭니다.




Proceed as follows:


  1. Calculate the similarity of Travis relative to the six users in the training data (done by adding together the number of similar purchases by the users).
  2. Having calculated the similarities, identify the user who is most similar to Travis by selecting the largest of the calculated similarities.
  3. Predict what Travis is likely purchase next by looking at the most recent purchase (the rightmost column in the table) of the most similar user from the previous step.


1. training data에서 6 명의 사용자에 대한 Travis의 유사성을 계산합니다 (사용자가 유사한 구매 횟수를 합산하여 계산).

2. 유사점을 계산 한 후 계산 된 유사성 중 가장 큰 것(숫자)을 선택하여 Travis와 가장 유사한 사용자를 식별합니다.

3. 이전 단계에서 가장 유사한 사용자의 가장 최근 구매 (테이블의 가장 오른쪽 열)를보고 Travis가 다음에 구매할 것으로 예상되는 것을 예측합니다.




In the above example, we only had six users’ data and our prediction was probably very unreliable. However, online shopping sites often have millions users, and the amount of data they produce is massive. In many cases, there are a hoard of users whose past behavior is very similar to yours, and whose purchase history gives a pretty good indication of your interests.



위의 예에서 우리는 6 명의 사용자 데이터 만 가지고 있었고 예측은 매우 신뢰할 수 없었습니다. 그러나 온라인 쇼핑 사이트는 대개 수백만 명의 사용자를 보유하고 있으며 이들이 생산하는 데이터의 양은 방대합니다. 많은 경우 사용자의 과거 행동이 당신과 매우 유사하며 구매 내역이 당의 관심사를 잘 보여주는 사용자가 많습니다.



These predictions can also be self-fulfilling prophecies in the sense that you are more likely to buy a product if it is recommended to you by the system, which makes it tricky to evaluate how well they actually work. The same kind of recommendation systems are also used to recommend music, movies, news, and social media content to users. In the context of news and social media, filters created by such systems can lead to filter bubbles.



이러한 예측은 시스템에서 사용자에게 권장되는 제품을 그 사용자가 구매할 확률이 높다는 의미에서 self-fulfilling prophecies이 될 수 있습니다. 이는 실제로 얼마나 효과적인지 평가하는 것이 까다로울 수 있습니다. 음악, 영화, 뉴스 및 소셜 미디어 콘텐츠를 사용자에게 추천하는데도 동일한 종류의 추천 시스템이 사용됩니다. 뉴스 및 소셜 미디어의 맥락에서 이러한 시스템에 의해 생성 된 필터는 필터 버블을 유발할 수 있습니다.




Exercise 15: Filter bubbles

As discussed above, recommending news of social media content that a user is likely to click or like, may lead to filter bubbles where the users only see content that is in line with their own values and views.



위에서 언급했듯이 사용자가 클릭하거나 좋아할만한 소셜 미디어 콘텐츠의 뉴스를 추천하면 사용자가 자신의 가치(values) 및 관점(views)과 일치하는 콘텐츠 만 보게되는 필터 버블이 발생할 수 있습니다.



  1. Do you think that filter bubbles are harmful? After all, they are created by recommending content that the user likes. What negative consequences, if any, may be associated with filter bubbles? Feel free to look for more information from other sources.
  2. Can you think of ways to avoid filter bubbles while still being able to recommend content to suit personal preferences? Try to come up with at least one suggestion. You can look for ideas from other sources, but we'd like to hear your own ideas too!


1. 필터 거품이 유해하다고 생각합니까? 결국, 그들은 사용자가 좋아할만한 내용을 추천하는 것을 통해 만들어집니다.  필터 거품과 관련해서 어떤 부정적인 요소가 있을 수 있을 까요? 여러분들 마음껏 다른 출처들을 통해 더 많은 정보를 찾아보세요.


2. 개인의 취향에 맞게 콘텐츠를 추천 하면서도 필터 거품을 피하는 방법이 있을까요? 적어도 하나의 제안을 내놓으십시오. 다른 출처에서 아이디어를 찾으셔도 되지만 여러분만의 생각을 한번 들어보고 싶습니다. 



Note: your answer should be at least a few sentences for each part.





반응형