Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
MỤC LỤC
MỤC LỤC...................................................................................................................................1
DANH MỤC CÁC TỪ VIẾT TẮT............................................................................................4
DANH MỤC CÁC BẢNG.........................................................................................................5
DANH MỤC HÌNH VẼ..............................................................................................................5
LỜI NÓI ĐẦU............................................................................................................................7
Chương 1.....................................................................................................................................9
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU...........................................................................9
1.1 Giới thiệu về khai phá dữ liệu...........................................................................................9
1.2 Các nhiệm vụ của khai phá dữ liệu.................................................................................10
1.3 Các loại dữ liệu được khai phá........................................................................................11
1.4 Lịch sử phát triển của Khai phá dữ liệu..........................................................................11
1.5 Ứng dụng của Khai phá dữ liệu.....................................................................................12
1.6 Phân loại các phương pháp khai phá dữ liệu.................................................................13
1.7 Một số thách thức đặt ra cho việc khai phá dữ liệu.......................................................13
Kết chương................................................................................................................................14
Chương 2...................................................................................................................................14
QUY TRÌNH VÀ PHƯƠNG THỨC THỰC HIỆN KHAI PHÁ DỮ LIỆU............................14
2.1 Quy trình tổng quát thực hiện Khai phá dữ liệu..............................................................14
2.2 Tiến trình khám phá tri thức khi đi vào một bài toán cụ thể...........................................15
2.3 Tiền xử lý dữ liệu............................................................................................................16
2.3.1 Làm sạch dữ liệu......................................................................................................17
2.3.1.1 Các giá trị thiếu.................................................................................................17
2.3.1.2 Dữ liệu nhiễu.....................................................................................................18
2.3.2 Tích hợp và chuyển đổi dữ liệu................................................................................19
2.3.2.1 Tích hợp dữ liệu................................................................................................19
2.3.2.2 Biến đổi dữ liệu.................................................................................................21
2.3.3 Rút gọn dữ liệu (Data reduction).............................................................................22
2.3.3.1 Rút gọn dữ liệu dùng Histogram.......................................................................23
2.3.3.2 Lấy mẫu (Sampling)..........................................................................................24

Chương 3...................................................................................................................................49
ỨNG DỤNG KỸ THUẬT KHAI PHÁ DỮ LIỆU TRONG HỆ THỐNG IDS.......................49
3.1 Giới thiệu chung .............................................................................................................49
3.2 Hệ thống IDS.................................................................................................................49
3.2.2 Hệ thống phát hiện xâm nhập - IDS ........................................................................49
3.1.2.1 Giới thiệu về IDS..............................................................................................49
3.2.2.2 Vai trò, chức năng của IDS..............................................................................50
3.2.2.3 Mô hình hệ thống IDS mức vật lý ....................................................................51
3.2.2.4 Cấu trúc và hoạt động bên trong của hệ thống IDS:.........................................51
3.2.2.5 Phân loại............................................................................................................55
3.3 Khai phá dữ liệu trong IDS.............................................................................................56
3.3.1 NIDS dựa trên khai phá dữ liệu ..............................................................................56
3.3.1.1. Nguồn dữ liệu Audit:.......................................................................................56
3.3.1.2 Xử lý dữ liệu kiểm toán thô và xây dựng các thuộc tính..................................58
3.3.1.3 Các phương thức khai phá dữ liệu trong NIDS................................................59
3.3.2 Tình hình trong nước...............................................................................................63
3.3.3 Tình hình thế giới.....................................................................................................63
3.3.3.1. Phát triển lọc phát hiện xâm nhập tuỳ chỉnh sử dụng khai phá dữ liệu:..........64
3.3.3.2. ADAM: Một thử nghiệm về việc thực hiện việc ứng dụng khai phá dữ liệu
trong hệ thống phát hiện xâm nhập ..............................................................................67
3.3.3.3. Một Framework về việc xây dựng các thuộc tính và các mô hình cho hệ thống
phát hiện xâm nhập (MADAM ID):.............................................................................69
3.3.3.4. Học luật cho phát hiện bất thường (Learning Rules for Anomaly Detection
-LERAD):......................................................................................................................70
3.3.3.5. Phát hiện xâm nhập dựa trên Entropy:.............................................................72
3.3.3.6. MINDS – Minnesota Intrusion Detection System:..........................................75
Kết chương................................................................................................................................81
Chương 4...................................................................................................................................82
XÂY DỰNG CHƯƠNG TRÌNH PHÁT HIỆN TẤN CÔNG DoS SỬ DỤNG KỸ THUẬT
KHAI PHÁ DỮ LIỆU...............................................................................................................82

5.3 Kết luận.........................................................................................................................109
5.4 Hướng phát triển...........................................................................................................110
Kết chương..............................................................................................................................110
TÀI LIỆU THAM KHẢO.......................................................................................................111

3


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
DANH MỤC CÁC TỪ VIẾT TẮT
AS
Analysis Services
BIDS
Intelligence Development Studio
BI Dev Studio
Business Intelligent Developtment
BSM
Basic Security Module
CSDL
Cơ sở dữ liệu
DM
Data mining: Khai phá dữ liệu
DMX
Data Mining eXtensions
DDoS
Distributed Denial of Service
DoS
Denial of Service
DSV
Data Source View

SRSWR
Simple random sample with replacement

4


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
DANH MỤC CÁC BẢNG
Bảng 2.1: Tần số quan sát.........................................................................................................21
Bảng 2.2: Dữ liệu chơi golf.......................................................................................................32
Bảng 2.3: Ví dụ về một CSDL giao dịch – D...........................................................................34
Bảng 2.4: Tập mục thường xuyên minsup = 50%....................................................................35
Bảng 2.5: Luật kết hợp sinh từ tập mục phổ biến ABE............................................................36
Bảng 2.6: Dữ liệu điều tra việc sở hữu các tiện nghi................................................................39
Bảng 2.7: Mẫu dữ liệu khách hàng...........................................................................................40
Bảng 2.8: Một số ví dụ dùng kỹ thuật k-láng giềng..................................................................41
Bảng 3.1: Các bản ghi của giao thức Telnet Records...............................................................59
Bảng 3.2: Ví dụ về các luật RIPPER từ các bản ghi Telnet......................................................60
Bảng 3.3: Mẫu tập dữ liệu huấn luyện......................................................................................71
Bảng 3.4: Thuật toán LERAD...................................................................................................71
Bảng 3.5: Các đặc điểm dựa trên cửa sổ thời gian....................................................................77
Bảng 3.6: Đặc điểm dựa trên Connection-window...................................................................77
Bảng 3.7 Tổng kết một số nghiên cứu NIDS của thế giới........................................................81
Bảng 4.1: Bảng sự kiện cho biến nhị phân...............................................................................85
Bảng 4.2: Một bảng quan hệ trong đó các bệnh nhân được mô tả bằng các biến nhị phân......86
Bảng 4.3: Bảng dữ liệu mẫu chứa các biến ở dạng hỗn hợp.....................................................86

DANH MỤC HÌNH VẼ
Hình 2.1: Data mining – một bước trong quá trình khám phá tri thức.....................................15
Hình 2.2: Tổng quan tiến trình khai phá dữ liệu.......................................................................16

Hình 3.11: Ví dụ về các chuỗi thường xuyên có hành động xen vào hoặc nhiễu.....................65
Hình 3.12: Phát triển bộ lọc tuỳ chỉnh với khai phá dữ liệu.....................................................66
Hình 3.13: Giai đoạn huấn luyện của ADAM..........................................................................67
Hình 3.14: Khai phá xâm nhập với ADAM..............................................................................68
Hình 3.15: Luồng dữ liệu MADAMID.....................................................................................69
Hình 3.16: Luồng hoạt động của phát hiện xâm nhập dựa trên Entropy..................................74
Hình 3.17: Hệ thống MINDS....................................................................................................76
Hình 3.18: Module phân tích kết hợp MINDS.........................................................................78
Hình 3.19: Các phương thức sắp xếp mẫu................................................................................79
Hình 4.1: Minh họa thuật toán k-means....................................................................................90
Hình 4.2: Nguyên lý chung của một tiến trình phát hiện xâm nhập sử dụng kỹ thuật phân cụm
...................................................................................................................................................94
Hình 5.1 Giao diện chính .......................................................................................................103
Hình 5.2 Tiền xử lý dữ liệu.....................................................................................................104
Hình 5.3 Giao diện khai phá...................................................................................................105
Hình 5.4 Màn hình khai phá dữ liệu của giao thức HTTP......................................................106
Hình 5.5 Màn hình tự động khai phá......................................................................................107

6


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS

LỜI NÓI ĐẦU
Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông
tin trong nhiều lĩnh vực của đời sống, kinh tế xã hội trong nhiều năm qua cũng
đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một
tích luỹ nhiều lên. Họ lưu trữ các dữ liệu này vì cho rằng trong nó ẩn chứa
những giá trị nhất định nào đó. Tuy nhiên, theo thống kê thì chỉ có một lượng
nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được phân tích, số

khoảng cách ngắn nhất, K- láng giềng gần nhất, phân cụm, kỹ thuật hiển thị dữ
liệu, mạng neural và thuật toán di truyền.
Chương 3: ỨNG DỤNG KỸ THUẬT KHAI PHÁ DỮ LIỆU TRONG HỆ
THỐNG IDS
Chương giới thiệu chi tiết về hệ thống phá hiện xâm nhập: định nghĩa, mô
hình, phân loại, cấu trúc và hoạt động bên trong; đi vào tìm hiểu việc ứng dụng
khai phá dữ liệu trong hệ thống IDS. Đồng thời cho biết được tình hình trong
nước và thế giới về việc ứng dụng khai phá dữ liệu trong hệ thống IDS và đã đi
vào cụ thể một số nghiên cứu của thế giới trong lĩnh vực này.
Chương 4: XÂY DỰNG CHƯƠNG TRÌNH PHÁT HIỆN TẤN CÔNG
DoS SỬ DỤNG KỸ THUẬT KHAI PHÁ DỮ LIỆU
Trong chương này trình bày việc đưa kỹ thuật khai phá dữ liệu phân cụm
vào một bài toán cụ thể - Phát hiện tấn công DoS. Mà cụ thể thuật toán sẽ sử
dụng ở đây là thuật toán k-mediods. Đồng thời đưa ra sơ đồ phân tích thiết kế
chương trình…
Chương 5: KẾT QUẢ ĐẠT ĐƯỢC – ĐÁNH GIÁ, KẾT LUẬN VÀ
HƯỚNG PHÁT TRIỂN

8


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
Chương này đưa ra một số yêu cầu về việc cài đặt để có thể chạy được
chương trình Demo đính kèm đồ án, các kết quả đã đạt được của đồ án, những
tổng kết và phương hướng phát triển của đồ án.
Sau đây sẽ trình bày chi tiết nội dung của đồ án.

Chương 1
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1 Giới thiệu về khai phá dữ liệu

có: phân cụm (clustering), tóm tắt (summerization), trực quan hoá (visualiztion),
phân tích sự phát triển và độ lệch (Evolution and deviation analyst), phân tích
luật kết hợp (association rules)…
- Các tác vụ khai phá dự báo thực hiện việc suy luận trên dữ liệu hiện thời
để đưa ra các dự báo. Kỹ thuật khai phá dữ liệu dự đoán: Có nhiệm vụ đưa ra
các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm
có: Phân lớp (classification), hồi quy (regression)…
1.2 Các nhiệm vụ của khai phá dữ liệu
Cho đến nay đã có rất nhiều công trình nghiên cứu và phát triển trong lĩnh
vực khai phá dữ liệu. Dựa trên những loại tri thức được khám phá, chúng ta có
thể phân loại như theo các nhiệm cụ như sau:
 Khai phá luật thuộc tính: tóm tắt những thuộc tính chung của tập dữ liệu
nào đó trong cơ sở dữ liệu. Ví dụ như những triệu chứng của một căn bệnh S thì
thường có thể được thể hiện qua một tâp các thuộc tính A.
 Khai phá những luật phân biệt: khai phá những đặc trưng, những thuộc
tính để phân biệt giữa tập dữ liệu này với tập dữ liệu khác. Ví dụ như nhằm phân
biệt giữa các chứng bệnh thì một luật phân biệt được dùng để tóm tắt những
triệu chứng nhằm phân biệt chứng bệnh xác định với những chứng bệnh khác.
10


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
 Khám phá luật kết hợp: khai phá sự kết hợp giữa những đối tượng trong
một tập dữ liệu. Giả sử hai tập đối tượng {A1, A2,… ,An} và {B1, B2,… ,Bn} thì
luật kết hợp có dạng {A1^A2^…^ An) →{B1^ B2^… ^Bn).
 Khám phá luật phân lớp: phân loại dữ liệu vào trong tập những lớp đã biết.
Ví dụ như một số chiếc xe có những đặc tính chung để phân vào các lớp dựa
trên cách tiêu thụ nhiên liệu hoặc có thể phân vào các lớp dựa trên trọng tải…
 Phân nhóm: xác định một nhóm cho một tập các đối tượng dựa trên thuộc
tính của chúng. Một số các tiêu chuẩn được sử dụng để xác định đối tượng có

11


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
- Những năm 1980: Hoàn thiện lý thuyết về CSDL quan hệ và các hệ quản
trị CSDL quan hệ, xuất hiện các hệ quản trị CSDL cao cấp (hướng đối tượng,
suy diễn, ...) và hệ quản trị hướng ứng dụng trong lĩnh vực không gian, khoa
học, công nghiệp, nông nghiệp, địa lý ...
- Những năm 1990-2000: phát triển Khai phá dữ liệu và kho dữ liệu, CSDL
đa phương tiện, và CSDL Web.
1.5 Ứng dụng của Khai phá dữ liệu
Khai phá dữ liệu là một lĩnh vực liên quan tới nhiều ngành học khác như: hệ
CSDL, thống kê, trực quan hoá… hơn nưa, tuỳ vào cách tiếp cận được sử dụng,
khai phá dữ liệu còn có thể áp dụng một số kỹ thuật như mạng nơron, lý thuyết
tập thô, tập mờ, biểu diễn tri thức… So với các phương pháp này, khai phá dữ
liệu có một số ưu thế rõ rệt.
 So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ, khai
phá dữ liệu có thể sử dụng với các CSDL chứa nhiều nhiễu, dữ liệu không đầy
đủ hoặc biến đổi liên tục. Trong khi đó phương pháp học máy chủ yếu được áp
dụng trong các CSDL đầy đủ, ít biến động và tập dữ liệu không qua lớn
 Phương pháp hệ chuyên gia: phương pháp này khác với khai phá dữ liệu ở
chỗ các ví dụ của chuyên gia thường ở mức cao hơn nhiều so với các dữ liệu
trong CSDL, và chúng thường chỉ bao hàm được các trường hợp quan trọng.
Hơn nữa các chuyên gia sẽ xác nhận giá trị và tính hữu ích của các mẫu phát
hiện được.
 Phương pháp thống kê là một trong những nên tảng lý thuyết của khai phá
dữ liệu, nhưng khi so sánh hai phương pháp với nhau ta có thể thấy các phương
pháp thống kê còn tồn tại một số điểm yếu mà khai phá dữ liệu khắc phục được:
- Các phương pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có
cấu trúc trong rất nhiều CSDL.

 Vv……và nhiều lĩnh vực khác
 Một số ứng dụng của khai phá dữ liệu trong lĩnh vực kinh doanh:
∗ BRANDAID: mô hình marketing linh hoạt tập chung vào hàng tiêu dùng
đóng gói.
∗ CALLPLAN: giúp nhân viên bán hàng xác định số lần viếng thăm của
khách hàng triển vọng và khách hàng hiện có.
∗ DETAILER: xác định khách hàng nào nên viếng thăm và sản phẩm nào
nên giới thiệu trong từng chuyến viếng thăm,
∗ GEOLINE: mô hình thiết kế địa bàn tiêu thụ và dịch vụ.
∗ MEDIAC: Giúp người quảng cáo mua phương tiện trong một năm, lập kế
hoạch sử dụng phương tiện bao gồm phác hoạ khúc thị trường, ước tính
tiềm năng
1.6 Phân loại các phương pháp khai phá dữ liệu
Chúng ta có thể phân lớp hệ thống khai phá dữ liệu theo các tiêu chuẩn sau:
Phân lớp dựa trên loại dữ liệu được khai phá: những hệ thống khai phá dữ
liệu làm việc với cơ sở dữ liệu quan hệ, nhà kho dữ liệu, cơ sở dữ liệu giao tác,
cơ sở dữ liệu hướng đối tượng, đa phương tiện và Web…
Phân lớp dựa trên kiểu tri thức khai phá: hệ thống khai phá dữ liệu xuất
kết quả kiểu tóm tắt, mô tả, luật kết hợp, phân lớp, phân nhóm và dự báo…
Phân lớp dựa trên loại kỹ thuật được sử dụng: hệ thống khai phá sử dụng
các kỹ thuật OLAP, kỹ thuật máy học (cây quyết định, mạng neural, thuật giải
tiến hóa, tập thô và tập mờ…).
Phân lớp dựa trên lĩnh vực áp dụng khai phá: hệ thống được dùng trong
nhiều lĩnh vực: sinh học, y khoa, thương mại và bảo hiểm…
1.7 Một số thách thức đặt ra cho việc khai phá dữ liệu
 Các cơ sở dữ liệu lớn
 Số chiều lớn
 Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không
còn phù hợp.
 Dữ liệu bị thiếu hoặc nhiễu

5)
6)
7)

Quá trình này gồm các bước:
Làm sạch dữ liệu (data cleaning): Loại bỏ nhiễu hoặc các dữ liệu không
thích hợp.
Tích hợp dữ liệu (data integration): Tích hợp dữ liệu từ các nguồn khác
nhau như: CSDL, Kho dữ liệu, file text…
Chọn dữ liệu (data selection): Ở bước này, những dữ liệu liên quan trực tiếp
đến nhiệm vụ sẽ được thu thập từ các nguồn dữ liệu ban đầu.
Chuyển đổi dữ liệu (data transformation): Trong bước này, dữ liệu sẽ được
chuyển đổi về dạng phù hợp cho việc khai phá bằng cách thực hiện các thao
tác nhóm hoặc tập hợp.
Khai phá dữ liệu (data mining): Là giai đoạn thiết yếu, trong đó các phương
pháp thông minh sẽ được áp dụng để trích xuất ra các mẩu dữ liệu.
Đánh giá mẫu (pattern evaluation): Đánh giá sự hữu ích của các mẫu biểu
diễn tri thức dựa vào một số phép đo.
Trình diễn dữ liệu (Knowlegde presention): Sử dụng các kỹ thuật trình diễn
và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử
dụng.

Hình 2.1: Data mining – một bước trong quá trình khám phá tri thức
2.2 Tiến trình khám phá tri thức khi đi vào một bài toán cụ thể
Chính vì mục tiêu khám phá trí thức ngầm định trong cơ sở dữ liệu nên quá
trình khai phá thường phải qua một số các giai đoạn cần thiết. Bao gồm những
giai đoạn chuẩn bị dữ liệu khai phá, giai đoạn khai phá dữ liệu và cuối cùng là
giai đoạn chuyển kết quả khai phá sang những tri thức cho con người hiểu được.
Chi tiết các bước thực hiện được mô tả trong bảng tóm tắt như sau:
15

tìm hiểu chi tiết về quá trình tiền xử lý trong tiến trình.
2.3 Tiền xử lý dữ liệu
16


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
Dữ liệu trong thực tế thường không sạch, và không nhất quán. Các kỹ
thuật tiền xử lý dữ liệu có thể cải thiện được chất lượng của dữ liệu, do đó nó
giúp các quá trình khai phá dữ liệu chính xác và hiệu quả. Tiền xử lý dữ liệu là
một bước quan trọng trong quá trình khám phá tri thức, bởi vì chất lượng các
quyết định phải dựa trên chất lượng của dữ liệu. Quá trình tiền xử lý dữ liệu bao
gồm: Làm sạch dữ liệu, tích hợp và biến đổi dữ liệu, rút gọn dữ liệu, rời rạc hóa
dữ liệu và xây dựng các lược đồ phân cấp khái niệm.

Hình 2.3: Các hình thức tiền xử lý dữ liệu
2.3.1 Làm sạch dữ liệu
Dữ liệu trong thực tế thường không đầy đủ, nhiễu, và không nhất quán. Quá
trình là sạch dữ liệu sẽ cố gắng điền các giá trị thiếu, loại bỏ nhiễu, và sửa chữa
sự không nhất quán của dữ liệu.
2.3.1.1 Các giá trị thiếu
Các phương pháp xử lý giá trị thiếu:
1. Bỏ qua bộ có giá trị thiếu: Phương pháp này thường được sử dụng khi
nhãn lớp bị thiếu (thường trong tác vụ khai phá dữ liệu phân lớp, classification).
Phương pháp này rất không hiệu quả, trừ khi một bộ chứa khá nhiều thuộc tính
với các giá trị thiếu. Đặc biệt phương pháp này rất kém hiệu quả khi phần trăm
giá trị thiếu trong từng thuộc tính là đáng kể.
2. Điền vào bằng tay các giá trị thiếu: Cách tiếp cận này tốn thời gian và
không khả thi khi thực hiện trên tập dữ liệu lớn với nhiều giá trị thiếu.
3. Sử dụng một hằng số toàn cục để điền vào các giá trị thiếu: Thay thế toàn
bộ giá trị thiếu của các thuộc tính bằng một hằng số như "Unknown" hay ∞. Nếu

Làm trơn bằng giá trị trung vị của bin: Mỗi giá trị trong bin được thay thế
bởi giá trị trung vị của bin.
Làm trơn bằng các biên của bin: Giá trị lớn nhất và giá trị nhỏ nhất trong
một bin được dùng nhận biết biên của bin. Mỗi giá trị của bin khi đó được
thay thế bởi giá trị biên gần nhất.
Bin có độ rộng càng lớn thì tập dữ liệu thu được sẽ càng "trơn".
Ví dụ 2.1: Cho dữ liệu của price (tính bằng $) đã được sắp xếp: 4, 8, 15,
21, 21, 24, 25, 28, 34.
Phân dữ liệu vào các bin (tần số bằng nhau):
Bin 1: 4, 8, 15
Bin 2: 21, 21, 24
Bin 3: 25, 28, 34
Làm trơn bằng giá trị trung bình của bin:
Bin 1: 9, 9, 9
Bin 2: 22, 22, 22
Bin 3: 29, 29, 29
Làm trơn bằng các biên của bin
18


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
Bin 1: 4, 4, 15
Bin 2: 21, 21, 24
Bin 3: 25, 25, 34
2. Phương pháp hồi qui: Dữ liệu có thể làm trơn bằng cách khớp nó với một
hàm nào đó, chẳng hạn như hàm hồi qui. Phương pháp hồi qui tuyến tính tìm
một đường thẳng tối ưu để khít với 2 thuộc tính (hay 2 biến), do đó một thuộc
tính có thể dùng để dự đoán thuộc tính còn lại. Hồi qui tuyến tính đa bộ là một
sự mở rộng của hồi qui tuyến tính đơn, trong đó hàm hồi qui chứa nhiều hơn 2
thuộc tính dự báo và dữ liệu được làm khít với một bề mặt đa chiều.

19


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
- Sự dư thừa dữ liệu: Giá trị một thuộc tính có thể được tính toán từ giá trị
của các thuộc tính khác. Sự không nhất quán trong việc đặt tên các thuộc tính
cũng có thể gây ra kết quả dư thừa trong tập dữ liệu. Một vài sự dư thừa các
thuộc tính có thể được dò tìm bằng phép phân tích tương quan. Cho 2 thuộc tính,
phép phân tích tương quan có thể đo được một thuộc tính có liên quan chặt chẽ
với thuộc tính khác hay không trên cở sở các dữ liệu sẵn có. Đối với các thuộc
tính số, chúng ta có thể tính toán sự liên quan giữa hai thuộc tính, A và B, bằng
cách tính hệ số tương quan:
N

a A, B =

∑ (ai − A)(bi − B)
i =1

Nσ Aσ B

N

=

∑ (a b ) − N AB
i =1

i i


(oij − eij ) 2
eij

i =1 j =1

Trong đó oij là tần số quan sát của sự kiện chung (A i;Bj) và eij là tần số mong
đợi của (Ai;Bj) được tính bởi:
e11 =

count ( A = ai ) × count ( B = b j )
N

,

Thống kê χ2 kiểm tra giả thuyết A và B có độc lập hay không. Phép kiểm tra
dựa trên một mức độ ý nghĩa, với (r-1)x(c-1) mức tự do. Nếu giả thuyết bị loại ta
kết luận rằng A và B phụ thuộc.
20


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
Ví dụ 2.2: Phép phân tích tương quan của các thuộc tính phân loại sử dụng
χ . Giả sử rằng một nhóm 1500 người được điều tra. Giới tính của mỗi người
được chú ý. Mỗi người được hỏi xem có thích tiểu thuyết hư cấu hay không. Vì
vậy chúng ta có hai thuộc tính: gender và prefered-reading. Tần số quan sát
(hay count) của mỗi possible joint event được ghi lại trong bảng (bảng 2.1) sau:
Male
Female
Total
fiction

+
90
210
360
840

= 284.44 + 121.90 + 71.11 + 30.48 = 507.93
Mức tự do cho bảng 2.1 là (2-1)x(2-1)=1. Cho một mức tự do, giá trị χ2 cần
bác bỏ giả thuyết ở 0.001 mức ý nghĩa là 10.828 (số này có được do tra bảng,
các bảng này thường có trong các sách thống kê). Từ kết quả tính toán ở trên,
chúng ta có thể loại bỏ giả thuyết prefered_reading và gender là không phụ
thuộc và rút ra kết luận: 2 thuộc tính trên có tương quan với nhau.
2.3.2.2 Biến đổi dữ liệu
Trong biến đổi dữ liệu, dữ liệu được chuyển đổi hay hợp nhất về dạng phù
hợp cho việc KTDL. Biến đổi dữ liệu bao gồm những việc sau đây:
- Làm trơn, tức là loại bỏ nhiễu ra khỏi dữ liệu. Các kỹ thuật bao gồm:
binning, regression, và clustering.
- Kết hợp, trong đó các phép toán tóm tắt (summary) hay các phép toán kết
hợp (aggregation) được áp dụng cho dữ liệu. Ví dụ, dữ liệu bán hàng hàng ngày
có thể được tính toán theo tháng hay theo năm. Bước này có thể sử dụng trong
việc xây dựng khối dữ liệu của dữ liệu ở nhiều mức.
- Khái quát hóa dữ liệu, trong đó dữ liệu ở mức khái niệm thấp hay dữ liệu
thô được tổng hợp ở khái niệm mức cao hơn.
- Chuẩn hóa, trong đó thuộc tính dữ liệu được tính tỉ lệ sao cho nó nằm trong
một khoảng nhỏ nào đó ví dụ như -1 đến 1; 0 đến 1.
Xây dựng thuộc tính (hay xây dựng đặc tính), trong đó các thuộc tính mới
được xây dựng và được thêm vào tập thuộc tính đã cho để trợ giúp cho quá trình
KTDL.
Các phương pháp chuẩn hóa dữ liệu:



v
10 j

trong đó j là giá trị nguyên nhỏ nhất mà Max(|v'|)


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS

Hình 2.4: Một histogram cho price sử dụng singleton bucket biểu diễn một cặp
price value/frequency

Hình 2.5: Một histogram có độ rộng bằng nhau cho price
Phân hoạch các giá trị thuộc tính:
Độ rộng bằng nhau: Trong một histogram độ rộng bằng nhau, độ rộng của
từng miền giá trị bucket là một hằng số (như độ rộng $10 của các bucket).
Độ sâu bằng nhau (hay độ cao bằng nhau): Trong một histogram độ sâu
bằng nhau, các bucket được tạo ra sao cho tần suất của từng bucket là một hằng
số (có nghĩa là mỗi bucket chứa đựng cùng một số mẫu dữ liệu kề nhau).
Tối ưu-V: Nếu chúng ta xét tất cả các histogram có thể có của một số bucket
đã cho, histogram tối ưu-V là histogram có độ khác biệt thấp nhất. Độ lệch
histogram là một tổng có trọng số của các giá trị gốc mà từng bucket biểu diễn,
trong đó trọng số của bucket bằng số giá trị trong bucket.
MaxDiff: Trong một histogram MaxDiff, xét sự khác biệt giữa từng cặp giá
trị liền kề (adjacent). Một biên của bucket được thiết lập giữa từng cặp cho các
cặp có β-1 sự khác biệt lớn nhất, trong đó β là số bucket được người sử dụng xác
định.
2.3.3.2 Lấy mẫu (Sampling)
Lấy mẫu có thể được sử dụng như một kỹ thuật rút gọn dữ liệu bởi ví nó cho
phép một tập dữ liệu lớn được biểu diễn bằng một tập mẫu ngẫu nhiên nhỏ hơn
24


Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS
nhiều của dữ liệu. Giả sử một tập dữ liệu D có N bộ. Các phương pháp có thể

ngừng của tập dữ liệu rút gọn. Tập dữ liệu này có thể được tiếp tục cải tiến bằng
cách tăng kích thước tập mẫu.
Ngoài các phương pháp đã nêu ở trên còn có một số phương pháp khác để
rút gọn dữ liệu như: clustering, rút gọn tập thuộc tính, rút gọn miền giá trị...

25