charm.py

from collections import defaultdict
from itertools import combinations


def charm_algorithm(sequences, min_support, min_confidence):
    # Step 1: Initialize single itemsets
    itemset_counts = defaultdict(int)
    for sequence in sequences:
        for item in sequence:
            itemset_counts[frozenset([item])] += 1

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

    # Step 3: Recursive exploration to find closed itemsets
    def charm_extend(itemsets, prefix):
        closed_itemsets = {}
        for itemset in itemsets:
            new_prefix = prefix.union(itemset)
            new_support = sum(1 for sequence in sequences if new_prefix.issubset(sequence))
            if new_support >= min_support:
                closed_itemsets[new_prefix] = new_support
                # Recursive call
                new_itemsets = {i for i in itemsets if i != itemset}
                closed_itemsets.update(charm_extend(new_itemsets, new_prefix))
        return closed_itemsets

    closed_itemsets = charm_extend(set(freq_itemsets.keys()), frozenset())

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

    return closed_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

closed_itemsets, rules = charm_algorithm(sequences, min_support, min_confidence)
print("Closed Frequent Itemsets:")
for itemset, count in closed_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})")