BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
VIỆN CÔNG NGHỆ THÔNG TIN
Phạm Hạ Thủy

NGHIÊN CỨU PHẦN TỬ NGOẠI LAI
TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán
Mã số: 62.46.35.01 TÓM TẮT LUẬN ÁN TIẾN SĨ


- Thư viện Quốc gia Hà Nội
CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN ÁN
1. Phạm Hạ Thuỷ (2001), "Thiết kế phần mềm kiểm toán trên nền cơ sở dữ liệu của
Kiểm toán Nhà nước", Tạp chí Tin học và điều khiển T17( 3),p.61-64.
2. Phạm Hạ Thuỷ (2005), "Ứng dụng cây quyết định vào việc xác định rủi ro kiểm
toán", Tạp chí Kiểm toán Số T60 (8), p.32-35.
3. Phạm Hạ Thuỷ
(2005), “Phát hiện phần tử ngoại lai theo luật hợp thành và ứng
dụng trong việc phát hiện sai sót trong chứng từ kế toán”, Tạp chí Tin học Tài
chính, số 29, p. 24-25.
4. Phạm Hạ Thuỷ (2005), “ Xác định phần tử ngoại lai trong cơ sở dữ liệu quan hệ”,
Tạp chí Tin học và điều khiển,T21(4),p.352-360.
5. Phạm Hạ Thuỷ - Hoàng Xuân Huấn (2006), "Phát hiện phần tử ngoại lai trong cơ
sở dữ
liệu nhờ phân tích hồi qui", Tạp chí Tin học và Điều khiển, T22(1), p.45-
52.
6. Vũ Đức Thi - Phạm Hạ Thuỷ (2007), " Phụ thuộc hàm xấp xỉ và phần tử ngoại lai
đối với phụ thuộc hàm", Tạp chí Tin học và Điều khiển, T23(1), p.80-85.

Một số báo cáo tại các hội thảo quốc gia về CNTT
1. Vũ Đức Thi - Phạm Hạ Thuỷ, " Find out Strong Dependencies over Relational
Database", Hội thảo khoa học quốc gia lần thức ba " Nghiên cứu phát triển và
ứng dụng công nghệ thông tin và truyền thông" - ICT.rda'06 được tổ chức tại Hà
Nội tháng 5/2006.

u ứng dụng việc phát hiện phần tử ngoại
lai vào trong các lĩnh vực khác nhau của đời sống xã hội: phòng chống
tội phạm máy tính; kiểm soát mạng; xử lý nhiễu, phát hiện mẫu, phát
hiện dị thường và làm sạch dữ liệu trong học máy và nghiên cứu y
học
Tuy nhiên các phương pháp phát hiện phần tử ngoại lai của các
tác giả đi trước mới chỉ đề xuất cho các tập dữ liệu nói chung, ch
ưa đi
sâu vào các loại dữ liệu có cấu trúc cụ thể. Mặt khác việc phát hiện
phần tử ngoại lai chỉ mới dựa trên việc xử lý các phần tử trong nội bộ
của tập dữ liệu. Vai trò của các ràng buộc, luật biết trước (các thông tin
bên ngoài có tính chất qui định, định hướng) mà các phần tử của tập dữ
liệu buộc phải tuân theo chưa được đặt ra (mà trong thực t
ế những bài
toán phát hiện hiên tượng gian lận, sai sót (hiện tượng ngoại lai) trong

2
các lĩnh vực kế toán, kiểm toán, quản lý kinh tế thì lại chủ yếu là dựa
vào các qui định, các luật biết trước). Điều này làm hạn chế đến hiệu
quả của việc phát hiện khi áp dụng vào những trường hợp CSDL cụ thể
hoặc đối với mục tiêu nhằm phát hiện những phần tử vi phạm những
luật (các ràng buộc hoặc qui tắc) được cho trước.
Hoạ
t động kiểm toán của Kiểm toán Nhà nước hiện nay là việc
kiểm tra, đánh giá và xác nhận tính đúng đắn, trung thực của báo cáo
tài chính; việc tuân thủ pháp luật; tính kinh tế, hiệu lực và hiệu quả
trong quản lý, sử dụng ngân sách, tiền và tài sản nhà nước. Hiện nay
hoạt động kiểm toán nhà nước ở Việt nam được tiến hành chủ yếu bằng
cách thủ công. Việc kiểm tra đánh giá mất rất nhi
ều công sức và thời

định, xây dựng mô hình lấy mẫu phục vụ cho mục đích phát hiệ
n phần
tử ngoại lai.
Một số mục tiêu cụ thể của Luận án được đặt ra là:
- Nghiên cứu phần tử ngoại lai trong cơ sở dữ liệu lớn dựa trên phụ
thuộc hàm, khoá và các dạng chuẩn nhằm giải quyết một số bài toán cụ
thể về phát hiện phần tử ngoại lai trong cơ sở dữ liệu quan hệ;
- Hoàn thiện thêm lý thuyết về phụ thu
ộc mạnh trong cơ sở dữ liệu quan
hệ và ứng dụng phụ thuộc mạnh trong việc phát hiện phần tử ngoại lai;
- Nghiên cứu phụ thuộc xấp xỉ loại 2 và ứng dụng vào việc phát hiện
phần tử ngoại lai;
- Cải tiến thuật toán xây dựng cây phân lớp và thuật toán tìm luật kết
hợp phân lớp;
- Nghiên cứu, đề xuất một số mô hình ứng dụng phát hiệ
n phần tử
ngoại lai vào thực tiễn hoạt động kiểm toán và quản lý tài chính.
Với việc hoàn thành các mục tiêu đã đặt ra, Luận án đã đạt được
một số kết quả, đóng góp một phần trong việc phát triển lý thuyết về tổ
chức và xử lý các file dữ liệu trong cơ sở dữ liệu và khai thác dữ liệu.
Luận án có ý nghĩa thực tế trong việc giải quyết mộ
t số bài toán trong
lĩnh vực kiểm toán và quản lý tài chính trong bối cảnh công cuộc tin
học hoá đang được triển khai mạnh mẽ trong các lĩnh vực này.
Luận án gồm 151 trang được bố cục thành 4 chương cùng với
phần mở đầu, kết luận và giới thiệu tài liệu tham khảo.
Chương 1. Lý thuyết cơ sở và các công trình nghiên cứu liên
quan, Luận án trình bày một số lý thuyết và công trình nghiên cứu của
các tác giả đi trướ
c làm cơ sở cho việc nghiên cứu.
5
CHƯƠNG 1
LÝ THUYẾT CƠ SỞ VÀ CÁC CÔNG TRÌNH NGHIÊN CỨU
LIÊN QUAN
Trong nội dung của chương này, Luận án trình bày một số lý
thuyết và công trình nghiên cứu của các tác giả đi trước làm cơ sở cho
việc nghiên cứu, bao gồm: một số nội dung cơ bản về CSDL quan hệ:
các khái niệm về quan hệ, tiên đề Amstrong, phụ thuộc hàm, khoá,
dạng chuẩn của quan hệ; một số vấn đề lý thuyết về khai thác dữ liệ
u:
phát hiện phần tử ngoại lai; khai thác và tìm kiếm luật kết hợp; xây
dựng cây quyết định.
Các khái niệm về phụ thuộc hàm, khoá và các dạng chuẩn của
quan hệ được tác giả của luận án sử dụng để xây dựng khái niệm về
phần tử ngoại lai đối với phụ thuộc hàm, khoá và các dạng chuẩn cũng
như các thuật toán dùng để phát hiện phần tử ngoại lai trong từ
ng
trường hợp.
Khái niệm phần tử ngoại lai trong một tập dữ liệu dùng để chỉ những
phần tử có sự khác biệt so với đa số các phần tử còn lại của tập dữ liệu.
Có nhiều phương pháp nghiên cứu về phần tử ngoại lai, tuy nhiên các
phương pháp phát hiện phần tử ngoại lai của các tác giả đi trước mới
chỉ đề xuất cho các t
ập dữ liệu nói chung, chưa đi sâu vào các loại dữ
liệu có cấu trúc cụ thể. Việc phát hiện phần tử ngoại lai chỉ mới dựa
trên việc xử lý các phần tử trong nội bộ của tập dữ liệu, vai trò của các
ràng buộc, luật biết trước (các thông tin bên ngoài có tính chất qui
định, định hướng) mà các phần tử của tập dữ liệu buộc phải tuân theo

C.S.Lee (2004). Trong Luận án chúng tôi đề xuất một số cải tiến đối
với các thuật toán này có ý nghĩa làm giảm khối lượng tính toán.

CHƯƠNG 2
PHÁT HIỆN PH
ẦN TỬ NGOẠI LAI TRONG
CƠ SỞ DỮ LIỆU QUAN HỆ
Đây là chương trọng tâm, trình bày những kết quả nghiên cứu
chính của Luận án. Các nội dung chính bao gồm:
1. Mô hình phát hiện phần tử ngoại lai dựa theo luật
Trong nội dung được trình bày chúng tôi đưa ra mô hình phát
hiện phần tử ngoại lai dựa theo luật (Rules – Based) trong CSDL quan
hệ. Các ràng buộc, qui tắc đối với CSDL quan hệ được đề cập ở đây có
nhiều loạ
i khác nhau bao gồm các luật qui định về sự phụ thuộc dữ
liệu: phụ thộc hàm, khoá đối với sơ đồ quan hệ hoặc file dữ liệu; phụ
thuộc tương quan giữa các thuộc tính; một hệ ràng buộc cho trước mà

7
các phần tử của tập dữ liệu phải tuân theo; các luật qui định về các
dạng chuẩn của sơ đồ quan hệ
2.Phần tử ngoại lai đối với phụ thuộc hàm, khóa của quan hệ
Khái niệm về phần tử ngoại lai đối với phụ thuộc hàm, khóa là
các khái niệm mới mà chúng tôi đưa ra cùng với việc giải quyết vấn đề
tìm các phần tử trong một bảng dữ
liệu vi phạm các điều kiện của phụ
thuộc hàm, khóa đối với một quan hệ. Hiện tượng vi phạm này cũng
thường xảy ra trong thực tế đối với quá trình cập nhật dữ liệu vào các
bảng dữ liệu sau khi một cơ sở dữ liệu đã được thiết kế xong (sai sót
hoặc cố tình khi cập nhật dữ liệu). Các hiện tượng này cần được phát

, t
j
∈ r
(i ≠ j) là một cặp ngoại lai đối với khoá nếu như đối với một khoá K∈
B, ta có t
i
(K) = t
j
(K).
Theo qui ước bảng dữ liệu được giả thiết là một quan hệ thì
không thể có 2 bộ trùng nhau hoàn toàn, do vậy nếu có 2 bộ trùng nhau
trên khoá thì chúng có thể trùng nhau trên toàn bộ R tức chúng là ngoại
lai đối với quan hệ. Hoặc chúng không bằng nhau trên các thuộc tính
còn lại (R \ K). Như vậy chúng lại là cặp ngoại lai theo phụ thuộc hàm.
Hiện tượng này thường xảy ra trong thực tế do quá trình cập nhật dữ
liệu sai do cố ý hoặc không cố ý.
Trong kết quả nghiên cứu chúng tôi đưa ra và chứng minh Định
lý 2.1 và mệnh đề 2.1. về dấu hiệu nhận biết các cặp phần tử ngoại lai đối
với phụ thuộc hàm, khóa của một quan hệ r. Dấu hiệu nhận biết được dựa

8
trên việc tính toán hệ bằng nhau E
r
của quan hệ r được định nghĩa như
sau:
E
r
= { E
i,j
: 1≤ i < j ≤m , E

r
mà X
⊆

E
i,j
và Y
⊄
E
i,j
.
- Mệnh đề 2.1 (Nhận biết cặp ngoại lai theo khoá)
Cho bảng dữ liệu r được giả thiết là một quan hệ trên sơ đồ quan
hệ (R, F); B được giả thiết là tập các khoá của r; E
r
là hệ bằng nhau
của r. Khi đó nếu ta có E
i,j
∈
E
r
chứa một khoá K
∈
B nào đó (tức là K
⊆
E
i,j
) thì cặp phần tử (t
i
, t

3. Phần tử ngoại lai đối với hệ ràng buộc dạng phụ thuộc hàm
Trong thực tế chúng ta gặp bài toán phải kiểm tra sự thoả mãn
một hệ ràng buộc dạng phụ thuộc hàm của các bộ giá trị của một quan
hệ cho trước. Các ràng buộc này thực chất là các luật kết h
ợp
(Associate rules) đã biết trước đối với một quan hệ nào đó. Việc phát
hiện những bộ của quan hệ không thoả mãn những luật kết hợp này có
ý nghĩa trong nhiều ứng dụng thực tế của hoạt động kiểm toán. Các
khái niệm và thuật toán được chúng tôi đưa ra trong Mục 2.5 Chương 2
nhằm giải quyết bài toán về phát hiện phần tử ngoại lai đối với một hệ
các luật kết hợp trong một quan hệ.
-Thuật toán 5- Xác định phần tử ngoại lai đối với hệ ràng buộc dạng
phụ thuộc hàm.
4. Phần tử ngoại lai đối với các dạng chuẩn
Trong thực tế sau khi một CSDL quan hệ được thiết kế xong, trong quá
trình cập nhật dữ liệu xảy ra hiện tượng các bảng dữ liệu có chứa
những bản ghi làm cho bảng dữ liệ
u không còn thỏa mãn điều kiện
dạng chuẩn được thiết kế. Hiện tượng này xuất hiện khi các bản ghi
(phần tử) được cập nhật sai. Ta sẽ gọi các phần tử này là các phần tử
ngoại lai của các dạng chuẩn. Việc phát hiện ra những bản ghi này để
xử lý có ý nghĩa làm sạch dữ liệu và chuẩn hóa một quan hệ, giúp cho
việc tiến hành khai thác dữ liệu được chính xác.
Các k
ết quả nghiên cứu của chúng tôi được trình bày trong mục
2.6, Chương 2 của Luận án. Trong nội dung chúng tôi trình bày khái
niệm và một số thuật toán để phát hiện các phần tử ngoại lai theo các
dạng chuẩn 2NF, 3NF, BCNF là các dạng chuẩn được dùng phổ biến
trong thiết kế CSDL. Để xây dựng thuật toán phát hiện phần tử ngoại
lai đối với các dạng chuẩn 3NF và BCNF chúng tôi sử dụng các dấu

là tập các thuộc tính thứ cấp. Đặt
G
r
= {C
i
: C
i
= M
i
- F
n
, M
i
∈ M}. Khi đó:
a) Nếu ∀ C
i
∈ G
r
mà C
i
+
= C
i
thì r ở dạng chuẩn 2NF.
b) Nếu với ∀C
i
mà C
i
+
≠ C

vào nghiên cứu, có ý nghĩa trong việc giải quyết nhiều bài toán thực tế.
Cho R là một tập hữu hạn không rỗng các thuộc tính, r = {t
1
, t
2
,
t
m
} là một quan hệ trên R và A, B ⊆ R. Ta nói rằng B phụ thuộc
mạnh vào A trên r, kí hiệu là
BA
S
⎯→⎯ nếu: ∀ t
i
, t
j
∈ r : nếu với mỗi a ∈
A mà t
1
(a) = t
2
(a) thì ta có ∀ b∈B: h
1
(b) = h
2
(b).

11
Các phụ thuộc mạnh cũng là các phụ thuộc hàm thông thường,
tuy nhiên chúng phản ánh mối phụ thuộc dữ liệu đặc biệt giữa một tập

R , Y
⊆
R nếu {a}
→
Y
∈
F
+
thì {a}
→
Y
∈
S
+
;
T2)
∀
A,B,C
⊆
R ta có CAB
S
⎯→⎯
∈
S
+
khi và chỉ khi CA
S
⎯→⎯
∈
S

S
+
;
Trong kết quả nghiên cứu của mình, chúng tôi đưa ra và chứng
minh một số các định lý và mệnh đề sau:
-Định lý 2.2 (Tính đúng đắn và đầy đủ của hệ T1-T3)
Cho (R,F) là một SĐQH, F
+
là bao đóng của F khi đó:

12
1- Tập các phụ thuộc mạnh S
+
được sinh ra từ tập F
+
theo các tính
chất T1-T3 là một họ s trên R;
2- Nếu S' là tập tất cả các phụ thuộc mạnh
∈
F
+
và S
+
được sinh ra từ
F
+
theo T1-T3 thì S' = S
+
;
3- Nếu S

+
là một họ s các phụ thuộc
mạnh trên R. Có thể tìm được một họ f các phụ thuộc hàm (F
+
) trên R
mà S
+
sẽ được sinh ra từ F
+
theo các tính chất T1- T3.
- Mệnh đề 2.3 (sự tồn tại phụ thuộc mạnh)
Cho SĐQH (R, F). Khi đó điều kiện để tồn tại phụ thuộc mạnh
không tầm thường trên F
+
khi và chỉ khi tồn tại ít nhất một thuộc tính
a
∈
R sao cho a
+
≠
a

với a
+
là bao đóng của a.
Vì các phụ thuộc mạnh đều có thể suy dẫn từ các phụ thuộc mạnh
dạng đơn (vế trái và vế phải chỉ có một phần tử), căn cứ vào các định
lý và mệnh đề được đề xuất, chúng tôi xây dựng các thuật toán xác
định các phụ thuộc mạnh dạng đơn. Các thuật toán được đề xuất:
Thuật toán 10- xác định các phụ thuộc mạnh dạng

những phụ thuộc hàm xấp xỉ kiểu tương quan hàm số. Để phân biệt với
khái niệm phụ thuộc hàm xấp xỉ của các tác giả trước đã đưa ra (một
phụ thuộc hàm xấp xỉ là một phụ thuộc hàm hầu như đúng trên r. Độ đo
được chọn là tỉ số gi
ữa các bản ghi không thoả luật với tống số các bản ghi
của r). phụ thuộc hàm xấp xỉ mà chúng tôi xây dựng được gọi là phụ
thuộc hàm xấp xỉ loại 2. Mặc dù khái niệm mà chúng tôi đưa ra chưa
bao quát được hết các loại phụ thuộc xấp xỉ trong quan hệ, tuy nhiên
trong phần nghiên cứu các tính chất của phụ thuộc hàm xấp xỉ loại 2,
chúng tôi chứng minh rằng khái niệm này bao hàm khái niệm về phụ
thuộc hàm thông thường (khi chọn mức xấp xỉ δ =0) và phản ánh mối
phụ thuộc mới trong quan hệ. Mặt khác, khái niệm này cũng đủ để ứng
dụng giải quyết nhiều bài toán trong lĩnh vực kiểm toán (vì rằng trong
các dữ liệu thông tin chủ yếu dùng cho kiểm toán thì các thuộc tính

14
trong các quan hệ thường được qui đổi thành giá trị bằng tiền - do vậy
việc áp dụng khái niệm phụ thuộc hàm xấp xỉ loại 2 vào phát hiện
những bất thường (ngoại lai) trong dữ liệu thông tin là hợp lý).
Cho r là một quan hệ trên tập thuộc tính R={A
1
,A
2
, A
n
} trong
đó các thuộc tính A
1
,A
2

∈
r, mà
ρ
(t
1
(X), t
2
(X))
≤

δ
thì ta cũng có
ρ
(t
1
(Y), t
2
(Y))
≤

δ
.
Trong đó
ρ
(t
1
(X), t
2
(X))được gọi là khoảng cách giữa t
1

t
2
(A
i
)
⏐
), A
i

∈
X );
- Hàm max(x,y) là hàm chọn ra số lớn nhất trong 2 số x,y;
- Trường hợp max(
⏐
t
1
(A
i
⏐
,
⏐
t
2
(A
i
)
⏐
) = 0, thì ta qui ước:

⏐

- Tính chất của hàm khoảng cách
ρ
(t
1
(X), t
2
(X)):
a1.
ρ
(t
1
(X), t
2
(X)) ≥ 0 với t
1
, t
2
, X tùy ý
a2.
ρ
(t
1
(X), t
2
(X))= 0
⇔
t
1
(X)= t
2


ρ
(t
1
(Y), t
2
(Y))
a5.
ρ
(t
1
(XY), t
2
(XY)) = max (
ρ
(t
1
(X), t
2
(X)),
ρ
(t
1
(Y), t
2
(Y)))
- Một số tính chất của phụ thuộc hàm xấp xỉ loại 2:

15
1) Cho r là một quan hệ trên tập thuộc tính R. Một phụ thuộc hàm đúng

Y là hai phụ thuộc hàm xấp xỉ
loại 2 mức
δ
1 và mức
δ
2 giữa X và Y trên r , khi đó nếu X
≈
>
δ
1
Y đúng
trên r thì X
≈
>
δ
2
Y cũng đúng trên r.
3) (tính phản xạ): Nếu Y
⊆
X khi đó X
≈
>
δ
Y là phụ thuộc hàm xấp xỉ
loại 2 với mức
δ
tùy ý (0
≤

δ

thuộc hàm xấp xỉ. Việc phát hiện phần tử ngoại lai đối với phụ thuộc
hàm xấp xỉ loại 2 được ứng dụng trong việc phân tích phát hiện hiện
tượng bấ
t thường trong sản xuất kinh doanh và quản lý tài chính.
Giả sử cho r= {t
1
, t
2
, t
m
} là một quan hệ trên tập thuộc tính R và
một số δ cho trước (0 ≤ δ < 1).
Kí hiệu E
r
δ
là hệ xấp xỉ mức δ của r được xây dựng như sau:
E
r
δ = { E(δ)
i,j
= {a : ⎜t
i
(a)-t
j
(a) ⎜/ max(⎜t
i
(a)⎜, ⎜t

của r. Quan hệ r thỏa phụ thuộc hàm xấp xỉ loại 2 mức
δ
: X
≈
>
δ
Y khi và
chỉ khi:

∀
E(
δ
)
i,j

∈
E
r
δ
: (X
⊆
E(
δ
)
i,j
)
⇒
(Y
⊆
E(

j
) với t
i
, t
j
∈
r, là cặp ngoại lai đối
với X
≈
>
δ
Y khi và chỉ khi X ⊆ E(δ)
i,j
và Y ⊄ E(
δ
)
i,j
với E(
δ
)
i,j
là phần
tử thuộc E
r
δ
tương ứng với cặp (t
i
, t
j
).

17
Trees) được dùng phổ biến trong các kỹ thuật phân lớp. Thuật toán
ID3, C4.5 (Quilan - 1990, 1993) được coi là điển hình cho thuật toán
phân lớp bằng cây quyết định. Thuật toán phân lớp dựa trên cây quyết
định và luật kết hợp của Bing Liu, Hsu, Ma (1998); Thuật toán phân
lớp dựa trên cây quyết định và phụ thuộc hàm xấp xỉ của Kwok-Wa
Lam và Victor C.S.Lee (2004) đã có những cải tiến so với các thuật
toán truyền thống. Các thuật toán này dựa trên việc phân tích một tập
m
ẫu học (Training set) có dạng bảng quan hệ và tạo ra một cây quyết
định dùng để phân lớp. Tuy nhiên các thuật toán này thường có những
hạn chế khi số các thuộc tính và số bản ghi của tập mẫu học là lớn thì
số phép toán cần thực hiện là rất lớn và việc duyệt nhiều lần trên tập
mẫu học. Trong Luận án để xuất việc cải tiến các thuật toán nói trên
với mục đích giả
m số lượng thuộc tính được đưa vào xây dựng cây
quyết định và giảm số lần duyệt trên tập mẫu học.
Trong thực tế, các hoạt động kiểm tra để phát hiện sai sót, gian
lận (hiện tượng ngoại lai) trong lĩnh vực kiểm toán, quản lý tài chính
nhiều khi cần phải thực hiện việc kiểm tra bằng thủ công và thực hiện
trên những mẫu đại diện của tập dữ
liệu tổng thể liên quan đến việc
chọn mẫu để phát hiện phần tử ngoại lai. Tuy nhiên trong các kết quả
nghiên cứu trước đây về phần tử ngoại lai thì việc lấy mẫu chưa được
đặt ra. Trong nội dung của Luận án, chúng tôi đề xuất một số phương
pháp lấy mẫu để phát hiện phần tử ngoại lai có ý nghĩa trong việc áp
dụng vào họat động kiểm toán mà s
ẽ được trình bày trong Chương 4.
Các kết quả nghiên cứu, bao gồm:
1. Xây dựng cây quyết định dựa trên khoá của quan hệ

k
là một quan hệ trên lược đồ R
k
(a
1
, a
2
, , a
s
,
C). Gọi D
k
là tập mẫu học khóa. Gọi T là cây phân lớp với tập mẫu học
D
k
. Chúng tôi phát biểu và chứng minh mệnh đề sau làm cơ sở cho
việc cải tiến thuật toán.
- Mệnh đề 3.1. Cây phân lớp T được xây dựng trên tập mẫu học khoá
D
k
phân lớp chính xác D
k
thì cũng phân lớp chính xác tập mẫu học D.
Khi thực hiện xây dựng cây quyết định (trong ID3, C4.5) thay
cho việc xét toàn bộ tập D thì tiến hành thực hiện xây dựng cây phân
lớp với tập mẫu học khóa D
k
. Do số thuộc tính trong tập khóa nhỏ hơn
hoặc cùng lắm là bằng R do vậy khối lượng tính toán sẽ được giảm bớt,
đặc biệt với việc chọn được khóa (siêu khóa) phù hợp (Trong cải tiến

giảm được 1/2 số lượng phép toán (chi tiết xem Mục 3.2, Chương 3
của Luận án).
3. Mô hình chọn mẫu thống kê để xác định ngoại lai
Thông thường để phát hiện phần tử ngoại lai trong một tập dữ
liệu cần tiến hành duyệt toàn bộ các phần tử trong tập dữ liệu để kiểm
tra. Trong nhiều trường hợp người ta phải xét tới từng trường hợp cụ
thể và phải tiến hành kiểm tra bằng phương pháp thủ công. Việc tiến
hành kiểm tra bằng thủ công thường sẽ mất rất nhiều công sức và thời
gian. Trường hợp số lượng các phần tử trong tập dữ liệu quá lớn người
ta chỉ có thể kiểm tra được bằng những mẫu đại diện. Điều này dẫn đến
khả năng bỏ sót những phần t
ử ngoại lai và kết luận suy cho tập tổng
thể thiếu chính xác. Do vậy dẫn đến việc cần phải đưa ra những
phương pháp lấy mẫu phát hiện ngoại lai đảm bảo yêu cầu những
trường hợp ngoại lai bị bỏ sót không gây nên ảnh hưởng lớn đến kết
luận tổng thể về tập dữ liệu. Đây cũng là bài toán quan trọng trong lĩnh
vực kiểm toán (trong ki
ểm toán việc lấy mẫu kiểm toán đảm bảo rằng
những sai sót, gian lận bị bỏ sót không gây nên những sai lệch mang
tính trọng yếu) cần giải quyết nhằm giảm được chi phí kiểm toán đồng
thời đạt được yêu cầu là những kết luận kiểm toán (liên quan đến
những gian lận và sai sót phát hiện được) đủ độ chính xác và độ tin
cậy. Vấn đề chọn mẫu để phát hiện ngoại lai tr
ước đó chưa được đề
cập.
Trong Luận án chúng tôi trình bày phương pháp chọn mẫu ngẫu
nhiên để phát hiện phần tử ngoại lai trên cơ sở đảm bảo độ chính xác
và độ tin cậy cho trước. Các phương pháp mà chúng tôi đưa ra chủ yếu
là việc áp dụng các phương pháp lấy mẫu trong thống kê toán học vào
các mô hình xác định phần tử ngoại lai trên mẫu được chọn.

này đòi hỏi có các phương pháp, thuật toán tin học để xây dựng các
phần mềm trợ giúp cho các ho
ạt động kiểm toán này. Các thuật toán,
phương pháp được trình bày trong Luận án được dùng để phục vụ mục
đích nói trên.
Các hiện tượng sai sót, gian lận có thể được phát hiện ra bằng sử
dụng các phương pháp phát hiện các phần tử ngoại lai theo luật trong
dữ liệu báo cáo tài chính (chủ yếu ở dạng CSDL quan hệ) mà đã được
chúng tôi nghiên cứu và trình bày trong các Chương 2, Chương 3.

21
Các ứng dụng được nghiên cứu áp dụng bao gồm:
- Phát hiện sai sót gian lận trong kê khai thuế và chi phí nguyên
vật liệu. Phương pháp dựa trên kết quả nghiên cứu về phát hiện phần tử
ngoại lai đối với phụ thuộc hàm và hệ ràng buộc (Mục 4.2.1 Chương
4).
- Phát hiện sự bất thường trong sản xuất kinh doanh (Mục 4.2.2,
Chương 4).
Khi trong dữ liệu báo cáo của doanh nghiệp phản ánh quá trình
sản xuất kinh doanh có sự tương quan hàm s
ố giữa các thuộc tính (phụ
thuộc hàm xấp xỉ loại 2) thì những số liệu phá vỡ sự tương quan, phản
ánh sự bất thường trong số liệu báo cáo. Chúng chứa đựng những sai
sót, gian lận trong đó. Những số liệu đó phải được tách riêng ra để
kiểm tra kỹ hơn. Phương pháp được sử dụng là phương pháp phát hiện
phần tử ngoại lai nhờ phân tích hồi qui được giới thi
ệu ở Chương 2.
- Phát hiện các chứng từ không hợp lệ. Các chứng từ không hợp
lệ là những chứng từ không được ghi chép theo đúng qui định của
nguyên tắc kế toán và chứa đựng những sai sót, gian lận. Thuật toán

- Ứng dụng phụ thuộc hàm mạnh vào phân tích hoạt động sản
xuất kinh doanh. Trong sản xuất kinh doanh chúng ta thấy có nhiều y
ếu
tố có quan hệ với nhau. Có những mối quan hệ phản ánh sự phụ thuộc
mạnh giữa các yếu tố (sự thay đổi của yếu tố này ảnh hưởng mạnh
hoặc quyết định đến yếu tố kia). Ví dụ trong tập dữ liệu phản ánh về
khối lượng (giá trị) sản phẩm được sản xuất với các khối lượng (giá trị)
các nguyên vật li
ệu tham gia vào quá trình sản xuất (có các định mức
qui định) thì mối quan hệ (phụ thuộc) giữa khối lượng sản phẩm được
sản xuất và khối lượng từng loại nguyên vật liệu là các phụ thuộc
mạnh. Việc phân tích kết quả hoạt động SXKD dựa trên việc phân tích
sự phụ thuộc mạnh giữa các yếu tố trong SXKD giúp cho kiểm toán
viên đánh giá được tình hình của hoạt động sản xu
ất kinh doanh
(SXKD) và các nguyên nhân chính ảnh hưởng đến kết quả của hoạt
động SXKD, từ đó giúp cho việc xác định được mục tiêu và nội dung
kiểm toán chính xác hơn.

KẾT L UẬN
Việc tổ chức các cơ sở dữ liệu, xử lý dữ liệu (mà chủ yếu là xử lý
các file dữ liệu), trao đổi thông tin là những công việc chính của những
bài toán ứng dụng công nghệ thông tin vào thực tế. Các nội dung công
việ
c này được thực hiện dựa trên những lý thuyết của công nghệ thông
tin về tổ chức quản lý cơ sở dữ liệu, xử lý trao đổi thông tin, phân tích