728x90 반응형 분류 전체보기249 [CS246] Filtering Data Streams Filtering with Hash Table, Bloom Filter Application Email spam filtering (이번 포스팅에서 자주 사용될 예시이다) 100만명의 user에 대하여 각 user마다 1000개의 good(trusted) 주소가 있다고 하자. good(trusted) mail은 NOT spam이다. Publish-subscribe systems news 기사 데이터를 모으고 있다고 하자. (포털 사이트) 어떤 keyword에 대하여 관심이 있는 기사를 맞춰 제공할 수 있다. Content filtering 보고싶은/보고싶지않은 컨텐츠를 필터링할 수 있다 광고시스템, 추천시스템 등 Bloom Filter: Algorithm 우리가 필터링하고 싶은 key의 집합을 $S$라 .. 2023. 12. 19. [Community Detection] Spectral Clustering Spectral Clustering: Graph Cut with Eigenvectors Graph Partitioning 다음과 같은 그래프 $G = (V, E)$에 대하여 우리는 2개의 disjoint group $\{ 1,2,3 \}$와 $\{ 4,5,6 \}$로 partitioning할 수 있다. 그렇다면 어떤게 좋은(good) partition으로 정의할 수 있을까? 어떻게 효율적(efficiently)으로 partition을 구할 수 있을까? 좋은 partition은 1) 같은 그룹끼리의 연결은 최대이며 2) 다른 그룹끼리의 연결은 최소화하는 것이다. 위 그림을 예시로 들면, 그룹 A, B 내부 노드끼리의 connection은 3개이고, A와 B의 connection은 2개이다. Graph Cu.. 2023. 12. 6. [CS246] Gradient Boosted Decision Trees (GBDT) Gradient Boosted Decision Tree: Additive Learning Example: Regression 다음과 같은 데이터에 대하여 regression task를 생각해보자. \[ D = \{ (10, -10),\ (20, 7),\ (25,8),\ (35,-7) \} \] 상수를 예측하는 것부터 시작하다. 여기서 $\hat{y}_i^{(0)}=0.5$라 하자. $y$: groud truth vector $y_i$는 $i$번째 instance(data point)의 ground truth이다. $\hat{y}^{(t)}$: $t$번째 round에서 예측한 predicted value vector $\hat{y}_i^{(t)}$는 $t$번째 round에서 예측한 $i$번째 instanc.. 2023. 12. 4. [CS246] Sampling from a Data Stream Fixed-proportion, Fixed-size, Reservoir Sampling Introduction data stream은 전체 데이터를 저장할 수 없기 때문에, 샘플링을 이용한다. 크게 2가지 방법이 있는데, fixed proportion 방법과 random sample of fixed size이다. Sampling a Fixed Proportion data stream의 일정 비율(예를 들어 10% 등)만큼 샘플링하는 것이다. stream이 커질수록 sample 역시 커진다. Problem with Naive Approach stream data가 (user, query, time)이라는 tuple의 형태로 들어온다고 할 때, unique query의 비율을 추정해보자. 이때 당연히 중복되.. 2023. 12. 4. [CS246] Mining Data Streams Mining Data Streams 많은 데이터 마이닝 상황에서 데이터 크기는 알 수 없다. 이러한 데이터를 data stream이라 부른다. data stream은 무한한 데이터가 한 번에 한 원소씩 들어온다고 생각할 수 있다. Applications Mining query stremas Mining click streams Mining social network news feeds Sensor networks Telephone call records IP packets monitored as a switch Problems on Data Streams Sampling data from a stream Filtering a data stream Counting distinct elements Findi.. 2023. 12. 3. [CS224w] Subgraphs and Motifs Subgraphs and Mofits Introduction and Motivation subgraph는 network의 block과도 같다. subgraph는 network의 특징이나 구별하는데 매우 도움이 된다. 특히 많은 도메인에서 반복되는 구조는 그래프에서 어떤 기능이나 행동(function or behavior)을 결정짓는다. Definition: Subgraph 주어진 그래프 $G=(V, E)$에 대하여 2가지 방법으로 subgraph $G'=(V', E')$ 를 정의할 수 있다. Def 1. Node-induced subgraph $V' \subset V$ $E' = \{ (u,v) \in E \ | \ u, v \in V' \}$ $G'$ is the subgraph of $G$ induc.. 2023. 11. 28. 이전 1 ··· 4 5 6 7 8 9 10 ··· 42 다음 728x90 반응형
