Принцип алгоритма Python Apriori (11)

Python

«Это 11-й день моего участия в ноябрьском испытании обновлений, ознакомьтесь с подробностями события:Вызов последнего обновления 2021 г." Алгоритм априори — это хорошо известный алгоритм анализа ассоциативных правил.

Предположим, у нас есть продуктовый магазин с ограниченным набором товаров, и нам очень интересно, какие товары часто покупают вместе. У нас есть только четыре элемента: элемент 0, элемент 1, элемент 2, элемент 3. Итак, каковы все возможные комбинации предметов, которые можно купить вместе? Эти товарные комбинации могут состоять из одного товара, такого как товар 0, или могут включать два, три или все четыре товара. Но нас не волнует, что кто-то купил два предмета 0 и четыре предмета 2, а только то, что он купил один или несколько предметов.

На изображении ниже показаны все возможные комбинации между элементами:

  • На рисунке номер элемента 0 используется для представления самого элемента 0.
  • Первый набор сверху вниз на рисункеϕ\phi, который представляет собой пустой набор или набор, не содержащий элементов.
  • Линии между наборами элементов указывают на то, что два или более набора могут быть объединены в более крупный набор.

Цель: Наша цель — найти коллекции предметов, которые часто покупают вместе. Мы используем поддержку множества для измерения его частоты.

Поддержка набора относится к тому, какая часть записей транзакций содержит этот набор.

Вопрос: Как сделать заданный набор как{0，3}, чтобы вычислить его поддержку?

  • Мы можем перебрать каждую запись и проверить, содержит ли запись 0 и 3, и если запись содержит и то, и другое, то увеличить общее количество. После сканирования всех данных разделите общее количество статистики на общее количество записей транзакций, чтобы получить поддержку.

Примечание. Описанный выше процесс и результаты относятся только к одному набору {0,3}. Необходимо повторить описанный выше процесс несколько раз, чтобы получить поддержку для каждого возможного набора. Мы можем подсчитать количество наборов на графике и увидеть, что даже для набора всего из 4 элементов требуется 15 обходов данных. По мере увеличения количества элементов количество обходов резко возрастает. Для наборов данных, содержащих N общих элементов2N−12^{N-1}Комбинация наборов предметов. И магазины нередко продают 10 000 или более товаров. Даже магазин, который продает всего 100 товаров, будет иметь1.26*10301.26 * 10^{30}возможные комбинации наборов элементов. На самом деле, даже для многих современных компьютеров выполнение вычислений занимает много времени.

Принцип априорного алгоритма может помочь нам сократить наборы элементов, которые могут представлять интерес, и сократить необходимое время вычислений.

Принцип априорного алгоритма:

  • Если набор элементов является частым, то все его подмножества являются частыми, например, предположим{1,2}часто, то{1}и{2}Также должны быть частыми.

  • Обращение этого принципа показывает, что если набор элементов встречается нечасто, то и все его надмножества также нечасты.

известные наборы предметов{2,3}бывает нечасто, то о наборе можно сразу судить{0,2,3},{1,2,3},{0,1,2,3}встречаются нечасто, поэтому поддержку этих наборов не нужно рассчитывать повторно.

Общий процесс априорного алгоритма:

  1. Соберите данные: используйте любой метод.
  2. Подготовьте данные: подойдет любой тип данных, так как мы сохраняем только коллекции.
  3. Анализ данных: используйте любой метод.
  4. Алгоритм обучения: используйте априорный алгоритм для поиска часто встречающихся наборов элементов.
  5. Алгоритмы тестирования: Процесс тестирования не требуется.
  6. Алгоритм использования: используется для обнаружения часто встречающихся наборов элементов и правил ассоциации между элементами.

Реализуйте метод сканирования набора данных:

from numpy import *


def loadDataSet():

Загрузить набор данных

 :return: dataset
    '''
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

def createC1(dataSet):
    '''
    创建C1候选项集，C1是所有大小为1的候选项集的列表
    :param dataSet:
    :return: C1
    '''
    # C1是所有大小为1的候选项集的列表
    C1 = []
    # 遍历数据集，逐个添加到C1中
    for record in dataSet:
        for item in record:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    # 使用不变集合存储C1内部的每个候选项集，那么就可以将其作为字典的Key，如果是list类型不能直接作为字典的Key
    return list(map(frozenset, C1))

def scanDataset(dataset, ck, minSupport):
    '''
    扫描数据集，判断频繁项集
    :param dataset:
    :param ck: ck是所有大小为k的候选项集的列表
    :param minSupport: 设置的最小支持度阈值
    :return: 符合条件的项集、每个项集的支持度
    '''
    # 存储项集的出现次数
    selectedSetCount = {}
    for record in dataset:    # 遍历每一条记录
        for candidateSet in ck:
            # 判断当前候选项集是不是当前记录的子集
            if candidateSet.issubset(record):    
                if candidateSet not in selectedSetCount:
                    selectedSetCount[candidateSet] = 1
                else:
                    selectedSetCount[candidateSet] += 1
    # 计算总条目数
    numItems = float(len(dataset))
    # 存储符合条件的项集
    retList = []
    # 存储项集的支持度
    supportData = {}
    for key in selectedSetCount:
        # 计算支持度
        support = selectedSetCount[key] / numItems
        if support >= minSupport:
            retList.insert(0, key)
        supportData[key] = support
    return retList, supportData

if __name__ == '__main__':
    from pprint import pprint
    dataset = loadDataSet()
    c1 = createC1(dataset)
    pprint(scanDataset(dataset, c1, 0.5))
Категории