본문 바로가기

검색 엔진

[박혜웅] 확장 불리언 모델(extended boolean model)

  • 확장 불리언 모델의 특징

    • 기존 불리언 모델에 순위부여 기능을 추가하기 위하여 개발

 

  • 확장 불리언 모델의 종류

    • 퍼지집합 모델
    • MMM(Mixed Min and Max) 모델 =Waller-Kraft 모델 
    • Paice 모델
    • P-Norm 모델
    • Infinite-One 모델

 

  •  불리언 모델의 제약사항과 해결방안

    • 정확한 비교만 가능하다 -> 근접연산이 가능하도록 수정
    • 불리언 연산에 대한 엄격한 해석 -> 적당한 선에서 융통성 부여

      • 불리언모델의 색인어에 대한 문헌가중치는 0 또는 1 인데 이것을 [0,1] 범위로 수정한다.
      • 예: 질의가 "A AND B AND C AND D"인 경우,

        • 불리언모델은 A,B,C,D중 1개라도 일치하지 않으면 검색하지 않는다.
        • ->사용자는 4개의 검색어중 3개만 적합한 문서도 만족할 수 있다.
      • 예: 질의가 "A OR B OR C OR D"인 경우

        • 불리언 모델은 검색어중 1개 일치하는 문서와 4개 일치하는 문서가 모두 같은 중요도를 갖는다. (순위가 없다.)
        • ->사용자는 검색어가 일치하는 개수에 따라 중요도(적합성, 유사도)이 다르다고 생각한다.
    • 불리언모델은 검색결과에 순위가 없다. -> 검색결과에 순위 부여
    • 불리언모델은 색인어에 대한 가중치가 없다. -> 색인시 색인어에 가중치 부여
    • 불리언모델은 질의용어에 대한 가중치가 없다. -> 질의의 검색어에 가중치 부여

 

  • 퍼지집합 모델

    • 불리언 연산 AND, OR 을 각 검색어의 가중치에 대한 MIN, MAX 값으로 계산한다.
    • 문헌-질의 유사도


 

  • MMM(Mixed Min and Max) 모델 =Waller-Kraft 모델

    • 퍼지집합 모델의 변형
    • 색인어에 대한 가중치중 최대, 최소값만 이용
    • 문헌-질의 유사도


    • MMM 예제

      • 조건

        • 질의= A OR B OR C
        • 가중치(A,B,C) = 0.5, 0.8, 0.6
        • r=0.7
      • 결과

        • max=0.8, min=0.5
        • SIM(D,Q) = (1-0.7)*0.5 + 0.7*0.8 = 0.71

 

  • Paice 모델

    • 퍼지집합 모델의 변형
    • 모든 색인어의 가중치 이용

      • 색인어를 가중치순으로 정렬하는데 비용 필요
    • 문헌-질의 유사도


    • Paice 예제

      • 조건

        • 질의= A OR B OR C
        • 가중치(A,B,C) = 0.5, 0.8, 0.6
        • r=0.7
      • 결과

        • 불리언연산자가 OR이므로, 내림차순으로 정렬: 0.8, 0.7, 0.5
        • SIM(D,Q) = (0.70*0.80.71*0.60.72*0.5) / (0.700.71+0.72)
           = 1.645/2.19 = 0.6689

 

  • P-Norm 모델

    • 거리기반 접근법

      • 문헌에 포함된 용어 n개에 대하여 n차원 공간 좌표 이용.
      • OR 질의는 (0,0,0,....0) 좌표로 부터의 거리 내림차순으로 정렬하여 문헌가중치 부여 (????)
      • AND 질의는 (0,0,0,....0) 좌표로 부터의 거리 오름차순으로 정렬하여 문헌가중치 부여 (????)
    • 문헌-질의 유사도



      • 상관계수 p

        • 불리언모델에서는 엄격한 계산을 하므로 ∞, 간단하계 계산할 때 1 사용
        • P값이 1보다 클 때 많은 계산 비용이 필요(지수계산)
      • 질의용어에 대한 가중치 a

        • w, (1-w) 에 a를 곱하여 사용할 수 있다
    • Paice 예제

      • 조건

        • 질의= A OR B OR C
        • 가중치(A,B,C) = 0.5, 0.8, 0.6
        • w =0.5, p=2
      • 결과

        • 분모= 0.52 + 0.52 +0.52 = 0.75
        • 분자= (0.5*0.5)2 + (0.5*0.8)2 + (0.5*0.6)2 = 0.3125
        • SIM(D,Q) = (0.3125/0.75)1/2 = 0.6455

 

  • 확장불리언 모델용 자료구조 설계
    • 문헌 자료구조

      • 문헌가중치 배열 이용: 각 색인어에 대한 가중치
      1. #define NUM_ITERM xxxx      // 장서(문헌집합)에 포함된 색인어 수
      2. typedef struct
      3. {
      4. float doc_wts[NUM_ITERM]; // 문헌가중치 = 각 색인어에 대한 가중치
      5. } DOC_STRUCT;
    • 질의 자료구조


      • 질의안에 포함된 검색어와 불리언연산자를 노드로 하는 트리구조 이용
      • 질의 자료구조 구성

        • 질의 식별자
        • 질의노드 배열(질의 트리): 색인용어 또는 연산자의 관계 표현

          • 색인용어 또는 연산자의 배열 인덱스
          • 왼쪽 자식노드
          • 오른쪽 자식노드
        • 색인용어 배열: 색인어 가중치
        • 연산자 배열: 불리언 연산자 종류 및 가중치
        1. typedef struct
        2. {
        3. long query_id;                  // 질의 식별자
        4. TREE_NODE *beg_node_array;   // 질의트리 시작위치(루트)
        5. ITERM_TUPLE *beg_item_array; // 색인어배열 시작위치
        6. OP_TUPLE *beg_op_array;      // 연산자배열 시작위치
        7. } QUERY_STRUCT;                 // 질의 자료구조
        8.  
        9. typedef struct
        10. {
        11. int iterm_op_index;   // 색인어 또는 불리언연산자에 대한 배열번호
        12. short child_index;     // 첬째 자식노드의 노드번호  (A OR B OR C에서 A)
        13. short sibling_index;    // 오른쪽 형제노드의 배열번호 (A OR B OR C에서 A의 형제노드는 B, B형제노드는 C, C는 형제노드가 없다)
        14. } TREE_NODE;            // 질의 트리 자료구조
        15.  
        16. typedef struct
        17. {
        18. long iterm_num;         // 질의안의 색인어 식별자
        19. float iterm_wt;      // 질의안의 색인어 가중치(P-norm에서만 사용)
        20. } ITERM_TUPLE;          // 질의안의 색인어 자료구조
        21.  
        22. typedef struct
        23. {
        24. int  op_type;          // 불리언연산자 종류 ( AND, OR, NOT ...)
        25. long op_coeff;         // 불리언연산자별 상관계수 (모델에 따라 다름)
        26. float op_wt;              // 연산자에 대한 가중치(옵션)
        27. } OP_TUPLE;               // 불리언연산자 자료구조