Aether_Q

集合内のアイテム数が0より大きい間  
	k個のアイテムからなる候補アイテムセットのリストを構築  
	データをチェックして各アイテムセットが頻繁であることを確認  
		データセット内の各取引記録tranに対して  
		各候補アイテムセットcanについて： 
			canがtranの部分集合であるか確認： 
				もしそうなら、canのカウント値を増加  
		各候補アイテムセットについて： 
		そのサポート度が最小値を下回らない場合、そのアイテムセットを保持 
		すべての頻繁アイテムセットリストを返す
	頻繁アイテムセットを保持し、k+1個のアイテムからなる候補アイテムセットのリストを構築
		頻繁アイテムセットの第二定理：非頻繁アイテムセットの超集合は必ず非頻繁である

# Aprioriアルゴリズムの補助関数

def loadDataSet():
    """
    テスト用の簡単なデータセットを作成
    """
    return [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]

def creatC1(dataSet):
    """
    入力：データセットdataSet
    出力：C1はサイズ1のすべての候補アイテムセットの集合
    プロセス：まず空のリストC1を作成し、これをすべての重複しないアイテム値を格納するために使用します。次に、データセット内のすべての取引記録を反復処理します。各記録に対して、記録内の各アイテムを反復処理します。もしあるアイテムがC1に存在しない場合、それをC1に追加します。ここでは、単純に各アイテムを追加するのではなく、そのアイテムのみを含むリストを追加します。これは、各アイテムの集合を構築するためです。なぜなら、Aprioriアルゴリズムの後続の処理では集合操作が必要だからです。Pythonは単一の整数のみを持つ集合を作成できないため、ここではリストを使用する必要があります（興味のある読者は試してみてください）。これが、単一アイテムリストからなる大きなリストを使用する理由です。最後に、大きなリストをソートし、その中の各単一要素リストをfrozenset()にマッピングし、最後にfrozensetのリストを返します。
    詳細：アルゴリズムは最初に入力データから候補アイテムセットリストを抽出するため、ここでは特別な関数が必要です。その後のアイテムセットリストは特定の形式で保存されます。ここで使用される形式はPythonのfrozenset型です。frozensetは「凍結」された集合を指し、つまりそれらは変更不可能であり、ユーザーはそれらを変更できません。ここではset型ではなくfrozensetを使用する必要があります。なぜなら、後でこれらの集合を辞書のキーとして使用する必要があるからです。frozensetを使用することでこれを実現できますが、setではできません。
    """
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
                
    C1.sort()
    return map(frozenset, C1)

def scanD(D, Ck, minSupport):
    """
    入力：データセット、候補アイテムセットリストCk、興味のあるアイテムセットの最小サポート度minSupport
    出力：この関数はCkからLkを生成し、さらにサポート度値を含む辞書を返します
    プロセス：関数はまず空の辞書ssCntを作成し、データセット内のすべての取引記録とC1内のすべての候補セットを反復処理します。C1内の集合が記録の一部である場合、辞書内の対応するカウント値を増加させます。ここで辞書のキーは集合です。データセット内のすべてのアイテムとすべての候補セットをスキャンした後、サポート度を計算する必要があります。最小サポート度要件を満たさない集合は出力されません。関数はまた、最小サポート度要件を満たす集合を含む空のリストを最初に構築します。次のループでは、辞書内の各要素を反復処理し、サポート度を計算します。サポート度が最小サポート度要件を満たす場合、辞書の要素をretListに追加します。関数は最後に最頻繁アイテムセットのサポート度supportDataを返します。
    詳細：retList.insert(0,key)という文を使用して、リストの先頭に任意の新しい集合を挿入できます。もちろん、必ずしも先頭に挿入する必要はありません。これは、リストを整理されたように見せるためです。
    """
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not ssCnt.has_key(can): ssCnt[can]=1
                else: ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.insert(0, key)
        supportData[key] = support
    return retList, supportData

# Aprioriアルゴリズム

def aprioriGen(Lk, k):
    """
    入力：頻繁アイテムセットリストLk、アイテムセット要素数k
    出力：候補アイテムセットCk
    例：{0}、{1}、{2}を入力として、{0,1}、{0,2}、および{1,2}を生成します
    プロセス：まず空のリストを作成し、次にLk内の要素数を計算します。次に、Lk内の各要素を他の要素と比較します。これは2つのforループを使用して実現できます。次に、リスト内の2つの集合を比較します。もしこれらの2つの集合の最初のk-2個の要素がすべて等しい場合、これらの2つの集合を結合してサイズkの集合を作成します。
    詳細：k-2は少し混乱を招くかもしれません。次に、詳細をさらに議論します。{0}、{1}、{2}を使用して{0,1}、{0,2}、{1,2}を構築する場合、これは実際には単一のアイテムをまとめることです。今、{0,1}、{0,2}、{1,2}を使用して3要素アイテムセットを作成したい場合、どうすればよいでしょうか？もし各2つの集合を結合すると、{0,1,2}、{0,1,2}、{0,1,2}が得られます。つまり、同じ結果の集合が3回繰り返されます。次に、3要素アイテムセットリストをスキャンして重複しない結果を得る必要があります。私たちがやるべきことは、リストを最小限に反復処理することです。今、集合{0,1}、{0,2}、{1,2}の最初の要素を比較し、最初の要素が同じ集合に対して結合操作を行うと、何が得られるでしょうか？{0,1,2}、そして操作は1回だけです！これにより、重複値を探すためにリストを反復処理する必要がなくなります。
    """
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk):
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1==L2:
                retList.append(Lk[i] | Lk[j])
    return retList

def apriori(dataSet, minSupport = 0.5):
    """
    入力：データセットdataSet、サポート度minSupport
    出力：Lは最小サポート度を満たす頻繁アイテムセットリスト、suppDataはアイテムセットのサポート度値辞書
    プロセス：関数は候補アイテムセットのリストを生成します。これは、まずC1を作成し、次にデータセットを読み込んでD（集合リスト）に変換することで実現されます。プログラム内ではmap関数を使用してset()をdataSetリスト内の各項目にマッピングします。次に、scanD()関数を使用してL1を作成し、L1をリストLに追加します。LにはL1、L2、L3…が含まれます。今、L1が得られたので、次にL2、L3…を探し続けます。これはwhileループを使用して実現され、より大きなアイテムセットのより大きなリストを作成し、次の大きなアイテムセットが空になるまで続けます。これが少し混乱しているように聞こえる場合、後でその作業フローを見ることができます。まずaprioriGen()を使用してCkを作成し、次にscanD()を使用してCkに基づいてLkを作成します。Ckは候補アイテムセットリストであり、scanD()はCkをスキャンし、最小サポート度要件を満たさないアイテムセットを削除します。LkリストはLに追加され、kの値が増加し、上記のプロセスを繰り返します。最終的に、Lkが空になると、プログラムはLを返して終了します。
    """
    C1 = creatC1(dataSet)
    D = map(set, dataSet)
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData

# 関連ルール生成関数

def generateRules(L, supportData, minConf=0.7):
    """
    入力：頻繁アイテムセットリスト、頻繁アイテムセットのサポートデータを含む辞書、最小信頼度閾値
    出力：信頼度を含むルールリストを生成し、後で信頼度に基づいてそれらをソートできます
    プロセス：この関数はL内の各頻繁アイテムセットを反復処理し、各頻繁アイテムセットに対して単一要素集合のリストH1を作成します。単一要素アイテムセットからは関連ルールを構築できないため、2つ以上の要素を含むアイテムセットからルール構築プロセスを開始する必要があります。もし集合{0,1,2}から始めるなら、H1は[{0},{1},{2}]であるべきです。もし頻繁アイテムセットの要素数が2を超える場合、さらなる統合を考慮します。具体的な統合は関数rulesFromConseq()を通じて行われ、後で統合プロセスについて詳しく説明します。もしアイテムセットに2つの要素しかない場合、関数calcConf()を使用して信頼度値を計算します。
    """
    bigRuleList = []
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            if (i > 1):
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    """
    作用：ルールを評価し、ルールの信頼度を計算し、最小信頼度要件を満たすルールを見つけます
    プロセス：関数は最小信頼度要件を満たすルールのリストを返します。これらのルールを保存するために、空のリストprunedHを作成します。次に、H内のすべてのアイテムセットを反復処理し、それらの信頼度値を計算します。信頼度計算時にはsupportData内のサポートデータを使用します。これらのサポートデータをインポートすることで、大量の計算時間を節約できます。もしあるルールが最小信頼度値を満たす場合、それらのルールを画面に表示します。チェックされたルールも返され、次の関数rulesFromConseq()で使用されます。同時に、brlリストも充填されます。brlは前にチェックされたbigRuleListです。
    """
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq]
        if conf >= minConf:
            print(freqSet-conseq,'-->',conseq,'conf',conf)
            brl.append((freqSet-conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    """
    作用：候補ルール集合を生成します
    プロセス：最初のアイテムセットからより多くの関連ルールを生成するために、rulesFromConseq()関数を使用できます。この関数には2つのパラメータがあります：1つは頻繁アイテムセット、もう1つはルールの右部に出現する可能性のある要素リストHです。関数はまずH内の頻繁集合のサイズmを計算します。次に、その頻繁アイテムセットがサイズmの部分集合を削除できるほど大きいかどうかを確認します。もし可能であれば、それを削除します。aprioriGen()関数を使用してH内の要素の重複しない組み合わせを生成できます。この結果はHmp1に保存され、次の反復のHリストとなります。Hmp1にはすべての可能なルールが含まれます。calcConf()を使用してそれらの信頼度をテストし、ルールが要件を満たすかどうかを確認します。もし複数のルールが要件を満たす場合、Hmp1を使用してrulesFromConseq()関数を再帰的に呼び出し、これらのルールをさらに組み合わせることができるかどうかを判断します。
    """
    m = len(H[0])
    if (len(freqSet) > (m+1)):
        Hmpl = aprioriGen(H, m+1)
        Hmpl = calcConf(freqSet, Hmpl, supportData, brl, minConf)
        if (len(Hmpl) > 1):
            rulesFromConseq(freqSet, Hmpl, supportData, brl, minConf)