퍼지 검색

퍼지 검색 기법은 확장 부울 모델과 퍼지 집합 이론에 기초한다.MMM(Mixed Min)과 Max(Max)와 Paice(Paice)의 두 가지 고전적인 퍼지 검색 모델이 있다.두 모델 모두 쿼리 가중치를 평가하는 방법을 제공하지 않지만, P-orms 알고리즘에서는 이를 고려한다.null

최소 및 최대 혼합 모델(MMM)

퍼지 집합 이론에서, 요소는 전통적인 멤버쉽 선택 대신에 주어진 세트 A에 대한 멤버쉽의 다양한 정도, 즉 d를_A 가지고 있다(원소는/원소가 아니다).
MMM에서^[1] 각 지수 항은 그것과 관련된 퍼지 집합을 가지고 있다.색인 용어 A에 관한 문서의 가중치는 A와 관련된 퍼지 집합에서 문서의 구성원 자격 정도라고 간주된다.조합과 교차로에 대한 조합원의 정도는 퍼지 집합 이론에서 다음과 같이 정의된다.

${\displaystyle d_{A\cap B}=min(d_{A},d_{B})}$

${\displaystyle d_{A\cup B}=max(d_{A},d_{B})}$

이에 따르면, A 또는 B 형식의 조회를 위해 검색해야 하는 문서는 A와 B 두 세트의 조합과 관련된 퍼지 집합에 있어야 한다.마찬가지로, 형식 A와 B의 질의를 위해 검색해야 하는 문서는 두 세트의 교차점과 관련된 퍼지 집합에 있어야 한다.따라서 또는 쿼리에 대한 문서의 유사성을 최대값(d_AB, d)으로 정의할 수 있으며, 문서에 대한 유사성은 최소값(d_A, d)으로_B 정의할 수 있다.MMM 모델은 쿼리 문서 유사성을 최소 문서 가중치와 최대 문서 가중치의 선형 조합으로 간주하여 부울 연산자를 부드럽게 하려고 한다.null

색인_A1 기간₁ 가중치_A22 d, d, ..., 용어 A, ..., A_n 및 질의에 대해 문서_An D가 주어지는 경우:

Q_or = (A₁, A 또는₂ ...또는_n A)
Q_and = (A와₁₂ A, ...와 A_n)

MMM 모델의 질의 문서 유사성은 다음과 같이 계산된다.

SlM(Q_or, D) = C_or1 *max(d_A1, d_A2, ..., d_An) + C_or2 *min(d_A1, d_A2, d, ..., d_An)
SlM(Q_and, D) = C_and1 *min(d_A1, d_A2, ..., d_An) + C_and2 * max(d_A1, d_A2 ..., d_An)

여기서 C_or1, C는_or2 또는 연산자에 대한 "연성" 계수, C_and1, C는_and2 및 연산자에 대한 연성 계수다.우리는 문서 가중치의 최대치를 또는 질의를 고려할 때 더 중요하고, 안과 질의를 고려할 때 최소한 더 중요하기 때문에, 일반적으로_or1 C > C와_or2and1 C > C가_and2 있다. 단순성을 위해 C_or1 = 1 - C와_or2 C_and1 = 1 - C로_and2 가정한다.

Lee와 Fox^[2] 실험은 최상의 성능이 보통 [0.5, 0.8] 범위의 C와_and1 0.2의 C에서_or1 발생한다는 것을 보여준다.일반적으로 MMM의 연산 비용은 낮고, 검색 효율은 표준 부울 모델보다 훨씬 좋다.null

파이스 모형

Paice 모델은^[3] MMM 모델의 일반적인 확장이다.지수 항에 대한 최소 및 최대 가중치만 고려하는 MMM 모형에 비해 Paice 모형은 유사도를 계산할 때 모든 항 가중치를 통합한다.

${\displaystyle S(D,Q)=\sum _{i=1}^{n}{n}{{r^{n}{r-1}*w_{di}}{\sum _{j=1}^{n}r-1}:{j-1}:{j-1}:{n-1}:{n:1}}$

여기서 r은 상수 계수이고 w는_di 쿼리의 경우 및 쿼리의 경우 오름차순, 또는 쿼리의 경우 내림차순으로 배열된다.n = 2인 경우 Paice 모델은 MMM 모델과 동일한 동작을 나타낸다.null

Lee와^[2] Fox의 실험은 r을 쿼리의 경우 1.0으로, 쿼리의 경우 0.7로 설정하면 검색 효과가 좋다는 것을 보여주었다.이 모델의 계산 비용은 MMM 모델의 계산 비용보다 높다.이는 MMM 모델은 a 및 또는 절이 고려될 때마다 항 가중치 집합의 최소 또는 최대값만 결정하면 되기 때문이며, 이는 O(n)에서 수행할 수 있다.Paice 모델에서는 및 절 또는 절이 고려되고 있는지에 따라 항 가중치를 오름차순 또는 내림차순으로 정렬할 것을 요구한다.이를 위해서는 적어도 0(n log n)의 정렬 알고리즘이 필요하다.부동 소수점 계산도 많이 필요하다.null

표준 부울 모델에 대한 개선 사항

Lee와 Fox는^[2] 표준 부울 모델을 MMM과 Paice 모델과 비교했는데, CISI, CACM, INSURC 세 가지 테스트 컬렉션이 그것이다.평균 평균 정밀도 향상에 대해 보고된 결과는 다음과 같다.

	시시	CACM	인스펙트
음.	68%	109%	195%
파이스	77%	104%	206%

이것은 표준 모델보다 매우 좋은 개선이다.MMM은 Paice와 P-norm 결과에 매우 근접해 있어 매우 좋은 기술이 될 수 있으며, 세 가지 중 가장 효율적이다.null

최근 작업

최근 강씨 등이..^[4] 개념 식별에 의해 지수화된 퍼지 검색 시스템을 고안했다.null

순수한 tf-idf 접근법에 관한 문서를 살펴보면, 심지어 정지어까지 제거하면, 문서의 주제와 관련된 단어가 남들보다 더 있을 것이고, 용어 빈도가 같기 때문에 같은 비중을 가질 것이다.만약 우리가 질의에 대한 사용자 의도를 고려한다면 우리는 문서의 조건에 더 무게를 둘 수 있다.각 용어는 해당 문서에 대한 개념의 중요성을 번역하는 특정 어휘사슬에서 개념으로 식별될 수 있다.
그들은 검색된 상위 5개 문서에 대한 평균 정밀도와 리콜에 대해 Paice와 P-norm보다 개선된 사항을 보고한다.null

자드로즈니는^[5] 퍼지 정보 검색 모델을 다시 찾았다.그는 더 나아가 퍼지 확장 부울 모델을 다음과 같이 확장한다.

• 문서에서도 키워드의 중요도 가중치로 언어 용어를 가정한다.
• 문서 및 질의의 표현에 관한 불확실성을 고려하여
• 문서와 질의의 표현에서 언어적 용어 및 Zadeh의 퍼지 논리(언어적 진술의 미적분)의 측면에서 일치점을 해석한다.
• 제안된 모델의 일부 실용적 측면, 특히 문서 및 질의 색인 기법을 다루다.

제안된 모델은 텍스트 정보 표현과 검색에 관한 부정확성과 불확실성을 모두 파악할 수 있도록 한다.null

참고 항목

• 정보 검색

추가 읽기

• Fox, E.; S. Betrabet; M. Koushik; W. Lee (1992), Information Retrieval: Algorithms and Data structures; Extended Boolean model, Prentice-Hall, Inc.

참조