본문 바로가기

Computer Science/Web Information System6

[웹정보] ch06 Association Rules2 Hash-based Filtering: 문제 상황 길이가 10인 문자열로 이루어진 1billion(10^9)개의 문자열 집합 S가 있음. F를 스캔하여 S 안에 있는 문자열을 출력하고 싶음. 메인메모리는 1GB -> 10^8byte S를 메인메모리에 다 올리지 못함 Solution 8billion 비트로 이루어진 비트 배열을 만들고, 모두 0으로 설정. 범위가 [0, 8*10^9)인 해시함수 h를 선택. S의 각 문자열을 해싱에 하나의 비트로 매핑하고, 해당 비트를 1로 설정. File의 문자열에 해당하는 해시 값이 1인 경우에만 출력 문자열 집합 S에는 1billion개의 문자열이 있음. bit array는 8billion 길이임. 비트 배열의 최대 1/8이 "1"임. false positive가 있을.. 2024. 4. 20.
[웹정보] ch06 Association Rules1 Market Baskets 우리는 basket 사이의 관계가 아니라 item 사이의 관계가 궁금하다! Frequent Itemset: itemset이 support threshold 값인 s 이상 나타나면 frequent itemsets이다!! 다른 예시들 Item: 물건, basket: 구매한 물건들의 집합 Item: 문서, basket: 문장 반대로 생각할 수도 있지만 사용하는 목적에 따라 다른 거임. 즉 counting의 대상이 item이 되는 것임 몇개의 문서가 해당 문장을 포함하고 있냐 Item: 단어, basket: 웹페이지 단어로 아래와 같은 웹 마이닝을 할 수 있음 1. 페이지를 주제에 따라 클러스터화 유용한 블로그 찾기 댓글의 감정 판별 모호한 검색어로 검색된 페이지 분할 - ex. 재규.. 2024. 4. 20.
[웹정보] ch05 Link Analysis2 Topic-Specific Page Rank Some problems with page rank: 페이지 랭크가 가지고 있는 몇가지 단점은 아래와 같다! 너무 일반적인 popularity를 측정함. 이는 그냥 권위있는 페이지가 짱임. ex. apple을 검색했을 때 사과, 회사 처럼 다양하게 나오도록 못함 중요성을 측정하는 단일 지표만 사용. 다른 모델의 예: hubs and authorities가 있음 link spam에 취약 인공적인 링크가 만들어져서 페이지 랭크를 조작하는 것이 가능함. Topic-Specific Page Rank: generic한 인기 대신, 하나의 주제 내에서의 인기를 측정할 수 있다. Bias the random walk : 랜덤 워커가 이동할 때 특정 집합 S의 웹페이지에서 .. 2024. 4. 16.
[웹정보] ch05 Link Analysis1 Chapter05 Link Analysis Page Rank Simple flow page model: 페이지 P는 중요도를 outlink에게 N등분 한다. 위처럼 3개의 미지수, 3개의 식으로는 유니크한 값이 나오지는 않아서 아래와 같은 식을 추가하면 값을 보일 수 있음. Matrix formulation: 행렬 M은 웹페이지 개수 x 웹페이지 개수 형태임. i와 j가 연결 안되어 있으면 Mij = 0, 연결되어있으면 Mij = 1/n 따라서 M은 stochastic matrix임. -> 매 column의 값들을 더하면 1이 됨. r은 랭크 벡터. ri는 page i의 중요도 점수이다. 이므로 랭크 벡터 r은 eigenvector가 되고, 1은 M의 eigenvalue가 된다. Power Iterati.. 2024. 4. 15.
[웹정보] ch03 Finding Similar Items2 Mining of Massive Datasets Jure Leskovec Stanford University, Anand Rajaraman Rocketship Ventures, Jeffrey D. Ullman Stanford University Chapter03 Finding Similar Items Application: Entity Resolution Entity Resolution: 두 엔티티가 같은지를 알아내는 것! 같은 값을 가진 상황에서 이들을 merge하고 싶을 때 사용을 많이 함. Matching Customer Records 문제 A회사가 B회사의 고객리스트에 광고하고 싶어함. 그렇다면 몇 명 치 요금을 내야할까? A회사 리스트와 B회사의 리스트가 겹치는 것도 있지 않겠냐! → LSH로 .. 2024. 3. 25.
[웹정보] ch03 Finding Similar Items1 Mining of Massive Datasets Jure Leskovec Stanford University, Anand Rajaraman Rocketship Ventures, Jeffrey D. Ullman Stanford University Chapter03 Finding Similar Items Shingling 문서, 이메일 등을 set으로 전환 2-Shingle 예시 k = 2, doc = ab cab Set of 2-shingles = {ab, b_, _c, , ca} (?? , 중복이면 한번만 써도 되나) k는 보통 8, 9, 10 8비트로는 256가지 표현 가능한데 charactor는 몇가지 안됨. 1Shingle이 1바이트이지 않아도 됨. 모든 char 조합 중 사실 실제 사용하는 것은 .. 2024. 3. 15.

티스토리툴바