본문 바로가기
728x90
반응형

스터디/데이터사이언스88

[CS246] Dimensionality Reduction (2) - PCA Principal Component Analysis (PCA)PCA 알고리즘으로 생성된 새로운 차원(dimension)을 주성분(principal component)라 부른다.원래 PCA 자체로는 차원축소가 아니지만, 이 포스트에서는 차원축소로 응용되는 특성에 대해 다룬다.PCA:  Algorithm데이터의 분산이 가장 큰 방향을 새로운 차원의 축으로 삼는 것이 핵심이다. (해당 축으로 데이터를 정사영했을 때 가장 range가 큰 것) 데이터의 분산이 곧 데이터의 분포를 가장 잘 설명할 것이기 때문이다.  첫번째 차원: 데이터의 분산이 가장 큰 방향두번째 차원: 첫번째 차원과 수직이면서, 데이터의 분산이 2번째로 큰 방향n번째 차원: 첫번째, 두번째, ..., (n-1)번째 차원과 모두 수직이면서, 데이.. 2023. 10. 8.
[CS246] Dimensionality Reduction (1) - Introduction Demensionality ReductionReducing Matrix Reduction대부분의 데이터는 행렬로 표현할 수 있다. 예를 들어, $m \times n$ 행렬은 $m$개의 점들과 $n$개의 feature로 생각할 수 있다. 선형대수를 이용하면, 행렬을 3개의 행렬의 곱으로 나타낼 수 있다. 이때 새로 생기는 3개의 행렬은 더 작은 차원 $r$을 공유한다. 예를 들어, SVD를 이용하면 $m \times n$ 행렬은 각각 $m\ times r,\ r \times r,\ r times n$ 이렇게 3개의 행렬을 얻게 되고 가운데 행렬은 대각행렬이기 때문에 $r \times r$은 사실상 $r \times 1$ 이다.Latent Factors원래 데이터의 차원을 $D$, 그리고 축소된(혹은 잠재공.. 2023. 10. 7.
[CS246] CURE Algorithm: Extension of k-means to clusters of arbitrary shapes Motivationk-mean과 BFR 알고리즘은 convex하거나 fixed-axis와 같은 클러스터 shape에 여러 가정이 있었다.CURE 알고리즘은 이러한 cluster shape에 어떠한 가정을 하지 않고 유클리드 거리만을 가정한다. 데이터가 정규분포일 필요도 없고, 고정된 축일 필요도 없다. 따라서 centroid 개념도 필요하지 않다. 대신에, collection of representative points가 클러스터의 표현을 나타낸다.클러스터 개수는 $k$개라고 가정한다. CURE는 Clustering Using REpresentatives의 앞글자를 따온 것이고, 원래 논문의 제목은  "CURE: An Efficient Clustering Algorithm for Large Databas.. 2023. 10. 2.
[CS246] BFR Algorithm: Extension of k-means to large data Motivationk-mean 알고리즘은 모든 데이터를 메모리에 올리고 클러스터링 알고리즘을 수행한다.그러나 현실세계의 데이터는 너무 커서(데이터베이스로 관리 등) 메인메모리에 올릴 수 없다.BFR 알고리즘을 매우 큰 데이터(disk-resident data sets)에 k-mean 클러스터링을 적용하는 알고리즘이다. BFR은 논문의 세 저자 Paul S. Bradley, Usama M. Fayyad, Cory A. Reina의 앞글자를 딴 것이다.(논문: Scaling Clustering Algorithms to Large Database)BFR OverviewAssume모든 클러스터는 axis-aligned ellipse이다. (그러나 각 axis마다 표준편차가 다른 것은 허용된다)Ideadata p.. 2023. 10. 1.
[CS246] Finding Similar Items (6) - LSH Family for Cosine Distance 이전까지 LSH를 구할 때 자카드 유사도를 이용했다.이번 포스트에서는 여러가지 유클리드/비유클리드 distance를 소개하고, 코사인 거리를 이용한 LSH를 알아보자.※ 정확히는 자카드 유사도는 거리는 아니다. (자카드 거리) = 1 - (자카드 유사도) 이다.Distance MeasuresAxioms of a Distance Measure$d$가 아래 4가지 조건을 충족하면 distance measure(거리 측도)라고 한다.$d(x, y) \ge 0$$d(x,y)=0 \text{ iff } x=y$$d(x, y) = d(y,x)$ (symmetric, 대칭성)$d(x,y) \le d(x,z) + d(z,y)$ (triangle inequality, 삼각부등식)다양한 유클리드/비유클리드 거리가 있지만,.. 2023. 9. 23.
[CS246] Finding Similar Items (5) - LSH Family Locality-Sensitive FamilyMeanings of Sensitivity Valuesfamily of $F$ of function은 다음을 만족하면 $(d_1, d_2, p_1, p_2)$-sensitive라고 부른다.모든 함수 $f \in F$와 점 $x,y$에 대하여 $d(x,y) \le d_1$이면, $f(x)=f(y)$일 확률은 최소 $p_1$이다.$d(x,y) \ge d_1$이면, $f(x)=f(y)$일 확률은 최대 $p_2$이다.$d$가 Jaccard distance라면 $d = 1-\text{sim}(x,y)$이므로$d(x,y) \le d_1 \Rightarrow 1 - \text{sim}(x, y) \le d_1 \Rightarrow 1 - d_1 \le \text{sim}(.. 2023. 9. 22.
728x90
반응형

티스토리툴바