b. Các bước thực hiện
Bước 1: Input
Tập dữ liệu D = {x1, x2,...,xn} gồm n phần tử trong không gian m
chiều.
Bước 2: Output: k cụm dữ liệu D1, D2,..., Dk thỏa mãn điều kiện:
Các phần tử trong cùng một cụm có tính chất tương tự nhau.
Các phần tử trong các cụm khác nhau có tính chất khác nhau.
Bước 3: Thuật toán
Khởi động: Chọn ngẫu nhiên k phần tử trong D làm trọng tâm Ci cho cụm Di
(i = 1, 2, ..., k).
Bước lặp:
Gán Di = ∅
Với mọi x ∈ D:
Tính khoảng cách d(x, ci) với mọi i = 1, 2, 3, ..., k.
Di = Di ∪ x nếu d(x, ci) nhỏ nhất với mọi i = 1, 2, 3, ..., k.
Lặp lại bước lặp cho đến khi quá trình hội tụ (không có sự thay đổi các phần tử trong cụm)
3.3.Thuật toán Luật kết hợp
3.3.1. Giới thiệu về thuật toán Luật kết hợp
a. Tập mục, giao dịch và cơ sở dữ liệu
Tập mục: Nếu X có k mục (tức |X| = k) thì X được gọi là k–itemset
Gọi I = {x1, x2, . . . , xn} là tập n mục (item). Một tập X ⊆ I được gọi là một tập mục (itemset).
Nếu X có k mục (tức |X| = k) thì X được gọi là k–itemset
Giao dịch: Ký hiệu D = {T1, T2, ..., Tm} là cơ sở dữ liệu gồm m giao dịch (transaction). Mỗi giao dịch Ti ∈ D là một tập mục, tức Ti ⊆ I.
b. Tập/mẫu phổ biến (frequent itemset/pattern)
Cho tập mục X (⊆ I)
Độ hỗ trợ của X, ký hiệu là sup(X, D), là số lượng giao dịch trong D
chứa tập X: sup(X, D) = |{T|T ⊆ D và X ⊆ T}|.
Độ hỗ trợ tương đối của X, ký hiệu là rsup(X, D) là số phần trăm các giao dịch trong D chứa X: rsup(X, D) = sup(X, D)/|D|.
Tập mục X được gọi là tập phổ biến trong cơ sở giao dịch D nếu up(X, D) >= minsup, với minsup là một ngưỡng độ hỗ trợ tối thiểu (minimum support threshold) do người dùng định nghĩa.
F là ký hiệu của tất cả các tập phổ biến.
F(k) là ký hiệu của tập các tập phổ biến có độ dài k.
Chia sẻ với bạn bè của bạn: |
