TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HỒ CHÍ MINH
KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH






ĐỀ CƯƠNG LUẬN VĂN TỐT NGHIỆP





ĐỀ TÀI
TÌM KIẾM HÌNH DẠNG BẤT THƯỜNG
TRONG TẬP CƠ SỞ DỮ LIỆU HÌNH ẢNH LỚN











Hướng dẫn : PGS. Dương Tuấn Anh
TS. Nguyễn Thanh Bình
Thực hiện : Nguyễn Thị Thiên Thanh

Mã số HV : 00707183




– 2010 –
MỤC LỤC

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI 1
1.1 . Tìm kiếm hình dạng bất thường: 1
1.2 . Dữ liệu chuỗi thời gian: 2
1.3. Mục tiêu và phạm vi: 2
1.4. Cấu trúc đề cương luận văn: 3

CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN 4
2.1. Các phương pháp tìm biên ảnh: 4
Một số phương pháp phát hiện biên trực tiếp: 5
Phương pháp Gradient 5
Phương pháp Laplace 7
2.2. Các phương pháp biểu diễn hình dạng: 8
2.3. Độ đo khoảng cách: 11
2.4. Các phương pháp xấp xỉ tuyến tính từng đoạn: 15
2.5. Các phương pháp rời rạc hóa: 17
2.6. Thuật toán tìm kiếm sự bất thường của hình dạng: 19

CHƯƠNG 3: HỆ THỐNG TÌM KIẾM HÌNH DẠNG BẤT ĐỒNG BỘ 22
3.1. Đặt vấn đề: 22
3.2. Hướng giải quyết: 22
3.3. Kiến trúc hệ thống: 23
3.4. Chuyển đổi dữ liệu hình ảnh sang dữ liệu chuỗi thời gian: 24

3.5. Cách đánh giá độ đo khoảng cách: 25
3.6. Bảng băm tìm kiếm (Locality-Sensitive Hashing): 25
3.7. Giải thuật tìm kiếm: 27

CHƯƠNG 4: NỘI DUNG NGHIÊN CỨU 30
4.1. Tổng kết: 30
4.2. Phương pháp đánh giá: 30
4.3. Các công việc chính cần thực hiện: 31
4.4. Mục tiêu kết quả cần đạt được: 31

KẾ HOẠCH LÀM VIỆC 32

TÀI LIỆU THAM KHẢO 33

DANH MỤC HÌNH

Hình 1.1: Một mẫu từ một bộ dữ liệu của 1.301 hình ảnh của các sinh vật biển và bất
thường thứ nhất được tìm thấy trong dữ liệu này là một con sao biển (nguồn [1]) 1
Hình 1.2: Một tập con của 32.028 hình ảnh của cánh ruồi giấm và những bất thường đầu
tiên được tìm thấy trong dữ liệu này là một cánh bị hư hỏng (nguồn [1]) 2
Hình 2.1: Các phương pháp biểu diễn hình dạng (nguồn [5]) 8
Hình 2.2: Hàm số theo góc tích lũy (nguồn [2]) 9
Hình 2.3: Biểu diễn chuỗi dữ liệu thời gian theo công thức diện tích (nguồn [2]) 10
Hình 2.4: Biểu diễn chuỗi dữ liệu thời gian theo vùng tam giác (nguồn [2]) 11
Hình 2.5: Tính khoảng cách theo Euclid (nguồn [3]) 12
Hình 2.6: Tính khoảng cách theo DTW (nguồn [3]) 13
Hình 2.7: Minh họa cách tính khoảng cách theo DWT 14
Hình 2.8: Minh họa phương pháp mã hóa SAX 18
Hình 2.9: Một ví dụ của thuật toán brute force (nguồn [1]) 20
Hình 2.10: Một ví dụ của việc áp dụng từ bỏ sớm cho thuật toán brute force (nguồn [1])

21
Hình 3.1: Kiến trúc hệ thống 24
Hình 3.2: Từ SAX khác nhau do hình dạng bị quay (nguồn [1]) 26
Hình 3.3: Bảng băm sử dụng LSH (nguồn [1]) 27
Hình 3.4: Mô tả quá trình ước tính độ tương tự (nguồn [1]) 28

DANH MỤC BẢNG
Bảng 2.1: Bảng kết quả so sánh các phương pháp biểu diễn hình dạng (nguồn [2]) 11
Bảng 2.2: Tìm kiếm sự bất thường bằng giải thuật Brute Force 19
Bảng 2.3: Giải thuật Brute Force cải tiến 21
Bảng 3.1: Giải thuật ước tính thứ tự tối ưu 28


Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 1
CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
1.1 . Tìm kiếm hình dạng bất thường:
Cơ sở dữ liệu hình ảnh lớn được sử dụng ngày càng tăng trong các ứng dụng thuộc các
lĩnh vực như giải trí, kinh doanh, nghệ thuật, kỹ thuật, và khoa học (Tanaka và Uehara,
2004). Trong số các thuộc tính của hình ảnh (ví dụ như hình dạng, màu sắc, và kết cấu), hình
dạng đặc biệt quan trọng vì con người thường có thể nhận ra các đối tượng dựa trên cơ sở
hình dạng (Zhang và Lu, 2004). Vì vậy, việc phân tích hình dạng đã được chú trọng nghiên
cứu rất nhiều trong ba thập kỷ qua. Hầu hết các nghiên cứu tập trung vào việc lập chỉ mục,
gom cụm, và phân loại.
Luận văn này sẽ nghiên cứu và đề xuất phương pháp tìm kiếm các hình dạng ít tương tự
nhất đối với tất cả các hình dạng khác trong một tập dữ liệu. Hình dạng này được gọi là bất
thường (discord). Hình 1.1 biểu diễn trực quan một hình dạng bất thường được tìm thấy
trong một bộ dữ liệu hình ảnh của 1.301 loài sinh vật biển. Trong khi hầu hết các sinh vật
được đại diện một số lần trong tập dữ liệu, sao biển chỉ xuất hiện một lần, và do đó nó được

xem như là hình dạng khác thường.

Hình 1.1: Một mẫu từ một bộ dữ liệu của 1.301 hình ảnh của các sinh vật biển và bất thường thứ
nhất được tìm thấy trong dữ liệu này là một con sao biển (nguồn [1])

Một ví dụ trong khai thác dữ liệu y khoa: Ruồi giấm là một trong những sinh vật nghiên
cứu nhiều nhất trong sinh học, đặc biệt là trong di truyền học. Hình 1.2 cho thấy một tập hợp
các hình ảnh cánh của ruồi giấm được thu thập cho một thí nghiệm đột biến được thực hiện
tại Florida State University (nhóm Zimmerman, 2000.) và sự bất thường.
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 2

Hình 1.2: Một tập con của 32.028 hình ảnh của cánh ruồi giấm và những bất thường đầu tiên được
tìm thấy trong dữ liệu này là một cánh bị hư hỏng (nguồn [1])
1.2 . Dữ liệu chuỗi thời gian:
Dữ liệu có yếu tố thời gian là sự quan sát tuần tự theo thời gian. Dữ liệu này có thể là 2
chiều hay nhiều chiều nhưng phải có 1 chiều là thời gian. Có rất nhiều loại dữ liệu khác nhau
có yếu tố thời gian và thông thường đây là những dữ liệu rất lớn (very large database). Theo
khảo sát từ 4000 hình ngẫu nhiên trên các tờ báo xuất bản giai đoạn 1974 – 1989 thì 75% là
các hình biểu diễn dữ liệu chuỗi thời gian. Đặt biệt, trong thời đại hiện nay, thông tin là rất
quan trọng. Tuy nhiên, dữ liệu thì quá lớn nên cần phải sử dụng công cụ máy tính để tìm
được những thông tin từ nguồn dữ liệu đó. Chính vì vậy những nghiên cứu và ứng dụng dữ
liệu chuỗi thời gian là những lĩnh vực rất rộng lớn và cần thiết của khoa học máy tính và các
ngành khoa học khác.
Trong phạm vi nghiên cứu của đề tài này, ta quan tâm đến dữ liệu chuỗi thời gian được
biểu diễn bằng một chuỗi các số thực X =
1 2

n

x x x
. Trong đó
i
x
là giá trị đo ở thời điểm thứ
i.
1.3. Mục tiêu và phạm vi:
Mục tiêu của luận văn là sẽ nghiên cứu và đề xuất phương pháp tìm kiếm các hình dạng
bất thường trong một tập dữ liệu lớn. Khi đó hệ thống cho phép người dùng đưa vào một tập
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 3
hình ảnh bitmap. Hệ thống sẽ tự động trích xuất hình dạng của các hình ảnh này và cho phép
người sử dụng đưa các hình dạng này vào cơ sở dữ liệu. Kết quả trả về là những hình dạng
được cho là bất thường so với tập hình dạng trong cơ sở dữ liệu đó.
Đề tài sẽ sử dụng đường biên của hình dạng như là thuộc tính để mô tả hình dạng. Hệ
thống sẽ phải xử lý dữ liệu đầu vào là tập hình ảnh. Giới hạn của đề tài là sẽ không nghiên
cứu nhiều đến việc nhiễu trong trích xuất đường biên và hình dạng quá đặc biệt như bị khuyết
lỗ hoàn toàn ở bên trong hình dạng.
1.4. Cấu trúc đề cương luận văn:
Tổ chức của các phần còn lại của luận văn theo cấu trúc sau đây:
Chương 2 sẽ giới thiệu một số lý thuyết nền tảng và các nghiên cứu liên quan mà chúng ta
sẽ sử dụng trong luận văn. Trước hết đó là các phương pháp xử lý ảnh, biểu diễn hình dạng sẽ
được sử dụng để tiền xử lý và đưa dữ liệu thô vào cơ sở dữ liệu. Sau đó là định nghĩa và cách
tính độ đo khoảng cách hay còn gọi là độ đo tương tự. Cuối cùng là một số lý thuyết về việc
ký hiệu hóa chuỗi dữ liệu thời gian.
Chương 3 trình bày về hệ thống tìm kiếm hình dạng bất thường trong tập dữ liệu lớn. Đầu
tiên là đặt vấn đề và hướng giải quyết. Cấu trúc của hệ thống được mô tả bằng biểu đồ khối
và cách giải quyết từng khối sẽ được nêu chi tiết ngay sau đó. Cuối cùng là trình bày cụ thể
các phương pháp, thuật toán chính được lựa chọn áp dụng vào hệ thống.

Chương 4 trình bày việc tổng kết lại các vấn đề và nội dung đã nghiên cứu trong giai
đoạn thực hiện đề cương và đề xuất phương pháp đánh giá thực nghiệm trong giai đoạn thực
hiện luận văn. Từ những điều đó, chúng ta có thể đưa ra danh sách những công việc cần thực
hiện và mục tiêu kết quả cần đạt được trong giai đoạn luận văn sắp tới.
Cuối cùng là bảng phân bố thời gian thực hiện và mục lục.
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 4
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC
CÔNG TRÌNH LIÊN QUAN
Trong đề tài này để giải quyết bài toán tìm kiếm hình dạng bất thường trong một tập cơ sở
dữ liệu lớn chúng ta cần sử dụng một số vấn đề lý thuyết và các công trình liên quan. Chương
này sẽ trình bày những điểm cơ bản của các lý thuyết và công trình liên quan đó.\
Trước hết, trong giai đoạn tiền xử lý chúng ta cần phải sử dụng biên ảnh như là thuộc tính
duy nhất biểu diễn một hình dạng. Vì vậy vấn đề cần được quan tâm trước tiên là tìm biên
ảnh của hình dạng. Có nhiều phương pháp tìm biên ảnh. Nội dung và điểm yếu, điểm lợi của
các phương pháp này sẽ được trình bày ở phần 2.1.



2.1. Các phương pháp tìm biên ảnh:
Biên là vấn đề quan trọng trong việc trích chọn đặc điểm nhằm tiến tới việc nhận dạng
ảnh (nguồn [18]). Cho đến nay chưa có định nghĩa chính xác về biên, trong mỗi ứng dụng
người ta đưa ra các độ đo khác nhau về biên, một trong các độ đo đó là độ đo về sự thay đổi
đột ngột về cấp xám. Ví dụ: Đối với ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là
điểm đen có ít nhất một điểm trắng bên cạnh. Tập hợp các điểm biên tạo nên biên hay đường
bao của đối tượng. Xuất phát từ cơ sở này người ta thường sử dụng hai phương pháp phát
hiện biên cơ bản:
Phát hiện biên trực tiếp: Phương pháp này làm nổi biên dựa vào sự biến thiên mức xám
của ảnh. Kỹ thuật chủ yếu dùng để phát hiện biên ở đây là dựa vào sự biến đổi cấp xám theo

hướng. Cách tiếp cận theo đạo hàm bậc nhất của ảnh dựa trên kỹ thuật Gradient, nếu lấy đạo
hàm bậc hai của ảnh ta có kỹ thuật Laplace.
Kỹ thuật phát hiện biên Gradient: Theo định nghĩa gradient là một véctơ có các thành
phần biểu thị tốc độ thay đổi giá trị của điểm ảnh.
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 5
Kỹ thuật phát hiện biên Laplace: Các phương pháp đánh giá gradient ở trên làm việc khá
tốt khi mà độ sáng thay đổi rõ nét. Khi mức xám thay đổi chậm, miền chuyển tiếp trãi rộng,
phương pháp cho hiệu quả hơn đó là phương pháp sử dụng đạo hàm bậc hai Laplace.
Phát hiện biên gián tiếp: Nếu bằng cách nào đó ta phân được ảnh thành các vùng thì
ranh giới giữa các vùng đó gọi là biên. Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối
ngẫu nhau vì dò biên để thực hiện phân lớp đối tượng. Khi chúng ta phân lớp xong nghĩa là
chúng ta đã phân vùng được ảnh và ngược lại, khi đã phân vùng được ảnh tức là ảnh đã được
phân lớp, do đó có thể phát hiện được biên.
Phương pháp phát hiện biên trực tiếp tỏ ra khá hiệu quả và ít chịu ảnh hưởng của nhiễu,
song nếu sự biến thiên độ sáng không đột ngột, phương pháp tỏ ra kém hiệu quả. Phương
pháp phát hiện biên gián tiếp tuy khó cài đặt, song lại áp dụng khá tốt trong trường hợp này.
Một số phương pháp phát hiện biên trực tiếp:
Phương pháp Gradient
Phương pháp Gradient (nguồn [18], không rõ tác giả) là phương pháp dò biên cục bộ
dựa vào cực đại của đạo hàm. Theo định nghĩa, gradient là một véctơ có các thành phần biểu
thị tốc độ thay đổi giá trị của điểm ảnh theo hai hướng x và y . các thành phần của gradient
được tính bởi:
df(x,y) f(x+dx,y) – f(x,y)
dx
= fx 
dx

df(x,y) f(x,y+dy) – f(x,y)

dy
= fy 
dy
với dx là khoảng cách giữa các điểm theo hướng x ( khoảng cách tính bằng số điểm) và tương
tự với dy. Trong thực tế ta thường cho dx = dy = 1
Trong phương pháp Gradient, người ta chia thành 2 kỹ thuật (do dùng 2 toán tử khác
nhau): kỹ thuật Gradient và kỹ thuật la bàn. Kỹ thuật Gradient dùng toán tử Gradient lấy đạo
hàm theo hai hướng; còn kỹ thuật la bàn lấy đạo hàm theo 8 hướng chính: Bắc, Nam, Đông ,
Tây và Đông Bắc, Tây Bắc, Đông Nam, Tây Nam.
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 6
Kỹ thuật Gradient: Kỹ thuật này (nguồn [18] , không rõ tác giả) sử dụng một cặp mặt
nạ H
1
và H
2
trực giao ( theo 2 hướng vuông góc). Nếu định nghĩa g
1
,g
2
là gradient tương ứng
theo 2 hướng x và y, thì biên độ của gradient, ký hiệu là g tại điểm (m,n) được tính theo công
thức:
A
0
= g(m,n) =  g²
1
(m,n) +


g
2
2
(m,n)

(2.1)

r
(m,n) = tan
-1
g
2
(m,n)/ g
1
(m,n) (2.2)
Chú ý: để giảm tính toán, công thức 2.2 được tính gần đúng bởi:
A
0
= | g
1
(m,n) | + | g
2
(m,n) |
Các toán tử đạo hàm được áp dụng là khá nhiều. Ở đây ta chỉ xét một số toán tử tiêu
biểu: toán tử Robert, Sobel, Prewitt…
Mặt nạ Robert: Đây là toán tử do Robert đề xuất vào năm 1965. Nó áp dụng trực tiếp
của các công thức đạo hàm tại điểm (x,y). với mỗi điểm ảnh I(x,y) của I, đạo hàm theo x,
theo y được ký hiệu tương ứng bởi g
x
, g

y
được tính:
g
x
= I(x +1,y) – I(x,y)
g
y
=I(x,y+1) – I(x,y)
điều này tương đương với việc chập ảnh với 2 mặt nạ H
1
và H
2
:
0 1 -1 0
H
1
=

-1 0
H
2
=

0 -1
Ta gọi H
1
, H
2
là mặt nạ Robert.
Cần lưu ý rằng, tuy ta nói rằng lấy đạo hàm của ảnh nhưng thực ra chỉ là mô phỏng và

xấp xỉ đạo hàm bằng kỹ thuật nhân chập do ảnh số là tín hiệu rời rạc.
Mặt nạ Sobel: được Duda và Hart đề xuất năm 1973 (nguồn [18])
-1 0 1 1 2 1
-2 0 2 0 0 0 H1 =
-1 0 1
H2 =
-1 - 2 -1
Ngang (hướng x) Dọc(hướng y)
Mặt nạ Prewitt: được prewitt đề xuất năm 1973 (nguồn [18])
H
1
=
-1 0 1
H
2
=
-1 -
2
-1
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 7
-
2
0
2

0 0 0
-1 0 1
1 2 1

Ngang (hướng x) Dọc(hướng y)
Mặt nạ đẳng hướng (Isometric): không rõ tác giả (nguồn [18])
Gradient được tính xấp xỉ công thức
Gx=Hx

I và Gy=Hy

I (Hx nhân chập với I, Hy nhân chập với I)
Kỹ thuật La bàn: Kỹ thuật này tương tự kỹ thuật Gradient. Toán tử la bàn dựa trên sự đánh
giá tất cả các hướng có thể của một đường biên ảnh trong một ảnh rời rạc. Vì vậy thay vì chỉ
áp dụng hai mặt nạ như các toán tử trong kỹ thuật Gradient ở trên, tám mặt nạ đã được dùng,
mỗi cái
cung cấp một cạnh đường biên dọc theo một trong tám hướng có thể của vòng.
Như vậy, mỗi điểm ảnh đầu ra là giá trị lớn nhất trong tám kết quả nhân xoắn của mặt nạ với
ma trận ảnh. Sau mỗi lần nhân xoắn, ta quay mặt nạ này đi một góc
0
45
ngược chiều kim
đồng hồ :
0
0
,
0
45
,
0
90
,
0
135

,
0
180
,
0
225
,
0
270
,
0
315
.
Phương pháp Laplace
Các phương pháp đánh giá gradient ở trên làm việc khá tốt khi mà độ sáng thay đổi rõ
nét. Khi mức sáng thay đổi chậm, miền chuyển tiếp trải rộng, phương pháp cho hiệu quả hơn
đó là sử dụng phương pháp đạo hàm bậc hai gọi là phương pháp Laplace (không rõ tác giả,
nguồn [18]). Kết quả nghiên cứu cho thấy phương pháp gradient rất nhạy cảm với nhiễu và
thường tạo nên biên kép. Toán tử Laplace dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ đạo
hàm bậc hai. Dưới đây là 3 kiểu mặt nạ hay dùng.
0 -1 0 -1 -1 -1 1 -2 1
H1= -1 4 -1 H2= -1 8 -1 H2= -2 8 -2
0 -1 0 -1 -1 -1 1 -2 1

Kỹ thuật Laplace cho đường biên mảnh, tức là đường biên có độ rộng bằng một pixel.
Tuy nhiên, kỹ thuật này rất nhạy cảm với nhiễu vì đạo hàm bậc hai thường không ổn định.
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 8
2.2. Các phương pháp biểu diễn hình dạng:

Có hai phương pháp tiếp cận trong việc mô tả và biểu diễn hình dạng (nguồn [5]): dựa
trên đường biên (boundary-based method) và dựa trên vùng (region-based method). Trong
mỗi lớp, các phương pháp có thể được chia thành phương pháp biểu diễn hình dạng dưới
dạng cấu trúc (structural) hoặc tổng thể (global).

Hình 2.1: Các phương pháp biểu diễn hình dạng (nguồn [5])

Trong các phương pháp trên, chỉ có các phương pháp thuộc nhánh dựa trên đường biên và
theo hướng tổng thể là có thể biểu diễn thành dữ liệu chuỗi thời gian. Ta gọi chung tên của
nhóm này là nhóm chữ ký (signature). Nhóm này bao gồm các phương pháp biểu diễn sau:
Kết hợp tọa độ (Complex coordinates): (nguồn [2])
Hàm số kết hợp tọa độ chỉ đơn giản là kết quả được tính từ việc kế hợp tọa độ theo trục x
và trục y của tất cả các điểm biên P theo công thức sau:
(2.3)
Trong đó g là trọng tâm của hình dạng, được tính theo công thức sau:
(2.4)
Khoảng cách trung tâm (Central distance): (nguồn [5])
Hàm số khoảng cách trung tâm là khoảng cách từ các điểm biên đến trọng tâm. Công thức
tính như sau:
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 9
(2.5)
Chiều dài dây cung (ChordLength): (nguồn [5])
Đối với mỗi điểm biên p, hàm số chiều dài cung của điểm đó là khoảng cách ngắn nhất
giữa p và một điểm p' cũng thuộc biên sao cho pp’ vuông góc với vector tiếp tuyến tại p. Điều
này cho thấy phương pháp này không phụ thuộc vào một điểm tham chiếu khác đó là trọng
tâm. Trọng tâm thường bị lệch nếu hình dạng bị nhiễu hoặc che khuất. Tuy nhiên, phương
pháp này rất nhạy cảm với nhiễu.
Hàm số theo góc tích lũy (Cumulative angular function): (nguồn [5])

Góc

(t) là góc tạo bởi 2 tiếp tuyến tại điểm biên z(t) và tiếp tuyến tại điểm biên gốc là
z(0) được tính bằng công thức:

(t) = [

(t) -

(0)]mod(2

)

Hình 2.2: Hàm số theo góc tích lũy (nguồn [2])
Gọi L là chu vi của đường biên của đường cong. Hàm số để tính toán dữ liệu chuỗi thời
gian theo phương pháp này như sau:
t
Lt
t  )
2
()(


(2.6)
Công thức độ cong (Curvature function): (nguồn [2])
Chọn một giá trị w hợp lý là bước nhảy trong việc lựa chọn điểm ảnh tiếp theo.

(t) là góc hợp bởi đường thẳng nối 2 điểm biên t và t+w với trục ngang.

(t) được tính

theo công thức sau:
)()(
)()(
arctan)(
wtxtx
wtyty
t





(2.7)
Hàm số để tính toán dữ liệu chuỗi thời gian theo phương pháp này như sau:
K(t) =

(t) -

(t-1) (2.8)
Công thức trên biểu diễn độ lệch của góc

theo thời gian, độ lệch K(t) càng nhỏ thì
đường cong tại điểm t được xem là càng trơn.
Công thức độ diện tích (Area function):
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 10
Hàm số để tính toán dữ liệu chuỗi thời gian theo phương pháp này được tính bằng diện
tích của tam giác được tạo bởi điểm biên thứ n, điểm biên thứ n+1 và trọng tâm, theo công
thức sau:

|)()()()(|
2
1
)(
1221
tytxtytxtA  (2.9)

Hình 2.3: Biểu diễn chuỗi dữ liệu thời gian theo công thức diện tích (nguồn [2])

Biểu diễn vùng tam giác (Triangle-area representation): (nguồn [2])
Các giá trị diện tích vùng tam giác (TAR) được tính bằng diện tích đại số của hình tam
giác được hình thành bởi 3 điểm trên ranh giới hình là

(2.10)
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 11

Hình 2.4: Biểu diễn chuỗi dữ liệu thời gian theo vùng tam giác (nguồn [2])

Phương pháp biểu diễn hình dạng bằng đường biên thực thi đơn giản hơn và phổ biến hơn
phương pháp biểu diễn hình dạng bằng vùng. Dưới đây là bảng kết quả so sánh (từ nguồn [2])
của các phương pháp trên:
Bảng 2.1: Bảng kết quả so sánh các phương pháp biểu diễn hình dạng (nguồn [2])

Các giá trị diện tích vùng tam giác (TAR) được tính bằng diện tích đại số của hình tam
giác được hình thành bởi 3 điểm trên ranh giới hình là
2.3. Độ đo khoảng cách:
Đã có nhiều độ đo khoảng cách đã được sử dụng. Việc chọn một độ đo khoảng cách là
tùy thuộc rất nhiều vào miền ứng dụng và trong nhiều trường hợp thì một độ đo thuộc chuẩn

Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 12
Lp đơn giản như độ đo Euclid là đủ tốt để dùng. Tuy nhiên trong nhiều trường hợp thì độ đo
Euclid tỏ ra quá cứng nhắc vì không thích nghi được với những phép biến đổi như tịnh tiến
(shifting), co giãn biên độ (scaling) hay xoắn trục thời gian (time warping). Nhiều phương
pháp tìm kiếm khoảng cách mới hơn dựa vào những độ đo khoảng cách mềm dẻo và vững
chắc hơn như độ đo xoắn thời gian động, chuỗi con chung dài nhất.
2.3.1. Độ đo Euclid
Cho hai chuỗi thời gian Q =
1

n
q q
và C =
1
n
c c
. Độ đo khoảng cách Euclid giữa hai
chuỗi thời gian này được cho bởi công thức.
(2.11)

Hình 2.5: Tính khoảng cách theo Euclid (nguồn [3])
Độ đo khoảng cách Euclid có ưu điểm là dễ hiểu, dễ tính toán, dễ mở rộng cho nhiều bài
toán khai phá dữ liệu chuỗi thời gian khác như gom cụm, phân lớp, nhận dạng mô típ, v.v
Nhưng độ đo khoảng cách này có nhược điểm là nhạy cảm với nhiễu, và không thích hợp khi
dữ liệu có đường căn bản khác nhau hay có biên độ dao động khác nhau.
Để khắc phục những nhược điểm trên, nhiều phương pháp khắc phục đã đươc đề nghị:
 Phương pháp chuẩn hóa dữ liệu chuỗi thời gian trước khi áp dụng các giải thuật so
trùng mẫu dựa trên giá trị trung bình và độ lệch chuẩn [6] . Trong đó, biến đổi dữ

liệu Q thành dữ liệu Q’ có cùng đường căn bản theo công thức sau:
o Q’ = Q – mean(Q)
o Với mean(Q) là giá trị trung bình của Q
 Để các dữ liệu có cùng biên độ dao động thì ta dùng phép biến đổi sau:
o Q’ = (Q- mean(Q)) / var(Q)
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 13
o Với mean(Q) là giá trị trung bình của Q và var(Q) là độ chệch chuẩn của
Q.
 Phương pháp trung bình di chuyển (moving average) [7] để làm trơn các đường
biểu diễn dữ liệu chuỗi thời gian. Với phương pháp này thì Q được biến đổi thành
Q’ - trong đó điểm ở vị trí i bằng trung bình cộng giá trị tại điểm i và k điểm lân
cận. Ví dụ trong trường hợp k=3 thì

'
1 1
( ) / 3
i i i i
x x x x
 
  

2.3.2. Độ đo xoắn thời gian động:
Việc so trùng 2 đường biểu diễn dữ liệu bằng cách tính khoảng cách từng cặp điểm 1-1
(điểm thứ i của đường thứ I so với điểm thứ i của đường thứ II) là không phù hợp trong
trường hợp hai đường này không hoàn toàn giống nhau nhưng hình dạng biến đổi rất giống
nhau. Như trong hình 2.5, hai đường biểu diễn rất giống nhau về hình dạng nhưng lệch nhau
về thời gian. Trong trường hợp này, nếu tính khoảng cách bằng cách ánh xạ 1-1 giữa 2 đường
thì kết quả rất khác nhau và có thể dẫn đến kết quả cuối cùng không giống như mong muốn.

Vì vậy để khắc phục nhược điểm này, thì một điểm có thể ánh xạ với nhiều điểm và ánh
xạ này không thẳng hàng. Phương pháp này gọi là xoắn thời gian động (Dynamic Time
Warping - DTW) được đề xuất bởi Bernt và Clifford, 1994.

Hình 2.6: Tính khoảng cách theo DTW (nguồn [3])
Dữ liệu vào của phương pháp DTW là 2 đường dữ liệu chuỗi thời gian và thông số w –
khung cửa sổ xoắn (warping window) ràng buộc 2 điểm i và j có thể ánh xạ nhau nếu |i–j|≤w.
Dữ liệu ra là tổng khoảng cách của các điểm được ánh xạ với nhau.
Cách tính DWT:
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 14
Cách đơn giản nhất để tính DWT của 2 đường X và Y là ta xây dựng ma trận Dm x n với m
= |X| và n= |Y|. Khi đó, Dij = d(xi , yj ). ( Hình 2.6)
Sau khi xây dựng ma trận D , ta tìm đường đi từ ô (0,0) đến ô (m,n) thỏa mãn những ràng
buộc sau:
 Không được đi qua trái hay đi xuống
 Đường đi phải liên tục
 Ô (i,j) thuộc đường đi phải thỏa |i - j| <= w
Giả sử có K ô đi từ ô (0,0) đến ô (m,n) thỏa mãn những điều kiện trên, khi đó
(2.12)
Tuy nhiên, ta có thể dùng quy hoạch động để giải quyết bài toán này. Trong đó, công thức
truy hồi để tính
D(i,j):

(2.13)

Hình 2.7: Minh họa cách tính khoảng cách theo DWT
Ưu điểm:
 Phương pháp DWT thì hiểu quả hơn rất nhiều so với phương pháp tính khoảng

cách theo Euclid. Đặt biệt trong các bài toán phân loại (classfication), gom cụm
(clustering) hay trong các các ứng dụng nhận dạng giọng nói….
 Phương pháp DWT cho phép nhận dạng những mẫu có hình dạng giống nhau
nhưng chiều dài hình dạng về mặt thời gian có thể khác nhau.
Nhược điểm:
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 15
 Nhược điểm lớn nhất của DTW là thời gian chạy rất lâu, gấp hàng trăm đến hàng
nghìn lần. Ban đầu đưa ra giải thuật DTW thì w = n (n là chiều dài của dữ liệu).
Khi đó, độ phức tạp là O(n2). Do đó, ta đưa ra thông số cửa sổ xoắn w (w < n) để
giảm độ phức tạp là O(wn).
Những cải tiến để phươmg pháp DTW hiệu quả hơn:
 Dùng phép ánh xạ để chuyển cách biểu diễn ban đầu sang cách biểu diễn khác
bằng cách nén dữ liệu và giảm tần số lấy mẫu. Khi đó việc tính toán theo TW
nhanh hơn.
 Trong phương pháp DTW trình bày ở trên ta dùng thông số w để giới hạn miền
tìm kiếm. Cải tiến này gọi là cận dưới (lower bound). Miền tìm kiếm này có thể
giới hạn bởi 2 đường thẳng song song như trên hoặc có thể có hình dạng khác (tùy
theo từng hợp cụ thể).
2.3.3. Một số định nghĩa liên quan:
Khoảng cách giữa hai hình dạng: Dist biễu diễn giá trị khoảng cách không âm giữa 2
chuỗi dữ liệu thời gian Q và C (cùng độ dài n), Dist(Q, C) = Dist(C, Q).
Hình dạng bất thường: Với một tập các hình dạng S, hình D là hình bất thường của S
nếu D có khoảng cách lớn nhất đến hình dạng tương tự nhất của nó. Điều đó có nghĩa là, tất
cả các hình dạng C trong S, hình dạng tương ứng gần nhất MC của C và hình dạng tương ứng
gần nhất MD của D, Dist(D, MD)> Dist(C, MC).
Hình dạng bất thường thứ k: Với một tập các hình dạng S, hình D là hình dạng bất hòa
thứ k của S nếu D có khoảng cách lớn nhất thứ k so với hình dạng tương ứng gần nhất của nó.
2.4. Các phương pháp xấp xỉ tuyến tính từng đoạn:

2.4.1. Phương pháp xấp xỉ tuyến tính từng đoạn ( PLA):
Phương pháp xấp xỉ tuyến tính từng đoạn (piecewise linear approximation) do E. Keogh
và cộng sự đề nghị ([11],[12]). Trong phương pháp này ta sẽ biểu diễn dữ liệu ban đầu bằng
chuỗi các đoạn thẳng tuyến tính. Mỗi đoạn thẳng tuyến tính nối cặp điểm ở hai đầu đoạn
thẳng xấp xỉ tốt nhất (best-fit) những điểm có trong phân đoạn chuỗi thời gian đó. Các đoạn
thẳng này có thể rời nhau hoặc liên tục. Cách biểu diễn này rất trực quan và nó phù hợp để
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 16
nén tất cả các loại dữ liệu chuỗi thời gian. Hơn nữa, việc tìm các chuỗi đoạn thẳng này có thể
được thực hiện trong thời gian tuyến tính.
2.4.2. Phương pháp xấp xỉ gộp từng đoạn (PAA):
Phương pháp xấp xỉ gộp từng đoạn (piecewise aggregate approximation) do E. Keogh và
cộng sự đề nghị năm 2001([13]). Phương pháp này rất đơn giản, ta tuần tự xấp xỉ k giá trị liền
kề nhau thành cùng một giá trị bằng trung bình cộng của k điểm đó. Qúa trình cứ tiếp tục như
vây từ trái sang phải. Kết quả cuối cùng là đường thẳng có dạng bậc thang.
Với phương pháp này, thời gian tính toán rất nhanh và cách biểu diễn của nó hỗ trợ nhiều
hàm tính khoảng cách.
2.4.3. Phương pháp xấp xỉ hằng số từng đoạn thích nghi:
Phương pháp xấp xỉ hằng số từng đoạn thích nghi do
E.Keogh
và cộng sự đề nghị [9].
Phương pháp
APCA
giống như phương pháp
PAA
là xấp xỉ dữ liệu ban đầu thành những đoạn
thẳng nằm ngang. Tuy nhiên, nó khác với
PAA
là các đoạn này có kích thước bằng nhau, còn

APCA
thì kích thước của các đoạn nằm ngang là khác nhau. Tuy nhiên phương pháp này rất ít
được sử dụng.
2.4.4. Phương pháp điểm PIP:
Năm 2001, Chung, Fu và các cộng sự ([9]) đã đưa ra kỹ thuật thu giảm số chiều dựa vào
các điểm PIP (perceptually important points). Giải thuật xác định các điểm PIP như sau: Với
một chuỗi thời gian T đã được chuẩn hóa, hai điểm PIP đầu tiên được chọn là điểm đầu tiên
và điểm cuối cùng của chuỗi T. Điểm PIP thứ ba được chọn là điểm trong T có khoảng cách
lớn nhất so với hai điểm PIP đầu tiên. Điểm PIP thứ tư được chọn là điểm trong T có khoảng
cách lớn nhất so với hai điểm PIP kế cận đã chọn (có thể là điểm đầu và điểm thứ ba hoặc
điểm thứ ba và điểm cuối). Tiến trình xác định các điểm PIP tiếp tục cho đến khi số điểm PIP
đạt được số điểm yêu cầu. Khoảng cách giữa một điểm trong T với 2 điểm PIP kếcận đã chọn
là đoạn thẳng đứng (vertical distance) từ điểm cần tính tới đường nối haiđiểm PIP kế cận đã
chọn.
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 17
2.5. Các phương pháp rời rạc hóa:
Trong phương pháp rời rạc hóa (discretization) thì từ dữ liệu ban đầu, ta sẽ chia thành
những đoạn dữ liệu nhỏ hơn, rồi sau đó, tương ứng với mỗi đoạn nhỏ này ta sẽ mã hóa chúng
bởi những đặc trưng của đoạn và tập hợp những đặc trưng của những đoạn nhỏ này sẽ làm
thành một tràng ký hiệu biểu diễn cho dữ liệu ban đầu (nguồn [4]). Có một số phương pháp
rời rạc hóa đã được đề xuất như SAX, ESAX, và iSAX. Lợi ích quan trọng của việc rời rạc
hóa dữ liệu chuỗi thời gian là điều này cho phép sử dụng những cấu trúc dữ liệu và giải thuật
vốn có trong lãnh vực xử lý chuỗi ký tự như cây hậu tố, kỹ thuật băm, mô hình xích
Markov,v.v…
2.5.1. Phương pháp xấp xỉ gộp ký hiệu hóa (SAX):
Lin, Keogh và các cộng sự ([16]) đã đề xuất một phương pháp rời rạc hóa có tên là xấp xỉ
gộp ký hiệu hóa (symbolic aggregate approximation – SAX) mà dựa trên phương pháp thu
giảm số chiều PAA và giả sử dữ liệu thu giảm số chiều đã đươc chuẩn hóa. SAX là quá trình

ánh xạ biểu diễn PAA của chuỗi thời gian thành một chuỗi ký tự rời rạc. Gọi a là kích thước
của bộ ký hiệu mà được dùng để rời rạc hóa chuỗi thời gian. Để ký hiệu hóa chuỗi thời gian
chúng ta phải tìm thấy các trị (điểm ngắt) sau đây:
1 2, 1
, ,
a
  

với
1 2 1

a
  

  

Sử dụng những trị này, chuỗi thời gian
1
, ,
w
T t t

sẽ được rời rạc hóa thành tràng ký
hiệu
1 2

w
C c c c
 . Mỗi đoạn
i

t
sẽ được mã hóa thành ký hiệu
i
c
dùng công thức sau:
(2.13)
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 18

Hình 2.8: Minh họa phương pháp mã hóa SAX

Trong hình 2.9, một chuỗi dữ liệu thời gian được biến đổi PAA rồi mã hóa thành các ký
hiệu SAX. Chuỗi thời gian được mã hóa thành baabccbc.
Chúng ta chú ý rằng dữ liệu chuỗi thời gian thường có phân bố xác xuất Gauss. Để có
một xác xuất bằng nhau (1/a) cho mỗi ký hiệu, ta phải chọn trị điểm ngắt
i

dựa trên bảng
xác xuất của phân bố Gauss. Sau giai đoạn mã hóa SAX, thì bài toán so trùng chuỗi thời gian
trở thành bài toán so trùng chuỗi ký tự. Để thực hiện việc so trùng này nhanh chóng thì cấu
trúc cây hậu tố (suffix tree) hay tập tin VA (vector approximation file) có thể được sử dụng
làm cấu trúc chỉ mục.
Trong nhiều trường hợp ta chỉ cần quan tâm đặc trưng của chuỗi thời gian thì phương
pháp mã hóa SAX này rất thích hợp và hiện tại đang được ứng dụng nhiều. Ngoài ra, trong
phương pháp mã hóa SAX, ta có thể sử dụng những cấu trúc dữ liệu và giải thuật có sẵn về
xử lý chuỗi ký tự như trong lĩnh vực xử lý dòng ký tự và xử lý trình tự sinh học. Tuy nhiên,
nhược điểm chính của SAX là cách định nghĩa những đặc trưng cũng như phương pháp này
không hỗ trợ tốt việc tính khoảng cách Euclid và dữ liệu chuỗi thời gian được giả định là phải
thỏa phân bố xác xuất Gauss.

2.5.2. Phương pháp ESAX:
Năm 2006, Lkhagva và các cộng sự ([17]) đã đề xuất một phương pháp rời rạc hóa là sự
mở rộng của SAX, gọi là ESAX (Extended SAX) để đem lại một cách rời rạc hóa hữu hiệu
hơn SAX khi áp dụng vào dữ liệu chuỗi thời gian trong lãnh vực tài chính. Do SAX dựa vào
cách biểu diễn PAA mà trong đó sự thu giảm số chiều là sử dụng các giá trị trung bình của
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 19
các chuỗi con được phân đoạn với độ dài bằng nhau, nên có khả năng bị mất đi một số mẫu
quan trọng trong dữ liệu chuỗi thời gian tài chính. Để khắc phục nhược điểm này, Lkhagva và
các cộng sự vẫn dựa vào PAA nhưng sau khi đạt được giá trị trung bình của mỗi phân đoạn,
họ đưa thêm vào giá trị nhỏ nhất và lớn nhất của mỗi phân đoạn. Như vậy mỗi phân đoạn
được diễn tả bằng một bộ ba <trị trung bình, trị nhỏ nhất, trị lớn nhất>, và sau đó bộ ba này
sẽ được mã hóa bằng 3 ký hiệu thay vì chỉ một ký hiệu như trong phương pháp rời rạc hóa
SAX (nguồn [4]).
2.5.3. Phương pháp iSAX:
Phương pháp rời rạc hóa iSAX (indexable symbolic aggregate approximation) được
Shieh và Keogh đưa ra năm 2008 ([20]). Phương pháp này là sự mở rộng của phương pháp
SAX mà thay vì mã hóa mỗi phân đoạn chuỗi thời gian thành một ký hiệu như là chữ hay số
nguyên, iSAX mã hóa nó thành số nhị phân, thí dụ “00”, “01”,”10”,”11”.
Với cách này iSAX có thể mã hóa chuỗi thời gian thành chuỗi bit và nhờ đó tiết kiệm
được rất nhiều chỗ bộ nhớ lưu trữ. Ngoài ra, iSAX còn hỗ trợ khả năng biểu diễn đa mức
phân giải (multi-resolution) dựa trên khả năng đa mức phân giải của các mức rời rạc hóa.
Bằng việc kết hợp với một cấu trúc chỉ mục cây phân cấp (hierarchical tree) với phương pháp
iSAX, ta có thể truy vấn nhanh trên cơ sở dữ liệu chuỗi thời gian với kích thước lớn lên đến
hàng terabyte.
2.6. Thuật toán tìm kiếm sự bất thường của hình dạng:
Thuật toán này được Koegh đề xuất vào năm 2006 (nguồn [1]).
Cho một tập hình dạng S có kích thước là m, thuật toán brute force để tìm kiếm sự bất
thường rất đơn giản và rõ ràng. Chúng ta chỉ cần lấy mỗi chuỗi dữ liệu thời gian và tìm

khoảng cách từ nó đến hình dạng tương tự nhất. Hình dạng có giá trị đó lớn nhất là bất
thường. Mã giả của thuật toán này như sau:
Bảng 2.2: Tìm kiếm sự bất thường bằng giải thuật Brute Force
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 20

Ví dụ sau cho phép chúng ta quan sát "dấu vết" của thuật toán brute force trên một tập dữ
liệu đơn giản của sáu sinh vật biển. Bất thường đầu tiên xảy ra là con sao biển, có khoảng
cách phù hợp gần nhất của nó là 26,7. Để tìm sự bất thường, thuật toán brute force tìm kiếm
các dữ liệu với các vòng lặp lồng nhau, vòng lặp ngoài tìm kiếm trên các hàng cho mỗi hình
ứng sZ-0cử viên, và quét vòng lặp bên trong trên các cột để xác định tìm kiếm ứng cử viên
phù hợp gần nhất. Các thuật toán brute force cần tính toán khoảng cách giữa 6 * (6-1) / 2 =
15 cặp hình dạng.

Hình 2.9: Một ví dụ của thuật toán brute force (nguồn [1])

Các thuật toán brute force dễ thực hiện và tạo ra kết quả chính xác. Tuy nhiên, nó có độ
phức tạp thời gian
2
( )
O m
(m là kích thước của S dữ liệu). Lưu ý rằng mặc dù mức độ phức
tạp thời gian là phương trình bậc hai, không gian cần thiết cho thuật toán là không đổi được
chỉ ra rõ ràng qua ma trận được lấp đầy ở ví dụ trên. Trong thực hiện thực tế, chúng ta có thể
xây dựng và kiểm tra chỉ có một thành phần tại một thời điểm.
Tìm kiếm hình dạng bất thường trong tập cơ sở dữ liệu lớn

Trang 21
Có một cách để tăng tốc độ tìm kiếm đó là trong vòng lặp trong, chúng ta thật sự không

cần phải tìm kiếm cận tương tự đúng gần nhất với ứng cử viên hiện tại. Một khi chúng ta tìm
thấy bất kỳ hình dạng nào tương tự hơn so với ứng cử viên hiện tại thể hiện ở biến
best_so_far_dist, chúng ta có thể ngừng tìm kiếm trong hàng đó vì ứng cử viên đó không thể
là hình dạng bất thường. Chúng ta gọi đây là tối ưu hóa là từ bỏ sớm (early abandoning). Nếu
chúng ta áp dụng tối ưu hóa để các dữ liệu sinh vật biển, chúng ta chỉ cần tính toán khoảng
cách giữa 12 cặp hình dạng.

Hình 2.10: Một ví dụ của việc áp dụng từ bỏ sớm cho thuật toán brute force (nguồn [1])
Sau khi áp dụng tối ưu hóa này, ta có giải thuật Brute Force được cải tiến như sau:
Bảng 2.3: Giải thuật Brute Force cải tiến