Luận văn tốt nghiệp

Phát hiện luật bằng cách sử dụng siêu
phằng tối ưu theo hướng tiếp cận thô TÓM TĂT KHOÁ LUẬN TỐT NGHIỆP
Cùng với sự phát triển của Công Nghệ Thông Tin ngày nay, khai phá tri thức
trong các cơ sở dư liệu lớn là một trong nhưng lĩnh vực được rất nhiều nhà nguyên cứu
và ứng dụng tin học đặc biệt quan tâm. Việc nguyên cứu những phương pháp có thể tự
động phát hiện những tri thức mới trong cơ sở dư liệu trên máy tính đã tỏ ra thực sự
hữu ích trong việc hỗ trợ quyết
định cho con người.
Hiện nay, trên thế giới có rất nhiều thuật toán khai phá tri thức bằng cách phân
lớp và rời rạc dữ liệu như: Sử dụng cây quyết định, phương pháp thống kê, các mạng
nơ ron, thuật toán di truyền, Trong một vài năm gần đây, lý thuyết tâp thô được nhiều

1.2.1.3. Khái niệm quan hệ không phân biệt được trong hệ thông tin. 15
1.2.1.4. Khái niệm tập các nhát cắt, nhát cắt trong bảng quyết định 16
1.2.1.5. Tập thô trong không gian xấp xỉ. 17
1.2.2. Khai phá tri thức theo cách tiếp cận tập thô. 19
1.2.2.1. Sự rời rạc hoá dữ liệu theo cách tiếp cận tập thô. 19
1.2.2.2. Lựa chọn thuộc tính dựa trên tập thô 19
1.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ô. 20
1.2.2.4. Khám phá mẫu trong hệ thông tin 20
1.3 . Kết luận. 21
Chương 2 KHAI PHÁ LUẬT KẾT HỢP 22
2.1 . Khai phá luật kết hợp trong cơ sở dữ liệu. 22
2.1.1. Bài toán xuất phát 22
2.1.2. Mô hình hoá bài toán 22
2.1.3. Thuật toán khai phá luật kết hợp. 25
2.1.3.1. Tập phổ biến 25
2.1.3.2. Khai phá luật dựa trên tập mục phổ biến 25
2.1.4. Kết luận 28
2.2 . Sinh cây quyết định từ hệ thông tin 29
2.2.1. Thuật toán học cây quyết định 29
2.2.2. Một số phương pháp giải quyết vấn đề rời rạc hoá. 35
2.2.2.1. Maximal Discernibility (MD) Heuristic 35
2.2.2.2. Sự rời rạc hoá định nghĩa bằng siêu phẳng. 36
2.2.2.3. Những tính chất của phương thức MD 39
2.2.2.4. Xây dựng cây quyết định không đối xứng. 43
2.2.3. Kết luận 50
Chương 3 CHƯƠNG TRÌNH THỬ NGHIỆM. 51
3.1 . Mô tả dữ liệu. 51
3.2 . Xây dựng chương trình. 53
3.3 . Kết quả thử nghiệm. 57
3.4 . Nhận xét. 61

ự chúng ta có là rất ít, những hiểu biết thực sự của chúng ta về lượng dữ liệu mà
chúng ta có còn rất hạn chế.
Xuất phát từ thực tế đó mà trong một vài năm gần đây các nhà nguyên cứu và
ứng dụng tin học phải nguyên cứu, tìm kiếm những phương pháp mới để khai thác triệt
để nhưng thông tin có trong cơ sở dữ liệu. Từ cuối những năm của thập kỷ 1980 khái
ni
ệm phát hiện tri thức trong cơ sở dữ liệu lần đầu tiên được nói đến, đây là quá trình
phát hiện tri thức tiềm ẩn, không biết trước và hữu ích trong các cơ sở dữ liệu lớn.
Khắc phục hạn chế của những mô hình cơ sở dữ liệu truyền thống chỉ với
những công cụ truy vấn dữ liệu không có khả năng tìm kiếm các thông tin mới, các
thông tin tiề
m ẩn trong cơ sở dữ liệu. Khai phá tri thức trong cơ sở dữ liệu là một quá
trình có thể tìm ra những thông tin mới, những thông tin hữu ích, và tiềm ẩn trong cơ
sở dữ liệu. Quá trình phát hiện tri thức gồm nhiều giai đoạn, trong đó giai đoạn khai
phá dữ liệu là quan trọng nhất. Đây là giai đoạn chính tìm ra những thông tin mới
trong cơ sở dữ liệu. Quá trình phát hiện tri thức là sự tiếp thu, s
ử dụng và phát triển các
thành tựu của nhiều lĩnh vực nguyên cứu ứng dụng tin học trước đó như: lý thuyết
nhận dạng, hệ chuyên gia, trí tuệ nhân tạo, thống kê, v.v.
Từ đầu những năm 80 Z. Pawlak đã đề xuất ra lý thuyết tập thô với một cơ sở
toán học rất chắc chắn. Trong những năm gần đây, lý thuyết tập thô được nhiều nhóm
nguyên cứu ho
ạt động trong lĩnh vực tin học nói chung và khai phá tri thức trong cơ sở
dữ liệu nói riêng nguyên cứu và áp dụng trong thực tế [2,4,6,10,12]. Lý thuyết tập thô
ngày càng được áp dụng rộng rãi trong lĩnh vực phát hiện tri thức. Nó tỏ ra rất hữu ích
trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật và đặc biệt hữu ích
trong các bài toán phải xử lý các dữ liệu mơ hồ, không chắc chắn. Các mối quan hệ
giữa d
ữ liệu trong mô hình này được biểu diễn qua mối quan hệ “không phân biệt
được”, các tập dữ liệu là mơ hồ, không chắc chắn được biểu diễn thông qua tập xấp xỉ

phân tích nội dung các bài báo được công bố về lĩnh v
ực khai phá tri thức trong những
năm gần đây. Từ những kiến thức thu được chúng tôi đã xây dựng được chương trình
thử nghiệm mô phỏng thuật toán xây dựng cây quyết định tối ưu bằng cách sử dụng
siêu phẳng tối ưu được trình bày trong [9]. Chương trình tiến hành khai phá tri thức
trong cớ sở dữ liệu lưu thông tin về 678 bệnh nhân tiểu đường cung cấp bởi tổ chức
“National Institute of Diabetes and Digestive and Kidney Diseases”. Từ
đó sinh ra các
luật quyết định hỗ trợ trong quá trình khám bệnh của bệnh nhân.
Khoá luận tốt nghiệp được trình bày gôm 3 phần: Phần mở đầu, 3 chương và
phần kết luận. Trong đó:
Chương 1: Khóa luận trình bày những kiến thức chung nhất về khai phá tri
thức và khai phá tri thức theo cách tiếp cận tập thô.
Chương 2: Khóa luận trình bày về chi tiết một số thuật toán khai phá tri thức,
chủ yếư là khai phá các luật trong các cơ s
ở dữ liệu. Trong đó đáng chú ý là thuật toán
xây dựng cây quyết định tối ưu bằng cách sử dụng siêu phẳng tối ưu.
Chương 3: Khóa luận trình bày kết quả thử nghiệm bài toán khai phá luật
trong cây quyết định tối ưu trình bày ở chương 2 và áp dụng trên cơ sở dữ liệu bệnh
nhân bị tiểu đường được lấy về từ trên mạng. Qua đó đánh giá được sự hiệ
u quả của
thuật toán được trình bày trong [9].
Khóa luận được hoàn thành duới sự giúp đỡ của Tiến Sĩ. Hà Quang Thuỵ , Bộ
môn các hệ thông thông tin, Khoa Công Nghệ, ĐHQG Hà Nội. Em xin bày tỏ lòng
kính trọng và sự biết ơn sâu sắc tới Thầy đã hướng dẫn, động viên và tạo điều kiện cho
em trong quá trình làm khoá luận tốt nghiệp. Em xin chân thành cảm ơn Thầy Đỗ
Văng Thành, Văn phong chính phủ, người đã truyền thụ cho em những kiến thức nền
tảng và cơ sở để em có thể hoàn thành bản khoá luận tôt nghiệp này. Em xin chân
thành cảm ơn các thầy cô giáo trong bộ môn Các Hệ Thống Thông Tin, nhóm
“Seminar Data Mining and KDD”. Cuối cùng em xin chân thành cảm ơn tới những

Mục đích của quá trình khai phá tri thức: Từ những cơ sở dữ liệu ngoài cuộc
sống thực tế sau một hoặc một số bước của quá trình sẽ rút ra được những tri thức mới.
Các bước trong quá trình này có thể lặp đi lặp lại nhiều lần và được mô tả theo hình
sau [4,8]:

Hình 1. Mô hình mô tả quá trình khai phá tri thức.
Giai đoạn 1:Xác định và định nghĩa vấn đề.
− Tìm hiểu lĩnh vực ứng dụng và nhiệm vụ đề ra, xác định các tri
thức đã có và các mục tiêu của người sử dụng.
− Tạo và chọn lựa cơ sở dữ liệu.
Giai đoạn 2: Thu nhập và tiền xử lý dữ liệu.
− Xử
lý và làm sạch dữ liệu trước: Bỏ đi các dữ liệu tạp bao gồm các
lỗi và các dạng không bình thường. Xử lý dữ liệu bị mất, chuyển đổi
dữ liệu phù hợp.
− Rút gọn kích thước dữ liệu nhận được: Nhận ra các thuộc tính hữu
ích cho quá trình phát hiện tri thức.
Giai đoạn 3: Khai phá dữ liệu.

giai đoạn khai phá dữ liệu là quan trọng nhất. Đây là giai đoạn duy nhất tìm được các
thông tin tiềm ẩn trong cơ sở dữ liệu.
1.1.3. Khai phá dữ liệu
Khai phá dữ liệu (hay data mining) được định nghĩa như là quá trình phát hiện
các tri thức mới, có giá trị từ những dữ liệu lớn được lưu trữ trong cơ sở,
datawarehouse hay các kho chứa thông tin khác. Khai phá dữ
liệu là một giai đoạn
quan trọng trong quá trình phát hiện tri thức. Về bản chất nó là giai đoạn duy nhất tim
ra được thông tin mới, thông tin tiềm ần có trong cơ sở dữ liệu. Mục đích nguyên thủy
của khai phá dữ liệu là mô tả và dự đoán [4]. Các kỹ thuật khai phá dữ liệu được chia
thành những mảng chính sau:
• Phân cụm và phân lớp dữ liệu: Quá trình này có thể xem là quá trình phân
tích một tập dữ liệu và sinh ra m
ột tập nhóm các luật mà chúng ta có thể sử
dụng để phân lớp dữ liệu trong tương lai. Khi phân lớp dữ liệu người ta
thường dựa trên một tập các mẫu huấn luyện để sinh ra các luật. Có rất nhiều
phương pháp để phân lớp dữ liệu được nguyên cứu như: Các phương pháp
học cây quyết định, phương pháp thông kê, các mạng nơ ron, các mạng xác
xuất Bayes,. . .
• Khai phá luật kết hợp: Mong muố
n tìm ra những mối quan hệ giữa các
thuộc tính hoàn toàn độc lập với nhau trong cơ sở dữ liệu. Luật kết hợp có thể
dùng để hỗ trợ quyết định. Ví dụ như các bài toán kinh doanh.
• Khai phá chuỗi: Luật chuỗi và khai phá chuỗi có thể coi như là một cách
trừu tượng của luật kết hợp và phát hiện các luật kết hợp trong cơ sở dữ liệu
phụ thuộc thờ
i gian.
Có rất nhiều phương pháp để có thể tiến hành khai phá dữ liệu đã được nguyên
cứu và đề ra như:
− Các phương pháp sinh cây quyết định.

Trong đó:
U : là một tập hữu hạn khác rỗng các đối tượng.
A : là một tập hữu hạn khác rỗng các thuộc tính.
a: U → V
a
với mọi a ∈ A. Tập V
a
được gọi là tập giá trị của
thuộc tính a.
Ví dụ: Có một hệ thông tin được biểu diễn như bảng sau: Trong bảng có 7 đối tượng
và có 3 thuộc tính là số lần mang thai của bệnh nhân
(1), lượng glucose trong huyết
tương sau 2 giờ uống thuốc (2), tuổi của bệnh nhân (8).
Mỗi đối tượng của bảng là một bệnh nhân đang tham gia khám bệnh tiểu
đường, trong đó các bác sĩ dựa vào một số chỉ số tương ứng với các thuộc tính sau để
xác định tình trạng của bệnh nhân.
Để thuận tiện cho việc trình bày từ giờ chúng ta chỉ ký hiệu các thuộc tính là
(1), (2), (8).
(1) (2) (8)
X1

2 102 31
X2 4 146 70
X3 3 102 28
X4 2 90 37
X5 2 90 31
X6 2 146 28
X7

2 102 31

1(ứng với trường h
ợp bị bệnh), và 2(ứng với trường hợp không bị bệnh)
(1) (2) (8) (9)
X1

2 102 31 1
X2 4 146 70 2
X3 3 102 28 1
X4 2 90 37 2
X5 2 90 31 1
X6 2 146 28 2
X7

2 102 31 2
Bảng 2. Ví dụ một bảng quyết định.
Nhìn vào bảng 2 ta tiếp tục xét các đối tượng X1 và X7 ta thấy chúng có giá trị
của các thuộc tính điều kiện là giống nhau, nhưng đối với kết quả quyết định đối với 2
đối tượng là khác nhau. Như thế chỉ dùng các thuộc tính điều kiện xét trong ví dụ trên
thì không thể xác định rõ tính chất bị bệnh hay không bị bệnh của một đối tượ
ng bất
kỳ. Sẽ tồn tại trường hợp mà với những giá trị điều kiện được đưa ra ta không thể xác
định đối tượng đó có bị bệnh hay không.
Chúng ta giả sử rằng tập các giá trị của giá trị quyết định d tương đương với tập
{1, . . ., r(d)} là các số nguyên dương từ 1 đến r(d), tập này được gọi là phạm vi của
thuộc tính quyết đinh d. Ta định ngh
ĩa một lớp quyết định thứ k như sau:
Địng nghĩa 4: Một lớp quyết định thứ k (ký hiệu là C
k
) là một tâp các đối tượng
thoả mãn: C

mà xRy.
Bây giờ chúng ta bắt đầu định nghĩa một quan hệ tương đương trên hệ thông
tin. Quan hệ này sau này được sử dụng đ
ê biểu diễn những thông tin mập mờ, không
rõ ràng.
Định nghĩa 6: Một quan hệ tương đương (ký hiệu là IND
A
(B)), được định
nghĩa như sau:
IND
A
(B)={(x,x’) ∈ U
2
⏐∀a ∈ B: a(x) = a(x’)}
Trong đó:
B: là một tập thuộc tính của các đối tượng, B∈A.
x, x
’
: là hai đối tượng bất kỳ thuộc U.
Khi đó IND
A
(B) là một quan hệ không phân biệt được B. Khi đó thì hai đối
tượng x, x
’
, mà (x, x
’
)∈IND
A
(B) thì khi đó hai đối tượng x, x
’

a
(u)) với mọi u∈ U,
ngược lại thì A được coi là không thống nhất.
1.2.1.4. Khái niệm tập các nhát cắt, nhát cắt trong bảng quyết định
Trong quá trình phân lớp và rời rạc dữ liệu, ta có thể dùng nhiều phương pháp.
Tuy nhiên, sử dụng nhát cắt để phân lớp dữ liệu là một trong những phương pháp phổ
biến. Ta xét đinh nghĩa nhát cắt dưới đây.
Định nghĩa 8: Xét một bảng quyết
định A =(U, A ∪ {d} ).
Trong đó:
U= {x
1
, . . . ,x
n
}, A={a
1
, . . . ,a
k
} và d:U→{1,. . .,r}
Giả sử V
a
=[l
a
, r
a
) ⊂ R với mọi a thuộc A Chúng ta giả sử rằng A là một bảng
quyết định thống nhất.
Xét P
a
là một cách chia V

K
và
).,[ ),[),[
12110
a
k
a
k
aaaa
a
aa
ccccccV
+
∪∪∪=

Khi đó P
a
sẽ định nghĩa duy nhất tập các nhát cắt trên V
a
:
{
}
a
k
aa
a
a
cccC ,,,
10
K=

B
=[X7]
B
={X1, X7},
[X2]
B
={X2},
[X3]
B
={X3},
[X4]
B
={X4},
[X5]
B
={X5},
[X6]
B
={X6}
Ta xét một tập X các bệnh nhân là bị bệnh (thuộc tính quyết định có giá trị 1)
X={X1, X3, X5}. Khi đó tập X là không mô tả được theo tập các tập sơ cấp trên. Hai
bệnh nhân X1 và X7 thuộc cùng một tập sơ cấp nhưng có giá trị quyết định khác nhau.
Khi diễn tả tập X có bênh nhân X1 thì phải chứa tập sơ cấp [X1]
B
. Mà tập [X1]
B
thì lại
chứa bênh nhân X7 là không bị bệnh (thuộc tính quyết định có giá trị là 2). Như vậy
tập X là không mô tả được theo các tập sơ cấp trên.
Khắc phục hạn chế trên ta có thể dùng tính chất của lý thuyết tập thô để biểu

A
(B), ta chỉ có thể có được
xấp xỉ trên và xấp xỉ dưới của nó.
a) Các tính chất của sự xấp xỉ[2,12]:
(1)
XB
⊆ X ⊆
X
B
,
(2)
B (
∅
) =
B
(
∅
), B (U) =
B
(U) = U,
(3)
B
(X ∪ Y) =
B
(X) ∪
B
(Y),
(4)
B ( X ∩ Y) = B (X) ∩ B (Y),
(5) Nếu X ⊆Y thì

B
(X)) =
B
(X).
Ký hiệu –X biểu thi thay cho U-X.
b) Bốn loại tập thô cơ bản:
Người ta phân tập thô thành 4 loại [9]:
• X là xác định thô thực sự theo B nếu
XB ≠
∅
và
X
B
≠ U.
• X là không xác định bên trong theo B nếu
XB =
∅
và
X
B
≠ U.
• X là không xác đinh bên ngoài theo B nếu
XB ≠
∅
và
X
B
= U.
• X là không xác định thực sự theo B nếu
XB =

rất nhiều người quan tâm [2,12]. Việc tìm kiếm tri thức trong các cơ sở dữ liệu được
tiến hành theo rất nhiều phương pháp khác nhau. Trong đó khai phá tri thức theo cách
tiếp cân tập thô là một phương pháp tỏ ra đặc biệt hiệu quả đối vớ
i những dữ liệu lớn
và nhiều kiểu khác nhau. Hơn thế nữa nó con có thể làm tốt với những cơ sở dữ liệu
không chắc chắn, có tính mơ hồ, không phân biệt được.
1.2.2.1. Sự rời rạc hoá dữ liệu theo cách tiếp cận tập thô
Trong lĩnh vực khai phá tri thức, một vấn đề đặt ra là làm sao chúng ta có thể
xử lý cả được những dữ liệu hỗn tạ
p với những giá trị liên tục. Có rất nhiều thuật toán
được sử dụng trong lĩnh vực rời rạc hoá dữ liệu như: Các phương pháp lập luận logic,
thuật toán NAIVE, . . . tuy nhiên không có một thuật toán được gọi là tối ưu và hiệu
quả nhất. Việc lưa chọn thuật toán vẫn còn phụ thuộc vào dạng dữ liệu mà chúng ta
cần xử lý. Các tác giả trong [1,2] đã đưa ra một số phương pháp rờ
i rạc hoá dữ liệu
dựa trên tập thô và lập luận logic.
Khi sử dụng phương pháp rời rạc hoá dữ liệu thì có nghĩa là chúng ta đã chấp
nhận sai số trong dữ liệu. Một ví dụ là khi đo về nhiệt độ của cơ thể thì ta thương gặp
những số thực nhưng chúng ta thường phải quy về giá trị nguyên hay những khoảng
khác nhau tuỳ từng bài toán cụ thể. Việc phân chia các giá trị
thực thành các khoảng
hợp lý là rất phức tạp. Khi đó thường cần phải có các chuyên gia trong các lĩnh vực cụ
thể tham gia cùng.
1.2.2.2. Lựa chọn thuộc tính dựa trên tập thô
Các cơ sở dữ liệu trong thực tế thương có rất nhiều thuộc tính, những thuộc
tính cần thiết cho lĩnh vực mà bài toán khai phá dữ liệu mà chúng ta đang xử lý không
phải là tất cả. Việc lựa chọn những thu
ộc tính phù hợp để tiến hành các phương pháp
khai phá dữ liệu là rất cần thiết. Các thuộc tính dư thừa không cần thiết trong quá trình
khai phá tri thức không chỉ làm cho bài toán trở lên phức tạp mà còn dẫn đền một thực

thể và các bộ sinh có thể.
− Những trường hợp không thấy trong quá trình khai phá dữ liệu sự không
chắc chắn của luật bao gồm cả khả năng dự đoán tr
ước các trường hợp
nó không được thể hiện rõ ràng trong độ mạnh của luật.
− Có thể sử dụng tri thức nền làm cơ sở cho việc lập bảng phân bố tổng
quát và quá trình khai phá.
A. Skowronvà Ning Zong [2] đã đưa ra phương pháp khám phá luật sư dụng
bảng phân bố tổng quát dựa trên tập thô với ý tưởng như sau:
− Từ bảng quyết định xây dựng bảng phân bố tổng quát.
− D
ựa trên các bảng phân bố tổng quát này sinh các vector phân biệt được.
− Tạo ra các tập rút gọn được từ các tập vector phân biệt được.
− Sinh ra các luật bao phủ tất cả các trường hợp.
1.2.2.4. Khám phá mẫu trong hệ thông tin
Việc tìm những mẫu quan hệ phức tạp được phát hiện trong những cơ sở dữ
liệu lớn một cách tự động là một trong những hướng nghiên cứu đang đượ
c chú trọng
trên thế giới. Trong trường hợp đơn giản thì mẫu chỉ là một vector có giá trị độ dài đủ
lớn của một sô thuộc tính được hỗ trợ của một lượng đủ lớn các đối tượng. Các bài
toán tìm mẫu thường có độ phức tạp lớn đòi hỏi những thuật toán tối ưu, thuật toán
đánh giá kinh nghiệm đủ tốt để có thể rút ra các mẫu gần tố
i ưu từ những cơ sở dữ liệu
lớn. Một lớp quan trọng của của phương pháp tìm kiếm mẫu là dựa trên những khuôn
mẫu quan hệ. Những khuôn mẫu này được xác định từ một bảng dữ liệu cho trước sử
dụng quan hệ thứ lỗi trong một số lớp quan hệ thứ lỗi giả định trước. Một quan hệ thứ
lỗi là tối ưu nếu tập các tham số miêu tả quan hệ này cho phép xây dự
ng những khuôn
mẫu dữ liệu thích hợp trên những bảng dữ liệu cho trước.
Có rất nhiêu ứng dụng cho việc phát hiện những khuôn mẫu trong hệ thông

Khai phá luật kết hợp là một kỹ thuật quan trọng và phát triển mạnh mẽ trong
những năm gần đây. Lần đầu tiên được Rakesh Agrawal, Tomasz Imielinski, Arun
Swami đề xuất năm 1993 [6]. Sau đó được nhiều nhà khoa học phát triển và cải tiến.
2.1 . Khai phá luật kết hợp trong cơ sở dữ liệu
2.1.1. Bài toán xuất phát
Cho trước một cơ sở dữ liệu lưu thông tin bán hàng của một siêu thị. Với
lượng dữ liệu được lưu giữ là tương đối lớn, người sử dụng mong muốn có những tri
thức từ cơ sở dữ liệu trên để có thể hoạch định kế hoạch kinh doanh phù hợp: Những
câu hỏi được đặt ra như nên đầu tư cho những m
ặt hàng nào, số lượng là bao nhiêu?
Sắp xếp các mặt hàng trong siêu thị như thế nào là hợp lý v . v ?
Với những câu hỏi như trên thì người sử dụng mong muốn có những thông tin
như là: ”75% những người mua bánh mì sẽ mua sữa”, hoặc “5% những người mua
rượu sẽ mua lạc”. Những phát biểu trên được gọi là các luật kết hợp. Bản thân nó
ngầm định một số quan hệ kết hợp một tập các đối t
ượng cùng tham gia mua hàng. Từ
những luật dạng trên thì người sử dụng có thể dùng để hỗ trợ những quyết định của họ
trong kinh doanh. Họ sẽ có chiến lược chẳng hạn như đầu tư lượng bánh mi và sữa gần
bằng nhau sao cho hiệu quả.
Trong phần này chúng tôi chỉ giải quyết ở mức độ là người khách hàng đó có
mua mặt hàng đó hay không, khi đó thì mỗi thuộc tính chỉ có 2 giá tri khác nhau là 0
ứ
ng với trường hợp người đó không mua mặt hàng này và bằng 1 nếu người đó có mua
mặt hàng đó.
2.1.2. Mô hình hoá bài toán
Trước tiên ta có một số định nghĩa như sau:
I = {i
1
,i
2

được định nghĩa: Conf(X⇒Y)=Supp(X∪Y)/Supp(X).ư
Ta thấy độ tin cậy của một luật chính là xác suất có đi
ều kiện của tác vụ chứa
Y xét trong điều kiện chứa X
Ví dụ: Để hiểu rõ hơn các định nghĩa trên chúng ta xét ví dụ sau:
Cho một cơ sở dữ liệu như bảng sau:
ID Tác vụ Các mục
T
1
A, C, D
T
2
B, E
T
3
A, B, C, E
T
4
B, E
T
5
B, D, F
Bảng 3. Ví dụ về một cơ sở dữ liệu.
Trong cơ sở dứ liệu trên gồm 5 tác vụ thao tác trên 6 tập mục là A, B, C, D, E,
F. Khi đó thì độ hỗ trợ tương ứng của từng mục sẽ là: Ở đây tổng số tác vụ là 5, trong
khi mục A xuất hiện trong 2 tác vụ là T
1
và T
3
nên có độ hỗ trợ là 2/5=40%

A, C, D 1 20%
B, D, F 1 20%
A, B, C, E 1 20%
Bảng 5. Độ hỗ trợ tương ứng của các tập mục khác
Ta xét một số luật sinh từ các tập mục phổ biến trên trong bảng sau. Trong các
luật của bảng ta xét luật A
⇒B thì supp({A, B})=20%, supp(A)=40% vì vậy
conf(A
⇒B)=50%.