백엔드 개발 파이썬 튜토리얼 Python의 FP-Growth 알고리즘에 대한 자세한 설명

Python의 FP-Growth 알고리즘에 대한 자세한 설명

Jun 09, 2023 pm 08:24 PM
python 연산 fp-growth

FP-Growth 알고리즘은 고전적인 빈발 패턴 마이닝 알고리즘으로, 데이터 세트에서 자주 함께 나타나는 항목의 컬렉션을 마이닝하는 데 매우 효율적인 알고리즘입니다. 이번 글에서는 FP-Growth 알고리즘의 원리와 구현 방법을 자세히 소개하겠습니다.

1. FP-Growth 알고리즘의 기본 원리

FP-Growth 알고리즘의 기본 아이디어는 데이터 세트의 빈발 항목 집합을 표현하기 위한 FP-Tree(빈번 항목 집합 트리)를 구축하고, 빈발 항목을 마이닝하는 것입니다. FP-Tree 세트에서. FP-Tree는 후보 빈발항목집합을 생성하지 않고도 빈발항목집합을 마이닝할 수 있는 효율적인 자료구조이다.

FP-Tree에는 루트 노드와 트리 노드라는 두 부분이 있습니다. 루트 노드에는 값이 없지만 트리 노드에는 항목 이름과 항목 발생 횟수가 포함됩니다. FP-Tree에는 동일한 노드를 가리키는 링크도 포함되어 있으며 이러한 링크를 "링크 포인터"라고 합니다.

FP-Growth 알고리즘의 프로세스는 두 부분으로 구성됩니다: FP-Tree 구축 및 빈발 항목 집합 채굴:

  1. FP-Tree 구축:

각 거래에 대해 비빈번 항목을 삭제하고 지원에 따라 빈도를 계산합니다. 빈번한 항목의 크기별로 정렬하여 빈번한 항목 집합을 가져옵니다.

각 트랜잭션을 탐색하여 각 트랜잭션의 빈발 항목 집합을 나타나는 순서대로 FP-Tree에 삽입합니다. 이미 노드가 있으면 개수를 늘립니다.

  1. 빈발 항목 집합 마이닝:

FP-Tree에서 빈발 항목 집합을 마이닝하는 방법은 다음과 같습니다.

FP-Tree의 맨 아래에서 시작하여 각 항목 집합의 조건 패턴 라이브러리를 찾습니다. 이 항목 집합을 포함하는 거래입니다. 이후 조건부 패턴 라이브러리에 대해 새로운 FP-Tree를 재귀적으로 구축하고 트리 내 빈발항목집합을 검색한다.

새로운 FP-Tree에서는 각 빈번 항목을 지지도에 따라 정렬하고 후보 집합을 구성한 후 재귀적으로 채굴합니다. 빈발항목집합을 모두 찾을 때까지 위 과정을 반복합니다.

2. FP-Growth 알고리즘 구현

FP-Growth 알고리즘 구현은 Python 프로그래밍 언어를 사용할 수 있습니다. 다음은 FP-Growth 알고리즘의 구현을 보여주는 간단한 예입니다.

먼저 데이터 세트를 정의합니다. 예:

dataset = [['v', 'a', 'p', 'e', 's'],
           ['b', 'a', 'k', 'e'],
           ['a', 'p', 'p', 'l', 'e', 's'],
           ['d', 'i', 'n', 'n', 'e', 'r']]
로그인 후 복사

그런 다음 주문된 항목 세트를 생성하는 함수를 작성합니다. 예:

def create_ordered_items(dataset):
    # 遍历数据集,统计每个项出现的次数
    item_dict = {}
    for trans in dataset:
        for item in trans:
            if item not in item_dict:
                item_dict[item] = 1
            else:
                item_dict[item] += 1

    # 生成有序项集
    ordered_items = [v[0] for v in sorted(item_dict.items(), key=lambda x: x[1], reverse=True)]
    return ordered_items
로그인 후 복사

그 중 create_ordered_items 함수는 개수에 따라 주문된 항목 세트를 얻는 데 사용됩니다. 항목의 발생.

다음으로 FP-Tree를 구축하는 함수를 작성하세요.

class TreeNode:
    def __init__(self, name, count, parent):
        self.name = name
        self.count = count
        self.parent = parent
        self.children = {}
        self.node_link = None

    def increase_count(self, count):
        self.count += count

def create_tree(dataset, min_support):
    # 生成有序项集
    ordered_items = create_ordered_items(dataset)

    # 建立根节点
    root_node = TreeNode('Null Set', 0, None)

    # 建立FP-Tree
    head_table = {}
    for trans in dataset:
        # 过滤非频繁项
        filtered_items = [item for item in trans if item in ordered_items]
        # 对每个事务中的项集按频繁项的支持度从大到小排序
        filtered_items.sort(key=lambda x: ordered_items.index(x))
        # 插入到FP-Tree中
        insert_tree(filtered_items, root_node, head_table)

    return root_node, head_table

def insert_tree(items, node, head_table):
    if items[0] in node.children:
        # 如果节点已存在,则增加其计数
        node.children[items[0]].increase_count(1)
    else:
        # 如果节点不存在,则插入新的节点
        new_node = TreeNode(items[0], 1, node)
        node.children[items[0]] = new_node
        # 更新链表中的指针
        if head_table.get(items[0], None) is None:
            head_table[items[0]] = new_node
        else:
            current_node = head_table[items[0]]
            while current_node.node_link is not None:
                current_node = current_node.node_link
            current_node.node_link = new_node

    if len(items) > 1:
        # 对剩余的项进行插入
        insert_tree(items[1:], node.children[items[0]], head_table)
로그인 후 복사

create_tree 함수는 FP-Tree를 구축하는 데 사용됩니다.

마지막으로 빈발 항목 집합을 마이닝하는 함수를 작성합니다.

def find_freq_items(head_table, prefix, freq_items, min_support):
    # 对头指针表中的每个项按照出现的次数从小到大排序
    sorted_items = [v[0] for v in sorted(head_table.items(), key=lambda x: x[1].count)]
    for item in sorted_items:
        # 将前缀加上该项,得到新的频繁项
        freq_set = prefix + [item]
        freq_count = head_table[item].count
        freq_items.append((freq_set, freq_count))
        # 构建该项的条件模式库
        cond_pat_base = get_cond_pat_base(head_table[item])
        # 递归地构建新的FP-Tree,并寻找频繁项集
        sub_head_table, sub_freq_items = create_tree(cond_pat_base, min_support)
        if sub_head_table is not None:
            find_freq_items(sub_head_table, freq_set, freq_items, min_support)

def get_cond_pat_base(tree_node):
    cond_pat_base = []
    while tree_node is not None:
        trans = []
        curr = tree_node.parent
        while curr.parent is not None:
            trans.append(curr.name)
            curr = curr.parent
        cond_pat_base.append(trans)
        tree_node = tree_node.node_link
    return cond_pat_base

def mine_fp_tree(dataset, min_support):
    freq_items = []
    # 构建FP-Tree
    root_node, head_table = create_tree(dataset, min_support)
    # 挖掘频繁项集
    find_freq_items(head_table, [], freq_items, min_support)
    return freq_items
로그인 후 복사

mine_fp_tree 함수는 빈발 항목 집합을 마이닝하는 데 사용됩니다.

3. 요약

FP-Growth 알고리즘은 효율적인 빈발 패턴 마이닝 알고리즘으로, FP-Tree를 구성함으로써 후보 빈발 항목 집합을 생성하지 않고도 빈발 항목 집합을 마이닝할 수 있습니다. Python은 FP-Growth 알고리즘을 구현하는 데 매우 적합한 프로그래밍 언어입니다. Python을 사용하면 이 알고리즘을 빠르게 구현하고 실제로 빈발 항목 집합을 마이닝하는 데 사용할 수 있습니다. 이 글이 FP-Growth 알고리즘의 원리와 구현 방법을 더 잘 이해하는 데 도움이 되기를 바랍니다.

위 내용은 Python의 FP-Growth 알고리즘에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

램프 아키텍처에서 Node.js 또는 Python 서비스를 효율적으로 통합하는 방법은 무엇입니까? 램프 아키텍처에서 Node.js 또는 Python 서비스를 효율적으로 통합하는 방법은 무엇입니까? Apr 01, 2025 pm 02:48 PM

많은 웹 사이트 개발자는 램프 아키텍처에서 Node.js 또는 Python 서비스를 통합하는 문제에 직면 해 있습니다. 기존 램프 (Linux Apache MySQL PHP) 아키텍처 웹 사이트 요구 사항 ...

SCAPY 크롤러를 사용할 때 파이프 라인 영구 스토리지 파일을 작성할 수없는 이유는 무엇입니까? SCAPY 크롤러를 사용할 때 파이프 라인 영구 스토리지 파일을 작성할 수없는 이유는 무엇입니까? Apr 01, 2025 pm 04:03 PM

SCAPY 크롤러를 사용할 때 파이프 라인 영구 스토리지 파일을 작성할 수없는 이유는 무엇입니까? 토론 Data Crawler에 Scapy Crawler를 사용하는 법을 배울 때 종종 ...

Python Cross-Platform 데스크탑 응용 프로그램 개발 : 어떤 GUI 라이브러리가 가장 적합합니까? Python Cross-Platform 데스크탑 응용 프로그램 개발 : 어떤 GUI 라이브러리가 가장 적합합니까? Apr 01, 2025 pm 05:24 PM

Python 크로스 플랫폼 데스크톱 응용 프로그램 개발 라이브러리 선택 많은 Python 개발자가 Windows 및 Linux 시스템 모두에서 실행할 수있는 데스크탑 응용 프로그램을 개발하고자합니다 ...

Python Process Pool이 동시 TCP 요청을 처리하고 클라이언트가 막히게하는 이유는 무엇입니까? Python Process Pool이 동시 TCP 요청을 처리하고 클라이언트가 막히게하는 이유는 무엇입니까? Apr 01, 2025 pm 04:09 PM

Python Process Pool은 클라이언트가 갇히게하는 동시 TCP 요청을 처리합니다. 네트워크 프로그래밍에 Python을 사용하는 경우 동시 TCP 요청을 효율적으로 처리하는 것이 중요합니다. ...

Python functools.partial 객체가 내부적으로 캡슐화 한 원래 함수를 보는 방법? Python functools.partial 객체가 내부적으로 캡슐화 한 원래 함수를 보는 방법? Apr 01, 2025 pm 04:15 PM

functools.partial in Python의 파이썬 funcTools.partial 객체의 시청 방법을 깊이 탐구하십시오 ...

파이썬 모래시 그래프 그리기 : 가변적 인 정의되지 않은 오류를 피하는 방법? 파이썬 모래시 그래프 그리기 : 가변적 인 정의되지 않은 오류를 피하는 방법? Apr 01, 2025 pm 06:27 PM

Python : 모래 시계 그래픽 도면 및 입력 검증을 시작 하기이 기사는 모래 시계 그래픽 드로잉 프로그램에서 Python 초보자가 발생하는 변수 정의 문제를 해결합니다. 암호...

정확한 흰색 원형 영역을 찾기 위해 파이썬에서 고해상도 이미지의 처리를 최적화하는 방법은 무엇입니까? 정확한 흰색 원형 영역을 찾기 위해 파이썬에서 고해상도 이미지의 처리를 최적화하는 방법은 무엇입니까? Apr 01, 2025 pm 06:12 PM

흰색 영역을 찾기 위해 파이썬에서 고해상도 이미지를 처리하는 방법은 무엇입니까? 9000x7000 픽셀의 고해상도 사진 처리, 두 가지 그림을 정확하게 찾는 방법 ...

파이썬에서 대형 제품 데이터 세트를 효율적으로 계산하고 정렬하는 방법은 무엇입니까? 파이썬에서 대형 제품 데이터 세트를 효율적으로 계산하고 정렬하는 방법은 무엇입니까? Apr 01, 2025 pm 08:03 PM

데이터 변환 및 통계 : 대규모 데이터 세트의 효율적인 처리이 기사는 제품 정보가 포함 된 데이터 목록을 다른 사람으로 변환하는 방법을 자세히 소개합니다 ...

See all articles