データマイニングの古典的なアルゴリズムPrefixSpanの簡単なPython実現

前言
ライブラリ依存性のない「純粋」py−based PrefixSpanアルゴリズムをpythonで実現した.
Github倉庫https://github.com/Holy-Shine/PrefixSpan-py
まず韓老が提案したこのデータマイニングアルゴリズムについて、このブログをよく見ることができ、説明が非常に細かい.私の実現も基本的にこの考えに従っている.
PrefixSpanアルゴリズムの原理の総括
このアルゴリズムが何をしたのか簡単に話してください.
複数の時系列列があるとします.
シリアル番号
シーケンス列
0
1, 4, 2, 3
1
0, 1, 2, 3
2
1, 2, 1, 3, 4
3
2, 1, 2, 4, 4
4
1, 1, 1, 2, 3
上記の5つのレコード列を見ると,=(1,2,3)==というサブシーケンスが頻繁に現れることがわかり,これはすべての列における潜在的な==シーケンスモード==である可能性が高い.ウイルス攻撃の例を挙げると、すべてのデバイスが1日以内に受けた攻撃シーケンスに共通のサブシーケンス(攻撃タイプ、攻撃開始者ip)があり、このサブシーケンスは同じハッカー組織が開始した大規模な攻撃である可能性が高い.PrefixSpanは、この潜在的なシーケンスパターンを効率的に検出するために使用される.
1.コードの概要
アルゴリズム全体は約120行のコードを実現し、キー関数は4つで、構造は以下の通りである.

|__PrefixSpan(...)  # PrefixSpan
    |__createC1(...)  #         
       |__rmLowSup(...) #            support 
    |__psGen(...)   #          
    |__genNewPostfixDic(..) #              

2.実装の詳細
データ・セットの長さを次のように仮定します(上記の表に対応します).

D = [
    [1,4,2,3],
    [0, 1, 2, 3],
    [1, 2, 1, 3, 4],
    [2, 1, 2, 4, 4],
    [1, 1, 1, 2, 3],
]

各データはシーケンスを表します.
アルゴリズムの流れは大体以下の通りである.

#                
L1, postfixDic = createC1(D, minSup)
#       L，        
L = [], k = 2
L.append(L1)
#       1，      ，         =0   ，    
while len(L[k-2]) > 0:
    #           （       1）
    Lk = psGen()
    #           
    posfixDic = genNewPostfixDic()
    #        
    L.append(Lk)
    k+=1

2.1初期プレフィックスセットの作成
まず、createC1のコードリストを見てみましょう.

def createC1(D, minSup):
    '''         ，    1     
    
    '''
    C1 = []
    postfixDic={}  
    lenD = len(D)

    for i in range(lenD):
        for idx, item in enumerate(D[i]):
            if tuple([item]) not in C1:
                postfixDic[tuple([item])]={}
                
                C1.append(tuple([item]))
            if i not in postfixDic[tuple([item])].keys():
                postfixDic[tuple([item])][i]=idx

    L1, postfixDic = rmLowSup(D, C1, postfixDic, minSup)              
    
    return L1, postfixDic

パラメータ:

D:データセット

minSup:PrefixSpanアルゴリズムのキーパラメータmin_support

戻り値:

L 1:低supportセットを除く候補プレフィックスセット

postfixDic:候補セットに対応する接尾辞セット

プレフィックスセットC 1
初期プレフィックスセットは、単一の要素のみを含むセットを含み、rmLowSupメソッドを呼び出す前に、上述したコードの初期プレフィックスセットC1の結果は、[(0,),(1,),(2),(3,),(4,)](各プレフィックスはtupleの形式であり、主にhashを可能にするためである);
接尾辞セットpostfixDicpostfixDicは接頭辞セットC1の接尾辞で、Python辞書です.各要素は、データセットのあるシーケンスで最も早く現れた現在の接頭辞の末尾位置を表します(このように処理すると、後続の接尾辞にアクセスするときに、最初から遍歴する必要はありません).例えば、上記のコードを実行した後:postfixDic[(1,)]={0:0, 1:1, 2:0, 3:1, 4:0}
データセットDを振り返ると、1は各行に現れ、第1行(以下、0と表記する)の末尾は0、第2行の位置は1...(位置0から)
次のように類推します.postfixDic[(1,2,3)]={0:3, 1:3, 2:3, 4:4}
接頭辞(1,2,3)は0,1,2,4行目に現れ、1行目の末尾に3,2行目の3...
同時に、len(postfixDic[prefix])を呼び出すと、接頭辞prefixがどのくらいのシーケンスに現れたかを知ることができ、これによって低support接頭辞を削除することができる.
低support接頭辞の削除rmLowSup関数のリストは次のとおりです.

def rmLowSup(D,Cx, postfixDic,minSup):
    '''
               support    
    '''
    Lx = Cx
    for iset in Cx:
        if len(postfixDic[iset])/len(D) < minSup:
            Lx.remove(iset)
            postfixDic.pop(iset)
        
    return Lx, postfixDic

接尾辞セットおよびpostfixDicの説明に従って、接頭辞prefixの支持度は、len(postfixDic[prefix])/len(D)、例えば、上記接頭辞(1,2,3)の支持度は4/5=0.8であり、閾値minSupより低い接頭辞およびそれに対応するpostfixDicのkeyは取り除かれる.
2.2新しい候補接頭辞セットの生成psGenコードリストは次のとおりです.

def psGen(D, Lk, postfixDic, minSup, minConf):
    '''    +1       
    '''

    retList = []
    lenD = len(D)
    #        
    for Ck in Lk:
        item_count = {}  #   item          
        #           
        for i in postfixDic[Ck].keys():
            #            
            item_exsit={}
            for j in range(postfixDic[Ck][i]+1, len(D[i])):
                if D[i][j] not in item_count.keys():
                    item_count[D[i][j]]=0
                if D[i][j] not in item_exsit:
                    item_count[D[i][j]]+=1
                    item_exsit[D[i][j]]=True

        c_items = []

        #   minSup minConf      
        for item in item_count.keys():
            if item_count[item]/lenD >= minSup and item_count[item]/len(postfixDic[Ck])>=minConf:
                c_items.append(item)
        
        #                ，        
        for c_item in c_items:
            retList.append(Ck+tuple([c_item]))
    
    return retList

現在の接頭辞セット(長さが等しい)の各接頭辞について、接尾辞セットpostfixDicによって、その可能な次の文字を掘り起こすことができる.例えば、接頭辞(1,2)のpostfixDic[(1,2)]={0:2, 1:2, 2:1, 3:2, 4:3}は、0,1,2,3,4行目に接頭辞(1,2)が存在することを示し、各行の接頭辞末尾位置、例えば0行目の末尾位置において、[postfixDic[(1,2)][0], len(D[0]))の範囲内で条件に適合する新しい要素、すなわち0行目の[2,4]の範囲内で検索することができる.
具体的な方法は、接尾辞の異なる要素が現在の行に現れるかどうかを統計し、それらが現れる行数を統計することです.検索プロセスは次の表に示します(対応する関数リストの前半).
行/要素候補の検索
0
1
2
3
4
0
0
0
0
1
0
1
0
0
0
1
0
2
0
1
0
1
1
3
0
0
1
0
1
4
0
0
0
1
0
総計
0
1
1
4
2
候補要素3,4がそれぞれ4回と2回現れていることがわかり、候補接頭辞(1,2,3)と(1,2,4)が5行のシーケンスの4行と2行に現れていることを示し、それらのsupport値は0.8と0.5とすぐに計算できる.
従来のPrefixSpanはここでのみmin_supportのポリシーは候補接頭辞セットをフィルタし、コードにはmin_が同時に使用されます.confidenceパラメータ、ここでは詳しく説明しません.
2.3接尾辞セットとpostfixDicの更新
コードリストを見てみましょう.

def genNewPostfixDic(D,Lk, prePost):
    '''          PrefixSpan  

      ：
        D：   
        Lk:      
        prePost:           

        ：
        (1,2)         (1,)       
    e.g.
        postifixDic[(1,2)]={1:2,2:3}     (1,2)         2，       3
    '''
    postfixDic = {}

    for Ck in Lk:
        # (1,2)         (1,)      
        postfixDic[Ck]={}
        tgt = Ck[-1]
        prePostList = prePost[Ck[:-1]]
        for r_i in prePostList.keys():
            for c_i in range(prePostList[r_i]+1, len(D[r_i])):
                if D[r_i][c_i]==tgt:
                    postfixDic[Ck][r_i] = c_i
                    break
    
    return postfixDic

次に、新しい候補接頭辞セットに基づいて接尾辞セットとpostfixDicを更新します.そのため、古い接頭辞セットpostfixDicを補助として必要とし、時間の複雑さを大幅に低減することができます.
例えば、接頭辞(1,2,3)の接尾辞を更新し、Dの0行目からすべてのシーケンスを巡回する必要はありません.(1,2,3)は必ず接頭辞(1,2)から来るので、接頭辞(1,2)が現れる行を巡って検索すればよいだけで、これも古い接頭辞セットが必要な理由です.
次に簡単です.これらの行で、新しい要素の位置を見つければいいです.例えば、接頭辞(1,2)の場合、その接尾辞postfixDic[(1,2)]={0: 2, 1: 2, 2: 1, 3: 2, 4: 3}は、0、1、2、3、4行のこれらの位置+1で3という要素が存在するかどうかを探し始める.上記のコードはこれです.
このようにして、条件に合致するすべてのサブシーケンスを得ることができます.
転載先:https://www.cnblogs.com/HolyShine/p/11176843.html