Khai phá Luật kết hợp trong cơ sở dữ liệu
đa phương tiện Nguyễn Thị Biên Trường Đại học Công nghệ
Luận văn ThS. ngành: Công nghệ phần mềm; Mã số: 60 48 10
Người hướng dẫn: PGS.TS. Đặng Văn Đức
Năm bảo vệ: 2012 Abstract. Tổng quan về phát hiện tri thức, quá trình phát hiện tri thức từ cơ sở dữ
liệu và khai phá dữ liệu. Nghiên cứu cơ sở dữ liệu đa phương tiện cũng như hệ quản
trị cơ sở dữ liệu đa phương tiện. Tìm hiểu về luật kết hợp trong khai phá dữ liệu qua
định nghĩa, bài toán, hướng tiếp cận và một số thuật toán phát hiện luận kết hợp.
Trình bày khai phá luật kết hợp trong cơ sở dữ liệu hình ảnh: dữ liệu hình ảnh; trích
chọn đặc trưng trong khai phá ảnh; khai phá luật kết hợp dựa trên nội dung ảnh bằng
thuật toán Apriori.

Keywords. Công nghệ phần mềm; Cơ sở dữ liệu đa phương tiện; Khai phá dữ liệu

Content
MỞ ĐẦU
Trong điều kiện và yêu cầu của thương trường, đòi hỏi phải có những phương pháp
nhanh, phù hợp, tự động, chính xác và có hiệu quả để lấy được thông tin có giá trị. Các tri
thức chiết xuất được từ cơ sở dữ liệu sẽ là một nguồn tài liệu hỗ trợ cho lãnh đạo trong việc
lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. Vì vậy, tính ứng
dụng của khai thác luật kết hợp từ cơ sở dữ liệu là một vấn đề đang được quan tâm.
Khai phá dữ liệu là giai đoạn quan trọng trong tiến trình khai thác tri thức từ cơ sở dữ liệu,

Hình 1.1: Quy trình phát hiện tri thức từ cơ sở dữ liệu
 Làm sạch dữ liệu: Loại bỏ dữ liệu nhiễu hoặc dữ liệu không thích hợp.
 Tích hợp dữ liệu: Tích hợp dữ liệu từ các nguồn khác nhau.
 Chọn dữ liệu: Chọn những dữ liệu liên quan trực tiếp đến nhiệm vụ.
 Chuyển đổi dữ liệu: Chuyển DL về những dạng phù hợp cho việc khai phá.
 Khai phá dữ liệu.
 Đánh giá mẫu: Đánh giá mẫu hoặc tri thức đã thu được.
 Trình diễn dữ liệu: Biểu diễn những tri thức khai phá được cho người sử dụng.
1.2.1. Xác định vấn đề
Trong thực tế, các cơ sở dữ liệu được chuyên môn hóa và phân chia theo các lĩnh vực
khác nhau như sản phẩm, kinh doanh, tài chính, … Vì vậy mà việc xác định lĩnh vực và định
nghĩa bài toán giúp định hướng cho giai đoạn tiếp theo thu thập và tiền xử lý dữ liệu.
1.2.2. Thu thập và tiền xử lý dữ liệu
Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại không đầy đủ,
không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy, giai đoạn thu thập và tiền xử lý
dữ liệu trở nên rất quan trọng trong quá trình phát hiện tri thức từ cơ sở dữ liệu. Người ta chia
giai đoạn thu thập và tiền xử lý dữ liệu thành các công đoạn như sau:
a. Chọn lọc dữ liệu
b. Làm sạch dữ liệu
c. Làm giàu dữ liệu
d. Mã hóa
1.2.3. Khai thác dữ liệu
Giai đoạn khai thác dữ liệu được bắt đầu sau khi dữ liệu đã được thu thập và tiến hành
xử lý. Trong giai đoạn này, công việc chủ yếu là xác định được bài toán khai thác dữ liệu,
tiến hành lựa chọn phương pháp khai thác phù hợp với dữ liệu có được và tách ra các tri thức
cần thiết.
1.2.4. Minh họa và đánh giá
Các tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo cáo phục
vụ cho các mục đích hỗ trợ quyết định khác nhau.
1.2.5. Đưa kết quả vào thực tế

Mục tiêu của phương pháp phân loại dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu.
Quá trình phân loại dữ liệu thường gồm hai bước : xây dựng mô hình và sử dụng mô hình để
phân loại dữ liệu.
 Bước 1 : Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước.
 Bước 2 : Sử dụng mô hình để phân loại dữ liệu.
Hay nói các khác, phân loại là học một hàm ánh xạ một mục dữ liệu vào trong số các lớp
cho trước.
b) Hồi quy
Phương pháp hồi quy khác với phương pháp phân loại dữ liệu ở chỗ, hồi qui dùng để
dự đoán về các giá trị liên tục còn phân loại dữ liệu chỉ dùng để dự đoán về các giá trị rời rạc.
Hồi quy là một hàm học ánh xạ mục dữ liệu thành một biến dự đoán có giá trị thực.
1.3.4.2. Khai phá dữ liệu mô tả
Kỹ thuật này có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu
trong CSDL hiện có. Bao gồm các kỹ thuật: Phân cụm; Khai phá luật kết hợp
a) Phân cụm
Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng tương tự
nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một một cụm là tương
đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng.
Hình 1.4. cho thấy sự phân cụm tập dữ liệu cho vay vào trong 3 cụm : Lưu ý rằng các
cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn một cụm.

Hình 1.4 : Phân cụm tập dữ liệu cho vay thành 3 cụm
b) Khai phá luật kết hợp
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 cơ sở dữ liệu. Mẫu đầu ra của giải thuật KPDL là luật kết hợp tìm được.
1.3.5. Kiến trúc của hệ thống khai phá dữ liệu
Kiến trúc điển hình của một hệ thống KPDL được trình bày trong hình 1.5.

Hình 1.5 : Kiến trúc điển hình của một hệ thống khai phá dữ liệu


các mục media.
MIRS: Là một hệ thống cơ sở cung cấp việc truy xuất thông tin Multimedia khi sử
dụng tổ hợp DBMS. Trong một MIRS các vấn đề về bảo mật hay phiên bản không được thực
hiện đầy đủ. Một MIRS đầy đủ gọi là một Hệ quản trị cơ sở dữ liệu đa phương tiện
(MMDBMS).
2.1.1.6. Trích chọn đặc trưng, Biểu diễn nội dung và Xây dựng chỉ mục
Một trong những nhiệm vụ quan trọng của MIRS là trích chọn đặc trưng hay biểu
diễn nội dung. Trích chọn đặc trưng là tiến trình tự động hay bán tự động. Chỉ mục là danh
từ, đề cập đến cấu trúc dữ liệu hay đề cập đến tổ chức các đặc trưng đã trích chọn để tìm
kiếm hiệu quả.
2.1.2. Vai trò của MIRS
Cần phải có MIRS vì:
 Ngày càng có nhiều dữ liệu đa phương tiện được thu thập và lưu trữ, để sử dụng tốt
cần phải có hệ thống truy tìm và chỉ số hóa tốt.
 Khác với loại dữ liệu chữ và số, dữ liệu đa phương tiện có tính chất và yêu cầu đặc
biệt, một CSDL truyền thống không phù hợp trong việc quản lý cơ sở dữ liệu đa
phương tiện.
 Các kỹ thuật truy tìm thông tin có thể giúp truy tìm đa phương tiện nhưng chúng chưa
có khả năng quản lý hiệu quả dữ liệu đa phương tiện.
2.1.2.1. Các DBMS và vai trò của chúng trong việc xử lý dữ liệu Multimedia
Các DBMS ngày nay được phát triển khá tốt và được sử dụng rông rãi cho các dữ liệu
có cấu trúc. DBMS quen thuộc là DBMS quan hệ (Ralational Database Management System
- RDBMS). Trong RDBMS, thông tin dược tổ chức thành bảng hoặc các quan hệ. [1]
Một dạng khác của các DBMS là hệ thống quản trị CSDL hướng đối tượng
(OODBMS- Object Oriented Database Management System). Các OODBMS kết nối các khả
năng của cơ sơ dữ liệu (như lưu trữ và tìm kiếm) và các đặc trưng hướng đối tượng (tóm
lược, sự thừa kế, tính đồng nhất đối tượng).
Khả năng cần có trong hệ thống như sau:
 Công cụ để tự động hoặc bán tự động trích chọn đặc trưng chứa trong dữ liệu đa phương
tiện.

 Đo tính “tương tự” giữa hai mục media như thế nào?
 Thiết kế giao diện như thế nào để nó có thể chấp nhận các câu truy vấn phức tạp, mờ và
mềm dẻo?
 So sánh hiệu năng giữa các hệ thống MIRS bằng cách nào?
 Làm thế nào để đáp ứng yêu cầu thời gian khi truyền tải hay trình diễn dữ liệu
Multimedia?
2.1.4 Khả năng mong đợi và các ứng dụng của MIRS
MIRS cần phải mạnh và mềm dẻo. Khả năng của chúng được miêu tả bằng các kiểu
truy vấn mà chúng có thể hỗ trợ. Các loại truy vấn mong đợi của MIRS như sau:
 Truy vấn trên cơ sở meta-data
 Truy vấn trên cơ sở mô tả
 Truy vấn trên cơ sở mẫu (pattern) hay đặc trưng
 Truy vấn theo thí dụ (by example)
 Truy vấn ứng dụng cụ thể:
 Cuối cùng, các MIRS sẽ tập trung vào chính thông tin thay thế các loại truyền thông
và việc miêu tả chúng có thể được sắp xếp hoặc dịch ra từ loại truyền thông này đến
loại truyền thông khác.
2.2. Dữ liệu đa phương tiện
Dữ liệu multimedia được chia thành hai lớp là các dữ liệu liên tục và các dữ liệu không
liên tục. Các dữ liệu liên tục bao gồm các dữ liệu âm thanh, video thay đổi theo thời gian.
Các dữ liệu không liên tục là các dữ liệu không phục thuộc vào thời gian, các loại dữ liệu đặc
trưng cho dạng này là các dữ liệu văn bản (có hoặc không có định dạng), hình ảnh tĩnh và các
đối tượng đồ họa. Các kiểu dữ liệu thông thường của một CSDL multimedia bao gồm:
 Dữ liệu văn bản (có hoặc không có định dạng).
 Đồ họa: là các bản vẽ, minh họa được mã hóa như các tệp postscript.
 Hình ảnh: là các hình ảnh được mã hóa sử dụng các dạng thức chuẩn như là
 JPEG hoặc MPEG.
 Các hoạt hình.
 Âm thanh.
 Video.

được các yêu cầu và cách thức thể hiện khác nhau. .
 Giả sử các kiểu media khác nhau có các yêu cầu cập nhật và sửa đổi thông tin khác
nhau thì hệ thống sẽ cập nhật các thành phần này như thế nào.
1. Khả năng quản trị lưu trữ lớn
2. Hỗ trợ truy vấn và khai thác dữ liệu
3. Tích hợp các phương tiện, tổng hợp và thể hiện
4. Giao diện và tương tác
5. Hiệu suất

CHƢƠNG 3 – LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU
3.1. Bài toán kinh điển dẫn đến việc khai phá luật kết hợp
Bài toán giỏ mua hàng trong siêu thị.
Giả định chúng ta có rất nhiều mặt hàng, ví dụ như “bánh mì”, “sữa”,…(coi là tính
chất hoặc trường). Khách hàng khi đi siêu thị sẽ bỏ vào giỏ mua hàng của họ một số mặt hàng
nào đó, và chúng ta muốn tìm hiểu các khách hàng thường mua các mặt hàng nào đồng thời,
chúng ta không cần biết khách hàng cụ thể là ai. Nhà quản lý dùng những thông tin này để
điều chỉnh việc nhập hàng về siêu thị, hay đơn giản là để bố trí sắp xếp các mặt hàng gần
nhau, hoặc bán các mặt hàng đó theo một gói hàng, giúp cho khắc đỡ mất công tìm kiếm.
Khai phá luật kết hợp được mô tả như sự tương quan của các sự kiện những sự kiện xuất
hiện thường xuyên một các đồng thời. Nhiệm vụ chính của khai phá luật kết hợp là phát hiện
ra các tập con cùng xuất hiện trong một khối lượng giao dịch lớn của một cơ sở dữ liệu cho
trước.
3.2. Định nghĩa về luật kết hợp
Định nghĩa:
Cho I={I1, I2, , Im} là tập hợp của m tính chất riêng biệt. Giả sử D là CSDL, với các
bản ghi chứa một tập con T các tính chất (có thể coi như ), các bản ghi đều có chỉ số
riêng. Một luật kết hợp là một mệnh đề kéo theo có dạng XY, trong đó X, Y  I, thỏa mãn
điều kiện XY=. Các tập hợp X và Y được gọi là các tập hợp tính chất (itemset). Tập X
gọi là nguyên nhân, tập Y gọi là hệ quả.
Có 2 độ đo quan trọng đối với luật kết hợp: Độ hỗ trợ (support) và độ tin cậy

tập hợp chứa X  Y, so với tổng số các bản ghi chứa X.
Chúng ta nhận thấy rằng tri thức đem lại bởi luật kết hợp dạng trên có sự khác biệt rất
nhiều so với những thông tin thu được từ các câu lệnh truy vấn dữ liệu thông thường như
SQL. Đó là những tri thức, những mối liên hệ chưa biết trước và mang tính dự báo đang tiềm
ẩn trong dữ liệu. Những tri thức này không đơn giản là kết quả của phép nhóm, tính tổng hay
sắp xếp mà là của một quá trình tính toán khá phức tạp.
Định nghĩa: Tập hợp thƣờng xuyên
Định nghĩa 3.5: Tập hợp X được gọi là tập hợp thường xuyên (Frenquent itemset) nếu có
supp(X) minsup, với minsup là ngưỡng độ hỗ trợ cho trước. Kí hiệu các tập này là FI
Tính chất 3.1: Giả sử A,B  I là hai tập hợp với AB thì supp(A) supp(B).
Như vậy, những bản ghi nào chứa tập hợp B thì cũng chứa tập hợp A
Tính chất 3.2: Giả sử A, B là hai tập hợp, A,B I, nếu B là tập hợp thường xuyên và AB
thì A cũng là tập hợp thường xuyên.
Thật vậy, nếu B là tập hợp thường xuyên thì supp(B) minsup, mọi tập
hợp A là con của tập hợp B đều là tập hợp thường xuyên trong cơ sở dữ liệu D vì supp(A)
supp(B) (Tính chất 3.1)
Tính chất 2.3: Giả sử A, B là hai tập hợp, A  B và A là tập hợp không thường xuyên thì B
cũng là tập hợp không thường xuyên
Định nghĩa 2.6: Một tập mục X được gọi là đóng (closed) nếu không có tập cha nào của X
có cùng độ hỗ trợ với nó, tức là không tồn tại một tập mục X’ nào mà X’X và t(X) = t(X’)
(với t(X) và t(X’) tương ứng là tập các giao chứa tập mục X và X’). Ký hiệu tập phổ biến
đóng là FCI.
Định nghĩa 2.7: Nếu X là phổ biến và không tập cha nào của X là phổ biến, ta nói rằng X là
một tập phổ biến lớn nhất (maximally frequent itemset). Ký hiệu tập tất cả các tập phổ biến
lớn nhất là MFI. Dễ thấy MFI FCI FI.
Khai phá luật kết hợp là công việc phát hiện ra (tìm ra, khám phá, phát hiện) các luật kết
hợp thỏa mãn các ngưỡng độ hỗ trợ () và ngưỡng độ tin cậy () cho trước. Bài toán khai phá
luật kết hợp được chia thành hai bài toán nhỏ, hay như người ta thường nói, việc giải bài toán
trải qua hai pha:
 Pha 1: Tìm tất cả các tập phổ biến (tìm FI) trong CSDL T.

Thuật toán 2- Tìm luật kết hợp khi đã biết các tập hợp thƣờng xuyên:
Input: I, D, S
Output: Các luật kết hợp thỏa mãn ngưỡng độ hỗ trợ , ngưỡng độ tin cậy .
Algorithm:
1) Lấy ra một tập xuất hiện –thường xuyên SS, và một tập con X  S.
2) Xét luật kết hợp có dạng X → (SX), đánh giá độ tin cậy của nó xem có nhỏ hơn  hay
không.
Thực chất, tập hợp S mà ta xét đóng vai trò của tập hợp giao S = XY, và do X (S
– X) = , nên coi như Y= S – X.
Các thuật toán xoay quanh khai phá luật kết hợp chủ yếu nêu ra các giải pháp để đẩy
nhanh việc thực hiện mục 1 của Thuật toán 1.
3.4. Một số thuật toán phát hiện luật kết hợp
3.4.1. Thuật toán Apriori
Thuật toán dựa trên một nhận xét khá đơn giản là bất kỳ tập hợp con nào của tập xuất
hiện  thường xuyên cũng là tập xuất hiện –thường xuyên. Do đó, trong quá trình đi tìm các
tập ứng cử viên, nó chỉ cần dùng đến các tập ứng cử viên vừa xuất hiện ở bước ngay trước
đó, chứ không cần dùng đến tất cả các tập ứng cử viên (cho đến thời điểm đó). Nhờ vậy, bộ
nhớ được giải phóng đáng kể.
 Bước 1: cho trước ngưỡng độ hỗ trợ 0 1. Tìm tất cả các mặt hàng xuất hiện –
thường xuyên.
 Bước 2: Ta tiến hành ghép đôi các phần tử của L1 (không cần để ý đến thứ tự), được
tập C2, tạp gọi là tập các ứng cử viên có 2 phần tử. Sở dĩ chỉ gọi là “ứng cử viên”, vì
chưa chắc chúng đã là – thường xuyên. Sau khi kiểm tra (dùng định nghĩa), ta lọc ra
được các tập hợp – thường xuyên có 2 phần tử. Ký hiệu tập hợp này là L2.
 Bước 3: Với chủ ý đã nêu (về tính chất tăng dần của các tập hợp – thường xuyên), ta
tiến hành tìm các ứng cử viên có 3 phần tử (lấy từ L1). Gọi nó là tập C3. Lưu ý là nếu
{A, B, C} muốn là “ứng cử viên” thì các tập 2 phần tử {A, B},{B,C},{C, A } đều
phải là – thường xuyên, tức là chúng đều là phần tử của tập L2. Ta đi “kiểm tra tư
cách đại biểu” trong tập C3 và lọc ra được tập các tập hợp – thường xuyên có 3 phần
tử. Tập hợp này được ký hiệu là L3.

end
Dưới đây là toàn bộ Thuật toán Apriori:
Thuật toán 3- Apriori [Agrawal1994]
Input: I, D, 
Output: L
Algorithm:
//Apriori Algorithm prposed by Agrawal R., Srikant, R. [Agrawal1994]
//procedure LargeItemsets
1) C1: = I; // Tập ứng cử viên có 1 phần tử
2) Sinh ra L1 bằng cách tính tần số xuất hiện của mặt hàng trong các giao dịch;
3) for (k=2; Lk-1 ; k++) do begin
//Tạo ra các tập ứng cử viên
// Các tập ứng cử viên có k phần tử được sinh ra từ các tập (k-1)- phần tử xuất hiện –
thường xuyên.
4) Ck = apriori-gen( Lk-1 );
// Tính độ hỗ trợ cho Ck
5) Count (Ck, D)
6) Lk = {c Ck| c.count }
7) end
8) L:= k Lk
Thuật toán Apriori cải tiến cũng giải quyết 2 tình huống “xấu”, đó là khi Ck hoặc Lk-
1 to quá, không chứa đủ trong bộ nhớ tính toán. Khi đó, cần tu chỉnh lại hàm apriori_gen()
một chút.
*Thuật toán Apriori nhị phân:
Thuật toán Apriori nhị phân sử dụng các vector bit cho các thuộc tính, vector nhị phân
n chiều ứng với n giao tác trong cơ sở dữ liệu. Có thể biểu diễn cơ sở dữ liệu bằng một ma
trận nhị phân trong đó dòng thứ I tương ứng với giao tác (bản ghi) ti và cột thứ j tương ứng
với mục (thuộc tính ) ij.
3.4.2. Thuật toán Apriori-TID
Thuật toán Apriori-TID là phần mở rộng theo hướng tiếp cận cơ bản của thuật toán

For all candidates c Ct do
c.count++;
if (C1) then Ck Ck t.TID,Ct 
end
Luật kết hợp= {c Ck | c.count minsup};
end
Answer = k Lk
Sự khác nhau giữa Apriori và AprioriTID là: cơ sở dữ liệu không được sử dụng để
đếm các support sau lần đầu tiên quét qua cơ sở dữ liệu. Vì sau lần quét đầu tiên các 1-
itemset đã được sinh (các L1), các L1 này được dùng để lọc ra các giao dịch của cơ sở dữ liệu
bất kỳ item nào là không phổ biến và những giao dịch trong C
1
chỉ chứa những item không
phổ biến. Kết quả đó được đưa vào C
2
và sử dụng lần quét đó. Vì vậy kích thước của C
2
là
khá nhỏ hơn so với C
1
. Sự giống nhau của hai thuật toán này là đều sử dụng bước cắt tỉa
trong hàm Apriori_gen().
3.4.3. Thuật toán Apriori-Hybrid
Thuật toán Apriori-Hybrid được coi như kết hợp giữa Thuật toán Apriori và thuật
toán Apriori-TID. Trong thuật toán Apriori-Hybrid, được sử dụng khi tổ chức lặp và chuyển
sang Apriori-TID khi đã chắc chắn rằng tập C
k
đã vào bộ nhớ chính. Thuật toán Apriori-
Hybrid được coi là tốt hơn so với Apriori và AprioriTID.
CHƢƠNG 4 – KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU HÌNH ẢNH

4.1.2 Các tham số chính của ảnh số
Kích thước ảnh:
Ta thường nói kích thước ảnh là x pixel và y dòng. Tổng số cột pixel và tổng số pixel
trên hàng. Số lượng pixel có trong bức ảnh sẽ quyết định kích cỡ ảnh, ảnh hưởng đến độ lớn
của các tệp ảnh. Chất lượng của bức ảnh khi được in hay hiển thị trên màn hình phụ thuộc
một phần vào số lượng các pixels tạo nên bức ảnh (đôi khi được gọi là độ phân giải-
resolution). Số lượng các pixels càng nhiều thì các chi tiết càng được hiển thị rõ, mức độ sắc
nét càng tăng đồng nghĩa với việc độ phân giải cũng lớn hơn. Nếu như phóng đại bức ảnh số
đủ lớn thì mắt người sẽ nhận ra được các pixels này.[1]
Tổng số bit biểu diễn từng pixel (pixel depth):
Với ảnh đa mức xám chất lượng chấp nhận được đòi hỏi 8 bit/pixel. Với ảnh màu, cần
24 bít/pixel (mỗi thành phần màu cần 8 bít). Dữ liệu của ảnh được tính như sau:
D= x.y.b
Trong đó: x - tổng số pixel/dòng ảnh
y - tổng số dòng ảnh và b – tổng số bit/pixel.
Thí dụ, ảnh 512 pixel x512 dòng và độ sâu pixel 24 bít, thì kích thước dữ liệu sẽ là:
D=512x512x24 bit = 768 KB.
4.2. Trích chọn đặc trưng trong khai phá ảnh
Trích chọn đặc trưng ảnh là bước tiền xử lý trong khai phá ảnh. Đây là bước quyết
định trong toàn bộ quá trình khai phá ảnh. Phương pháp trích chọn xuất phát từ hình ảnh - rút
ra mẫu và nhận được tri thức từ các hình ảnh sưu tập, giải quyết phần lớn với việc nhận dạng
và trích chọn những đặc trưng duy nhất của phạm vi cụ thể. Có nhiều giá trị dặc trưng khác
nhau, mục đich chính là nhận ra những đặc trưng tốt nhất và từ đó rút ra những thông tin có
liên quan từ ảnh. Trích chọn đặc trưng ảnh rất có giá trị trong kiểm tra ảnh. [9]
Thông thường, hình ảnh có các đặc trưng sau: Màu sắc, kết cấu, hình dạng, cạnh, …
4.2.1. Trích chọn đặc trưng màu sắc
Có một số kỹ thuật trích chọn đặc trưng về màu sắc – Trung bình màu trong tỷ lệ màu
xám, Trung bình màu trong định dạng RBG, và Trung bình màu trong YCBCR (Y là độ sáng
và CB, CR là các thành phần màu . Việc đánh giá các phương pháp khác nhau sử dụng Độ
chính xác (Precision) và Nhớ lại (Recall), và nhận thấy rằng YCBCR thực hiện tốt hơn hai

Edge cùng với đặc trưng về màu sắc mô tả ranh giới và vùng bên trong của Egeria.[9]
Những hình sau đây là kết quả thu được khi kiểm thử một tập các ảnh có màu tối Hình 4.2. Trích chọn đặc trưng Edge
4.2.4. Kết hợp các đặc trưng
Tất cả các đặc trưng được kết hợp thành hình ảnh chiết xuất cuối cùng như hình bên.

Hình 4.3. Kết hợp các đặc trưng
Tất cả các khối có các đại lượng tương tự nhau cho mỗi đặc trưng. Do đó sau khi xử lý
các đặc trưng được trích chọn, mỗi khối cụ thể là một chuỗi 1 (Yes) và 0 (No), chiều dài
tương ứng với số đặc trưng được trích chọn. Việc kết hợp các đặc trưng được trích chọn đồng
nghĩa với việc hình thành các công thức. Một luật (rule) kết hợp ba đặc trưng là
color&edge|textures, có nghĩa là color AND edge OR textures.[9]
Luật thứ nhất và luật thứ ba chỉ ra rằng màu sắc kết hợp với texture hoặc edge đưa đến
kết luận rằng Edgeria là trong khối hiện tại. Luật thứ hai chỉ ra rằng khi không có đặc trưng
nào là 1 thì Egeria chắc chắn vắng mặt. Luật thứ 4 chỉ ra rằng màu sắc không đủ chắc chắn để
chứng minh sự hiện diện của Egeria. Bảng 4.1. Ví dụ minh họa sự kết hợp các đặc trưng
Color
Textures
Edge
Class
1
0
1
1
0
0
0
0

cách sử dụng GLCM (Ma trận Gray Level Cooccurrence). [6]
Ma trận GLCM của một hình ảnh được tính toán bằng cách sử dụng một vector d, xác
định bởi bán kính ä và định hướng è. Tần số thông thường có thể được sử dụng bằng cách
phân chia giá trị trong mỗi ô bằng tổng số các cặp điểm ảnh có thể. Do đó các nhân tố bình
thường cho 0 ° sẽ được (Nx - 1) × Ny với Nx là chiều rộng và Ny là chiều cao của hình ảnh.
Cấp độ lượng tử không kém phần quan trọng trong việc xác định sự xuất hiện đặc trưng
texture. Ngoài ra, sự xuất hiện của ma trân các phần tử lân cận có liên quan chặt chẽ chất
lượng hình ảnh.
Lựa chọn bán kính δ:
Giá trị δ nằm trong khoảng từ 1, 2 đến 10. Áp dụng cho các giá trị khoảng cách lớn
thì ma trận GLCM không nắm bắt được thông tin chi tiết texture. Có thể thấy rằng độ chính
xác phân loại một cách tổng thể với δ =1,2,4,8 là có thể chấp nhận được với kết quả tốt nhất
với δ = 1 và 2. Kết luận này là hợp lý, một điểm ảnh có nhiều tương quan với những điểm
ảnh gần hơn là những điểm ảnh ở vị trí xa.
Lựa chọn góc θ:
Mỗi điểm ảnh đều có tám điểm ảnh lân cận, vì vậy lựa chọn góc θ là: 0
0
, 45
0
, 90
0
,
135
0
, 180
0
, 225
0
, 270
0

ZiZiPm

Cường độ trung bình
Độ lệch chuẩn
σ =
2

=
2


Độ tương phản trung bình
Độ mịn
R=1-1/(1+σ
2
)
Độ mịn liên quan đến mật độ
trong một vùng
Third moment
)()(
3
1
0
3 i
L
i
i
zpmz 



zpzpe





Đại lượng ngẫu nhiên

Bước 3: Chuẩn bị cơ sở dữ liệu giao dịch
Các đặc trưng đã trích chọn được tổ chức trong một cơ sở dữ liệu dưới dạng một giao dịch –
yếu tố cấu thành đầu vào (input) để phát sinh các luật kết hợp. Các giao dịch có dạng [Image
ID, F1;F2;:::;Fn] trong đó F1:::Fn là n đặc trưng đã được trích chọn với hình ảnh cho trước.
Bước 4: Khai phá luật kết hợp
Phát hiện các tập mục thường xuyên là chìa khóa trong việc khai phá luật kết hợp.
Để thực hiện khai phá dữ liệu thuật toán kết hợp, ta mô tả các thuộc tính số trước, có
nghĩa là, các giá trị thuộc tính tiếp theo sẽ phân chia thành nhiều phân đoạn. Các thuật toán
kết hợp truyền thống thong qua một phương pháp lặp để tìm kiếm, điều này yêu cầu lượng
tính toán lớn và quá trình giao dịch phức tạp. Bời vì lý do này, một thuật toán kết hợp mới
được đề xuất. Thuật toán mới thông qua một phương pháo vecto để tìm kiếm các tập mục
thường xuyên.[6]
Nói chung, thuật toán mới bao gồm 4 pha:
- Biến đổi cơ sở dữ liệu giao dịch thành ma trận Boolean.
- Tạo ra một tập mục thường xuyên L1
- Cắt tỉa ma trận Boolean
- Tạo ra các tập mục thường xuyên k.
Mô tả thuật toán chi tiết qua các bước như sau:
1. Biến đổi cơ sở dữ liệu vào ma trận Boolean
2. Tạo ra một tập mục thường xuyên L1
3. Cắt tỉa ma trận Boolean
4. Tạo ra k- tập mục thường xuyên k Lk

3. Trần Hoài Nam, Cơ sở dữ liệu đa phương tiện yêu cầu và các vấn đề, Luận văn thạc
sỹ, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội, 2004.
4. Lê Huy Thập, Khai phá dữ liệu, Bài giảng cho cao học, Hà Nội 2012.S
Tiếng Anh
5. Carlos Ordonez and Edward Omiecinski, Image Mining: A New Approach for Data
Mining, Georgia Institute of Technology, 1998.
6. David Hand, Heikki Mannila and Padhraic Smyth, Principles of Data Mining, The
MIT Press, 2001.
7. Deepa S. Deshpande, Association Rule Mining Based on Image Content, International
Journal of Information Technology and Knowledge Management, 2011.
8. Guojun Lu, Multimedia Database Management Systems, Artech House, Inc. 1999.
9. Jelena Tesic, Shawn Newsam and B.S. Manjunath, Mining Image Datasets using
Perceptual Asociation Rules, Electrical and Computer Engineering Department
University of California, Santa Barbara, CA 93106-9560.
10. Patricia G. Foschi, Feature Extraction for Image mining, Romberg Tiburon Center for
Enviromental Studies, San Francisco State University
11. Petra Perner, Data Mining on Multimedia Data, Lecture Notes in Computer Science,
Springer-Verlag Berlin Heidelberg 2002.