Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
MỤC LỤC

MỤC LỤC 1
LỜI MỞ ĐẤU 2
NỘI DUNG 4
I. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 4
1. Khái niệm: 4
2. Quá trình phát hiện tri thức trong CSDL 14
3. Các kỹ thuật khai phá dữ liệu 16
II. LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU 18
1. Khai phá luật kết hợp 18
2. Lý thuyết về luật kết hợp 19
III. MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 29
1. Thuật toán Apriori 29
2. Thuật toán khắc phục nhược điểm thuật toán Apriori - Thuật toán FP-growth 36
IV. KỸ THUẬT GOM CỤM TRONG KHAI PHÁ DỮ LIỆU 40
1.Giới thiệu kỹ thuật phân cụm 40
2.Giới thiệu thuật toán K-means 41
3. Nội dung thuật toán K-means 42
4. Đánh giá thuật toán K-means 49
5. Thuật toán K-mediods - Biến thể và cải tiến của thuật toán K-means 49
V. GIỚI THIỆU CHƯƠNG TRÌNH DEMO THUẬT TOÁN APRIORI 50
1. Xây dựng chương trình 50
Chương trình được viết bằng ngôn ngữ lập trình C# với mục đích giúp người sử dụng: 50
2. Sử dụng chương trình: 51
3. Giao diện chương trình: 51
4. Code chương trình: 54
VI. GIỚI THIỆU CHƯƠNG TRÌNH DEMO THUẬT TOÁN K-MEANS 68
1. Xây dựng chương trình 68
Chương trình được viết bằng ngôn ngữ lập trình C++ với mục đích giúp người sử dụng:. .68

CSDL (Knowlegde Discovery in Databases – KDD) là như nhau. Tuy nhiên
trên thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình khám
phá tri thức trong CSDL. Trong xu thế phát triển chung, việc nắm bắt được
thông tin được xem là cơ sở của mọi hoạt động sản xuất, kinh doanh. Cá
nhân hoặc tổ chức nào có thể thu thập và hiểu được thông tin, và hành động
để đưa ra các phương án dựa trên các thông tin được kết xuất từ các thông
tin đã có thì có thể nói bước đầu đã đạt được thành công trong hoạt động.
HVTH: Nguyễn Thị Kim Phượng Trang 2
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
Ví dụ: Khảo sát thông tin để tìm hiểu nhu cầu mua sắm của khách
hàng, trên cơ sở đó đề ra chiến lược kinh doanh, sắp xếp các nhóm hàng
trong siêu thị hợp lý hay có cách tiếp cận đặc biệt đến các đối tượng người
dùng đa dạng (phân nhóm khách hàng tiềm năng, VIP để có thể phục vụ
khách hàng tốt nhất…). Mặt khác, sự tăng trưởng vượt bậc của các CSDL:
thương mại, quản lý và khoa học đã làm nảy sinh và thúc đẩy sự phát triển
của kỹ thuật thu thập, lưu trữ, phân tích và khai phá dữ liệu… không chỉ bằng
các phép toán đơn giản thông thường như: phép đếm, thống kê… mà đòi hỏi
cách xử lý thông minh hơn, hiệu quả hơn. Từ việc nắm bắt thông tin “có chọn
lọc” các nhà quản lý có được thông tin có ích để tác động trở lại quá trình sản
xuất, kinh doanh của mình… Các kỹ thuật cho phép ta khai thác được tri
thức hữu dụng từ CSDL được gọi là các kỹ thuật khai phá dữ liệu (DM –
Data Mining). Trong đó, khai phá luật kết hợp và gom cụm dữ liệu là
những nội dung quan trọng trong khai phá dữ liệu. Chính vì những hiệu
quả thiết thực của khai phá dữ liệu, mà trong bài thu hoạch chuyên đề “Khai
phá dữ liệu và nhà kho dữ liệu” em sẽ trình bày nội dung: “Tìm hiểu luật kết
hợp và kỹ thuật gom cụm trong khai phá dữ liệu – chương trình demo
thuật toán Apriori và K-means”, với mục đích hệ thống hóa kiến thức của
môn học mới, phân tích ưu khuyết điểm của từng thuật toán để người dùng có
thể định hướng cách tiếp cận cũng như lựa chọn sử dụng kỹ thuật đúng theo
yêu cầu hay thích hợp trong từng lĩnh vực mà mình quan tâm và qua demo

- Gom nhóm dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai
phá tri thức. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ
liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.
- Trích lọc dữ liệu: Là bước tuyển chọn những tập dữ liệu cần được khai phá
từ các tập dữ liệu lớn (Databases, Data Warehouses, Data Repositories)
ban đầu theo một số tiêu chí nhất định.
- Làm sạch, tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu
không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, ), tổng hợp dữ liệu
(nén, nhóm dữ liệu, tính tổng, xây dựng các histograms, lấy mẫu, ), rời rạc
HVTH: Nguyễn Thị Kim Phượng Trang 4
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
hóa dữ liệu (rời rạc hóa dựa vào histograms, entropy, phân khoảng, ). Sau
bước tiền xử lý này, dữ liệu sẽ nhất quán, đầy đủ hơn.
- Chuyển đổi dữ liệu: Chuyển đổi dữ liệu về dạng phù hợp cho việc khai phá
bằng cách thực hiện các thao tác nhóm hoặc tập hợp.
- Khai phá dữ liệu: Là bước áp dụng những kỹ thuật phân tích, những mối
quan hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn thời
gian nhất của toàn bộ quá trình khám phá tri thức.
- Đánh giá luật: Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên
một số phép đo. Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ
liệu để biểu diễn tri thức khai phá được cho người sử dụng.
Mục đích chính của khai thác dữ liệu:
- Mô tả: mô tả về những tính chất hoặc đặc tính chung của dữ liệu trong cơ
sở dữ liệu hiện có
- Dự đoán: đưa ra các dự đoán dựa vào việc phân tích dữ liệu hiện thời.
Dựa vào hai mục đích chính này của khai thác dữ liệu, người ta sử dụng các
phương pháp sau:
Các phương pháp khai thác dữ liệu
HVTH: Nguyễn Thị Kim Phượng Trang 5
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc

Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
 Kỹ thuật hồi qui : Mục tiêu của phương pháp này là phát hiện và đưa ra
các mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải
thuật khai phá dữ liệu là tập luật kết hợp tìm được.
Phương pháp lựa chọn
Mục đích của kỹ thuật phân loại chính là dự đoán thuộc tính lớp dựa vào các
trường đã biết trong cơ sở dữ liệu và dựa vào tập huấn luyện mẫu.
Giới thiệu các kỹ thuật phân loại
• Cây quyết định
Tư tưởng thuật toán
Cây quyết định là cấu trúc cây có dạng biểu đồ luồng, mỗi nút trong là kiểm
định trên một thuộc tính, mỗi nhánh đại diện cho một kết quả kiểm định, các
nút lá đại diện cho các lớp. Nút cao nhất trên cây là nút gốc.
Rút luật từ Cây quyết định “Chơi Tennis” (theo VD: tập học trang 8,9)
Để phân loại một mẫu chưa biết, các giá trị thuộc tính của mẫu sẽ được kiểm
định trên cây. Đường đi từ gốc tới một nút lá cho biết dự đoán lớp đối với mẫu
đó. (Với P là mẫu dương tương ứng quyết định Yes; Với N là mẫu âm tương
ứng quyết định No)
Mục đích giải thuật: Xây dựng cây quyết định từ tập training set cho trước.
• Thuật toán ID3
HVTH: Nguyễn Thị Kim Phượng Trang 7
Nắng
Vừa
00
Thời ết
Thời ết
Độ ẩm
Độ ẩm
Gió
Gió

Độ đo lựa chọn thuộc tính - Information Gain
Entropy:
Ý nghĩa: Xác định độ hỗn loạn thông tin của dữ liệu.
Công thức : Entropy(P1, P2, P3…)=-P1 log P1-P2 log P2-…-Pn log Pn
Information Gain
Ý nghĩa: Độ lợi thông tin. Nó xác định mức độ hiệu quả của một thuộc tính
trong bài toán phân lớp dữ liệu. Đó chính là sự rút gọn mà ta mong đợi khi
phân chia các lớp dữ liệu theo thuộc tính này.
Công thức: Gains = Entropy [trước khi phân hoạch] – Entropy [sau khi
phân hoạch]
= Entropy (S) – Entropy (P1, P2 , , Pn)
Cây quyết định sẽ lựa chọn thuộc tính có Gains lớn nhất làm nút gốc.
Ví dụ:
Outlook Temperator Humidity Windy Play ?
Sunny hot high FALSE no
Sunny hot high TRUE no
Overcast hot high FALSE yes
Rain mild high FALSE yes
Rain cool normal FALSE yes
Rain cool normal TRUE no
Overcast cool normal TRUE yes
HVTH: Nguyễn Thị Kim Phượng Trang 8
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
Sunny mild high FALSE no
Sunny cool normal FALSE yes
Rain mild normal FALSE yes
Sunny mild normal TRUE yes
Overcast mild high TRUE yes
Overcast hot normal FALSE yes
Rain mild high TRUE no

các đối tượng trong training data (thường sử dụng khoảng cách
Euclidean)
3. Sắp xếp khoảng cách theo thứ tự tăng dần và xác định K láng giềng gần
nhất với Query Point
4. Lấy tất cả các lớp của K láng giềng gần nhất đã xác định
5. Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho
Query Point
Ví dụ minh họa
Trong hình dưới đây, training Data được mô tả bởi dấu (+) và dấu (-), đối
tượng cần được xác định lớp cho nó (Query point) là hình tròn đỏ. Nhiệm vụ
của chúng ta là ước lượng (hay dự đoán) lớp của Query point dựa vào việc
lựa chọn số láng giềng gần nhất với nó. Nói cách khác chúng ta muốn biết liệu
Query Point sẽ được phân vào lớp (+) hay lớp (-).
HVTH: Nguyễn Thị Kim Phượng Trang 11
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
Ta thấy rằng:
1- Nearest neighbor : Kết quả là + (Query Point được xếp vào lớp dấu +)
2- Nearest neighbors : không xác định lớp cho Query Point vì số láng giềng
gần nhất với nó là 2 trong đó 1 là lớp + và 1 là lớp – (không có lớp nào có số
đối tượng nhiều hơn lớp kia)
5- Nearest neighbors : Kết quả là – (Query Point được xếp vào lớp dấu – vì
trong 5 láng giềng gần nhất với nó thì có 3 đối tượng thuộc lớp – nhiều hơn
lớp + chỉ có 2 đối tượng).
• Thuật toán Naive Bayesian
Tư tưởng thuật toán
Định lý Bayes
Định lý Bayes cho phép tính xác suất xảy ra của một sự kiện ngẫu nhiên A khi
biết sự kiện liên quan B đã xảy ra. Xác suất này được ký hiệu là P(A\B), và
đọc là "xác suất của A nếu có B". Đại lượng này được gọi xác suất có điều
kiện hay xác suất hậu nghiệm vì nó được rút ra từ giá trị được cho của B hoặc

HVTH: Nguyễn Thị Kim Phượng Trang 13
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
4. Cho trước các tập dữ liệu với nhiều thuộc tính, việc tính P(X|Ci) sẽ rất tốn
kém. Để giảm tính toán khi đánh giá P(X|Ci), giả định ngây thơ của độc lập có
điều kiện lớp được thiết lập. Điều này làm cho giá trị của các thuộc tính là
độc lập có điều kiện với nhau, cho trước nhãn lớp của mẫu, tức là không có
mối quan hệ độc lập giữa các thuộc tính. Vì thế, P(x1|Ci), P(x2|Ci), , P(xn|Ci)
được đánh giá từ các mẫu huấn luyện với:
(a) Nếu Ak là xác thực thì P(xk|Ci)=sik/si với sik là số lượng các mẫu huấn
luyện của lớp Ci có giá trị xk tại Ak và si là số lượng các mẫu huấn luyện
thuộc về Ci.
(b) Nếu Ak là giá trị liên tục thì thuộc tính được giả định có phân phối
Gaussian. Bởi vậy, với g(xk,µCi,σCi) là hàm mật độ (thông thường) Gaussian
của thuộc tính Ak,với µCi,σCi đại diện cho các giá trị trung bình và độ lệch
chuẩn của thuộc tính Ak đối với các mẫu huấn luyện của lớp Ci.
5. Để phân loại một mẫu chưa biết X, với P(X|Ci)P(Ci) được đánh giá cho lớp
Ci. Mẫu X được ấn định vào lớp Ci khi và chỉ khi:
P(X|Ci)P(Ci) > P(X|Cj)P(Cj) với 1≤ j ≤ m, j ≠ i
Hay nói cách khác, nó được ấn định tới lớp Ci mà tại đó P(X|Ci)P(Ci) cực đại.
2. Quá trình phát hiện tri thức trong CSDL
Khám phá tri thức trong CSDL (KDD) là lĩnh vực liên quan đến các
ngành như: thống kê, học máy, CSDL, thuật toán, trực quan hoá dữ liệu, tính
toán song song và hiệu năng cao,…
Mục đích của quá trình phát hiện tri thức là rút ra tri thức từ dữ liệu
trong CSDL lớn. Quá trình KDD là quá trình gồm nhiều giai đoạn và lặp lại, mà
trong đó sự lặp lại có thể xuất hiện ở bất cứ
bước nào.
Quá trình đó có thể được mô tả theo hình
sau:
HVTH: Nguyễn Thị Kim Phượng Trang 14

ra quyết định nhằm tự động hoá quá trình này.
Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ liệu mà
trong đó khai phá dữ liệu là công đoạn quan trọng nhất.
3. Các kỹ thuật khai phá dữ liệu
3.1 Các kỹ thuật tiếp cận trong Data mining
Căn cứ vào lớp các bài toán cần giải quyết, khai phá dữ liệu có các kỹ
thuật áp dụng sau:
Phân lớp và dự đoán: xếp một đối tượng vào một trong những lớp đã biết
trước. Ví dụ: phân lớp các dữ liệu của bệnh nhân trong hồ sơ bệnh án. Hướng
tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết
định, mạng nơ ron nhân tạo.
Luật kết hợp: Phương pháp này nhằm phát hiện ra các luật kết hợp giữa
các thành phần dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ
liệu là tập luật kết hợp tìm được. Có thể lấy một ví dụ đơn giản về luật kết hợp
như sau: phân tích CSDL bán hàng nhận được thông tin về những khách
hàng mua máy tính cũng có khuynh hướng mua phần mềm quản lý tài chính
trong cùng lần mua được miêu tả trong luật kết hợp sau:
“Mua máy tính → Mua phần mềm quản lý tài chính”
[Độ hỗ trợ: 40%, độ tin cậy: 70%].
Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật. Chúng
tương ứng phản ánh sự hữu ích và sự chắc chắn của luật đã khám phá. Độ
hỗ trợ 40% có nghĩa là: 40% của tất cả các tác vụ đã phân tích chỉ ra rằng
máy tính và phần mềm quản lý tài chính là đã được mua cùng nhau. Còn độ
tin cậy 70% có nghĩa là 70% các khách hàng mua máy tính cũng mua phân
mềm quản lý tài chính.
HVTH: Nguyễn Thị Kim Phượng Trang 16
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
Phân tích chuỗi theo thời gian: Tượng tự như khai phá luật kết hợp
nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng
dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự

là tập
các item - khi đó
YX
⇒
diễn đạt ý nghĩa rằng bất cứ khi nào giao tác
T
có
chứa
X
thì chắc chắn
T
có chứa
Y
. Độ tin cậy của luật (rule confidence) có
thể được hiểu như xác suất điều kiện
)|( TXTYp
⊆⊆
. Ý tưởng của việc khai
thác các luật kết hợp có nguồn gốc từ việc phân tích dữ liệu mua hàng của
khách và nhận ra rằng “Một khách hàng mua mặt hàng X1 và X2 thì sẽ mua
mặt hàng Y với xác suất là c%”.
HVTH: Nguyễn Thị Kim Phượng Trang 17
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
Ứng dụng trực tiếp của các luật này trong các bài toán kinh doanh làm cho
luật kết hợp trở thành một phương pháp khai thác phổ biến. Hơn nữa, luật kết
hợp không chỉ bị giới hạn trong phân tích sự phụ thuộc lẫn nhau trong phạm vi
các ứng dụng bán lẻ mà chúng còn được áp dụng thành công trong rất nhiều
bài toán kinh doanh. Như vậy, khai phá luật kết hợp là một phương pháp xử lý
thông tin quan trọng và phổ biến, nó nhằm khám phá mối liên hệ giữa các
mẫu dữ liệu.

kéo theo một số mục khác. Chỉ xét những qui luật mà tỉ lệ hỗ trợ lớn hơn 40%
và độ tin cậy lớn hơn 90%.
Hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách
hàng được yêu cầu điền vào các mẫu bán hàng để công ty có được một
CSDL về các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan
hệ "tuổi, giới tính, nghề nghiệp và sản phẩm". Khi đó có thể có rất nhiều
câu hỏi tương ứng với luật trên. Ví dụ trong lứa tuổi nào thì những khách
hàng nữ là giới nhân viên văn phòng/công sở đặt mua mặt hàng gì đó, ví
dụ mỹ phẩm chẳng hạn là nhiều nhất, thoả mãn một ngưỡng nào đó?
2. Lý thuyết về luật kết hợp
2.1 Khái niệm
Cho một tập I = {I1, I2, , Im} các tập m mục, một giao dịch T được định
nghĩa như một tập con của các khoản mục trong I (T⊆I).
Tương tự như khái niệm tập hợp, các giao dịch không được trùng lặp,
nhưng có thể nới rộng tính chất này của tập hợp và trong các thuật toán sau
này, người ta đều giả thiết rằng các khoản mục trong một giao dịch và trong
tất cả các tập mục khác, có thể coi chúng đã được sắp xếp theo thứ tự từ điển
của các mục.
Gọi D là CSDL của n giao dịch và mỗi giao dịch được đánh nhãn với một
định danh duy nhất. Nói rằng, một giao dịch T ∈ D hỗ trợ một tập X ⊆ I nếu nó
chứa tất cả các item của X.
Điều này nghĩa là X ⊆ T, trong một số trường hợp người ta dùng ký hiệu
T(X) để chỉ tập các giao dịch hỗ trợ cho X. Kí hiệu support(X) (hoặc sup(X),
HVTH: Nguyễn Thị Kim Phượng Trang 19
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
s(X)) là tỷ lệ phần trăm của các giao dịch hỗ trợ X trên tổng các giao dịch
trong D, nghĩa là:
sup(X) =
{ }
D

⊆∧⊆
(2.2)
Tuy nhiên, không phải bất cứ luật kết hợp nào có mặt trong tập các luật có
thể được sinh ra cũng đều có ý nghĩa trên thực tế. Mà các luật đều phải thoả
mãn một ngưỡng hỗ trợ và tin cậy cụ thể. Thực vậy, cho một tập các giao dịch
D, bài toán phát hiện luật kết hợp là sinh ra tất cả các luật kết hợp mà có độ
tin cậy conf lớn hơn độ tin cậy tối thiểu minconf và độ hỗ trợ sup lớn hơn độ
hỗ trợ tối thiểu minsup tương ứng do người dùng xác định. Khai phá luật kết
hợp được phân thành hai bài toán con:
HVTH: Nguyễn Thị Kim Phượng Trang 20
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
Bài toán 1: Tìm tất cả các tập mục mà có độ hỗ trợ lớn hơn độ hỗ trợ tối
thiểu do người dùng xác định. Các tập mục thoả mãn độ hỗ trợ tối thiểu được
gọi là các tập mục phổ biến.
Bài toán 2: Dùng các tập mục phổ biến để sinh ra các luật mong muốn. Ý
tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta có
thể xác định luật nếu AB => CD giữ lại với tỷ lệ độ tin cậy:
)sup(
)sup(
AB
ABCD
conf =
(2.3)
Nếu conf ≥ minconf thì luật được giữ lại (luật này sẽ thoả mãn độ hỗ trợ tối
thiểu vì ABCD là phổ biến).
2.2 Một số tính chất liên quan đến các hạng mục phổ biến:
2.2.1. Với tập mục phổ biến, có 3 tính chất sau:
Tính chất 1 (Độ hỗ trợ của tập con):
Với A và B là tập các mục, nếu A ⊆ B thì sup(A) ≥ sup(B)
Điều này là rõ ràng vì tất cả các giao tác của D hỗ trợ B thì cũng hỗ trợ A.

Nếu A→(L - A) không thoả mãn độ tin cậy cực tiểu thì luật
B →(L -B) cũng không thoả mãn, với các tập mục L,A,B và B ⊆ A ⊂ L
Vì supp(B) ≥ sup(A) (theo tính chất 1) và định nghĩa độ tin cậy, chúng ta
nhận được: conf(B →(L-B)) =
)sup(
)sup(
)sup(
)sup(
A
L
B
L
≤
< minconf (2.4)
Cũng như vậy: Nếu có (L-C)→ C thì ta cũng có luật (L – D)→D, với D⊆C và
D≠∅.
Bởi vì D⊆C nên (L - D) ⊇ (L - C), do đó sup(L - D) ≤ sup(L-C)
HVTH: Nguyễn Thị Kim Phượng Trang 22
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
⇒
)sup(
)sup(
)sup(
)sup(
CL
L
DL
L
−
≥

HVTH: Nguyễn Thị Kim Phượng Trang 23
Bài Thu Hoạch “DATA MINING”  GVHD: PGS - TS Đỗ Phúc
Luật kết hợp nhiều mức: Cách tiếp cận theo luật này sẽ tìm kiếm thêm
những luật có dạng “mua máy tính PC => mua hệ điều hành AND mua
phần mềm tiện ích văn phòng, …” thay vì chỉ những luật quá cụ thể như
“mua máy tính IBM PC => mua hệ điều hành Microsoft Windows AND mua
phần mềm tiện ích văn phòng Microsoft Office, …”. Như vậy dạng luật đầu là
dạng luật tổng quát hoá của dạng luật sau và tổng quát theo nhiều mức khác
nhau.
Luật kết hợp mờ: Với những hạn chế còn gặp phải trong quá trình rời rạc
hoá các thuộc tính số (quantitave attributes), các nhà nghiên cứu đã đề xuất
luật kết hợp mờ nhằm khắc phục các hạn chế trên và chuyển luật kết hợp về
một dạng tự nhiên hơn, gần gũi hơn với người sử dụng một ví dụ của dạng
này là: “thuê bao tư nhân = ‘yes’ AND thời gian đàm thoại lớn AND cước nội
tỉnh = ‘yes’ => cước không hợp lệ = ‘yes’, với độ hỗ trợ 40% và độ tin cậy
85%”. Trong luật trên, điều kiện thời gian đàm thoại lớn ở vế trái của luật là
một thuộc tính đã được mờ hoá.
Luật kết hợp với thuộc tính được đánh trọng số: Trong thực tế, các
thuộc tính trong CSDL không phải lúc nào cũng có vai trò như nhau. Có một
số thuộc tính được chú trọng hơn và có mức độ quan trọng cao hơn các thuộc
tính khác. Ví dụ khi khảo sát về doanh thu hàng tháng, thông tin về thời gian
đàm thoại, vùng cước là quan trọng hơn nhiều so với thông tin về phương
thức gọi Trong quá trình tìm kiếm luật, chúng ta sẽ gán thời gian gọi, vùng
cước các trọng số lớn hơn thuộc tính phương thức gọi. Đây là hướng nghiên
cứu rất thú vị và đã được một số nhà nghiên cứu đề xuất cách giải quyết bài
toán này. Với luật kết hợp có thuộc tính được đánh trọng số, chúng ta sẽ khai
thác được những luật “hiếm” (tức là có độ hỗ trợ thấp, nhưng có ý nghĩa đặc
biệt hoặc mang rất nhiều ý nghĩa).
Luật kết hợp song song: Bên cạnh khai thác luật kết hợp tuần tự, các nhà
làm tin học cũng tập trung vào nghiên cứu các thuật giải song song cho quá

Tập chỉ báo phổ biến nhị phân
Cho hệ thông tin nhị phân SB = (O, D, B, χ) và một ngưỡng θ ∈ (0, 1).
HVTH: Nguyễn Thị Kim Phượng Trang 25

Trích đoạn GIỚI THIỆU CHƯƠNG TRÌNH DEMO THUẬT TOÁN K-MEANS

---