ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI


Hà Nội, 02/03/2012
Môn: Lý thuyết tập thô và ứng dụng
Tên đề tài: Nghiên cứu cách thể hiện Data Mining sử dụng lý thuyết tập
thô, tìm hiểu luật kết hợp trong khai thác dữ liệu, demo quá trình khai phá
dữ liệu sử dụng thuật toán Apriori
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
LỚP: KHMT4 – K5
Sinh viên: Nguyễn Ngọc Tuấn
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
MỤC LỤC
I. LỜI MỞ ĐẦU 3
II. CƠ SỞ LÝ THUYẾT TẬP THÔ LIÊN QUAN 4
1. Khai phá trí thức trong csdl (Knowdlege Discovery in Databases – KDD) 4
2. Tập thô trong khai phá trí thức 4
3. Mô tả các bước khai phá dữ liệu sử dụng lý thuyết tập thô 5
3.1. Hiệu chỉnh dữ liệu: 5
3.2. Rút gọn tập thuộc tính: 5
3.3. Rút trích tập luật: 5
III. KỸ THUẬT KHAI PHÁ DỮ LIỆU SỬ DỤNG LUẬT KẾT HỢP 6
1. Tổng quan 6
2. Các khái niệm và công thức thể hiện: 7
2.1. Độ hỗ trợ: 7
2.2. Độ hỗ trợ tối thiểu: (minsupp) 7
2.3. Độ tin cậy: 7
2.4. Độ tin cậy tối thiểu: (minconf) 7
3. Các bước khai phá luật kết hợp 7
4. Thuật toán sinh các luật kết hợp Apriori (ý tưởng của Agrawal and Srikant - 1994) 7

sản xuất, kinh doanh. Cá nhân hoặc tổ chức nào thu thập và hiểu được thông tin
và hành động dựa trên các thông tin được kết xuất từ các thông tin đã có sẽ đạt
được thành công trong mọi hoạt động. Chính vì lý do đó, việc tạo ra thông tin, tổ
chức lưu trữ và khai thác ngày càng trở nên quan trọng và gia tăng không ngừng.
Sự tăng trưởng vượt bậc của các cơ sở dữ liệu (CSDL) trong cuộc sống
như: 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ừ đó các nhà quản lý có được thông tin có
ích để tác động lại quá trình sản xuất, kinh doanh của mình… đó là tri thức. Các
kỹ thuật cho phép ta khai thác được tri thức hữu dụng từ CSDL (lớn) được gọi là
các kỹ thuật khai phá dữ liệu (DM – Data Mining). Khai phá luật kết hợp là một
nội dung quan trọng trong khai phá dữ liệu.
Kỹ thuật khám phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam
kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần
đưa vào ứng dụng.
Khai phá dữ liệu (Data Mining) được coi là quá trình trích xuất các thông
tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các CSDL,
kho dữ liệu… Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một
số thuật ngữ khác có ý nghĩa tương tự như: Khám phá tri thức từ cơ sở dữ liệu
(Knowledge Discovery in Database-KDD), trích lọc dữ liệu (knowlegde
extraction), phân tích dữ liệu/mẫu (data/pattern analysis), khảo cổ dữ liệu (data
archaeology), nạo vét dữ liệu (data dredging).
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 3 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
Báo cáo trình bày một số vấn đề về khám phá tri thức, khai phá dữ liệu, và
trình bày rõ vấn đề khai phá luật kết hợp và ứng dụng một số thuật toán khai phá
luật kết hợp trong CSDL có sử dụng lý thuyết tập thô.

nhiều khía cạnh (Lin và Cercone, 1997; Pal và Skowron, 1999; Pawlak, 1982;
1991; Skowron và Rauszer, 1992), được sử dụng trong các giai đoạn khác nhau
của quá trình khai phá trí thức, như là chọn lọc thuộc tính, khai thác thuộc tính,
rút gọn tập dữ liệu, sinh ra bảng quyết định và rút trích tập luật (mẫu, luật kết
hợp) (Komorowski et al., 1999)
3. Mô tả các bước khai phá dữ liệu sử dụng lý thuyết tập thô
3.1. Hiệu chỉnh dữ liệu:
Khi nhận dạng dữ liệu có thể có những bản ghi trong bảng thuộc tính không
thể nhận biết được do lỗi nhập liệu
Để xử lý trường hợp này, chúng ta có thể xem dữ liệu sau định dạng như là
một hệ thống thông tin không đầy đủ, và điền giá trị thích hợp theo thuật
toán của nhóm tác giả Dai Dai, Jiangpeng Wang.
3.2. Rút gọn tập thuộc tính:
Như đã biết, từ một bảng quyết định có nhiều đối tượng, tập luật quyết định
rút trích được là rất lớn. Để thu gọn tập luật quyết định mà không làm mất đi tính
đặc trưng của bảng quyết định, một trong những phương án là thu gọn tập thuộc
tính.
3.3. Rút trích tập luật:
Sinh luật quyết định là một kết quả quan trọng của phần mềm. Thuật toán
sử dụng để sinh luật dựa tiếp cận tính toán hạt của các tác giả Haiyan Yu và
Daoping Wang. Thuật toán đã được công bố và so sánh với các thuật toán rút
trích dữ liệu khác. Tính ưu việt của thuật toán là việc kết xuất dữ liệu được phân
lớp, tổ hợp đơn giản). Trong phần mềm demo, luật kết hợp với thuật toán apriori
được dùng để rút trích tập luật.
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 5 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
III. KỸ THUẬT KHAI PHÁ DỮ LIỆU SỬ DỤNG LUẬT KẾT
HỢP
1. Tổng quan

2.3. Độ tin cậy:
Là số phần trăm giao tác có chứa tập B trong số những thao tác chứa tập A
confidence(A ⇒ B [ s, c ]) = p(B|A) = p(A∪B) / p(A) = support({A,B}) /
support({A})
2.4. Độ tin cậy tối thiểu: (minconf)
Là phần trăm tối thiểu giao tác có chứa tập B trong số những thao tác chứa
tập A.
Nếu minconf cao, ít luật nhưng tất cả “gần như đúng”
Nếu minconf thấp, nhiều luật nhưng phần lớn là không chắc chắn
3. Các bước khai phá luật kết hợp
Bước 1: Tìm các tập phổ biến: các tập các phần tử có độ support tối thiểu
Bước 2: Dùng các tập phổ biến để tạo ra luật kết hợp
4. Thuật toán sinh các luật kết hợp Apriori (ý tưởng của Agrawal
and Srikant - 1994)
4.1. Định nghĩa
Phương pháp sinh ứng viên để tìm tập phổ biến được Agrawal [13] đề xuất
từ năm 1993 với thuật toán Apriori. Ý tưởng của thuật toán Apriori dựa trên kết
luận: nếu một tập danh mục là phổ biến thì tất cả tập con của nó cũng phải phổ
biến (tính chất 2 – tập phổ biến). Do vậy không thể có trường hợp một tập phổ
biến có tập con là không phổ biến hay nói cách khác tập phổ biến nhiều danh
mục hơn chỉ có thể được tạo ra từ các tập phổ biến ít danh mục hơn.
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 7 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
4.2. Tư tưởng chính của thuật toán Apriori
Tư tưởng chính của thuật toán Apriori là: Tìm tất cả frequent itemsets: k-
itemset (itemsets gồm k items) được dùng để tìm (k+1)- itemset.
Đầu tiên tìm 1-itemset (ký hiệu L1). L1 được dùng để tìm L2 (2-itemsets).
L2 được dùng để tìm L3 (3-itemset) và tiếp tục cho đến khi không có k-itemset
được tìm thấy.

Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 9 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
Kết quả ta có các luật kết hợp sau (với min_sup= 40%, min_conf=70%):
R1: Beer => Diaper (support =60%, confidence = 75%)
R2: Diaper =>Beer (support =60%,confidence = 75%)
R3: Milk =>Beer (support =40%, confidence = 100%)
R4: Baby Powder => Diaper (support =40%,confidence = 100%)
Từ kết quả các luật được sinh ra bởi giao dịch bán hàng trên, ta thấy rằng
có luật có thể tin được (hợp lý) như Baby Powder => Diaper, có luật cần phải
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 10 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
phân tích thêm như Milk =>Beer và có luật có vẻ khó tin như Diaper =>Beer.Ví
dụ này sinh ra các luật có thể không thực tế vì dữ liệu dùng để phân tích
(transaction database) hay còn gọi là tranining data rất nhỏ.
Thuật toán Apriori được dùng để phát hiện các luật kết hợp dạng khẳng
định (Positive Rule X=>Y) nhị phân (Binary Association Rules) chứ không thể
phát hiện các luật kết hợp ở dạng phủ định (Negative Association Rule) chẳn
hạn như các kết hợp dạng “Khách hàng mua mặt hàng A thường KHÔNG mua
mặt hàng B” hoặc “Nếu ủng hộ quan điểm A thường KHÔNG ủng hộ quan
điểm B”. Khai phá các luật kết hợp dạng phủ định (Mining Negative Association
Rules) có phạm vi ứng dụng rất rộng và thú vị nhất là trong Marketing, Health
Care và Social Network Analysis.
4.4. Mã giải
 Bước kết hợp : C
k
được tạo bằng cách kết L
k-1
với chính nó

return ∪
k
L
k
;
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 11 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
IV. BÀI TOÁN THỰC TẾ
1. TỔNG QUAN BÀI TOÁN ỨNG DỤNG
Một tổ chức đào tạo cho các phòng khám về kiến thức và kỹ năng chăm sóc
người bệnh đã tạo ra một ứng dụng để lưu lại các thông tin về các khóa đào tạo,
trong đó có thông tin quan trọng là tên những phòng khám đã tham gia đào tạo.
Dựa vào nguồn dữ liệu đó, tổ chức đào tạo muốn dùng luật kết hợp để khai thác
độ ủng hộ và độ tin cậy của các tập các phòng khám, giúp tổ chức định hướng tốt
các đối tượng tham gia chương trình lâu dài, bền vững.
Mô hình bảng CSDL trong SQL SERVER:
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 12 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
2. GIẢI QUYẾT BÀI TOÁN SỬ DỤNG TẬP THÔ & THUẬT
TOÁN APRIORI
Sử dụng lý thuyết tập thô và thuật toán Apiori cài đặt trực tiếp trên store
procedure của SQL server
Các bước xây dựng thuật toán như sau:
2.1. Bước 1: Chọn bảng thuộc tính ban đầu:
CREATE PROCEDURE [dbo].[getTraining_Attendees_SourceData]
AS
SELECT * FROM (SELECT ROW_NUMBER() OVER(ORDER BY TrainingId) AS
'RowNum', * FROM TRAINING_ATTENDEES) A

OPCNames nvarchar(max), ItemsCount int, Support float);
declare @minItemsMatch float
declare @maxItemsMatch int
set @minItemsMatch = 0
set @maxItemsMatch = 0
/* Tổng số khóa học có ít nhất 1 OPC tham dự*/
SELECT @maxItemsMatch = count(*) from training where trainingid
in(select trainingid from training_attendees_reduce where OPCID is not null
and ProvinceID is not null)
/* Số lượng lần tham dự tối thiểu */
SET @minItemsMatch = @maxItemsMatch * @minSup
/* Lấy ra tập mẫu đầu tiên cấp 1 - Level 1*/
INSERT INTO @TempCandidate(OPCIDs, OPCNames, ItemsCount, Support)
SELECT OPCID, OPCName, Temp.SessionsCount,
ROUND(CONVERT(float,Temp.SessionsCount)/CONVERT(float,@maxItemsMatch), 4)*100 FROM
(select distinct B.OPCID, B.OPCName,
(select count(*)
from training_attendees_reduce C where C.OPCID = A.OPCID) as SessionsCount
from training_attendees_reduce A
inner join OPC B on A.OPCID = B.OPCID) as Temp
where Temp.SessionsCount >= @minItemsMatch
order by OPCID
/* Khai báo các biến cần thiết */
Declare @OPCIDsTemp varchar(max)
Declare @OPCNamesTemp nvarchar(max)
Declare @SupportTemp varchar(max)
Declare @OPCIDsSubTemp varchar(max)
Declare @OPCSubNamesTemp nvarchar(max)
Declare @counter int
Declare @subcounter int

cần phải xét ngược lại) */ (Ví dụ: tập level 1 có phần tử 1,2,3,7,8,10. Tập đang xét là 4,5 thì chỉ xét tiếp
4,5,7)
/* Kiểm tra xem phần tử có phải Level 1 không */
SELECT @Pos = CASE (CHARINDEX(',', @OPCIDsTemp))
WHEN 0 THEN -1
ELSE LEN(@OPCIDsTemp) - CHARINDEX(',',
REVERSE(@OPCIDsTemp))+2
END

IF @Pos >= 0
SET @LastCheck = SUBSTRING(@OPCIDsTemp, @Pos,
LEN(@OPCIDsTemp)) /* Phần tử Level > 1 */
ELSE
SET @LastCheck = @OPCIDsTemp /*Phần tử Level 1*/
/* Tập các phần tử cần ghép của Level 1 */
INSERT INTO #TempCandidateOther SELECT OPCIDs FROM
@TempCandidate
where RowNum<=@candidatesFirstCount and
CONVERT(INT,OPCIDs)>CONVERT(INT,@LastCheck)
SET @subcounter = 0
Select @candidatesOtherCount = Count(*) from #TempCandidateOther
/* Bắt đầu chạy vòng lặp để ghép thử phần tử Level 1 với phần tử hiện tại. Các
phần tử có thể ghép được tiếp thuộc Level 1 sẽ ngày càng bị thu hẹp lại theo thời gian khi Level càng cao
*/
While @subcounter < @candidatesOtherCount
BEGIN
SELECT @OPCIDsSubTemp = @OPCIDsTemp + ',' +
OPCIDs from #TempCandidateOther
where Rownum = @subcounter + 1
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 16 / 22

@TempCandidate(OPCIDs, OPCNames, ItemsCount, Support) VALUES(@OPCIDsSubTemp,
@OPCNames, @newFounds,
ROUND(CONVERT(float,@newFounds)/CONVERT(float,@maxItemsMatch), 4)*100)
END
SET @subcounter = @subcounter + 1
END
/* Xóa bảng tạm, cắt bỏ hết dữ liệu và đánh lại identity cho trường ROWNUM
lại từ đầu */

DELETE FROM #TempCandidateOther
truncate table #TempCandidateOther

Set @counter = @counter + 1

/* Cập nhật biến @candidatesCount để tiếp tục mở rộng vùng duyệt nếu có
phần tử mới được thêm vào */
Select @candidatesCount = Count(*) from @TempCandidate
END
Đến bước này, khi ta thử kiểm tra tập dữ liệu có độ ủng hộ tối thiểu (vd:
0.4) trở lên có dạng ví dụ như sau:
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 17 / 22
BÀI TẬP LỚN – LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG – TẬP THÔ VÀ LUẬT KẾT HỢP
Giáo viên hướng dẫn: Th.S Vũ Anh Tú
2.4. Bước 4: Dùng các tập phổ biến để tạo ra luật kết hợp
/* Tạo bảng tạm lấy dữ liệu từ bảng kết quả từ bước 1 thỏa mãn điều kiện là một tập mới không trùng với
tập đang xét có thỏa mãn độ phổ biến tối thiểu khi sinh ra tập mới và độ tin cậy tối thiểu đối với tập đang
xét không */
CREATE TABLE #TempConfOther(RowNum INT identity, OPCIDs varchar(max), OPCNames
nvarchar(max), Support float);
/* Tạo một biến bảng lưu trữ các phần tử thỏa mãn độ tin cậy và độ phổ biến */

BEGIN
SELECT @OPCIDsSubTemp = OPCIDs,
@OPCSubNamesTemp=OPCNames FROM #TempConfOther where RowNum = @subcounter + 1
/* Kiểm tra số lượng buổi đào tạo mà OPCIDs của cả hai tập
hợp đều tham dự cùng nhau */
set @sql = N'SELECT @i=Count(*) FROM (select
trainingid from
(
select distinct trainingid, OPCID from
training_attendees_reduce where OPCID in(' + @OPCIDsTemp + ',' + @OPCIDsSubTemp + '))
as Temp
Group by Trainingid
having count(*) = (len(''' + @OPCIDsTemp + ',' +
@OPCIDsSubTemp + ''') - len(replace(''' + @OPCIDsTemp + ',' + @OPCIDsSubTemp + ''','','','''')) + 1))
as ABC'
EXEC SP_EXECUTESQL @sql, N'@i int output',
@count_associate output
SET @confTemp = 0
IF @count_associate > 0
/* Tính độ tin cậy */
SET @confTemp = CONVERT(float,
@count_associate) / CONVERT(float, @count_supitem)
SET @newFounds = 0
/* Chọn được ứng viên thỏa mãn */
IF @confTemp >= @minConf AND
@count_associate >= @minItemsMatch
BEGIN
/* Đưa vào bảng các tập kết quả thỏa mãn */
INSERT INTO
@TempCandidateConf VALUES(@OPCIDsTemp, @OPCNamesTemp, @OPCIDsSubTemp,

• Đọc CSDL nhiều lần và việc phát sinh phải kiểm tra lượng lớn các ứng
viên
 Cách Khắc phục: Dùng phương pháp không sinh ứng viên như phương
pháp FP—Tree (Freequence Pattern Tree)
V. KẾT LUẬN
Báo cáo đã trình bày tổng quan và các nét đặc trưng nhất trong việc sử dụng
luật tập thô và luật kết hợp để khai phá dữ liệu và cách sử dụng thuật toán
Apriori.
Về mặt lý thuyết, khai phá tri thức bao gồm các bước: Hình thành, xác định
và định nghĩa bài toán; thu thập và tiền xử lý dữ liệu; khai phá dữ liệu, rút ra các
tri thức; sử dụng các tri thức phát hiện được.
Trong quá trình thực hiện báo cáo, em đã cố gắng tập trung tìm hiểu và
tham khảo các tài liệu liên quan. Tuy nhiên, với thời gian và trình độ có hạn nên
không tránh khỏi những hạn chế và thiếu sót. Chúng em rất mong được sự nhận
xét và góp ý của thầy Vũ Anh Tú và bạn bè cùng lớp để báo cáo của em hoàn
thiện hơn.
Em xin chân thành cảm ơn thầy đã hướng dẫn em hoàn thành bản báo cáo
này
VI. TÀI LIỆU THAM KHẢO
[1] Nguyễn Đức Thuần (2010) – Phủ tập thô và độ đo đánh giá hiệu năng
tập luật quyết định - Luận án Tiến sĩ Toán học, Viện Công Nghệ Thông Tin.
[2] Hrudaya Ku. Tripathy, B. K. Tripathy, and Pradip K. Das - An
Intelligent Approach of Rough Set in Knowledge Discovery Databases - World
Academy of Science, Engineering and Technology 35 2007
[3] Introduction to Data Mining (Pang-Ning Tan, Michael Steinbach, Vipin
Kumar) - 2006 - Pearson Addison-Wesley
Nguyễn Ngọc Tuấn – Lớp KHMT4 – K5 Trang 22 / 22