728x90 반응형 분류 전체보기268 [CS246] Filtering Data Streams Filtering with Hash Table, Bloom FilterApplicationEmail spam filtering (이번 포스팅에서 자주 사용될 예시이다)100만명의 user에 대하여 각 user마다 1000개의 good(trusted) 주소가 있다고 하자.good(trusted) mail은 NOT spam이다.Publish-subscribe systemsnews 기사 데이터를 모으고 있다고 하자. (포털 사이트)어떤 keyword에 대하여 관심이 있는 기사를 맞춰 제공할 수 있다.Content filtering보고싶은/보고싶지않은 컨텐츠를 필터링할 수 있다광고시스템, 추천시스템 등 Bloom Filter: Algorithm우리가 필터링하고 싶은 key의 집합을 $S$라 하자.길이가 $n$인.. 2023. 12. 19. [Community Detection] Spectral Clustering Spectral Clustering: Graph Cut with EigenvectorsGraph 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 Cutspar.. 2023. 12. 6. [CS246] Gradient Boosted Decision Trees (GBDT) Gradient Boosted Decision Tree: Additive LearningExample: 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$번째 instance의 predi.. 2023. 12. 4. [CS246] Sampling from a Data Stream Fixed-proportion, Fixed-size, Reservoir SamplingIntroductiondata stream은 전체 데이터를 저장할 수 없기 때문에, 샘플링을 이용한다.크게 2가지 방법이 있는데, fixed proportion 방법과 random sample of fixed size이다. Sampling a Fixed Proportiondata stream의 일정 비율(예를 들어 10% 등)만큼 샘플링하는 것이다. stream이 커질수록 sample 역시 커진다. Problem with Naive Approachstream data가 (user, query, time)이라는 tuple의 형태로 들어온다고 할 때, unique query의 비율을 추정해보자. 이때 당연히 중복되는 que.. 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 MofitsIntroduction and Motivationsubgraph는 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$ induced by $V.. 2023. 11. 28. 이전 1 ··· 7 8 9 10 11 12 13 ··· 45 다음 728x90 반응형
