2015년 3월 31일 화요일

solr in action ch6 Text analysis

6 Text analysis


6.1 Analyzing micro blog text

솔라가 어떻게 텍스트 분석에 접근하는 패턴을 확인하자
아래는 이번챕터에서 확인 할 컴포넌트 목록이다.
  • analyzer, tokenizer and chain of token filters
  • custom field type 정의 방법
  • 일반적인 언어 분 전략 소개(remove stop words, lowercasing, removing accents, synonym expansion, and stemming)
아래의 트위터 메세지를 생각해보자 유저는 샌프란시스코 북쪽해변에서 라떼 카페를 먹고 있다 만약 다른 유저가 샌트란시스코 북쪽 해변에서 좋은 커피집을 검색한다고 가정해보자.검색엔진의 입장에서 우리는 유저의 검색어를 생각해 축약어 SF’S 를 san francico, sf 로 변경해야 하며 악센트를 없애야 하고 기본 적인 스탑 워드도 없애야 한다.
#Yummm :) Drinking a latte at Caffé Grecco in SF's historic North Beach...
Learning text analysis with #SolrInAction by @ManningBooks on my i-Pad
위와 같은 텍스트가 솔라 텍스트 분석을 거치면 아래와 같이 변경된다. 어떤일이 벌어진걸까?
#yumm,drink,caffe ,latte,grecco,sf,north,beach
learn,text,analysis,#solrinaction,@manningbooks,my,ipad,i,pad
아래는 기본적으로 솔라에서 제공하는 텍스트 분석 툴들이다.
  • allterms -> lowercased(SF’s -> sf) | LowerCaseFilterFactory
  • a,at,in…. -> 사라짐 | StopFilterFactory
  • Drinking -> drink | KStemFilterFactory
  • SF’s -> sf, san francisco | WordDelimiterFilterFactory
  • Caffé -> caffe | ASCIIFoldingFilterFactory
  • i-pad -> ipad, i pad | WordDelimiterFilterFactory
  • Yummm -> #yumm | PatternReplaceCharFilterFactory

    우리는 이챕터에서 위의 필터들에 대해서 자세이 설명한 것이다.

6.2 Basic text analysis

책에서 준 설정으로 변경하고 예전 데이터 날리자
cp $SOLR_IN_ACTION/example-docs/ch6/schema.xml  $SOLR_INSTALL/example/solr/collection1/conf/
cp $SOLR_IN_ACTION/example-docs/ch6/wdfftypes.txt $SOLR_INSTALL/example/solr/collection1/conf/
rm -rf $SOLR_INSTALL/example/solr/collection1/data/*
filedType을 정의해보자
  • name : 전체적으로 나타낼 이름
  • class : 어떤 타입을 다룰것인가.
    <fieldType name="text_general" class="solr.TextField" positionIncrementGap="100">
    
  1. 6.2.1 Analyzer
    텍스트를 어떻게 분석할지 정한다 보통 1개이상의 analyzer 을 달며 보통 인덱스 시와 쿼리 시를 구분한다. 예를 들면 인덱스 시에는 동의어를 처리하지 않고(데이터가 커지므로) 쿼리할때 처리하면된다
    단 만약 로우어 케이스를 인덱스시에 사용했다면 쿼리 시에도 빼먹지 말고 달아주자
  2. 6.2.2 Tokenizer
    analyzer는 크게 3개로 스탭으로 텍스트를 분석한다.
    • character filtering : 6.3.1 확인
    • tokenization : 파싱
    • token filtering : 필터링
      토크나이저는 꼭 팩토리 패턴으로 만들어서 등록하자(생성자에 설정 넘겨주거나 xml에 설정 넘겨주는등에서 필요하다)
  3. 6.2.3 Token filter
    토큰에 대해 3개중 한가지 일을 처리한다.
    • 변환 : 토큰을 변경시킴 예를 들면 lowercase or stemming
    • 추가 : 동의어 등을 처리하기 위해 토큰을 추가함
    • 삭제 : stop words등을 다루기 위해 토큰을 삭제함
  4. 6.2.4 StandardTokenizer
    기본 분리 조건
    • 공백, 구두점(, :, 등)을 기준으로 단어를 분리하고 해당 공백과 구두점을 삭제
    • 인터넷 도메인 이름과 이메일을 하나의 토큰으로 리턴
    • 하이픈으로 연결된 단어를 2개의 단어로 분리(ex i-pad -> i, pad)
    • 토큰 최대 길이를 지정(기본 255)
    • 단어 앞의 #,@ 등을 삭제함
  5. 6.2.5 Removing stop words with stopFilterFactory
    언어에 따라 스탑 워드를 다르게 선택 할 수 있음 구글의 경우 인덱스는 다하고 쿼리가 올때 검색 결과에 따라 쿼리에서 스탑워드를 제거 하거나 안하거나를 판단해서 검색의 질을 높임
     <filter class="solr.StopFilterFactory" ignoreCase="true" words="lang/stopwords_en.txt" />
    
  6. 6.2.6 LowerCaseFilterFactory—lowercase letters in terms
    로우어 케이스 처리를 안한 인덱스가 유저의 쿼리와 정확이 일치한다면 검색 결과의 질을 높일수 있다. 즉 늘 상대적이다. 또한 동의어를 처리할때 동의어가 로우어 케이스 기반으로 작성되어 있다면 로우어 케이스 필터 다음에 동의어 필터를 정의 해야 한다.
  7. 6.2.7 Testting your analysis with Solr’s analysis form
    문서를 솔라에 넣지 않고 분석테스트를 할수있음 어떻게 정의해 놓은 텍스 분석 스탭을 받는지 아주 친절하게 잘나온다.
    아무런 작업을 하지 않고 한글을 테스트 해도 잘나온다
    하지만 실제로 index 에 값을 넣고 query에 한글을 테스트 하면 잘 매치되지 않는다(매치되는 단어는 연파랑색으로 디스 플레이된다.)
     http://localhost:8983/solr/#/collection1/analysis
    
    alt img

6.3 Defining a custom field type for microblog text

우리의 요구 조건에 맞추기 위해서 우리는 새로운 타입을 만들어 텍스트 분석을 해보자 요구 조건은 위와 같다
  • Drinking -> drink | stemming
  • learning -> learn | stemming
  • SF’s -> sf, san francisco | remove ‘s
  • Caffé -> caffe | remove diacritics
  • i-pad -> ipad, i pad | remove hyphen in the middle of word
  • #Yummm -> #yumm | collapse down to a max of two
  • #solrinaction,@manningbooks -> solrinaction, manningbooks | remove #,@
<fieldType name="text_microblog" class="solr.TextField" positionIncrementGap="100">
  <analyzer type="index">
    <charFilter class="solr.PatternReplaceCharFilterFactory"
                pattern="([a-zA-Z])\1+"
                replacement="$1$1"/>                    
    <tokenizer class="solr.WhitespaceTokenizerFactory"/>        
    <filter class="solr.WordDelimiterFilterFactory" 
            generateWordParts="1" 
            splitOnCaseChange="0"
            splitOnNumerics="0"
            stemEnglishPossessive="1"
            preserveOriginal="0"
            catenateWords="1" 
            generateNumberParts="1" 
            catenateNumbers="0" 
            catenateAll="0" 
            types="wdfftypes.txt"/>
    <filter class="solr.StopFilterFactory"
            ignoreCase="true"
            words="lang/stopwords_en.txt"
            />                
    <filter class="solr.LowerCaseFilterFactory"/>
    <filter class="solr.ASCIIFoldingFilterFactory"/>
    <filter class="solr.KStemFilterFactory"/>
  </analyzer>
  <analyzer type="query">      
    <charFilter class="solr.PatternReplaceCharFilterFactory"
                pattern="([a-zA-Z])\1+"
                replacement="$1$1"/>                    
    <tokenizer class="solr.WhitespaceTokenizerFactory"/>                           
    <filter class="solr.WordDelimiterFilterFactory" 
            splitOnCaseChange="0"
            splitOnNumerics="0"
            stemEnglishPossessive="1"
            preserveOriginal="0"
            generateWordParts="1" 
            catenateWords="1" 
            generateNumberParts="0" 
            catenateNumbers="0" 
            catenateAll="0" 
            types="wdfftypes.txt"/>
    <filter class="solr.LowerCaseFilterFactory"/>
    <filter class="solr.ASCIIFoldingFilterFactory"/>
    <filter class="solr.StopFilterFactory"
            ignoreCase="true"
            words="lang/stopwords_en.txt"
            />                
    <filter class="solr.SynonymFilterFactory" 
            synonyms="synonyms.txt" 
            ignoreCase="true" 
            expand="true"/>
    <filter class="solr.KStemFilterFactory"/>
  </analyzer>      
</fieldType>
  • 위와 같이 새로운 타입을 정의 하자
    위의 설정 오버뷰
  • PatternReplaceCharFilterFactory | 정규식을 사용해서 토크 나이징 전에 캐릭터를 변환한다.
  • WhitespaceTokenizerFactory | 화이트 스페이스만 사용해 토큰을 분리한다.
  • WordDelimiterFilterFactory | 알고리즘을 사용해 구두점 및 여러가지 방법으로 토큰을 분리한다.
  • ASCIIFoldingFilterFactory | 악센트 등을 가능하면 ASCII문자로 변환시킨다.
  • KStemFilterFactory | 영문에 stemming을 한다. | Porter stemmer 보다 조금들 aggressive 하다.
  • SynonymFilterFactory | 쿼리와 동일한 동의어들을 집어 넣는다.
  1. 6.3.1 Collapsing repeated letters with PatternReplaceCharFilterFactory
    솔라에서는 캐릭터 필터라는 프리프로세서를 사용할수있다. 토큰 필터와 유사하게 해당 텍스트에 대해 더하거나 변경하거나 삭제하거나 할수 있다. 솔라4에는 4개의 charfilter 가 존재한다.
    • solr.MappingCharFilterFactory | 외부 설정 파일에 설정된대로 특정 캐릭터를 변환한다.
    • solr.PatternReplaceCharFilterFactory | 정규식을 사용해 캐릭터를 다른값으로 변경한다.
    • solr.HTMLStripCharFilterFactory | 소스에 html 마크업 테그를 삭제 후 텍스트만 리턴
      <charFilter class="solr.PatternReplaceCharFilterFactory"
        pattern="([a-zA-Z])\1+"
        replacement="$1$1"/>
      
      위의 필터는 정규식 필터이다 패턴은 반복대는 1나 이상의 문자를 1번 그룹으로($1) 두번 나열 해라 라는뜻이다.
      정규식 테스트는 intellij 일 경우 cmd + f 로 테스트 하는게 최고 인거 같다 :)
  2. 6.3.2 Preserving hashtags, mentions, and hypenated terms
    StandardTokenizer 는 디펄트로 #,@,-을 단어에서 제거한다. 하지만 단어의 @를 제거 할 경우 대체적으로 서치 결과에 좋지 않는 영향을 미친다.(특히 스테밍과 합쳐지면)
    또한 #fail 이라고 쓰면 일반 적인 fail의 의미가 아니라 다른 무언과의 관계에서 만족스럽지 못함을 의미한다.(첨알았다…) 만약 우리가 특수 캐릭터등을 보존하고 싶을때를 생각해보자
    일단 StandardTokenizer는 어떻게 구현되어있을까? 만약 개발자리면 안에서 #,@등으로 그냥 split 하고 있음을 추측 할 수 있다 하지만 위 클래스는 상속하기 힘들게 되어 있다 그리고 우리는 코드 한줄 안적고 커스터 마이징 할 수 있다.
    • WhiteSpaceTokenerFactory
      그냥 화이트 캐릭터로만 분리하는애다 문제는 이렇게 하면 :),…등이 남는다.
    • WordDelimiterFilterFactory
      <filter class="solr.WordDelimiterFilterFactory" 
                generateWordParts="1" 
                splitOnCaseChange="0"
                splitOnNumerics="0"
                stemEnglishPossessive="1"
                preserveOriginal="0"
                catenateWords="1" 
                generateNumberParts="1" 
                catenateNumbers="0" 
                catenateAll="0" 
                types="wdfftypes.txt"/>
      
      wdfftypes.txt에 우리가 분리자로 사용하지 않을 # => ALPHA, @ => ALPHA 로 정의 하면 해당 단어를 분리자로 사용하지 않는다. WordDelimiterFilterFactory 예제를 아래에 나열한다.
    • 사용하면 1로 표시한다 아래는 이름 | 설명 | 디폴트 값
    • generateWordParts | 단어들을 내부 파싱규칙에 따라 분리하고 서브워드 그룹을 만든다. | 1
    • splitOnCaseChange | 카멜 케이스를 분리함 SolrInAction -> Solr In Action | 1
    • splitOnNumerics | 단어 + 숫자 들을 각각의로 분리 R2D2 -> R,2,D,2 | 1
    • stemEnglishPossessive | 영문에서 소유표현을 없앰 SF`s -> SF | 1
    • preserveOriginal | 원본을 토근으로 다시 넣음 SFs -> SFS, SF | 0
    • catenateWords | 서브워드 파트들을 하나의 단어로 연결한다. i-Pad -> iPad | 0
    • generateNumberParts | 숫자용 구두점들을 분리한다. 865-1234 -> 865,1234 | 1
    • catenatNumbers | 넘버가 서브 파트로 분리될 경우 다시 연결한다. 865-1234 -> 8651234 | 0
    • catenateAll | generateWordParts = 1, generateNumberParts = 1 일때는 모든 부분을 하나의 토큰으로 연결한다 | 0
  3. 6.3.3 Removing diacitical marks using ASCIIFolingFilterFactory
    라틴 계열의 언어에서만 동작함으로 다른 언어의 악센트를 제거 할려면 ICUFoldingFilterFactory를 사용하자
    영어에서 적용할려면 로우어 케이스 다음에 설정하는걸 추천한다.
     <filter class="solr.ASCIIFoldingFilterFactory"/>
    
  4. 6.3.4 Stemming with KStemFilterFactory
    KStemFilterFactory 머가 Porter 보다 훨씬 들 적극적으로(aggressive) 스태밍 작업을 한다.
    내부적으로는 스태밍 해서는 안되는 단어집을 들고 있다 operating
  5. 6.3.5 Injecting synonyms at query time with SynonymFilterFactory
    쿼리시에 동의어를 쿼리에 집어 넣는다. 인덱스 시에 집어넣으면 나중에 추가하면 예전 인덱스 된 애들이 문제가 생길수 있음으로 비추한다.
    보통 맨마지막에 추가한다. (변형 될 필요가 없음으로)
     <filter class="solr.SynonymFilterFactory" 
                 synonyms="synonyms.txt" 
                 ignoreCase="true" 
                 expand="true"/>
    

6.4 Advanced field attributes

> 고급 옵션을 살펴보자
- schema.xml  의 고급 옵션
- 언어별 분석
- 솔라 플러그인을 활용해 텍스트 분석을 확장하기
  1. 6.4.1 Advanced field attributes
    아래의 옵션들은 text field에만 적용
    • 속성 | true 일때 | default value
    • omitNorms | 길이 nomailztion 을 끔, 인덱싱을 빠르게하고 저장공간을 절약함, norm을 키면 짧은 문장이 긴문장과 비슷한 관계 점수를 얻을수 있음 만약 필드의 길이가 비슷하다면 norm 을 끄는걸 권장함 | false
    • termVectors | 단어 백터들을 사용해 코사인 디스턴스를 재는거 같은대 …성능에 문제 있을 여지있음 | false
    • termPositions | 보통 hit highlihting 성능을 증가 시키기 위해 사용됨 인덱스 길이 큼|false
    • termOffset | 보통 hit highlihting 성능을 증가 시키기 위해 사용됨 인덱스 길이 큼|false
    • omitNorms
      검색할떄 TF공식 사용안함 (검색시 계산 비용 줄일수 있음)
    • Terms vectors
      문서끼리 유사도 비교할때 사용 보통 (More like this)라고 부름 9장에 상세이 나옴
  2. 6.4.2 Per-language text analysis
    언어별로 는 어떻게 해야 할까?
    • 가장 간단한 방법은 언어별 인덱스를 만드는거다
      schema.xml
      <field name="text_fr" type="text_microblog_fr" indexed="true" stored="true" />
      data
      <add>
        <doc>
            <field name="lang">fr</field>
            <field name="text_fr">Le vrai philosophe n'attend rien des hommes, et il
             leur fait tout le bien dont il est capable. Voltaire</field>
         </doc>
      </add>
      
      위와 같이 언어를 처음부터 알지 못할 경우는 ch14 멀티언어에서 상세이 다룬다.
  3. 6.4.3 Extending text analysis using a Solr plugin
    이제 코드를 통해서 제공하지 않는 기능을 제공하는걸 확인해 보자 일단 aaa/dfg.com 이라는 짧은 url 이 있을때 해당 url을 원래 url로 변경해서 인덱스 하는 작업을 해보자 분석 체인 중 해당 기능은 토큰필터를 확장하는게 가장 편하기 때문에 확장해 보자 우리는 TokenFilterFactory와 TokenFilter 를 확장할것이다.
    • Custom token filter class
      책의 소스를 확인하자
      schema.xml
      <filter class="sia.ch6.ResolveUrlTokenFilterFactory" shortenedUrlPattern="http:\/\/bit.ly\/[\w\-]+" />
      
      플러그인을 만들었으면 jar 파일로 만들어 아래 설정대로 해야지 솔라에서 인식한다.
      <lib dir="plugins/" regex=".*\.jar" />
      
      플러그인 확장해서 소스 코드 짜고 jar파일 만들어서 플러그인에 넣고 스키마에 설정하고 솔라 올리면 된다.

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