2015년 3월 31일 화요일

massive mining data ch6 Frequnet Itemsets

6 Frequnet Itemsets

자주 함께 나오는 아이템 셋을 찾아보자 다를 말로하면 연관 룰을 찾는다고 할수도 있다.
이챕터에서 일단 마켓-바구니(items vs basket many to many relations ship) 모델을 소개한다.
우리의 목적은 각각의 바구니에서 동시에 같이 나오는 아이템 셋을 찾는것이다.
3장에서 나온 문제와는 다르다. 3장에서는 비슷한 바구니를 찾는거라면 여기서는 정확이 몇개의 바구니에서 나왔는지 수를 센다.
위의 차이점은 A-Prioir 알고리즘을 소개한다. 해당 알고리즘은 연관 규칙이 성립하기 위해서는 상위의 셋의 모든 서브셋이 frequent 해야 한다는 조건에 기반을 둔다.
그후 해당 알고리즘을 변형시켜 빠른 속도에 추정치를 리턴하는 변형 알고리즘들을 확인한다.
  1. 6.1 The Market-Basket Model?
    market-basket 모델은 전형적인 다대다 관례를 가진 모델이다.
    한쪽은 items 이라고 부르며 반대쪽은 baskets 이라고 한다.
    baskets은 여러개의 아이템으로 구성되 었다.
    또한 우리는 각 바스켓에 포함된 아이템의 수가 적다고 가정한다.
    또한 바스켓 자체는 매우 큰 데이터라고 가정한다.
    • 6.1.1 Definition of frequent Itemsets
      여러 바스켓에 동일한 아이템셋이 여러번 나타나면 우리는 frequent 라고 한다.
      기준을 정하기 위해 아이템셋의 모든 바크셋에서 노출 빈도수가 특정 수 s(support threshold)보다 크다면 해당 itemset을 frequent 라고 정의하자 
      ex1)
1.{Cat, and, dog, bites}
2.{Yahoo, news, claims, a, cat, mated, with, a, dog, and, produced, viable,
offspring}
3.{Cat, killer, likely, is, a, big, dog}
4.{Professional, free, advice, on, dog, training, puppy, training}
5.{Cat, and, kitten, training, and, behavior}
6.{Dog, &, Cat, provides, dog, training, in, Eugene, Oregon}
7.{Dog, and, cat, is, a, slang, term, used, by, police, officers, for, a, malefemale, relationship}
8.{Shop, for, your, show, dog, grooming, and, pet, supplies}
위와 같이 8개의 basket에 item 들이 word 로 존재할떄 해당 3이상의 frequent 아이템들을 찾아보자 
singleton sets
cat 7
and  5
dog 7
training 3
a 3
다른 단어들은 2 이하임으로 제외
dubleton을 찾아보자 싱글톤인 애들의 조합만이 더블톤이 될 가능성이 있음으로 
  training    a        and        cat
dog    4,6            2,3,7    1,2,8    1,2,3,6,7
cat    5,6            2,3,7    1,2,5
and 5            2,7
a    none
위의 조합 표를 보면 
{dog,a}        3
{dog,and}    3
{dog,cat}    5
{cat,a}        3
{cat,and}    3
triple 을 찾아보면 doubleton 조합중에서 아래의 2조합만 가능하며 실제로 카운팅해보면
{dog, cat, and}    2
{dog, cat, a}    3
{dog, cat, a}만이  trpiple 임을 알수 있다.
  1. 6.1.2 Application of Frequent Itemsets
    실재로 frequent itemsets는 월마트 등에서 유저가 쇼핑카드에 물건을 담아 사가는 것을 분석하는대서 시작했다.
    목적은 마케팅에 있다 예를 들어 맥주와 기저기과 함께 팔린다고 하자 이유는 집에 아기가 있으면 외출 할수 없기 때문에 맥주를 사간다 라는 가정이 성립된다. 그러면 기저기를 싸게 팔고 맥주값을 올린다면? 소비자는 싸게 기저기를 사서 좋고 마트는(맥주 값을 올렸기 떄문에 기저기 값을 내린 손해가 없다) 물건을 많이 팔아서 좋다. 유일하게 경쟁 마트만 손해를 본다.
    • 해당 알고리즘을 다른곳에 응용할수 있다.
    1. related concepts
      item == word, basket == document 라고 하고 stop words 를 제거 하고 자주 나오는 단어 셋을 찾아본다면 새로운 정보를 습득할수 있다. 예를 들어 트위터 메세지 에서 정말 잘 안나오는 단어인{Brad, Angelina}가 같이 나온다면 어떠한 연관 관계가 생겼다는걸 추측 할 수 있다.
    2. Plagiarism
      item == documents, basket == sentacnes 이라고 해보자
      문서는 문장으로 이루어져 있다. 만약 여러문서에서 동일한 문장이 자주 나온다면 해당 문서는 표절 문서라고 추측 할수 있다.
      items
doc1 = {
 "hello me",
 "nice to meet you",
 "origin words"
}
copydoc1 = {
 "hello me",
 "nice to meet you",
 "change words"
}
basket
basket1 = {
 "hello me",
 "nice to meet you",
 "origin words"
}
basket2 = {
 "hello me",
 "nice to meet you",
 "change words"
}
{"hello me", "nice to meet you"}is frequent item
      item 과 basket 의 관계는 다대다관계일뿐 어느 하나가 다른 하나에 완전이 포함되지 않아도 된다.
    3. Biomarkers
      item 이 두종류로 구성되어 있다.
      item == (유전적 특징 또는 피의 단백질 구조로 특징을 나타낼수있는것) 또는 질병, basket == 환자 데이터
      만약 여러 특징이 동일한 질병과 자주 frequent item set 을 이룬다면 해당 특징이 질병을 유발할수 있다고 추측 할수 있다.
  1. 6.1.3 Association Rules
    I \rightarrow j 는 I set 이 있다면 j 아이템이 같이 존재할 가능성이 높다는것이다.
    그렇다면 그 가능성은 어떻게 표현할까?
    confidence == \frac{I\bigcup \{j\}}{I}
     ex2) ex1 을 생각해보자 {cat,dog} -> and 라는 연관 규측의 confidence 를 구해보자
 {cat,dog}은 1,2,3,6,7에 존재하고 {cat,dog,and}는 1,2,7 에 존재한다. 즉 confidence 는 3/5 이다.
    연관도를 측정하는대에는 interest 라는 개념도 필요하다
    interest == \frac{I\bigcup \{j\}}{I} - \frac{\{j\}}{\{\phi\}}
    위의 식에서 \frac{\{j\}}{\{\phi\}}는 {j}가 있는 바스켓의 수, \{\phi\}은 전체 바스켓의수
    만약 양의 관계라면 증가할꺼고 음의 관계라면 감소할꺼다
    예를 들면 콜라를 사면 팹시를 사지 않을것이다.
     ex3){dog}-> cat confidence = 5/7 {}->cat 6/8(전체 8개에서 6번 나옴)
 interest == -0.036 == 0
 {cat}->kitten 
 interest =0.042 == 0
    interest 가 둘다 너무 낮기 떄문에 둘다 의미가 없다.
  1. 6.1.4 Finding Association Rules with High Confidence
    실제 오프라인 마켓에서 support 는 1% confience 는 50%이상으로 잡아야만 효과가 있다.
    즉 I\bigcup \{j\}는 충분이 높은 support를 가지고 있다.
    너무 많은 frequent itemset 이 발견된다면 s를 높여서 수를 조정하
  1. 6.2 Market Baskets and the A-Priori Alogrithm
    자 이제 기본적인 A-Priori Algorithm 을 확인하고 그후 발전된 방법에 대해서 이야기해보자
  1. 6.2.1 Representation of Marekt-Basket Data
    일단 바스켓 데이터는 파일에 바스켓 별로 저장되어 있다고 하자
     {23,456,1001}-{3,18,92,145}....
    일단 하나의 서버에서만 생각을 해보자 (뒤에가면 병렬서버 알고리즘 나옴)
    바스켓 파일의 양은 메인 메모리에 무조건 맞지 않고
    만약 아이템 쌍의 수가 매인 메모리에 맞을 정도로 작다고 가정하면 아이탬이 20 개일 경우
    20C2 로 구할수 있다.
    만약 아이탬이 크거나 쌍의 크기가 k로 증가한다면 문제가 생긴다.
    하지만 알고리즘에의해 해결 할수 있음으로 실제적으로 알고리즘의 속도는 바스켓 파일을 블락단위로 메모리에 읽는 시간으로 측정 할 수 있다. 또한 모든 알고리즘은 바스켓파일을 순차적으로 읽기 때문에 알고리즘의 속도는 파일 전체를 몇번 읽느냐로 측정하자(우리는 바스켓 파일의 크기를 조정 할수 없다)
  1. 6.2.2 Use of Main Memory for Itemset Counting
    일단 우리가 셀려고 하는 숫자가 메인 메모리에 맞지 않는다면 디스크 IO가 발생하고 알고리즘은 느려진다.
    그러므로 우리는 메모리에 맞지 않는 데이터는 처리 할 수 없다고 가정하자 
     ex)6.5 어떤 알고리즘이 아이템 쌍의 숫자를 센대고 생각해보자 그러면 우리는 nC2의 integer 를 저장할 공간이 필요하다. 쌍의 수를 약  n^2/2 라고 하고 integer 를 4 byte 라고 한다면 우리는 2n^2 byte 가 필요하다는걸 알 수 있다. 만약 메모리가 2G(2^31)이라고 한다면 n<2^15 임으로 n은 약33,000 개까지 가능하다는걸 알 수 있다.
    결국 메모리 사용량이 중요함으로 아이템이 “bread” 처럼 들어가 있을 경우 해쉬 테이블을 만들어 integer 에 mapping 하자
     1,bread
 2,cat
 3,aa
    • The Triangular-Matrix Method
      저장 공간을 삼각 벡터에 저장한다고 생각하면 공간 낭비가 됨으로 (대각선의 반이 낭비됨) (2차원 메트릭스에 저장할때) 즉 {i,j}이고 1 <= j <= i <= n이 성립할때
      k = (i - 1)(n - \frac{i}{2}) + j -i
      1차원 배열에 저장할수 있다 k 가 배열 인덱스
    • The Triples Method
      i < j 일때 우리는 [i,j,c]로 저장할수있다. 해당 구조는 i,j 를 키로 한 해쉬 테이블로 만들경우 쉽게 검색 할수있다. 위의 삼각 메트릭스 저장보다 좋은건 0을 저장하지 않아도 된다는것이다.
      즉 nC2 * 1/3 보다 0을 가진 페어의 수가 많다면 Triangular-Matrix 아니면 Triples Method를 사용하는게 저장 공간 효율에 더 좋다.
      ex6.6) 10^5 개의 아이템이 존재하고 10^7개의 바스켓이 존재하고 각각의 바스켓에 10개의 아이템이 존재한다고 가정해보자 이때 triangular-matrix method 의 경우 10^5C2 = 5 * 10^9 개의 integer 숫자를 저장할 공간이 필요하다 하지만 바스켓에 존재하는 모든 페어의 개수는 10^7(10C2)임으로 = 10^7 * 10 * 9 / 2 = 10^8 * 4.5 임을 알수 있다. 극단적으로 4.5 * 10^8이 모두 0이 아 아니라고 Triples Method 를 사용한다고 하고 해당 개수에 3(i,j,c)을 곱하면 4.5 * 3 * 10^8  = 1.5  * 10^9 의 저장공간이 필요하다  이와 같은 경우 어떠한 경우에도 Triples Method 가 유리함을 알 수 있다.
  1. 6.2.3 Monotonicity of Itemsets
    만약 아이템 셋 I 가 frequent item 이되려면 모든 I의 subset은 frequent item 이어야한다.
    이유는 간단하다 J\subseteq I이라면 I를 포함한 모든 바스켓은 반드시 J를 포함해야한다.
    즉 J 의 횟수는 I 보다 크거나 같다. 또한 I가 support thread hold s 보다 높다면 J도 높다.
    또한 J는 I - J 에서 하나 두개의 element 가 빠진 바스켓에 포함 될수 있다. 위의 상황을 생각하면 J는 I 보다 크다.
     A = {a,b,c,d,e}
 B = {a,b,c,q}
 C = {a,b,c,d,z}
 I = {a,b,c,d}
 J = {a,b,c}
 S = 2 일때 
 B의 경우 I - j = {d} 를 빼고 J를 포함하는 바스켓의 예이다.
    또한 maximal 이라는 개념을 보자 만약 특정 support s를 주어준다면 우리는 해당 아이템셋을 포함한 어떠한 슈퍼 셋도 없을때 그 아이템셋을 maximal 이라고 할 수 있다. 우리가 모든 maximal itemset을 리스트 한다면 maximal list의 모든 subset itemsets들은 frequent 이고 maximal item set의 subset 이 아닌 모든 item set들은 frequent 하지 않음을 알수있다.
     ex)6.7
 ex)6.1 을 보면 s = 3
 singleton : {cat},{dog},{a},{and},{traing}
 doubleton : {dog,a},{dog,and},{dog,cat},{cat,a},{cat,and}
 triple    : {dog,cat,a}
 싱글톤을 보면 traing 을 포함한 더블톤이 존재하지 않는다 그럼으로 maximal 의 정의에 의해 traing은 maximal 이다.
 트리플을 보면 and 를 포함하지 않느다 즉 {dog,and},{cat,and}은 maximal 이다.
 또한 {dog,cat,a} 는 maximal 이다.
  1. 6.2.4 Tyranny of Counting Pairs
    지금까지 우리는 쌍을 세는대 집중해 왔다 왜 그랬을까? 아이템 수가 아무리 많아도 싱글톤을 세는대 문제가 발생하는 경우는 희귀할 것이다. 물론 tripte,quadruples 를 셀때 문제가 발생 할 수 있다. 하지만 monotonicity를 사용하면 뒤로 갈수록 조합은 줄어든다.
    예를 들어 쌍의 경우에도 최초 가정인 support s 가 충분이 높다면 문제가 될게 없다.
    (싱글톤 중 support s를 만족하는 수가 작기 때문에 통과한 itemset 끼리의 조합도 적다.)
  1. 6.2.5 The A-Priori Algorithm
    자 이제 쌍을 세는대 집중해보자 만약 우리가 모든쌍을 메모리에 셀수 있을정도의 메모리가 가능하다면(triangular matrix or triple) 문제는 쉽다. 바스켓 파일을 처음부터 끝까지 읽어 내려가면서 모든 바스켓에서 루프를 두번 돌면서 모든 쌍에 대해서 카운트를 넣어주면 된다. 그후 모든 쌍에 대해서 s를 넘는 쌍을 구하면 끝이다.
    하지만 쌍이 너무 많아서 메모리에 들어갈수 없다면 어떻게 될까? 이때 해결책으로 A-priori 알고리즘이 나온다. 기본 아이디어는 카운트 하는 아이템의 숫자를 줄인다. 단 위에서처럼 한번의 리드가 아닌 2번의 리드로 처리한다.(그래도 랜덤 엑세스에 비교하면 엄청 낮은 코스트를 가진다.)
    • The First Pass of A-Priori
      두개의 테이블을 만든다. 1번 테이블은 (만약 필요하다면) name 을 integer 로 맵핑하는 테이블이다.
      1,bread
2,cat food
3,dog food
4,toy
      2번 테이블은 1차원 배열로 해당 아이템의 인덱스에 카운트를 넣기 위해 준비한다. 최초 모든 카운트는 0이다.
      우리는 바스켓 파일을 읽으면서 아이템 이름을 index 로 변환후 해당 인덱스에 +1 을 한다.
    • Between the Passes of A-Priori
      2번 테이블에서 support threshold s 보다 큰 아이템을 골라 낸다면 threshold 자체가 1%를 넘기 떄문에 많은 아이템들이 없어진다. 메모리 공간의 효율성을 위해서 좀전에 만든 1번 테이블을 다시 만든다.
      (이전 테이블 1~n, 이후 테이블 1~m)
      //2,4번이 s 보다 클경우
1,cat food
2,toy
    • The Second Pass of A-Priori
      모든 아이템 m 에대해서 쌍을 만든다. 필요한 공간은 2n^2 이 아니라 2m^2 이다. 또는 Triples Method를 사용할수도 있다.
      1.각각의 바스켓에서 frequent item을 뽑아 낸다.
2.뽑아낸 item을 이중 루프를 돌면서 가능한 모든쌍을 만든다.
3.모든 쌍에 대해서 카운트 데이터 구조에 +1 을 한다.
      마지막에 thread hold s 보다 큰 item set을 골라낸다.
  1. 6.2.6 A-Priori for All Frequent Itemsets
    만약 해당 k가 하나도 존재하지 않는다면 monotonicity 속성이 이보다큰 freqeunt set이 존재 하지 않음을 알려줌으로 stop 할 수 있다.
    그렇지 않다면 k 에서 k+1 로 갈떄 아래의 순서를 실행한다.
     1.$C_k$ k의 가능한 모든 아이템 조합들의 셋 (실제로 frequent item임을 확인하기 위해서는 카운팅 해야함)
 2.$L_k$ k의 사이중에서 실제로 freqeunt time set들의  set
    위 순서를 생각하면
    C1 -> filter -> L1 -> construct -> C2 -> filter -> L2 -> construct -> C3 ….
    C1의 경우 singleton을 찾는 작업이다. 모든 아이템에 대해서 C1을 만들고 카운팅한다. filter 에서 s가 안되는 애들을 빼내면 L1 singleton 이 나온다.
    L1 을 가지고 가능한 모든 조합을 카운팅할수 있는 C2를 정의하고 실제로 카운팅을 한다.
    (이때문터는 Triples Method가 더유리하기 떄문에 카운팅 할때 C2에 집어넣는다.)
    C2에서 s가 넘는 애들을 빼면 L2 doubltone 이 나온다.
    C3의 경우 L2의 모든 조합을 가지고 C3를 정의하고 실제로 카운팅을 한다.카운팅할떄 L2에 존재하는 애들만 조합으로 만든다.
    C3에서 s를 비교해 큰애들로 L3를 만든다.
    원하는 만큼 반복할수 있다.
    알고리즘을 요약하면 아래와 같다.
    1.C_k를 정의한다 k는 아이템 셋의 사이즈이고 모든 k-1은 L_k에 존재한다.
    2.실제로 바스켓을 읽어 드리며 C_K에 존재하는 셋을 카운트해서 L_k를 찾는다.
    3.s 가 크다면 해당 아이템은 L_k에 존재하게 된다.
     ex)6.8
 모든 아이템이 1~10의 숫자로 이루어져 있고 1~5까지가 singleton이라고 하자
 또한 {1,2},{2,3},{3,4},{4,5}만이 더블톤이고 {2,3,4} 트리플일때 
 알고리즘을 돌리자 최초 C1에는 1~10까지 의 모든 숫자가 있고 싱글톤은 1~5라고 했으니 L1은 1~5이다.
 L1의 모든 조합을 가지고 있는 셋을 C2라고 정의하자 바켓을 읽으면서 L1에 존재하는 조합들만 카운팅을 하면 C2의 조합중 {1,2},{2,3},{3,4},{4,5}이 더블톤임을 할수 있고 해당 셋이 L2이다.
 L2를 가지고 C3를 정의하고 바켓을 읽으면서 L2에 존재하는 조합들만 카운트 하면 {2,3,4}만이 트리플임을 알수 있다.

원본책  http://www.mmds.org
​
작성자:
라벨: