Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ωω o0o ωω
BÀI THU HOẠCH MÔN HỌC
HỆ HỖ TRỢ QUYẾT ĐỊNH
HỆ HỖ TRỢ QUYẾT ĐỊNH
Đề tài:
Đề tài:
DATA MINING VÀ ỨNG DỤNG
DATA MINING VÀ ỨNG DỤNG
TRONG PHÒNG CHỐNG XÂM NHẬP
TRONG PHÒNG CHỐNG XÂM NHẬP
GVHD : PGS.TS. Đỗ Phúc
HVTH : Nguyễn Thanh Bình
MSHV : CH1301005
  
HVTH: Nguyễn Thanh Bình Trang 1
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
Tp. HCM, tháng 06 năm 2014
MUC LUC
LỜI MỞ ĐẦU 3
LỜI CẢM ƠN 4
CHƯƠNG I: ĐẶT VẤN ĐỀ 5
CHƯƠNG II: DATA MINING 7
2.1 Giới thiệu về Data mining 7
2.2 Các nhiệm vụ của Data mining 9
2.3 Ứng dụng của Data mining 10
2.4 Các phương pháp khai phá dữ liệu 12
2.4.1 Phương pháp quy nạp (Induction) 12
2.4.2 Cây quyết định và luật 12

internet, v.v. Từ đó, chúng ta thấy được vị trí quan trọng của internet, và các vấn đề
bảo mật, phòng chống/ngăn ngừa các tấn công của hackers trên internet cũng là vấn đề
quan trọng không những cho doanh nghiệp, công ty, trường học, mà còn cho chính
phủ, v.v. Như vậy, việc phòng chống tấn công mạng máy tính là công việc vô cùng
quan trọng và cấp bách hiện nay.
HVTH: Nguyễn Thanh Bình Trang 3
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
LỜI CẢM ƠN
Em xin chân thành cảm ơn thầy Đỗ Phúc đã truyền đạt kiến thức môn Hệ hỗ trợ
quyết định. Qua đó giúp em có đầy đủ kiến thức để hoàn thành bài thu hoạch này.
Nhân đây em cũng xin gửi lời cảm ơn chân thành đến gia đình, bạn bè, đồng
nghiệp đã động viên tin thần cho em trong suốt quá trình học tập của mình.
Sau cùng, em xin kính chúc quý Thầy Cô trong bộ môn Khoa Học Máy Tính
cùng thầy Đỗ Phúc dồi dào sức khỏe để thực hiện sứ mệnh cao đẹp của mình là truyền
đạt kiến thức cho thế hệ mai sau.
Một lần nữa em xin chân thành cảm ơn
TP. HCM, ngày 20 tháng 06 năm 2014
Học viên thực hiện
(ký và ghi rõ họ tên)
HVTH: Nguyễn Thanh Bình Trang 4
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
Nguyễn Thanh Bình
CHƯƠNG I: ĐẶT VẤN ĐỀ
Hiện nay đa số các doanh nghiệp vừa nhỏ, hay lớn, các tổ chức, công ty, trường
học, chính phủ, v.v. đều kết nối internet. Và một điều thách thức hiện nay là vấn đề
bảo mật thông tin trên internet. Bảo mật thông tin trở thành bài toán cấp thiết từ khi
mạng internet phát triển một cách bùng nổ.
Hệ thống thông tin khổng lồ trên internet được chia sẻ trên khắp thế giới. Tuy
nhiên, đồng thời với lợi ích to lớn của nó, mạng internet cùng với các công nghệ liên
quan cũng cho thấy mặt hạn chế tất yếu là tính mất an toàn, dễ bị xâm phạm, tấn công.

mã độc. Một trong những giải pháp để bảo mật thông tin là phát hiện ra các cuộc tấn
công, các mã độc hại, v.v. Để phát hiện các cuộc tấn công, v.v. chúng ta cần xây dựng
hệ thống phát hiện xâm nhập – IDS(Intrusion Detection System) hay hệ thống ngăn
chặn tấn công – IPS(Intrusion Prevention System).
Bài luận này sẽ đề cập đến một vấn đề là kết hợp các kỷ thuật Data mining( khai
phá dữ liệu) và ứng dụng trong phòng chống, phát hiện xâm nhập.
HVTH: Nguyễn Thanh Bình Trang 6
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
CHƯƠNG II: DATA MINING
2.1 Giới thiệu về Data mining
Khai phá dữ liệu (Data mining) là một khái niệm ra đời vào những năm cuối của
thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị
tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai phá dữ liệu liên
quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có
tính chính quy (regularities) trong tập dữ liệu.
Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện
tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) để chỉ toàn bộ
quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu
là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết
xuất ra các mẫu từ dữ liệu. Lịch sử phát triển của Data mining
Những năm 1960: Xuất hiện Cơ sở dữ liệu(CSDL) theo mô hình mạng và mô
hình phân cấp.
Những năm 1970: Thiết lập nền tẩng lý thuyết cho CSDL quan hệ, các hệ quản
trị CSDL quan hệ.
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.

liệu
o Đá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.
Đây là mô hình minh họa cho các quá trình khai thác dữ liệu : Một số ứng dụng
kỹ thuật khai phá dữ liệu trong viễn thông.
HVTH: Nguyễn Thanh Bình Trang 8
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
2.2 Các nhiệm vụ của Data mining
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
HVTH: Nguyễn Thanh Bình Trang 9
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phú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.
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 {A
1
, A
2
,… ,A
n
} và {B
1
, B

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
HVTH: Nguyễn Thanh Bình Trang 10
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
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:
o 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.
o Các phương pháp thống kê hoạt động hoàn toàn theo dữ liệu, nó không sử
dụng tri thức có sẵn về lĩnh vực.
o Kết quả phân tích của hệ thống có thể sẽ rất nhiều và khó có thể làm rõ
được.
o Phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định
phân tích dữ liệu như thế nào và ở đâu.
Khai thác dữ liệu được ứng dụng rộng rãi trong rất nhiều lĩnh vực như:
o Ngân hàng: Xây dựng mô hình dự báo rủi ro tín dụng; tìm kiếm tri thức,
qui luật của thị trường chứng khoán và đầu tư bất động sản; phát hiện
dùng thẻ tín dụng giả trên mạng và là công cụ hữu ích cho dịch vụ quản lý
rủi ro cho thương mại điện tử

về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong (internal node) tương ứng
với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến
đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của
các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng
HVTH: Nguyễn Thanh Bình Trang 12
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn
gọn là cây quyết định.
Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai phá
dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho
các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại đó.
Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành các tập con
dựa theo một kiểm tra giá trị thuộc tính. Quá trình này được lặp lại một cách đệ qui cho
mỗi tập con dẫn xuất. Quá trình đệ qui hoàn thành khi không thể tiếp tục thực hiện việc
chia tách được nữa, hay khi một phân loại đơn có thể áp dụng cho từng phần tử của tập
con dẫn xuất. Một bộ phân loại rừng ngẫu nhiên (random forest) sử dụng một số cây
quyết định để có thể cải thiện tỉ lệ phân loại.
Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính toán
các xác suất có điều kiện. Cây quyết định có thể được mô tả như là sự kết hợp của các
kỹ thuật toán học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một
tập dữ liệu cho trước. Dữ liệu được cho dưới dạng các bản ghi có dạng: (x, y) = (x
1
, x
2
,
x
3
, x
k
, y). Biến phụ thuộc (dependant variable) y là biến mà chúng ta cần tìm hiểu,

nhau của các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên
trong nhóm. Một kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh giá thuộc
tính của các thành phần như là hàm của các tham số của các thành phần. Phương pháp
này được gọi là phương pháp phân hoạch tối ưu (optimal partitioning). Một ví dụ ứng
dụng của phương pháp phân nhóm theo độ giống nhau là cơ sở dữ liệu khách hàng, ứng
dụng của phương pháp tối ưu ví dụ như phân nhóm khách hàng theo số các tham số và
các nhóm thuế tối ưu có được khi thiết lập biểu thuế bảo hiểm.
Mẫu đầu ra của quá trình khai phá dữ liệu sử dụng kỹ thuật này là các tập mẫu
chứa các dữ liệu có chung những tính chất nào đó được phân tách từ cơ sở dữ liệu. Khi
các mẫu được thiết lập, chúng có thể được sử dụng để tái tạo các tập dữ liệu ở dạng dễ
hiểu hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt động cũng như công
việc phân tích. Đối với cơ sở dữ liệu lớn, việc lấy ra các nhóm này là rất quan trọng.
HVTH: Nguyễn Thanh Bình Trang 14
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
CHƯƠNG III: ỨNG DỤNG KỸ THUẬT DATA
MINING TRONG HỆ THỐNG IDS
3.1 Hệ thống IDS
3.1.1 Giới thiệu
Ngày nay, sự phát triển liên tục của công nghệ máy tính là không thể phủ nhận.
Có rất nhiều công ty thiết lập các cổng giao dịch Internet và các khách hàng ngày càng
quan tâm hơn đến việc mua bán trên mạng, các thông tin thu thập được phát triển
nhanh chóng. Mạng Internet đã trở thành một công cụ thông dụng cho việc giao tiếp.
Cùng với sự phát triển của công nghệ thì chúng ta lại phải đối mặt với sự cần
thiết phải tăng cường công tác an ninh. Tính gần gũi, mở rộng và sự phức tạp của
Internet làm cho sự cần thiết của an ninh hệ thống thông tin càng trở nên cấp thiết hơn
bao giờ hết. Việc kết nối hệ thống mạng thông tin vào các hệ thống mạng như Internet
và các hệ thống điện thoại công cộng làm tăng thêm khả năng tiềm ẩn rủi ro đối với hệ
thống.
Đồ án này có tham vọng khám phá và kiểm tra các vấn đề có thể có đối với một
hệ thống phát hiện xâm nhập - IDS, một phần rất quan trọng của an ninh máy tính nói

3.1.2.2 IPS - Intrusion Prevention System:
Là một hệ thống chống xâm nhập, được định nghĩa là một phần mềm hoặc một
thiết bị chuyên dụng có khả năng phát hiện xâm nhập và có thể ngăn chặn các nguy cơ
gây mất an ninh. IDS và IPS có rất nhiều điểm chung, do đó hệ thống IDS và IPS có
thể được gọi chung là IDP- Intrusion Detection and Prevention. IDS chỉ có chức năng
phát hiện xâm nhập dựa vào các mẫu có sẵn. IPS có chức năng ngăn chặn những xâm
nhập được nghi ngờ ở IDS.
3.1.2.3 Vai trò, chức năng của IDS
Phát hiện các nguy cơ tấn công và truy nhập trái phép. Đây là vai trò chính của
một hệ thống phát hiện xâm nhập IDS, nó có nhiệm vụ xác định những tấn công và truy nhập
HVTH: Nguyễn Thanh Bình Trang 16
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
trái phép vào hệ thống mạng bên trong. Hệ thống IDS có khả năng hỗ trợ phát hiện các nguy
cơ an ninh đe dọa mạng mà các hệ thống khác (như bức tường lửa) không có, kết hợp với hệ
thống ngăn chặn xâm nhập IPS giúp cho hệ thống chặn đứng, hạn chế các cuộc tấn công, xâm
nhập từ bên ngoài.
Khả năng cảnh báo và hỗ trợ ngăn chặn tấn công. IDS có thể hoạt động trong
các chế độ làm việc của một thiết bị giám sát thụ động (sniffer mode) hỗ trợ cho các
thiết bị giám sát chủ động hay như là một thiết bị ngăn chặn chủ động (khả năng loại
bỏ lưu lượng khả nghi). IDS hỗ trợ cho các hệ thống an ninh đưa ra các quyết định về
lưu lượng dựa trên địa chỉ IP hoặc cổng cũng như đặc tính của tấn công.
IDS còn có thể cảnh báo và ghi lại các biến cố cũng như thực hiện bắt giữ gói
lưu lượng khi phát hiện tấn công để cung cấp cho nhà quản trị mạng các thông tin để
phân tích và điều tra các biến cố.
Tổ hợp của những thuộc tính và khả năng này cung cấp cho nhà quản trị mạng
khả năng tích hợp IDS vào mạng và tăng cường an ninh đến một mức độ mà trước đây
không thể đạt đến bằng các biện pháp đơn lẻ như bức tường lửa.
3.1.2.4 Cấu trúc và hoạt động bên trong của hệ thống IDS:
Hệ thống phát hiện xâm nhập bao gồm 3 modul chính: Modul thu thập thông tin,
dữ liệu; modul phân tích, phát hiện tấn công; modul phản ứng.

HVTH: Nguyễn Thanh Bình Trang 18
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
Phát hiện tình trạng bất thường (Anomaly detection models): dựa trên sự bất
thường: Ban đầu chúng lưu giữ những mô tả sơ lược về các hoạt đọng bình thường, các
cuộc tấn công xâm nhập gây ra các hoạt động bất bình thường và kỹ thuật này phát
hiện ra các hoạt động bất bình thường đó. Ban đầu, chúng lưu giữ các mô tả sơ lược về
các hoạt động bình thường của hệ thống.
Các cuộc tấn công xâm nhập gây ra các hoạt động bất bình thường và kỹ thuật
này phát hiện ra các hoạt động bất bình thường đó. Phát hiện dựa trên mức ngưỡng
Phát hiện nhờ quá trình tự học. Phát hiện dựa trên những bất thường về giao thức. Ưu
điểm: có thể phát hiện ra các kiểu tấn công mới, cung cấp các thông tin hữu ích bổ sung
cho phương pháp dò sự lạm dụng. Nhược điểm: thường tạo ra một số lượng các cảnh
báo sai làm giảm hiệu suất hoạt động của mạng.
Cảnh báo: Quá trình này thực hiện sinh ra các cảnh báo tùy theo đặc điểm và
loại tấn công, xâm nhập mà hệ thống phát hiện được.
Modul phản ứng: Đây là một điểm khác biệt giữa hệ thống phát hiện xâm nhập
IDS và một hệ thống ngăn chặn xâm nhập IPS. Đối với hệ thống IDS, chúng thường
chỉ có khả năng ngăn chặn rất hạn chế bởi vì chúng dựa trên cơ chế phản ứng thụ động
(passive response). Cơ chế phản ứng thụ động không thể ngăn chặn được tổn thất vì nó
chỉ được đưa ra sau khi tấn công đã ảnh hưởng tới hệ thống. Khi có dấu hiệu của sự tấn
công hoặc thâm nhập, modul phát hiện tấn công sẽ gửi tín hiệu báo hiệu có sự tấn công
hoặc thâm nhập đến modul phản ứng.
Lúc đó modul phản ứng gửi tín hiệu kích hoạt tường lửa thực hiện chức nǎng
ngǎn chặn cuộc tấn công hay cảnh báo tới người quản trị. Tại modul này, nếu chỉ đưa
ra các cảnh báo tới các người quản trị và dừng lại ở đó thì hệ thống này được gọi là hệ
thống phòng thủ bị động. Modul phản ứng này tùy theo hệ thống mà có các chức nǎng
và phương pháp ngǎn chặn khác nhau.
3.1.2.5 Phân loại
IDS được chia làm hai loại chính: HIDS (Host Intrusion Detection System):
triển khai trên máy trạm hoặc server quan trọng, chỉ để bảo vệ riêng từng máy.

thường (hành vi bình thường nhưng được xem như là đáng nghi) không phải là một
hành động xâm nhập được gán cờ như một hành động xâm nhập. Điều này sẽ cho kết
quả chắc chắn sai; các hành vi xâm nhập trái phép không được gán nhãn xâm nhập sẽ
cho kết quả chắc chắn sai, điều này sẽ gây ra tình trạng nguy hiểm hơn.
Trong hệ thống phát hiện xâm nhập dự trên khai phá dữ liệu, chúng ta cần một
cơ sở dữ liệu, tốt nhất là một cơ sở dữ liệu lớn vì khai phá dữ liệu là vô hướng với cơ
sở dữ liệu, cái mà sẽ chứa tất cả các hành vi hay các dấu hiệu vô hại. Sau đó kỹ thuật
khai phá dữ liệu có thể được áp dụng trên cơ sở dữ liệu này để xác định các mối tương
quan và liên kết trong dữ liệu để tìm kiếm một luật mới.
HVTH: Nguyễn Thanh Bình Trang 21
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
3.2.1 Luật phân lớp
Phát hiện xâm nhập có thể được xem như là một vấn đề phân nhóm: ta phải chia
mỗi bản ghi của dữ liệu kiểm toán vào một tập rời rạc các hạng mục có thể, bình
thường hay một kiểu xâm nhập cụ thể.
Căn cứ vào tập các bản ghi, cái mà có một thuộc tính là lớp nhãn, thuật toán
phân lớp có thể tính một mô hình mà sử dụng các giá trị thuộc tính đúng đắn nhất để
biểu diễn cho mỗi khái niệm. Ví dụ, xét các bản ghi kết nối sử dụng giao thức telnet ở
hình dưới. Ở đây, hot là đếm số truy cập vào thư mục hệ thống, tạo và thực hiện các
chương trình… compromise là thuộc tính đến số lỗi “không tìm thấy” file hay đường
dẫn, và “Jump to” các xâm nhập… RIPPER (một thuật toán học máy dựa trên luật
chuẩn được phát triển tại trung tâm nghiên cứu ATT) một chương trình học luật phân
nhóm, các luật tạo ra cho việc phân nhóm các kết nối telnet và một số các luật được
hiển thị trong bảng sau
HVTH: Nguyễn Thanh Bình Trang 22
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
Ở đây, chúng ta thấy rằng quả thật RIPPER chọn các giá trị thuộc tính duy nhất
để xác định các xâm nhập. Những luật này trước tiên có thể được xem xét kỹ và chỉnh
sửa bởi các chuyên gia an toàn, sau đó là được kết hợp vào trong hệ thống phát hiện sự
lạm dụng. Sự chính xác của một môt hình phân nhóm phụ thuộc trực tiếp vào tập các

Mục đích của phân cụm là tìm ra bản chất bên trong các nhóm của dữ liệu. Các
thuật toán phân cụm (Clustering Algorithms) đều sinh ra các cụm (clusters). Tuy nhiên,
không có tiêu chí nào là được xem là tốt nhất để đánh hiệu của của phân tích phân cụm,
điều này phụ thuộc vào mục đích của phân cụm như: data reduction, “natural clusters”,
“useful” clusters, outlier detection.
HVTH: Nguyễn Thanh Bình Trang 24
Tiểu luận Hệ hỗ trợ quyết định PGS.TS Đỗ Phúc
CHƯƠNG IV- XÂY DỰNG CHƯƠNG TRÌNH
PHÁT HIỆN XÂM NHẬP
4.1 Thuật toán phân cụm
4.1.1 Thuật toán gom cụm bằng phương pháp K-means
Thuật toán k-means phân hoạch một tập n object vào trong k cluster sao cho các
đối tượng trong một cluster có độ tương tự cao và các đối tượng trong các cluster khác
nhau có độ tương tự thấp. Mỗi cluster được đại diện bởi trọng tâm (cluster mean) của
nó. Phương pháp k-means phân hoạch một đối tượng vào các cụm dựa trên khoảng
cách của đối tượng đó đến trọng tâm của các cụm. Một đối tượng được phân vào một
cluster nếu khoảng cách từ đối tượng đó đến cluster đang xét là nhỏ nhất. Sau đó các
cluster mean được cập nhật. Quá trình lặp đi lặp lại cho đến khi hàm mục tiêu đồng
qui. Một cách điển hình, hàm mục tiêu square-error được sử dụng:
2
1
∑ ∑
= ∉
−=
k
i Cp
i
i
mpE
Trong đó, p là đối tượng thuộc cluster C