LAPAlgorithm/lap.py at master · andrejstrogonov/LAPAlgorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
from itertools import combinations
from collections import defaultdict

def lap_algorithm(sequences, min_support, min_confidence):
    # Step 1: Initialize candidate itemsets
    candidate_itemsets = {frozenset([item]): 1 for sequence in sequences for item in sequence}

    # Step 2: Scan the database and count support
    itemset_counts = defaultdict(int)
    for sequence in sequences:
        for itemset in candidate_itemsets:
            if itemset.issubset(sequence):
                itemset_counts[itemset] += 1

    # Step 3: Filter candidate itemsets based on min_support
    freq_itemsets = {itemset: count for itemset, count in itemset_counts.items() if count >= min_support}

    # Step 4: Linear approximation for larger itemsets
    def linear_approximation(itemsets, length):
        approximated_itemsets = {}
        for itemset in itemsets:
            for other_itemset in itemsets:
                if len(itemset.union(other_itemset)) == length:
                    combined = itemset.union(other_itemset)
                    approximated_support = min(itemsets[itemset], itemsets[other_itemset])
                    approximated_itemsets[combined] = approximated_support
        return approximated_itemsets

    k = 2
    current_itemsets = freq_itemsets
    while current_itemsets:
        approximated_itemsets = linear_approximation(current_itemsets, k)
        current_itemsets = {itemset: sum(1 for sequence in sequences if itemset.issubset(sequence)) for itemset in approximated_itemsets}
        freq_itemsets.update({itemset: count for itemset, count in current_itemsets.items() if count >= min_support})
        k += 1

    # Step 6: Generate association rules
    rules = []
    for itemset in freq_itemsets:
        for i in range(1, len(itemset)):
            for antecedent in combinations(itemset, i):
                antecedent = frozenset(antecedent)
                consequent = itemset - antecedent
                if consequent:
                    antecedent_support = freq_itemsets[antecedent]
                    itemset_support = freq_itemsets[itemset]
                    confidence = itemset_support / antecedent_support
                    if confidence >= min_confidence:
                        rules.append((antecedent, consequent, confidence))

    return freq_itemsets, rules

# Example usage
sequences = [
    ['относительный_вес=нормальный', 'зн=да'],
    ['относительный_вес=недостаточный', 'зн=да'],
    ['коронарный_риск=ниже_среднего', 'сердзаб=низкий'],
    ['коронарный_риск=средний', 'сердзаб=низкий'],
    ['старт=да', 'сердзаб=иной'],
    ['возраст=25_или_меньше', 'пол=ж', 'основная_продолжительность=72'],
    ['возраст=25_или_меньше', 'пол=м', 'основная_продолжительность=67'],
    ['возраст=25-55', 'пол=ж', 'основная_продолжительность=67'],
    ['возраст=25-55', 'пол=м', 'основная_продолжительность=62'],
    ['возраст=55_или_больше', 'пол=ж', 'основная_продолжительность=64'],
    ['возраст=55_или_больше', 'пол=м', 'основная_продолжительность=60'],
    ['вес=55_или_меньше', 'сложение=мелкое', 'пол=ж', 'относительный_вес=нормальный'],
    ['вес=85_или_больше', 'сложение=мелкое', 'пол=ж', 'относительный_вес=излишний'],
    ['вес=55-85', 'сложение=мелкое', 'пол=ж', 'относительный_вес=излишний'],
    ['вес=55_или_меньше', 'сложение=крупное', 'относительный_вес=недостаточный'],
    ['вес=55_или_меньше', 'сложение=крупное', 'пол=м', 'относительный_вес=недостаточный'],
    ['вес=55-85', 'сложение=мелкое', 'пол=ж', 'относительный_вес=излишний'],
    ['вес=55-85', 'сложение=крупное', 'пол=ж', 'относительный_вес=нормальный'],
    ['вес=55-85', 'сложение=мелкое', 'пол=м', 'относительный_вес=нормальный'],
    ['вес=55-85', 'сложение=крупное', 'пол=м', 'относительный_вес=недостаточный'],
    ['вес=85_или_больше', 'пол=ж', 'относительный_вес=излишний'],
    ['вес=85_или_больше', 'пол=м', 'сложение=мелкое', 'относительный_вес=излишний'],
    ['вес=85_или_больше', 'пол=м', 'сложение=крупное', 'относительный_вес=нормальный'],
    ['холестерин=низкий', 'жиры=излишек', 'коронарный_риск=ниже_среднего'],
    ['холестерин=низкий', 'жиры=норма', 'коронарный_риск=средний'],
    ['холестерин=излишек', 'коронарный_риск=выше_среднего'],
    ['холестерин=норма', 'коронарный_риск=средний'],
    ['соль=излишек', 'кровяное_давление=выше_среднего'],
    ['соль=норма', 'кровяное_давление=среднее'],
    ['кальций=излишек', 'риск_остеопороза=ниже_среднего'],
    ['кальций=норма', 'риск_остеопороза=средний'],
    ['кальций=низкий', 'риск_остеопороза=выше_среднего'],
    ['относительный_вес=излишний', 'коронарный_риск=выше_среднего', 'кровяное_давление=выше_среднего', 'курение=да', 'перспектива=унылая'],
    ['относительный_вес=излишний', 'коронарный_риск=выше_среднего', 'кровяное_давление=выше_среднего', 'курение=нет', 'перспектива=плохая'],
    ['относительный_вес=излишний', 'коронарный_риск=выше_среднего', 'кровяное_давление=среднее', 'курение=нет', 'перспектива=хорошая'],
    ['относительный_вес=излишний', 'сердзаб=низкий', 'кровяное_давление=среднее', 'курение=нет', 'перспектива=хорошая'],
    ['зн=да', 'сердзаб=низкий', 'кровяное_давление=среднее', 'курение=нет', 'перспектива=отличная'],
    ['зн=да', 'коронарный_риск=выше_среднего', 'кровяное_давление=среднее', 'курение=да', 'перспектива=посредственная'],
    ['зн=да', 'сердзаб=низкий', 'кровяное_давление=среднее', 'курение=да', 'перспектива=посредственная'],
    ['зн=да', 'сердзаб=низкий', 'кровяное_давление=среднее', 'курение=нет', 'перспектива=хорошая'],
    ['старт=да', 'перспектива=неизвестна'],
    ['раса=негроидная', 'происхождение=средиземноморское', 'риск=высокий'],
    ['характер=агрессивный', 'тип_личности=тип_a'],
    ['характер=мягкий', 'тип_личности=тип_b'],
    ['тип_личности=тип_a', 'риск=высокий'],
    ['старт=да', 'риск=неизвестен'],
    ['потребление_алкоголя=умеренное', 'дополн=посредственно'],
    ['потребление_алкоголя=не_употребляет', 'дополн=хорошо'],
    ['потребление_алкоголя=чрезмерное', 'дополн=плохо'],
    ['перспектива=унылая', 'риск=высокий', 'дополн=плохо', 'фактор=минус_12'],
    ['перспектива=отличная', 'риск=неизвестен', 'дополн=посредственно', 'фактор=плюс_12'],
    ['перспектива=отличная', 'риск=высокий', 'дополн=посредственно', 'фактор=ноль'],
    ['перспектива=хорошая', 'риск=высокий', 'дополн=посредственно', 'фактор=ноль'],
    ['перспектива=хорошая', 'риск=высокий', 'фактор=минус_12'],
    ['перспектива=посредственная', 'риск=высокий', 'фактор=минус_12'],
    ['перспектива=отличная', 'риск=неизвестен', 'дополн=хорошо', 'фактор=плюс_12'],
    ['перспектива=отличная', 'риск=неизвестен', 'дополн=плохо', 'фактор=плюс_12'],
    ['перспектива=посредственная', 'риск=неизвестен', 'фактор=плюс_12'],
    ['перспектива=хорошая', 'риск=неизвестен', 'фактор=ноль'],
    ['перспектива=унылая', 'риск=неизвестен', 'фактор=ноль'],
    ['старт=да', 'фактор=неизвестен'],
    ['старт=выход', 'фактор=выход'],
    ['основная_продолжительность=72', 'фактор=ноль', 'продолжительность=72'],
    ['основная_продолжительность=67', 'фактор=ноль', 'продолжительность=67'],
    ['основная_продолжительность=64', 'фактор=ноль', 'продолжительность=64'],
    ['основная_продолжительность=62', 'фактор=ноль', 'продолжительность=62'],
    ['основная_продолжительность=60', 'фактор=ноль', 'продолжительность=60'],
    ['основная_продолжительность=72', 'фактор=плюс_12', 'продолжительность=84'],
    ['основная_продолжительность=67', 'фактор=плюс_12', 'продолжительность=79'],
    ['основная_продолжительность=64', 'фактор=плюс_12', 'продолжительность=76'],
    ['основная_продолжительность=62', 'фактор=плюс_12', 'продолжительность=74'],
    ['основная_продолжительность=60', 'фактор=плюс_12', 'продолжительность=72'],
    ['основная_продолжительность=72', 'фактор=минус_12', 'продолжительность=60'],
    ['основная_продолжительность=67', 'фактор=минус_12', 'продолжительность=55'],
    ['основная_продолжительность=64', 'фактор=минус_12', 'продолжительность=52'],
    ['основная_продолжительность=62', 'фактор=минус_12', 'продолжительность=50'],
    ['основная_продолжительность=60', 'фактор=минус_12', 'продолжительность=48']
]
min_support = 2
min_confidence = 0.5

freq_itemsets, rules = lap_algorithm(sequences, min_support, min_confidence)
print("Frequent Itemsets:")
for itemset, count in freq_itemsets.items():
    print(f"{set(itemset)}: {count}")

print("\nAssociation Rules:")
for antecedent, consequent, confidence in rules:
    print(f"Rule: {set(antecedent)} -> {set(consequent)} (Confidence: {confidence:.2f})")