Download Luận văn Khai phá luật theo tiếp cận tập thô
Mục lục
Phần mở đầu.5
Chương I. Tổng quan về khám phá tri thức theo tiếp cận tập thô.9
I.1. Hệ thông tin và tập thô.9
I.1.1. Một số khái niệm . 9
I.1.1.1. Khái niệm về hệ thông tin . 9
I.1.1.2. Khái niệm về bảng quyết định . 10
I.1.1.3. Quan hệ không phân biệt được trong hệ thông tin . 11
I.1.1.4. Tập mô tả được và ngôn ngữ mô tảtập . 13
I.1.2. Tập thô trong không gian xấp xỉ . 14
I.1.2.1. Tập xấp xỉ trên, xấp xỉ dưới và miền biên . 14
I.1.2.2. Hàm thô và một số độđo phụ thuộc có thuộc tính liên quan . 19
I.2. Khám phá tri thức theo tiếp cận tập thô . 20
I.2.1. Tính phụ thuộc thuộc tính trong hệ thông tin . 20
I.2.1.1. Tính phụ thuộc thuộc tính . 20
I.2.1.2. Tập thuộc tính rút gọn và tập thuộc tính nhân . 21
I.2.1.3. Ma trận phân biệt được và hàm phân biệt được . 23
I.2.2. Quá trình khám phá tri thức theo tiếp cận tập thô . 24
I.2.2.1. Sự rời rạc hoá dựa trên tập thô và lập luận logic . 25
I.2.2.2. Lựa chọn thuộc tính dựa trên tập thô với phương pháp đánh giá kinh nghiệm . 25
I.2.2.3. Khám phá luật bởi bảng phân bố tổng quát dựa trên tập thô . 27
I.2.3. Khám phá mẫu trong hệ thông tin . 27
I.3. Kết luận chương I . 29
Chương II. Khám phá luật theotiếp cận tập thô và đối
sánh với khám phá luật kết hợp . 30
II.1. Khám phá luật kết hợp, nội dung cơ bản của khám phá tri thức
trong cơ sở dữ liệu . 30
II.1.1. Luật kết hợp . 30
II.1.2. Một số cơ sở toán học khai phá luật kết hợp . 32
II.1.2.1. Tập phổ biến . 32
II.1.2.2. Khai phá luật kết hợp dựa trên tập phổ biến. 33
II.2. Quá trình khám phá tri thức theo tiếp cận tâp thô . 35
II.2.1. Quá trình khám phá luật trong bảng quyết định . 35
II.2.1.1. Luật trong bảngquyết định . 35
II.2.1.2. Hai đặc trưng của luật: Độ mạnh và độ nhiễu của luật . 35
II.2.1.3. Quá trình khám phá luật . 36
II.2.1.4. Thuật toán tối ưu hoá các luật . 45
II.2.1.5. Thuật toán giải pháp gần tối ưu hoá các luật . 45
II.2.1.6. Tiêuchuẩn lựa chọn luật trong tập thô . 46
II.2.2. Quá trình khám phá mẫu trong bảng quyết định . 46
II.2.2.1. Khái niệm mẫu . 46
II.2.2.2. Hai bài toán mẫu cơ bản . 47
II.2.2.3. Các phương pháp sinh mẫu . 51
II.2.3. Mối liên hệ giữa mẫu và luật theo tiếp cận tập thô . 58
II.3. So sánh luật theo tiếp cận tập thôvà luật kết hợp . 60
II.4. Kết luận chương II . 62
Chương III. ứng dụng của mẫu và thử nghiệm quá trình
khám phá luật theo tiếp cận tập thô .63
III.1. ứng dụng của mẫu . 63
III.1.1. Mẫu và quá trình phân loại ban đầu . 63
III.1.2. Mô tả các lớp quyết định . 65
III.1.3. Mẫu và bài toán phân tách bảng dữ liệu lớn . 66
III.1.4. Mẫu và bài toán phân lớp . 67
III.2. Thử nghiệm quá trình khám phá luật theo tiếp cận tập thô trên bài
toán quản lý thông tin khách Xuất nhập cảnh qua cửa khẩu . 69
III.2.1. Bài toán quản lý thông tinkhách Xuất nhập cảnh qua cửa khẩu . 69
III.2.1.1. Mô tả bài toán XNC . 69
III.2.1.2. Tập thô trong bài toán quản lý thông tin khách Xuất nhập cảnh . 71
III.2.2. Đề xuất giải quyết tập thô trong bài toán . 71
III.2.2.1. Mô tả dữ liệu . 71
III.2.2.2. Quá trình phát hiện luật . 74
III.2.2.3. Đề xuất ứng dụng luật tìm được trong bài toán thực tế . 81
III.3. Kết luận chương III . 82
Kết luận . 84
Tài liệu tham khảo.
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Theo cách diễn đạt thông th−ờng, luật kết hợp đ−ợc viết d−ới dạng X⇒Y⏐(c,s)
với:
- X và Y là các tập mục và X ∩ Y = ∅,
- c là độ tin cậy của luật,
- s là độ hỗ trợ của luật
-31-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
Độ tin cậy của luật biểu thị độ mạnh luật đ−ợc tính bằng tỷ lệ phần trăm các bản
ghi mà tất cả các thuộc tính trong Y đều có giá trị đúng trong số tất cả các bản
ghi mà tất cả các thuộc tính trong X đều có giá trị đúng.
Độ hỗ trợ của luật là độ đo có ý nghĩa thống kê của luật, tức là tỷ lệ phần trăm
các bản ghi mà tất cả các thuộc tính trong X ∪ Y có giá trị đúng.
Để minh họa, chúng ta xem xét một tập dữ liệu bán hàng tại siêu thị. Trong đó,
các bản ghi (phiếu bán hàng) thể hiện các mặt hàng đ−ợc bán trong siêu thị nh−
“Sữa, Bơ, Bánh mì, Xà phòng, N−ớc ép trái cây”.
Luật kết hợp dạng {Bánh mì, Sữa} ⇒ {N−ớc ép trái cây} ⏐(0.98, 0.70) có
nghĩa là:
- có tới 70% số l−ợt khách hàng mua cả ba mặt hàng Bánh mì, Sữa, N−ớc ép
trái cây,
- và 98% số l−ợt khách hàng nếu mua Bánh mì và Sữa thì cũng mua kèm thêm
N−ớc ép trái cây.
D−ới đây, chúng ta sẽ trình bày khái niệm luật kết hợp một cách hình thức hơn.
Giả sử I = {i1,i2,....,im} là một tập toàn bộ các mục (item). Trong ví dụ trên, I
chính là tập tên các mặt hàng), D là một tập các giao tác trong đó mỗi giao tác T
∈ D chính là một tập các mục T ⊆ I (trong ví dụ trên, mỗi giao tác T t−ơng ứng
với một phiếu mua hàng, T gồm tên các mặt hàng có trong phiếu mua hàng đó).
Mỗi giao tác đ−ợc liên kết với một định danh duy nhất (đ−ợc gọi là TID) của nó.
Giao tác T chứa X (tập các mục trong I) đ−ợc biểu diễn bằng quan hệ X ⊆ T.
Định nghĩa 2.1 (Luật kết hợp)
Luật kết hợp là một biểu diễn dạng X⇒Y với X⊂ I, Y⊂ I và X∩Y=∅.
-32-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
Định nghĩa 2.2 (Độ hỗ trợ của một tập mục)
Cho X là một tập mục. Độ hỗ trợ của X, kí hiệu là supp(X), là đại l−ợng
tần số các giao tác có chứa X trong tập tất cả các giao tác.
supp(X) =
)(
})
{
Dcard
TXTcard ⊆
trong đó card là hàm tính số l−ợng (cardinal).
Mệnh đề 2.1.
Nếu A ⊆ B với A, B là các tập mục thì supp(A) ≥ supp(B).
Kết quả này nhận đ−ợc từ lập luận rằng là mỗi giao dịch trong D nếu đã hỗ trợ B
thì tất yếu hỗ trợ A.
Định nghĩa 2.3 (Độ hỗ trợ và độ tin cậy của luật kết hợp)
Độ hỗ trợ của luật kết hợp X ⇒ Y, ký hiệu là supp(X ⇒ Y), đ−ợc xác định
theo: supp(X ⇒ Y) = supp(X∪Y)
Độ tin cậy của luật kết hợp X ⇒ Y, ký hiệu là conf(X ⇒ Y), đ−ợc xác
định theo: conf(X ⇒ Y) =
supp(X)
Y)supp(X∪
Nhận xét: Độ tin cậy của luật kết hợp có dạng một "xác suất có điều kiện" của
sự kiện xuất hiện Y khi đã xuất hiện X.
Độ hỗ trợ mang ý nghĩa "độ mạnh" theo nghĩa ảnh h−ởng của luật kết hợp
trong toàn bộ hệ thống, độ tin cậy mang ý nghĩa về tính tin cậy của phát biểu
"nếu X thì Y". Khái niệm tập phổ biến nh− trình bày trong phần sau cho thấy
mục tiêu "có giá trị" của khám phá luật kết hợp.
-33-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
II.1.2. Một số cơ sở toán học khai phá luật kết hợp
II.1.2.1. Tập phổ biến
Định nghĩa 2.4 (Tập phổ biến)
Tập mục X ⊆ I thoả mãn supp(X) ≥ minsup với minsup là độ hỗ trợ tối thiểu
cho tr−ớc thì X đ−ợc gọi là tập phổ biến.
Khái niệm tập phổ biến cho biết rằng, chúng ta chỉ khám phá các luật có "độ
ảnh h−ởng" v−ợt quá một ng−ỡng nào đó hay cũng vậy, chúng ta bỏ qua các luật
ít có ảnh h−ởng.
Từ mệnh đề 2.1 và định nghĩa tập phổ biến, nhận đ−ợc hệ quả sau đây.
Hệ quả. 2.1. Cho A, B là hai tập mục, A ⊆ B.
a. Nếu B là tập phổ biến thì A cũng là tập phổ biến.
b. Nếu A là tập không phổ biến thì B cũng là tập không phổ biến.
II.1.2.2. Khai phá luật kết hợp dựa trên tập phổ biến
Khai phá luật kết hợp trong cơ sở dữ liệu đã thu hút sự chú ý của nhiều nhóm
nghiên cứu về KDD [2, 7]. Mục tiêu là sinh ra tất cả các luật có độ hỗ trợ và độ
tin cậy lớn hơn độ hỗ trợ tối thiểu cho tr−ớc (gọi là minsup) và độ tin cậy cho
tr−ớc (gọi là minconf). Bài toán chia ra làm 2 b−ớc:
- Sinh ra tất cả các tập mục có đỗ hỗ trợ lớn hơn minsup (các tập phổ biến).
- Với mỗi tập phổ biến, sinh ra tất cả các luật có độ tin cậy lớn hơn minconf.
Việc sinh ra tất cả các luật dựa trên tập phổ biến (b−ớc 2) có thể đ−ợc giải quyết
tóm tắt nh− sau: Với mỗi tập phổ biến X và một tập con Y của X (Y ⊂ X), xem
xét tập X’ = X\Y bao gồm các phần tử của X mà không thuộc Y. Nếu tỷ số giữa
độ hỗ trợ của X với độ hỗ trợ của X' mà lớn hơn minconf thì sinh ra luật X’ ⇒ Y.
-34-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
Việc sinh ra luật kết hợp bằng cách sử dụng tất cả các tập phổ biến t−ơng đối đơn
giản, tuy nhiên việc phát hiện ra tất cả các tập phổ biến cùng với những giá trị độ
hỗ trợ của chúng lại là một bài toán khó nếu lực l−ợng của tập dữ liệu là lớn.
Thông th−ờng một siêu thị có m (m lên đến hàng nghìn) mặt hàng (mục), số
l−ợng các tập mục khác nhau sẽ là 2m, do đó việc tính toán độ hỗ trợ cho các tập
mục đòi hỏi nhiều thời gian.
Để giảm bớt không gian tìm kiếm tổ hợp, thuật toán tìm luật kết hợp có thể khai
thác 2 tính chất của tập phổ biến đã đ−ợc phát biểu trong hệ quả 2.1.
Đây là các đặc điểm có thể sử dụng cho thuật toán cơ sở tìm tất cả các tập phổ
biến, giống nh− thuật toán Apriori [2], có thể tóm tắt những b−ớc chính nh− sau:
1- Tìm tập tất cả các tập phổ biến có cỡ là 1 (Tính độ hỗ trợ của mọi 1-tập mục
bằng việc quét toàn bộ cơ sở dữ liệu. Hủy đi các 1-tập mục không là tập phổ
biến).
2- Mở rộng 1-tập mục phổ biến nhận đ−ợc từ b−ớc 1 để có đ−ợc các 2-tập mục
bằng cách lần l−ợt bổ sung thêm một mục vào 1-tập mục phổ biến để sinh ra
tất cả các 2-tập mục cho việc lựa chọn tiếp theo. Tính độ hỗ trợ của các 2-
tập mục đ−ợc sinh ra và loại bỏ tất cả các 2-tập mục không là tập phổ biến.
3- Lặp lại các b−ớc trên cho đến b−ớc thứ k, tập phổ biến (k-1) đ−ợc mở rộng
thành k-tập mục và kiểm tra tính phổ biến.
Quá trình trên đ−ợc lặp lại cho đến khi không tìm đ−ợc tập phổ biến mới. Có một
số thuật toán dựa trên các b−ớc chính này đã đ−ợc giới thiệu, chúng khác nhau
chủ yếu bởi việc sinh ra các tập mục cho các lần kiểm tra tiếp theo và cách tính
toán độ hỗ trợ của các tập mục đó.
-35-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
II.2. Quá trình khám phá tri thức theo tiếp cận tập thô
II.2.1. Quá trình khám phá luật trong bảng quyết định
II.2.1.1. Luật trong bảng quyết định
Giả sử A = (U, A∪{d}) là một bảng quyết định; X biểu thị sự kết hợp giữa
các từ nhận dạng (descriptors) bao hàm trong các thuộc tính điều kiện A; Y biểu
thị một từ nhận dạng d=v trong đó v là bất kỳ một giá trị nào của thuộc tính
quyết...
Download miễn phí Luận văn Khai phá luật theo tiếp cận tập thô
Mục lục
Phần mở đầu.5
Chương I. Tổng quan về khám phá tri thức theo tiếp cận tập thô.9
I.1. Hệ thông tin và tập thô.9
I.1.1. Một số khái niệm . 9
I.1.1.1. Khái niệm về hệ thông tin . 9
I.1.1.2. Khái niệm về bảng quyết định . 10
I.1.1.3. Quan hệ không phân biệt được trong hệ thông tin . 11
I.1.1.4. Tập mô tả được và ngôn ngữ mô tảtập . 13
I.1.2. Tập thô trong không gian xấp xỉ . 14
I.1.2.1. Tập xấp xỉ trên, xấp xỉ dưới và miền biên . 14
I.1.2.2. Hàm thô và một số độđo phụ thuộc có thuộc tính liên quan . 19
I.2. Khám phá tri thức theo tiếp cận tập thô . 20
I.2.1. Tính phụ thuộc thuộc tính trong hệ thông tin . 20
I.2.1.1. Tính phụ thuộc thuộc tính . 20
I.2.1.2. Tập thuộc tính rút gọn và tập thuộc tính nhân . 21
I.2.1.3. Ma trận phân biệt được và hàm phân biệt được . 23
I.2.2. Quá trình khám phá tri thức theo tiếp cận tập thô . 24
I.2.2.1. Sự rời rạc hoá dựa trên tập thô và lập luận logic . 25
I.2.2.2. Lựa chọn thuộc tính dựa trên tập thô với phương pháp đánh giá kinh nghiệm . 25
I.2.2.3. Khám phá luật bởi bảng phân bố tổng quát dựa trên tập thô . 27
I.2.3. Khám phá mẫu trong hệ thông tin . 27
I.3. Kết luận chương I . 29
Chương II. Khám phá luật theotiếp cận tập thô và đối
sánh với khám phá luật kết hợp . 30
II.1. Khám phá luật kết hợp, nội dung cơ bản của khám phá tri thức
trong cơ sở dữ liệu . 30
II.1.1. Luật kết hợp . 30
II.1.2. Một số cơ sở toán học khai phá luật kết hợp . 32
II.1.2.1. Tập phổ biến . 32
II.1.2.2. Khai phá luật kết hợp dựa trên tập phổ biến. 33
II.2. Quá trình khám phá tri thức theo tiếp cận tâp thô . 35
II.2.1. Quá trình khám phá luật trong bảng quyết định . 35
II.2.1.1. Luật trong bảngquyết định . 35
II.2.1.2. Hai đặc trưng của luật: Độ mạnh và độ nhiễu của luật . 35
II.2.1.3. Quá trình khám phá luật . 36
II.2.1.4. Thuật toán tối ưu hoá các luật . 45
II.2.1.5. Thuật toán giải pháp gần tối ưu hoá các luật . 45
II.2.1.6. Tiêuchuẩn lựa chọn luật trong tập thô . 46
II.2.2. Quá trình khám phá mẫu trong bảng quyết định . 46
II.2.2.1. Khái niệm mẫu . 46
II.2.2.2. Hai bài toán mẫu cơ bản . 47
II.2.2.3. Các phương pháp sinh mẫu . 51
II.2.3. Mối liên hệ giữa mẫu và luật theo tiếp cận tập thô . 58
II.3. So sánh luật theo tiếp cận tập thôvà luật kết hợp . 60
II.4. Kết luận chương II . 62
Chương III. ứng dụng của mẫu và thử nghiệm quá trình
khám phá luật theo tiếp cận tập thô .63
III.1. ứng dụng của mẫu . 63
III.1.1. Mẫu và quá trình phân loại ban đầu . 63
III.1.2. Mô tả các lớp quyết định . 65
III.1.3. Mẫu và bài toán phân tách bảng dữ liệu lớn . 66
III.1.4. Mẫu và bài toán phân lớp . 67
III.2. Thử nghiệm quá trình khám phá luật theo tiếp cận tập thô trên bài
toán quản lý thông tin khách Xuất nhập cảnh qua cửa khẩu . 69
III.2.1. Bài toán quản lý thông tinkhách Xuất nhập cảnh qua cửa khẩu . 69
III.2.1.1. Mô tả bài toán XNC . 69
III.2.1.2. Tập thô trong bài toán quản lý thông tin khách Xuất nhập cảnh . 71
III.2.2. Đề xuất giải quyết tập thô trong bài toán . 71
III.2.2.1. Mô tả dữ liệu . 71
III.2.2.2. Quá trình phát hiện luật . 74
III.2.2.3. Đề xuất ứng dụng luật tìm được trong bài toán thực tế . 81
III.3. Kết luận chương III . 82
Kết luận . 84
Tài liệu tham khảo.
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
-tập mục.Theo cách diễn đạt thông th−ờng, luật kết hợp đ−ợc viết d−ới dạng X⇒Y⏐(c,s)
với:
- X và Y là các tập mục và X ∩ Y = ∅,
- c là độ tin cậy của luật,
- s là độ hỗ trợ của luật
-31-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
Độ tin cậy của luật biểu thị độ mạnh luật đ−ợc tính bằng tỷ lệ phần trăm các bản
ghi mà tất cả các thuộc tính trong Y đều có giá trị đúng trong số tất cả các bản
ghi mà tất cả các thuộc tính trong X đều có giá trị đúng.
Độ hỗ trợ của luật là độ đo có ý nghĩa thống kê của luật, tức là tỷ lệ phần trăm
các bản ghi mà tất cả các thuộc tính trong X ∪ Y có giá trị đúng.
Để minh họa, chúng ta xem xét một tập dữ liệu bán hàng tại siêu thị. Trong đó,
các bản ghi (phiếu bán hàng) thể hiện các mặt hàng đ−ợc bán trong siêu thị nh−
“Sữa, Bơ, Bánh mì, Xà phòng, N−ớc ép trái cây”.
Luật kết hợp dạng {Bánh mì, Sữa} ⇒ {N−ớc ép trái cây} ⏐(0.98, 0.70) có
nghĩa là:
- có tới 70% số l−ợt khách hàng mua cả ba mặt hàng Bánh mì, Sữa, N−ớc ép
trái cây,
- và 98% số l−ợt khách hàng nếu mua Bánh mì và Sữa thì cũng mua kèm thêm
N−ớc ép trái cây.
D−ới đây, chúng ta sẽ trình bày khái niệm luật kết hợp một cách hình thức hơn.
Giả sử I = {i1,i2,....,im} là một tập toàn bộ các mục (item). Trong ví dụ trên, I
chính là tập tên các mặt hàng), D là một tập các giao tác trong đó mỗi giao tác T
∈ D chính là một tập các mục T ⊆ I (trong ví dụ trên, mỗi giao tác T t−ơng ứng
với một phiếu mua hàng, T gồm tên các mặt hàng có trong phiếu mua hàng đó).
Mỗi giao tác đ−ợc liên kết với một định danh duy nhất (đ−ợc gọi là TID) của nó.
Giao tác T chứa X (tập các mục trong I) đ−ợc biểu diễn bằng quan hệ X ⊆ T.
Định nghĩa 2.1 (Luật kết hợp)
Luật kết hợp là một biểu diễn dạng X⇒Y với X⊂ I, Y⊂ I và X∩Y=∅.
-32-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
Định nghĩa 2.2 (Độ hỗ trợ của một tập mục)
Cho X là một tập mục. Độ hỗ trợ của X, kí hiệu là supp(X), là đại l−ợng
tần số các giao tác có chứa X trong tập tất cả các giao tác.
supp(X) =
)(
})
{Dcard
TXTcard ⊆
trong đó card là hàm tính số l−ợng (cardinal).
Mệnh đề 2.1.
Nếu A ⊆ B với A, B là các tập mục thì supp(A) ≥ supp(B).
Kết quả này nhận đ−ợc từ lập luận rằng là mỗi giao dịch trong D nếu đã hỗ trợ B
thì tất yếu hỗ trợ A.
Định nghĩa 2.3 (Độ hỗ trợ và độ tin cậy của luật kết hợp)
Độ hỗ trợ của luật kết hợp X ⇒ Y, ký hiệu là supp(X ⇒ Y), đ−ợc xác định
theo: supp(X ⇒ Y) = supp(X∪Y)
Độ tin cậy của luật kết hợp X ⇒ Y, ký hiệu là conf(X ⇒ Y), đ−ợc xác
định theo: conf(X ⇒ Y) =
supp(X)
Y)supp(X∪
Nhận xét: Độ tin cậy của luật kết hợp có dạng một "xác suất có điều kiện" của
sự kiện xuất hiện Y khi đã xuất hiện X.
Độ hỗ trợ mang ý nghĩa "độ mạnh" theo nghĩa ảnh h−ởng của luật kết hợp
trong toàn bộ hệ thống, độ tin cậy mang ý nghĩa về tính tin cậy của phát biểu
"nếu X thì Y". Khái niệm tập phổ biến nh− trình bày trong phần sau cho thấy
mục tiêu "có giá trị" của khám phá luật kết hợp.
-33-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
II.1.2. Một số cơ sở toán học khai phá luật kết hợp
II.1.2.1. Tập phổ biến
Định nghĩa 2.4 (Tập phổ biến)
Tập mục X ⊆ I thoả mãn supp(X) ≥ minsup với minsup là độ hỗ trợ tối thiểu
cho tr−ớc thì X đ−ợc gọi là tập phổ biến.
Khái niệm tập phổ biến cho biết rằng, chúng ta chỉ khám phá các luật có "độ
ảnh h−ởng" v−ợt quá một ng−ỡng nào đó hay cũng vậy, chúng ta bỏ qua các luật
ít có ảnh h−ởng.
Từ mệnh đề 2.1 và định nghĩa tập phổ biến, nhận đ−ợc hệ quả sau đây.
Hệ quả. 2.1. Cho A, B là hai tập mục, A ⊆ B.
a. Nếu B là tập phổ biến thì A cũng là tập phổ biến.
b. Nếu A là tập không phổ biến thì B cũng là tập không phổ biến.
II.1.2.2. Khai phá luật kết hợp dựa trên tập phổ biến
Khai phá luật kết hợp trong cơ sở dữ liệu đã thu hút sự chú ý của nhiều nhóm
nghiên cứu về KDD [2, 7]. Mục tiêu là sinh ra tất cả các luật có độ hỗ trợ và độ
tin cậy lớn hơn độ hỗ trợ tối thiểu cho tr−ớc (gọi là minsup) và độ tin cậy cho
tr−ớc (gọi là minconf). Bài toán chia ra làm 2 b−ớc:
- Sinh ra tất cả các tập mục có đỗ hỗ trợ lớn hơn minsup (các tập phổ biến).
- Với mỗi tập phổ biến, sinh ra tất cả các luật có độ tin cậy lớn hơn minconf.
Việc sinh ra tất cả các luật dựa trên tập phổ biến (b−ớc 2) có thể đ−ợc giải quyết
tóm tắt nh− sau: Với mỗi tập phổ biến X và một tập con Y của X (Y ⊂ X), xem
xét tập X’ = X\Y bao gồm các phần tử của X mà không thuộc Y. Nếu tỷ số giữa
độ hỗ trợ của X với độ hỗ trợ của X' mà lớn hơn minconf thì sinh ra luật X’ ⇒ Y.
-34-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
Việc sinh ra luật kết hợp bằng cách sử dụng tất cả các tập phổ biến t−ơng đối đơn
giản, tuy nhiên việc phát hiện ra tất cả các tập phổ biến cùng với những giá trị độ
hỗ trợ của chúng lại là một bài toán khó nếu lực l−ợng của tập dữ liệu là lớn.
Thông th−ờng một siêu thị có m (m lên đến hàng nghìn) mặt hàng (mục), số
l−ợng các tập mục khác nhau sẽ là 2m, do đó việc tính toán độ hỗ trợ cho các tập
mục đòi hỏi nhiều thời gian.
Để giảm bớt không gian tìm kiếm tổ hợp, thuật toán tìm luật kết hợp có thể khai
thác 2 tính chất của tập phổ biến đã đ−ợc phát biểu trong hệ quả 2.1.
Đây là các đặc điểm có thể sử dụng cho thuật toán cơ sở tìm tất cả các tập phổ
biến, giống nh− thuật toán Apriori [2], có thể tóm tắt những b−ớc chính nh− sau:
1- Tìm tập tất cả các tập phổ biến có cỡ là 1 (Tính độ hỗ trợ của mọi 1-tập mục
bằng việc quét toàn bộ cơ sở dữ liệu. Hủy đi các 1-tập mục không là tập phổ
biến).
2- Mở rộng 1-tập mục phổ biến nhận đ−ợc từ b−ớc 1 để có đ−ợc các 2-tập mục
bằng cách lần l−ợt bổ sung thêm một mục vào 1-tập mục phổ biến để sinh ra
tất cả các 2-tập mục cho việc lựa chọn tiếp theo. Tính độ hỗ trợ của các 2-
tập mục đ−ợc sinh ra và loại bỏ tất cả các 2-tập mục không là tập phổ biến.
3- Lặp lại các b−ớc trên cho đến b−ớc thứ k, tập phổ biến (k-1) đ−ợc mở rộng
thành k-tập mục và kiểm tra tính phổ biến.
Quá trình trên đ−ợc lặp lại cho đến khi không tìm đ−ợc tập phổ biến mới. Có một
số thuật toán dựa trên các b−ớc chính này đã đ−ợc giới thiệu, chúng khác nhau
chủ yếu bởi việc sinh ra các tập mục cho các lần kiểm tra tiếp theo và cách tính
toán độ hỗ trợ của các tập mục đó.
-35-
Khai phá luật theo tiếp cận tập thô Tiêu Thị Dự
II.2. Quá trình khám phá tri thức theo tiếp cận tập thô
II.2.1. Quá trình khám phá luật trong bảng quyết định
II.2.1.1. Luật trong bảng quyết định
Giả sử A = (U, A∪{d}) là một bảng quyết định; X biểu thị sự kết hợp giữa
các từ nhận dạng (descriptors) bao hàm trong các thuộc tính điều kiện A; Y biểu
thị một từ nhận dạng d=v trong đó v là bất kỳ một giá trị nào của thuộc tính
quyết...