관련 규칙 - Python 기반 Apriori 알고리즘 구현

Apriori 핵심 사상: 연결 을 통 해 후보 항목 과 지지 도 를 만 든 다음 가지치기 로 빈번 한 항목 집합 을 생 성 합 니 다.
핵심 개념:

항 집: 항의 집합.k 항목 을 포함 하 는 항목 집합 을 k 항목 집합 이 라 고 합 니 다. 예 를 들 어 {a, s, d} 은 3 항목 집합 입 니 다.

지지 도: 항목 집합 A, B 가 동시에 발생 할 확률.

최소 지지 도: 통계 적 의미 에서 가장 낮은 중요성.

신뢰 도: 항 집 A 가 발생 하면 항 집 B 가 발생 할 확률.

최소 신뢰 도: 관련 규칙 의 최저 신뢰 도.

최소 지지 도 한도 값 과 최소 신뢰 도 한도 값 을 동시에 만족 시 키 는 규칙 을 강 한 규칙 이 라 고 한다.

항목 집합의 지지 도 계수 (절대 지지 도): 항목 집합의 출현 빈도, 즉 모든 항목 집합 을 포함 하 는 사무 계수.

빈번 한 항목 집합: 항목 집합 의 상대 적 인 지지 도 는 미리 정 의 된 최소 지지 도 한도 값

을 만족 시 킵 니 다.
실현 절차:
주요 사상: 사무 데이터 집중 에 존재 하 는 가장 빈번 한 항목 집합 을 찾아내 고 얻 은 최대 빈번 한 항목 집합 과 미리 설 정 된 최소 신뢰 도 한도 값 을 이용 하여 강 한 관련 규칙 을 생 성 한다.
Apriori 의 성질: 빈번 한 항목 집합 이 아 닌 모든 빈 부분 집합 도 빈번 한 항목 집합 이 어야 합 니 다.
단계:
 

모든 빈번 한 항목 집합 (지원 도 는 주어진 최소 지원 도 한도 값 보다 커 야 함) 을 찾아내 고 연결 단계 와 가지치기 단 계 를 서로 융합 시 켜 최대 빈번 한 항목 집합 LK

를 얻 습 니 다.
연결 단계: K 항목 집합 을 찾 습 니 다.
 

                주어진 최소 지지 도 한도 값 에 대해 각각 1 개의 후보 집합 C1 을 선택 하고 이 한도 값 보다 작은 항목 집합 을 제거 하면 1 개의 빈번 한 집합 L1 을 얻 을 수 있 습 니 다.

                L1 자체 연결 로 2 개의 후보 집합 C2 를 만 들 고 C2 에서 제약 조건 을 만족 시 키 는 항목 집합 을 보류 하면 2 개의 빈번 한 집합 을 얻 을 수 있 으 며 L2 로 기록 합 니 다.

                L2 와 L3 를 연결 하여 3 개의 후보 집합 C3 를 생 성하 고 C3 에서 제약 조건 을 충족 하 는 항목 집합 을 보류 하여 3 개의 빈번 한 집합 을 얻어 L3 로 기록 합 니 다. 이 순환 으로 최대 빈번 한 항목 집합 Lk 얻 기;

가지치기: 연결 단계 에 이 어 후보 항목 Ck 를 만 드 는 과정 에서 검색 공간 을 줄 이 는 목적 을 달성 합 니 다.
                Ck 는 L (k - 1) 과 LK 가 연결 되 어 생 성 되 기 때문에 Apriori 의 성질 에 따라 빈번 한 항목 집합 이 아 닌 모든 빈 부분 집합 도 빈번 한 항목 집합 이 어야 하기 때문에 이 성질 에 만족 하지 않 는 항목 집합 은 CK 에 존재 하지 않 고 만족 하지 않 는 항목 집합 을 삭제 합 니 다.
      2. 빈번 한 항목 집합 에서 강 한 관련 규칙 이 생 긴 다. 과정 1 은 예 정 된 최소 지지 도 한도 값 을 초과 하지 않 은 항목 집합 을 제거 했다.이 규칙 들 이 예 정 된 최소 신뢰 도 한도 값 을 충족 시 키 면 강력 한 관련 규칙 을 발굴 할 수 있다.
 
예시:
Apriori 알고리즘:

#-*- coding: utf-8 -*-
from __future__ import print_function    #Python3.+        
import pandas as pd

#       ，    L_{k-1} C_k   
def connect_string(x, ms):
  x = list(map(lambda i:sorted(i.split(ms)), x))
  l = len(x[0])
  r = []
  for i in range(len(x)):
    for j in range(i,len(x)):
      if x[i][:l-1] == x[j][:l-1] and x[i][l-1] != x[j][l-1]:
        r.append(x[i][:l-1]+sorted([x[j][l-1],x[i][l-1]]))
  return r

#         
def find_rule(d, support, confidence, ms = u'--'):
  result = pd.DataFrame(index=['support', 'confidence']) #      
  
  support_series = 1.0*d.sum()/len(d) #     （C1）
  column = list(support_series[support_series > support].index) #         （  ，       L1）
  k = 0
  
  while len(column) > 1:
    k = k+1
    print(u'
     %s   ...' %k)
    column = connect_string(column, ms)
    print(u'  ：%s...' %len(column))
    sf = lambda i: d[i].prod(axis=1, numeric_only = True) #           （     1,      [      ‘0 ’，‘1 ’   ，            1,       ]）
    
    #      ，     、      。       ，          。
    d_2 = pd.DataFrame(list(map(sf,column)), index = [ms.join(i) for i in column]).T
    
    support_series_2 = 1.0*d_2[[ms.join(i) for i in column]].sum()/len(d) #         （C2）
    column = list(support_series_2[support_series_2 > support].index) #        ,       ，      L2
    support_series = support_series.append(support_series_2)  #       ，   （L1+L2）
    column2 = []
    
    for i in column: #       ， {A,B,C}   A+B-->C  B+C-->A  C+A-->B？
      i = i.split(ms)
      for j in range(len(i)):
        column2.append(i[:j]+i[j+1:]+i[j:j+1])
    
    cofidence_series = pd.Series(index=[ms.join(i) for i in column2]) #        ，      
 
    for i in column2: #       
      cofidence_series[ms.join(i)] = support_series[ms.join(sorted(i))]/support_series[ms.join(i[:len(i)-1])]
    
    for i in cofidence_series[cofidence_series > confidence].index: #     
      result[i] = 0.0
      result[i]['confidence'] = cofidence_series[i]
      result[i]['support'] = support_series[ms.join(sorted(i.split(ms)))]
  
  result = result.T.sort_values(['confidence','support'], ascending = False) #    ，  (  ‘confidence’    ，  ‘support’    )
  print(u'
   ：')
  print(result)
  
  return result

 
파일 읽 기, 계산 실행, 출력 결과:

#-*- coding: utf-8 -*-
#  Apriori            
from __future__ import print_function
import pandas as pd
from apriori import * #       apriori  （      apriori    ，   ‘apriori.py’）

inputfile = '../data/menu_orders.xls'
outputfile = '../tmp/apriori_rules.xls' #    
data = pd.read_excel(inputfile, header = None)

print(u'
       0-1  ...')
ct = lambda x : pd.Series(1, index = x[pd.notnull(x)]) #  0-1       (            1，      。0- ，1- )
b = map(ct, data.as_matrix()) # map    
data = pd.DataFrame(list(b)).fillna(0) #      ，   0  
print(u'
    。')
del b #      b，    

support = 0.2 #     
confidence = 0.5 #     
ms = '---' #   ，  '--'，        ， A--B。               

find_rule(data, support, confidence, ms).to_excel(outputfile) #    

 
lambda 문법:
 

lambda argument_list:expression

map:
 

b = map(ct, data.as_matrix()) # map    , data.as_matrix()         ct   

python 에서 함수 식 프로 그래 밍 은 주로 몇 가지 함수 의 사용 으로 구성 된다.

map (): 하나씩 옮 겨 다 니 며 함 수 를 map () 목록 의 모든 요소 에 하나씩 적용 합 니 다.  (본질 적 으로 for 명령)

lambda (): 행 내 함수, 익명 함수.lambda arguements=expression

reduce (): 재 귀 계산 에 사용,

             reduce (lambda x, y: x * y, range (1, n + 1) 는 먼저 목록 의 앞의 두 요 소 를 함수 lambda 의 매개 변수 로 연산 한 다음 에 연산 결과 와 세 번 째 숫자 를 매개 변수 로 한 다음 에 연산 결과 와 네 번 째 숫자 를 함수 의 매개 변수 로 합 니 다.
      4. filter (): 필 터 는 목록 의 조건 에 맞 는 요 소 를 선별 하 는 데 사 용 됩 니 다.우선 선택 은 bool 형 함수 로 되 돌아 가 는 값 이 필요 합 니 다.
              b=filter( lambda x : x>5 and x<8 , range(10) )   함수 lambda 를 판단 하여 이 함 수 를 range (10) 의 모든 요소 에 작용 합 니 다. "True" 라면 "선택" 요 소 를 선택 하고 마지막 으로 조건 을 만족 시 키 는 모든 요 소 를 하나의 목록 으로 구성 합 니 다.
         
오류 교정:
 

result = result.T.sort(['confidence','support'], ascending = False)

오류 발생: AttributeError: 'DataFrame' object has no attribute 'ort'
다음으로 변경:

 result = result.T.sort_values(['confidence','support'], ascending = False) 

 
참고 문헌: