파이썬에서 행렬의 가능한 모든 교차점을 결정하는 가장 좋은 방법은 무엇입니까?

Question

각 행이 고유 한 단어를 나타내는 행렬 (목록 목록)이있는 경우 각 행은 고유 한 문서를 나타내며 모든 항목은 1 또는 0이며 주어진 열의 단어가 주어진 행에 대한 문서.

하나 이상의 단어가 둘 이상의 문서와 공통된 단어와 문서의 가능한 조합을 모두 결정하는 방법을 알고 싶습니다. 결과는 다음과 같이 보일 수 있습니다.

[ [[Docid_3, Docid_5], ['word1', 'word17', 'word23']], 
    [[Docid_3, Docid_9, Docid_334], ['word2', 'word7', 'word23', 'word68', 'word982']], 
    ... 

... 가능한 조합마다 다음과 같이 표시 될 수 있습니다. 완전한 조합 세트를 제공하는 솔루션과 다른 세트의 서브 세트가 아닌 조합만을 제공하는 솔루션을 좋아할 것입니다. 예를 들어 [[Docid_3, Docid_5], ['word1', 'word17']]이 아닌 첫 번째 예제의 완전한 서브 세트이기 때문입니다.

나는 마음에 들지 않는 우아한 해결책이 있고 맥주가 도움이되지 않는다고 느낀다.

감사합니다.

Answer 1

얼마나 많은 문서가 있습니까? 몇 개의 독특한 단어가 있습니까? 얼마만큼의 RAM이 있습니까?

다음 시나리오에서 무엇을 생산할 것입니까? 문서 A에는 단어 1, 2, 3이 있습니다. B는 1, 2; C는 2, 3이 있습니다.

Answer 2

1. 텍스트를 표준화합니다. 너는 string.lowercase의 문자열 만 원한다. 다른 모든 항목은 분할/제거합니다.
2. set을 이렇게 설정하십시오. 이 같은

3. 를 사용하여 뭔가 모든 규모의 가능한 모든 그룹을 얻을 수 있습니다 :

   def get_all_lengths_combinations_of(elements): 
       for no_of_items in range(2, len(elements)+1): 
       for items in itertools.combinations(elements, no_of_items) 
        yield items  
   

   내가 진짜 itertools 마법사가 가능 izip()을 포함, 더 좋은 것을 가지고 올 것이라 확신합니다.

4. 는이 같은 set.intersection() 방법을 사용할 수 있어야 기억 단어 설정 문서 ID 대응 관계를 구축,

   set.intersection(*list_of_sets_to_intersect) 
   

Answer 3

먼저 - 0 및 1 당신의 매트릭스를한다 아주 다루기 힘든 구조로 직접 처리 할 수 ​​있습니다. "column headings"(단어)는 행렬의 첫 번째 목록 (아마도 첫 번째 항목 제외)이고 "행 표제"(docids)는 각 행의 첫 번째 항목입니다 (아마 첫 번째 행 빼기).). 그리고 (파이썬 2.6 이상 가정) :

이

def makemap(matrix): 
    im = iter(matrix) 
    words = next(im)[1:] 
    themap = {} 
    for row in im: 
    mapent = set() 
    docid = row[0] 
    for w, bit in zip(words, row[1:]): 
     try: 
     if bit: mapent.add(w) 
     except: 
     print 'w is %r' % (w,) 
     raise 
    themap[docid] = mapent 
    return themap 

는 이제 모든 문서 가능 하위 집합을 확인해야 - 부분 집합의 총 수는 거대하다 그래서 당신은 정말 당신만큼 해당 검색 나무를 가지 치기 할 모든 부분 집합 (예 : 다양한 길이의 itertools.combinations에 대한 반복)의 무차별 대입 생성은 물론 어떤 가지 치기도 수행하지 않습니다.

모든 2 조합 (모든 docids 쌍 - 물론 itertools.combinations)을 시작으로하고, 첫 번째 배치 (2+ 단어가 커먼 인 쌍)를 "가능한 2 길이 하위 집합 ". 이는 다른 매핑에서 tuple 또는 frozensets의 docids를 키로 사용할 수 있습니다.

그럼, 난 단지 총 교차 확인 (각 DOCID 더 하나 기존 가능한 N 길이의 하위 집합을 확장 하려고 것, 실현 가능한 (N + 1) - 길이 하위 집합을 만드는 것은 여전히 ​​2+ 긴 물론). 적어도 2**N 개의 하위 집합 (또는 2**N - N - 1 개의 하위 집합 중 적어도 두 개 이상은 모두 맹목적으로 시도하지 않고 적어도 일부)을 삭제하는 것이 좋습니다.

특정 N 길이 서브 세트를 확장 할 수없는 것으로 입증 된 모든 문서 식별 코드를 기록하면 더 나은 결과를 얻을 수 있습니다 (N + 1 길이의 서브 세트를 사용하지 않는 것이 좋습니다) . 이것은 가지 치기/최적화의 두 번째 레벨로 시도해 볼 가치가 있습니다.

추가 정리 작업이 필요할 수도 있지만 더 많은 가지 치기 작업을 수행 할 수는 있지만 즉시 마음에 들지는 않습니다. 그래서 여기부터 시작하겠습니다. (가독성을 위해 items 대신 iteritems, tuple 등의 frozenset 대신 마이크로 옵티 마이 제이션을 사용하는 것을 신경 쓰지는 않습니다. 모든 시퀀스가 ​​계산 된 구조의 지수 크기 인 O(N)과 비교할 때 거의 중요하지 않습니다. 물론 튜닝/최적화 단계에서 시도해 볼 가치는 있지만).

def allfeasiblesubsets(matrix): 
    mapping = makemap(matrix) 
    docids = sorted(mapping.keys()) 
    feasible_len2 = {} 
    dont_bother = dict((d, set([d])) for d in docids) 
    for d1, d2 in itertools.combinations(docids, 2): 
    commonw = mapping[d1].intersection(mapping[d2]) 
    if len(commonw) >= 2: 
     feasible_len2[d1, d2] = commonw 
    else: 
     dont_bother[d1].add(d2) 
     dont_bother[d2].add(d1) 
    all_feasible = [feasible_len2] 
    while all_feasible[-1]: 
    feasible_Np1 = {} 
    for ds, ws in all_feasible[-1].items(): 
     md = max(ds)   
     for d, w in mapping.items(): 
     if d <= md or any(d in dont_bother[d1] for d1 in ds): 
      continue 
     commonw = w.intersection(ws) 
     if len(commonw) >= 2: 
      feasible_Np1[ds+(d,)] = commonw 
    all_feasible.append(feasible_Np1) 
    return all_feasible[:-1] 

당신은 내 제안 "더 가지 치기"의 온화한 양식을 적용한 알 수 있습니다 - dont_bother 레코드 만 "호환성"한 DOCID과 다른 사람 사이 (공통의 < 2 개 단어) -이 월 이러한 "호환되지 않는 문서"의 몇 가지 쌍이 있고 간단하고 합리적으로 방해가되지 않는 경우 도움이되지만 더 어려운 "전체"대안처럼 가지 치기에서 강력하지는 않습니다. 나는 또한 feasible* dicts에있는 모든 키를 중복을 피하기 위해 중복 된 작업을 피하기 위해 docids의 정렬 된 튜플 (itertools.combinations은 원래 쌍을 제공함)로 유지하려고합니다. OK 표시

mat = [ ['doc']+'tanto va la gatta al lardo che ci lascia lo zampino'.split(), 
     ['uno', 0, 0, 0, 1, 0, 1, 0, 0, 0, 1], 
     ['due', 1, 0, 0, 0, 0, 1, 0, 1, 0, 1], 
     ['tre', 1, 0, 0, 0, 0, 0, 0, 1, 0, 1], 
     ['qua', 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]] 

mm = makemap(mat) 
print mm 
afs = allfeasiblesubsets(mat) 
print afs 

결과, 다음과 같습니다 :

여기 (이 후, 물론 기능의 itertools에 대한 import 및 collections이 같은 파일에) 내가 해봤 작은 예입니다

{'qua': set(['gatta', 'lo', 'ci', 'lardo']), 'tre': set(['lo', 'ci', 'tanto']), 'due': set(['lo', 'ci', 'lardo', 'tanto']), 'uno': set(['gatta', 'lo', 'lardo'])} 
[{('due', 'tre'): set(['lo', 'ci', 'tanto']), ('due', 'uno'): set(['lo', 'lardo']), ('qua', 'uno'): set(['gatta', 'lo', 'lardo']), ('due', 'qua'): set(['lo', 'ci', 'lardo']), ('qua', 'tre'): set(['lo', 'ci'])}, {('due', 'qua', 'tre'): set(['lo', 'ci']), ('due', 'qua', 'uno'): set(['lo', 'lardo'])}] 

물론 완전히 테스트하지 않았으므로 여전히 버그가 숨어있을 수 있습니다. BTW, 여기에 제공된 결과 (여러 가지 증가하는 길이에 대한 dicts 목록, 각 dict가 docids 세트의 정렬 된 튜플 형식을 키로 설정하고 공통 단어를 값으로 사용함)이 쉽게 게시 될 수 있기를 바랍니다. 중첩 목록과 같이 선호하는 다른 형식으로 처리됩니다.

(중요한 것은 아니지만이 예에서 사용한 텍스트는 오래된 이탈리아 속담입니다 .-)).

Answer 4

진짜 문제 크기에 대한 SO what-tried-and-true-algorithms-for-suggesting-related-articles-are-out-there

를 살펴 보자는> (100 개) 문서, 10000 개 단어를 말할 얻을 좋은 bitarray 모듈 방식, "동일한 알고리즘에 의해 말한다
(파이썬은 C보다 약 20 배 더 느리다 "). "다른 서브 세트 아닌 단지 조합"에

: (111) (111)와 × 3 서브 매트릭스로서 hit23와 2 × 2 행렬 (2 개 문서, 일반적인 3 개 단어)를 hit22 정의 등등.
주어진 hit22가 많은 hit2n에있을 수 있습니다. — 2 워드 프로세서, n 워드,
그리고 많은 hitn2 s — n 워드 프로세서, 2 워드. 재미 있네.

Monday 14Jun 추가 : bitarray를 사용하는 기능이 거의 없습니다.
(실제 문서 분류에 대한 소개/파이썬 모듈? 몰라.)

""" docs-words with bitarray, randombits """ 
# google "document classification" (tutorial | python) ... 
# https://stackoverflow.com/questions/1254627/what-tried-and-true-algorithms-for-suggesting-related-articles-are-out-there 

from __future__ import division 
import random 
import sys 
from bitarray import bitarray # http://pypi.python.org/pypi/bitarray 

__date__ = "14jun 2010 denis" 

ndoc = 100 
nbits = 1000 

exec "\n".join(sys.argv[1:]) # run this.py ndoc= ... 
random.seed(1) 
me = __file__.split('/') [-1] 
print "%s ndoc=%d nbits=%d" % (me, ndoc, nbits) 

    # bitarray stuff -- 

def bitslist(bits): 
    """ 011001 -> [1,2,5] """ 
    return [ j for j in range(len(bits)) if bits[j] ] 

hex_01 = { 
    "0": "0000", "1": "0001", "2": "0010", "3": "0011", 
    "4": "0100", "5": "0101", "6": "0110", "7": "0111", 
    "8": "1000", "9": "1001", "a": "1010", "b": "1011", 
    "c": "1100", "d": "1101", "e": "1110", "f": "1111", 
} 

def to01(x, len_): 
    x = "%x" % x 
    s = "".join(hex_01[c] for c in x) 
    return (len_ - len(s)) * "0" + s 

def randombits(nbits): 
    """ -> bitarray 1/16 1, 15/16 0 """ 
    hibit = 1 << (nbits - 1) 
    r = (random.randint(0, hibit - 1) 
     & random.randint(0, hibit - 1) 
     & random.randint(0, hibit - 1) 
     & random.randint(0, hibit - 1)) # prob 1/16 
    return bitarray(to01(r, nbits)) 

#............................................................................... 
doc = [ randombits(nbits) for j in range(ndoc) ] # ndoc x nbits 

def mostsimilarpair(): 
    """ -> (sim, j, k) most similar pair of docs """ 
    mostsim = (-1,-1,-1) 
    for j in range(ndoc): 
     for k in range(j+1, ndoc): 
       # allpairs[j,k] -> scipy.cluster.hier ? 
      sim = (doc[j] & doc[k]).count() # nr bits (words) in common, crude 
      mostsim = max(mostsim, (sim,j,k)) 
    return mostsim 

sim, jdoc, kdoc = mostsimilarpair() 
print "The 2 most similar docs:" , 
print "doc %d has %d words," % (jdoc, doc[jdoc].count()) , 
print "doc %d has %d," % (kdoc, doc[kdoc].count()) 
print "%d words in common: %s" % (sim, bitslist(doc[jdoc] & doc[kdoc])) 
print "" 

#............................................................................... 
def docslike(jdoc, thresh): 
    """ -> (doc index, sim >= thresh) ... """ 
    for j in range(ndoc): 
     if j == jdoc: continue 
     sim = (doc[j] & doc[jdoc]).count() 
     if sim >= thresh: 
      yield (j, sim) 

thresh = sim // 2 
print "Docs like %d, with >= %d words in common:" % (jdoc, thresh) 
for j, sim in docslike(jdoc, thresh): 
    print "%3d %s" % (j, bitslist(doc[j] & doc[jdoc])) 

""" 
The 2 most similar docs: doc 72 has 66 words, doc 84 has 60, 
12 words in common: [11, 51, 119, 154, 162, 438, 592, 696, 800, 858, 860, 872] 

Docs like 72, with >= 6 words in common: 
    2 [3, 171, 258, 309, 592, 962] 
... 
"""