DAMPER's blog

k-means Algorithm 유클리디안 공간/distance 를 가정. k (cluster 수)를 뽑으면서 시작. (1). 초기 centroid k개를 뽑는다. (2). 각 점들을 가장 가까운 centroid를 포함하는 cluster에 할당한다. (3). 각 cluster의 centroid를 다시 계산한다. (4). (2), (3)을 centroid가 변경되지 않을 때까지 계속한다. k는 어떻게 선정하는가? k를 진행하면서 centroid까지의 평균 distance가 빠르게 덜어지는 구간에서 선택.

Clustering 점들이 주어지고, 점들 사이에 distance가 정의되어있다. N개의 cluster로 점들을 그룹화 하자. cluster의 멤버들은 비슷하거나 가깝다.(distance가 작다.) cluster가 다른 멤버들은 서로 비슷하지 않다. Usually: 점들은 고차원 공간에 존재한다. Similarity는 distance 척도로 정의된다. (유클리디안, 코사인, Jaccard, edit distance 등) clustering 고려 사항. 몇개의 cluster로 나눌지? 차원이 높으면 어렵다. 고차원 공간에서 clustering은 어려워 보인다. 거의 모든 pair들은 비슷한 distance를 가진다. -> 차원의 저주 차원의 저주 차원이 증가하면서 관측할수록 빈 공간이 많아지고 데이터간 거..

Finding similar items ex. - pages with similar words - Customers who purchased similar products - Images with similar features - Recommendations and search Problem definition 고차원 데이터 points x1, x2, .... , xn이 주어진다. distance fuction d(x1, x2) 가 주어진다. 이는 x1과 x2 사이의 거리를 나타낸다. d(xi, xj)가 s보다 작은 모든 pair of data points(xi, xj)를 찾아보자. Naive solution : O(N^2) N은 data points의 크기를 나타낸다. LSH를 사용하면 O(N)만에 가..

A pirori algorithm 2-pass 접근법으로 메인 메모리 사용을 줄일 수 있다. Key Idea : Monotonicity 만약 아이템 셋 I가 적어도 s번 등장한다면, 집합 I의 모든 부분집합 J 또한 s번 이상 등장한다. 만약 아이템 i가 s 미만으로 등장한다면 i를 포함안 아이템 부분집합이 s 번 미만으로 등장한다. A-priori algorithm 구성 1. pass-1 : 모든 transaction을 1회 읽으면서 메인 메모리에 각각의 아이템의 등장횟수를 저장한다. item수만큼의 메모리 저장 공간이 필요하다. items that appear >= s times are frequent items 2. pass-2 : 모든 transaction을 다시 읽으면서 각각의 아이템의 등장횟수..

연관 규칙 찾기 많은 transaction이 존재한다고 하자. 각 transaction에는 아이템들의 부분집합이 있을 때 연관규칙을 찾아보자. Q1 : transaction들에서 빈번하게 등장하는 아이템 부분집합을 찾자 Support 란? 부분집합 I를 모두 포함하는 transaction의 수 또는 부분집합 I를 모두 포함하는 transaction의 비율 다음 표는 각 transaction에 해당하는 Item들을 나타낸 표이다. Transaction ID Items 1 Bread, Coke, Milk 2 Beer, Bread 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Coke, Diaper, Milk 위 표에 따르면 부분집합 {Beer, Brea..