Môn: Kho dữ liệu và Khai phá dữ liệu
GVHD: PGS.TS. Hà Quang Thụy
Học viên: Bùi Thu Hải
Vũ Thị Anh Trâm
Trường Đại học Công Nghệ - ĐHQG Hà Nội
Khoa Công nghệ thông tin
 
Tiểu luận 8:
Thuật toán xác định
phần tử gây nhiễu (outlier) nhanh
trong không gian đa chiều
NộI DUNG TRÌNH BÀY
1. Giới thiệu.
2. Định nghĩa và kí hiệu.
3. Thuật toán.
4. Kết quả thực nghiệm và kết luận.
TÀI LIệU

Tài liệu chính:
- Fabrizio Angiulli and Clara Pizzuti, Fast Outlier Detection in High Dimensional Spaces, ISI – CNR, c/o DEIS,
Universita della Calabria 87036 Rende (CS), Italy.

Sách đọc thêm:
- Hà Quang Thụy, Tập bài giảng môn Kho dữ liệu và khai phá dữ liệu.
- Các tài liệu điện tử khác
1.GIớI THIệU

Xác định các phần tử gây nhiễu là 1 trong những nhiệm vụ mà khai phá dữ liệu đang giải quyết.

Nhiều thuật toán xem các phần tử gây nhiễu như là các nhiễu, phải được loại bỏ vì nó làm giảm
độ chính xác của thuật toán.


Dựa vào mật độ

Khả năng 1 phần tử có thể trở thành phần tử gây nhiễu phụ
thuộc vào mật độ láng giềng địa phương (còn được gọi là “hệ số
gây nhiễu cục bộ LOF” được gán cho mỗi đối tượng)

Nhược điểm: Chi phí tính toán LOF lớn vì phải tính LOF cho
từng đối tượng.

Dựa trên khoảng cách

Thuật toán do Knorr và Ng giới thiệu

Thuật toán do Ramaswamy, Rastogi và Shim giới thiệu

Thuật toán HilOut do Fabrizio Angiulli và Clara Pizzuti giới thiệu
CÁCH TIếP CậN DựA TRÊN KHOảNG
CÁCH

Thuật toán do Knorr và Ng giới thiệu: Cho tập dữ liệu a, các tham số k và δ. Phần tử p ϵ
a được gọi là phần tử gây nhiễu nếu có tối đa k điểm mà khoảng cách từ nó tới p ≤ δ.

Nhược điểm:

Phụ thuộc vào 2 tham số k và δ.

Không sắp xếp thứ bậc các phần tử gây nhiễu.

Thuật toán không thể áp dụng được trong không gian


Thuật toán Hilout do Fabrizio Angiulli và Clara Pizzuti giới thiệu.

Kí hiệu ω
k
(p) là tổng khoảng cách từ p tới k láng ghiềng gần nó nhất, còn được gọi là trọng số của p, được sử
dụng để xếp thứ bậc các điểm trong tập dữ liệu.

Phần tử gây nhiễu là phần tử có có trọng số lớn.

Kí hiệu DB là tập dữ liệu d chiều trong siêu lập phương D = [0,1]
d
.

Sử dụng đường cong Hilbert ánh xạ D sang đoạn I = [0,1], tìm k láng ghiềng gần nhất của mỗi điểm bằng cách
xem xét các phần tử đứng trước và đứng sau nó trong p.
1. GIớI THIệU (TIếP)

Sử dụng tính chất của ánh xạ: nếu 2 điểm gần nhau trong I thì chúng cũng gần nhau trong D, điều ngược
lại không đúng.

Để tránh việc mất điểm ở gần, tập dữ liệu được điều chỉnh d+1 lần dọc theo đường chéo chính của khối
siêu lập phương [0,2]
d
.

Không gian đường cong được sử dụng để ánh xạ từ không gian đa chiều sang không gian 1 chiều để tìm
các điểm láng giềng gần nhất của mỗi điểm 1 cách nhanh chóng, nhưng việc tính toán khoảng cách vẫn
được thực hiện trong không gian gốc.
1. GIớI THIệU (TIếP)

k là tập n phần tử gây nhiễu đầu tiên.
t
t
d
i
iitt
qpqpdL
/1
1
)||(),(
∑
=
−==
2. ĐịNH NGHĨA VÀ KÍ HIệU (TIếP)

Kí hiệu là 1 số thực dương. Ta nói out* là 1 ước chừng của out
n
k nếu
. Trong đó w* là và w
n
là trọng số của
outlier
n
k


Các điểm trong DB được sắp xếp thứ tự theo trọng số.

n phần tử out
n

mà các điểm trung tâm được xem như các điểm trong không gian hữu hạn.

Đặt D là tập và điểm pϵD.

H(p) là ảnh nghịch đảo của p trong ánh xạ (giá trị Hilbert của p).

DB là 1 tập trong D.

H(DB) là tập
KHÔNG GIAN ĐƯờNG CONG (TIếP)

Hpred(p) và Hsucc(p) là 2 điểm đứng liền trước và đứng liền sau p trong H(DB) theo thứ tự đường cong
Hilbert.

Hpred(p,m) và Hsucc(p,m) là điểm đứng liền trước và liền sau thứ m của p.

Sử dụng tính chất: nếu 2 điểm trong khoảng đơn vị I là gần nhau thì hình ảnh tương ứng của chúng cũng
gần nhau trong siêu lập phương D. Điều ngược lại không đúng. Do vậy việc giảm số chiều: từ d chiều sang
1 chiều có thể dẫn tới mất 1 số tính chất. Để hạn chế điều này sử dụng thêm phương pháp chuyển dịch
hoặc quay siêu lập phương D.
PHƯƠNG PHÁP CHUYểN DịCH HOặC
QUAY SIÊU LậP PHƯƠNG D

Duy trì sự gần nhau của 2 điểm trong không gian d chiều bằng vài hệ số khi chúng chuyển sang
không gian 1 chiều. Số lần điều chỉnh phụ thuộc vào d chiều.

Cho 1 tập DB và vecto

Một điểm p thuộc DB có thể được biến đổi d+1 lần dọc theo đường chéo chính bằng cách p
j

Bổ đề 1: Cho 1 tập DB, 1 điểm p thuộc DB, 2 số nguyên dương a và b và 1 tập các điểm

Đặt r = và

Ta có:
1. Các điểm trong S là |S| là các láng ghiềng thực sự đầu
tiên của p trong DB.
2.
3. THUẬT TOÁN

Thuật toán HilOut gồm 2 giai đoạn:
 Thực hiện tối đa d + 1 lần quét tập dữ liệu vào
và cho kết quả là - một xấp xỉ của Out
k
n
,
ở đây , với chi phí thời gian
phức tạp thấp.
 Thực hiện một lần quét đơn tập dữ liệu và tính
toán Out
k
n
để có được kết quả chính xác cần tìm.
3. THUẬT TOÁN (tiếp)

Mỗi lần quét HilOut tính toán một cận dưới và cận trên tới trọng số wk của mỗi
điểm và nó giữ các giá trị cận dưới lớn nhất trong WLB.

Giá trị thứ n, w* trong WLB là 1 cận dưới tới trọng số của phần tử gây nhiễu thứ n
và nó được sử dụng để xác định các điểm có khả năng là các phần tử gây nhiễu.

nằm trong vùng lân cận

Count: số điểm trong vùng lân cận
3. THUẬT TOÁN (tiếp)

Input của thuật toán là tập dữ liệu DB với N điểm trong siêu lập phương [0,1]
d
, số
n các phần tử gây nhiễu cần tìm và k là số láng giềng gần nhất được chỉ định.

Cấu trúc dữ liệu để thực hiện gồm hai đống (heap) của n các thuộc tính điểm OUT
và WLB, tập TOP, một danh sách các thuộc tính điểm PF.

Cuối mỗi lần lặp, thuộc tính được lưu trong OUT, WLB tương ứng là n giá trị lớn
nhất của trường Weight, WLb(f) =
, , TOP là tập 2n thuộc tính điểm phổ biến nhất được thiết lập từ sự kết hợp
các thuộc tính được lưu trong OUT và WLB ở cuối lần lặp trước đó.