MỤC LỤC
TRANG PHỤ BÌA
LỜI CAM ĐOAN
LỜI CẢM ƠN
MỤC LỤC
MỞ ĐẦU 1
CHƢƠNG I: KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC 3
1.1. Khai phá dữ liệu 3
1.1.1. Khái niệm 3
1.1.2. Khai phá dữ liệu và phát hiện tri thức 4
1.1.3. Quá trình phát hiện tri thức từ cơ sở dữ liệu 4
1.1.3.1. Xác định bài toán 5
1.1.3.2. Thu thập và tiền xử lý 5
1.1.3.3. Khai phá dữ liệu và rút ra các tri thức 6
1.1.3.4. Phát biểu và đánh giá kết quả 6
1.1.3.5. Sử dụng tri thức đã phát hiện 6
1.2. Các phƣơng pháp khai phá dữ liệu 7
1.2.1. Phƣơng pháp quy nạp . 7
1.2.2. Cây quyết định và luật 7
1.2.3. Khai phá luật kết hợp 8
1.2.3.1. Giới thiệu 8
1.2.3.2. Các khái niệm cơ bản 8
1.2.3.3. Thuật toán khai phá dữ liệu bằng luật kết hợp 9
1.2.4. Mạng Neuron 11
1.2.5. Giải thuật di truyền 11
1.3. Ứng dụng của khai phá dữ liệu 12
CHƢƠNG II: HỆ HỖ TRỢ RA QUYẾT ĐỊNH VÀ MÔ HÌNH HỖ TRỢ
QUYẾT ĐỊNH 13
2.1. Hệ hỗ trợ ra quyết định 13
2.1.1. Khái niệm 13
4.1. Bài toán 43
4.3. Chƣơng trình ứng dụng 50
4.3. Kết quả thực nghiệm 53
KẾT LUẬN 54
DANH SÁCH CÁC TỪ VIẾT TẮT
DANH SÁCH CÁC HÌNH
DANH SÁCH CÁC BẢNG
TÀI LIỆU THAM KHẢO -1-
MỞ ĐẦU
Khai phá dữ liệu (Data mining) là một lĩnh vực khoa học tiềm năng, mang lại
nhiều lợi ích thiết thực. Mục đích của việc khai phá dữ liệu là tìm ra đƣợc mối
tƣơng quan tiềm ẩn trong cơ sở dữ liệu mà các phƣơng pháp phân tích dữ liệu
truyền thống chƣa làm đƣợc hay xử lý chƣa thật sự tốt. Trong đó, khai phá dữ liệu
và phát hiện tri thức đã trở thành một lĩnh vực nghiên cứu sôi động, thu hút sự quan
tâm của rất nhiều ngƣời trên khắp các lĩnh vực khác nhau nhƣ các hệ cơ sở dữ liệu,
thống kê, chiết xuất thông tin, nhận dạng, học máy, trí tuệ nhân tạo, v.v . . .
Việc nghiên cứu khai phá dữ liệu trong lĩnh vực giáo dục đào tạo vẫn còn
chƣa đƣợc quan tâm đúng mức. Trƣớc đây, có một số nhà nghiên cứu đã sử dụng hồ
sơ học sinh, sinh viên, đặc biệt là thông tin về điểm để dự báo kết quả học tập toàn
khoá hoặc từng giai đoạn. Một số phƣơng pháp dự báo thƣờng đƣợc sử dụng: Đại
số và logic, Hồi quy tuyến tính, Cây quyết định (Decision Tree), mạng Bayes
(Bayesian Network),… Hồi quy Bayes đƣợc áp dụng cho bài toán dự đoán dùng
công thức Bayes để phân lớp, phƣơng pháp này mang lại nhiều kết quả khả quan.
Đây là phƣơng pháp học phân lớp có giám sát và dựa trên xác suất.
Kết quả học tập đƣợc xem là mức độ thành công trong học tập của học sinh
khi xem xét trong mối quan hệ với mục tiêu đã xác định, các chuẩn kiến thức và kỹ
tốn kém và dễ dẫn đến những sai lệch. Do đó để có thể khai phá hiệu quả các cơ sở
dữ liệu lớn cần phải có những kỹ thuật mới, đó là các kỹ thuật khai phá dữ liệu
(Data Mining).
Khai phá dữ liệu là một lĩnh vực khoa học khá mới, nhằm tự động hóa khai
thác những thông tin, tri thức hữu ích, tiềm ẩn trong các cơ sở dữ liệu cho các tổ
chức, doanh nghiệp, từ đó thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh
của tổ chức, doanh nghiệp này. Các kết quả nghiên cứu cùng với những ứng dụng
thành công trong khai phá dữ liệu, khám phá tri thức cho thấy khai phá dữ liệu là
một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng thời có ƣu thế hơn
hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện nay, khai phá dữ liệu
đƣợc ứng dụng rộng rãi trong các lĩnh vực nhƣ: Phân tích dữ liệu hỗ trợ ra quyết
định, điều trị y học, tin-sinh học, thƣơng mại, tài chính, bảo hiểm, text mining, web
mining .
Do sự phát triển nhanh chóng về phạm vi áp dụng và các phƣơng pháp tìm
kiếm tri thức, nên đã có nhiều quan điểm khác nhau về khai phá dữ liệu [7].
1.1.1. Khái niệm
Khai phá dữ liệu [7] là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên
trong lƣợng lớn dữ liệu đƣợc lƣu trữ trong các cơ sở dữ liệu, kho dữ liệu… Hiện
-4-
nay, ngoài thuật ngữ khai phá dữ liệu, ngƣời ta còn dùng một số thuật ngữ khác có ý
nghĩa tƣơng tự nhƣ: khai phá tri thức từ cơ sở dữ liệu (knowlegde mining from
databases), trích lọc dữ liệu (knowlegde extraction), phân tích dữ liệu/mẫu
(data/pattern analysis), khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu (data
dredging). Nhiều ngƣời coi khai phá dữ liệu là một thuật ngữ thông dụng khác là
khám phá tri thức trong cơ sở dữ liệu (Knowlegde Discovery in Databases – KDD)
là nhƣ nhau.
1.1.2. Khai phá dữ liệu và phát hiện tri thức
Yếu tố thành công trong nhiều hoạt động là biết sử dụng thông tin có hiệu quả.
Điều đó có nghĩa là từ các dữ liệu có sẵn phải tìm ra những thông tin tiềm ẩn mà
việc xác định lĩnh vực và định nghĩa bài toán giúp định hƣớng cho giai đoạn tiếp
theo thu thập và tiền xử lý dữ liệu.
1.1.3.2. Thu thập và tiền xử lý
Các cơ sở dữ liệu thu đƣợc thƣờng chứa rất nhiều thuộc tính nhƣng lại không
đầy đủ, không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy giai đoạn thu
thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình phát hiện tri thức từ
cơ sở dữ liệu. Có thể nói giai đoạn này chiếm từ 70%-80% giá thành trong toàn bộ
bài toán.
Ngƣời ta chia giai đoạn và tiền xử lý dữ liệu nhƣ: Gom dữ liệu, chọn dữ liệu,
làm sạch, mã hoá dữ liệu, làm giàu, đánh giá và trình diễn dữ liệu.
-6-
1.1.3.3. Khai phá dữ liệu và rút ra các tri thức
Là trích ra các mẫu hoặc các mô hình ẩn dƣới các dữ liệu, giai đoạn này rất
quan trọng bao gồm các công đoạn nhƣ: chức năng, nhiệm vụ và mục đích của khai
phá dữ liệu, dùng phƣơng pháp khai phá nào? Thông thƣờng các bài toán khai phá
dữ liệu bao gồm: Các bài toán mang tính mô tả – đƣa ra tính chất chung của dữ liệu,
bài toán dự báo – bao gồm cả việc phát hiện các suy diễn dựa trên dữ liệu hiện có.
1.1.3.4. Phát biểu và đánh giá kết quả
Các tri thức phát hiện từ cơ sở dữ liệu cần đƣợc tổng hợp dƣới dạng các báo
cáo phục vụ cho các mục đích hỗ trợ các quyết định khác nhau.
Do nhiều phƣơng pháp khai thác có thể đƣợc áp dụng nên các kết quả có mức độ
tốt, xấu khác nhau. Việc đánh giá các kết quả thu đƣợc là cần thiết, các tri thức phát
hiện từ cơ sở dữ liệu cần đƣợc tổng hợp dƣới dạng các báo cáo phục vụ cho các mục
đích hỗ trợ các quyết định khác nhau.
Do nhiều phƣơng pháp khai thác có thể đƣợc áp dụng nên các kết quả có mức độ
tốt, xấu khác nhau. Việc đánh giá các kết quả thu đƣợc là cần thiết, giúp tạo cơ sở cho
những quyết định chiến lƣợc. Thông thƣờng, chúng đƣợc tổng hợp, so sánh bằng các
biểu đồ và đƣợc kiểm nghiệm.
1.1.3.5. Sử dụng tri thức đã phát hiện
cây, qua các cạnh tƣơng ứng với các giá trị, thuộc tính của đối tƣợng tới lá.
Tạo luật: Các luật đƣợc tạo ra nhằm suy diễn một số mẫu dữ liệu có ý nghĩa
về mặt thống kê. Các luật có dạng Nếu P thì Q, với P là mệnh đề đúng với một phần
trong CSDL, Q là mệnh đề dự đoán.
Cây quyết định và luật có ƣu điểm là hình thức mô tả đơn giản, mô hình suy
diễn khá dễ hiểu đối với ngƣời sử dụng. Tuy nhiên, giới hạn của nó là mô tả cây và
luật chỉ có thể biểu diễn đƣợc một số dạng chức năng và vì vậy giới hạn về cả độ
chính xác của mô hình.
-8-
1.2.3. Khai phá luật kết hợp
1.2.3.1. Giới thiệu
Khai phá luật kết hợp [8]: Là tìm các mẫu phổ biến, sự kết hợp, sự tƣơng
quan, hay các cấu trúc nhân quả giữa các tập đối tƣợng trong các cơ sở dữ liệu giao
tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác.
1.2.3.2. Các khái niệm cơ bản
- Gọi I = {I
1
, I
2
, , I
m
} là tập m thuộc tính riêng biệt, mỗi thuộc tính gọi là
một mục.
- Gọi D là một cơ sở dữ liệu chứa n giao dịch, trong đó mỗi bản ghi T là một
giao dịch và chứa các tập mục, X I. T đƣợc gán nhãn với một định danh
duy nhất.
- Ta nói rằng, một giao dịch T D hỗ trợ một tập X I nếu nó chứa tất cả
các mục của X.
- Một tập mục X đƣợc gọi là tập mục k phần tử (k-itemset) nếu lực lƣợng của
[BT1] Tìm tất cả các tập mục có độ hỗ trợ lớn hơn hay bằng minsup cho
trƣớc (tập mục phổ biến).
[BT2] Sử dụng các tập mục phổ biến để sinh ra các luật kết hợp với độ tin
cậy minconf cho trƣớc [8].
Thuật toán Apriori [8]
Đầu vào: CSDL giao dịch D và ngƣỡng phổ biến minsup
Đầu ra: FIs chứa tất cả các tập phổ biến của D
Mã giả:
Gọi C
k
: Tập các ứng viên có kích thƣớc k
L
k
: Các tập phổ biến có kích thƣớc k
-10-
Ví dụ:
Cho CSDL dƣới đây, minsup = 50%, confsup = 60%. Tìm luật kết hợp
TID
Tập các mục trong giao dịch
1
Bánh mì, Bơ, Trứng
2
Bơ, Sữa, Trứng
3
Bơ
4
Bánh mì, Bơ
C1:
Tập mục
Độ hỗ trợ
Bánh mì
50%
Bơ
100%
Trứng
50%
Sữa
25%
1.2.4. Mạng Neuron
Mạng Neuron là tiếp cận tính toán mới liên quan tới việc phát triển cấu trúc
toán học và khả năng học. Các phƣơng pháp là kết quả của việc nghiên cứu mô hình
học của hệ thống thần kinh con ngƣời.
Mạng Neuron có thể đƣa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính
xác và có thể đƣợc sử dụng để chiết xuất các mẫu và phát hiện ra các xu hƣớng quá
phức tạp mà con ngƣời cũng nhƣ các kỹ thuật máy tính khác không thể phát hiện
đƣợc. Khi đề cập đến khai thác dữ liệu, ngƣời ta thƣờng đề cập nhiều đến mạng
Neuron. Tuy mạng Neuron có một số hạn chế gây khó khăn trong việc áp dụng và
phát triển nhƣng nó cũng có những ƣu điểm đáng kể.
Nguồn [7]
Hình 1.2: Thể hiện sơ đồ khai phá dữ liệu bằng mạng Neuron
Một trong số những ƣu điểm phải kể đến của mạng Neuron là khả năng tạo ra
các mô hình dự đoán có độ chính xác cao, có thể áp dụng đƣợc cho rất nhiều loại
bài toán khác nhau, đáp ứng đƣợc nhiệm vụ đặt ra của khai phá dữ liệu nhƣ phân
lớp, gom nhóm, mô hình hóa, dự báo các sự kiện phụ thuộc vào thời gian, v.v.
1.2.5. Giải thuật di truyền
Giải thuật di truyền, nói theo nghĩa rộng là mô phỏng lại hệ thống tiến hóa
trong tự nhiên, chính xác hơn đó là giải thuật chỉ ra tập các cá thể đƣợc hình thành,
đƣợc ƣớc lựợng và biến đổi nhƣ thế nào? Ví dụ nhƣ xác định xem làm thế nào để
Dữ liệu
Mô hình mạng
Neuron
Mẫu chiết xuất
đƣợc
-12-
lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào sẽ bị loại bỏ. Giải thuật
cũng mô phỏng lại yếu tố gen trong nhiễm sắc thể sinh học trên máy tính để có thể
Trong thập niên 1970, Scott Morton đƣa ra khái niệm đầu tiên về hệ hỗ trợ ra
quyết định (Decision Support Systems - DSS). Ông định nghĩa DSS nhƣ là những
hệ thống máy tính tƣơng tác nhằm giúp những ngƣời ra quyết định sử dụng dữ liệu
và mô hình để giải quyết các vấn đề không có cấu trúc.
Hệ hỗ trợ quyết định - HHTQĐ là các hệ dựa trên máy tính, có tính tƣơng tác,
giúp các nhà ra quyết định dùng dữ liệu và mô hình để giải quyết các bài toán phi
cấu trúc (S. Morton, 1971).
HHTQĐ kết hợp trí lực của con ngƣời với năng lực của máy tính để cải tiến
chất lƣợng của quyết định. Đây là các hệ dựa vào máy tính hỗ trợ cho ngƣời ra
quyết định giải các bài toán nửa cấu trúc (Keen and Scott Morton, 1978).
HHTQĐ là tập các thủ tục dựa trên mô hình nhằm xử lý dữ liệu và phán đoán
của con ngƣời để giúp nhà quản lý ra quyết định (Little, 1970) [6].
+ Thuận lợi của hệ HHTQĐ [6]
Tăng số phƣơng án xem xét, so sánh, phân tích độ nhạy, hiệu quả.
Hiểu rõ các quan hệ nghiệp vụ trong toàn hệ thống tốt hơn
Đáp ứng nhanh trƣớc các tình huống không mong đợi, dễ điều chỉnh và
thay đổi khi cần thiết.
Có thể thực hiện các phân tích phi chính qui
Học tập và hiểu biết thêm các nguồn tài nguyên chƣa đƣợc tận dụng
Cải thiện những cách thực hiện truyền thống
Kiểm soát kế hoạch, tiêu chuẩn hoá các thủ tục tính toán
Tiết kiệm chi phí cho các thủ tục hành chính
Quyết định tốt hơn
Tinh thần đồng đội tốt hơn
-14-
Tiết kiệm thời gian
Dùng các nguồn dữ liệu tốt, có chọn lọc.
+ Các hỗ trợ mong đợi từ HHTQĐ
Thông tin trạng thái và dữ liệu thô
Nguồn [6]
Hình 2.1: Mô hình hệ hỗ trợ ra quyết định
-15-
Phân hệ quản lý dữ liệu (Data Management) gồm một cơ sở dữ liệu
(database) chứa các dữ liệu cần thiết của tình huống và đƣợc quản lý bởi một hệ
quản trị cơ sở dữ liệu (DBMS – Data Base Management System). Phân hệ này có
thể đƣợc kết nối với nhà kho dữ liệu của tổ chức (Data Warehouse) – là kho chứa
dữ liệu của tổ chức có liên quan đến vấn đề ra quyết định. Thực hiện công việc lƣu
trữ các thông tin của hệ và phục vụ cho việc lƣu trữ, cập nhật, truy vấn thông tin.
Phân hệ quản lý mô hình (Model Management) còn đƣợc gọi là hệ quản trị cơ
sở mô hình (MBMS – Model Base Management System) là gói phần mềm gồm các
thành phần về thống kê, tài chính, khoa học quản lý hay các phƣơng pháp định
lƣợng nhằm trang bị cho hệ thống năng lực phân tích, cũng có thể có các ngôn ngữ
mô hình hóa. Thành phần này có thể kết nối với các kho chứa mô hình của tổ chức
hay ở bên ngoài. Bao gồm các mô hình ra quyết định (DSS models) và việc quản lý
các mô hình này. Một số ví dụ của các mô hình này bao gồm: Mô hình nếu thì, Mô
hình tối ƣu, Mô hình tìm kiếm mục đích, Mô hình thống kê, v.v
Phân hệ quản lý dựa vào kiến thức có thể hỗ trợ các phân hệ khác hay hoạt
động độc lập nhằm đƣa ra tính thông minh của quyết định đƣa ra. Nó cũng có thể
đƣợc kết nối với các kho kiến thức khác của tổ chức.
Phân hệ giao diện người dùng (User Interface Management) giúp ngƣời sử
Hƣớng tri thức: Hệ hỗ trợ ra quyết định có thể đề nghị và đƣa ra những
tƣvấn cho ngƣời ra quyết định. Những hệ này là các hệ chuyên gia với một kiến
thức chuyên ngành cụ thể, nắm vững các vấn đề trong chuyên ngành đó và có kỹ
năng để giải quyết những vấn đề này. Các công cụ khai thác dữ liệu cũng có thể
dùng để tạo ra các hệ dạng này.
Theo Holsapple và Whinston (1996):
Phân ra 6 loại hệ hỗ trợ ra quyết định:
- Hƣớng văn bản (Text-Oriented DSS)
- Hƣớng cơ sở dữ liệu (Database-Oriented DSS)
- Hƣớng bảng tính (Spreasheet-Oriented DSS)
- Hƣớng ngƣời giải quyết (Solver-Oriented DSS)
- Hƣớng luật (Rule-Oriented DSS)
- Hƣớng kết hợp (Compound DSS)
-17-
Hƣớng văn bản: Thông tin (bao gồm dữ liệu và kiến thức) đƣợc lƣu trữ dƣới
dạng văn bản. Vì vậy hệ thống đòi hỏi lƣu trữ và xử lý các văn bản một cách hiệu
quả. Các công nghệ mới nhƣ hệ quản lý văn bản dựa trên web, Intelligent Agents
có thể đƣợc sử dụng cùng với hệ này.
Hƣớng cơ sở dữ liệu: Cơ sở dữ liệu đóng vai trò chủ yếu trong hệ này. Thông
tin trong cơ sở dữ liệu thƣờng có cấu trúc chặt chẽ, có mô tả rõ ràng. Hệ này cho
phép ngƣời dùng truy vấn thông tin dễ dàng và rất mạnh về báo cáo.
Hƣớng bảng tính: Một bảng tính là một mô hình để cho phép ngƣời dùng
thực hiện việc phân tích trƣớc khi ra quyết định. Bảng tính có thể bảo gồm nhiều
- Mô hình đƣờng đợi (waitiong line models)
Mô hình dự báo: Mô hình này đƣợc sử dụng nhiều đáng kể trong cách hệ
thống hỗ trợ quản trị, cũng nhƣ đối với mô hình tối ƣu, yêu cầu dữ liệu đầu vào có
liên quan tới các sự kiện trong tƣơng lai.
Mô hình máy học và nhận biết mẫu: Mục tiêu của mô hình này là phát triển
khả năng thông minh hiểu và có khả năng trích ra tri thức từ các kinh nghiệm cũ và
sử dụng lại trong tƣơng lai. Mô hình này đƣợc sử dụng để phát triển các thuật toán
hiệu quả cho việc thực hiện nhiệm vụ trên.
Mô hình tối ƣu: Nhiều tiến trình ra quyết định đƣa ra bởi các công ty hay tổ
chức phức tạp thƣờng theo hƣớng: đƣa ra một vấn đề đƣợc định nghĩa rõ ràng,
ngƣời ra quyết định sẽ đƣa ra một tập các quyết định, giải pháp và sau đó là quá
trình đánh giá hiệu quả, so sánh chọn ra giải pháp tốt nhất. Mô hình phù hợp với các
tiến trình ra quyết định mà bị giới hạn bởi tài nguyên sử dụng, và chúng cần phải sử
dụng một cách hợp lý nhất. Tài nguyên ở đây có thể là con ngƣời, sản phẩm,
nguyên liệu, các thành phần, nhân tố tài chính.
Mô hình quản lý dự án: Một dự án là một tập phức tạp các hoạt động có liên
quan với nhau đƣợc đƣa ra nhằm mục đích hƣớng tới một mục tiêu nhất định đƣợc
đặt ra, nó có thể một sản phẩm công nghiệp, một hệ thống thông tin, sản phẩm mới
hoặc một cấu trúc tổ chức mới, phụ thuộc vào các miền ứng dụng khác nhau. Quá
trình thực thi một dự án yêu cầu tới các kế hoạch và các tiến trình kiểm soát từng
hoạt động độc lập cũng nhƣ tài nguyên về con ngƣời, kỹ thuật và tài chính cần thiết
để đạt đƣợc mục đích cuối cùng.
-19-
Mô hình phân tích nguy cơ: Ngƣời ra quyết định đƣợc yêu cầu chọn lựa một
hƣớng đi trong một số hƣớng có sẵn mà không có các thông tin về ảnh hƣởng của
các các chọn này tới sự việc có thể xảy ra trong tƣơng lai.
Mô hình đƣờng đợi: Mục đích của lý thuyết hàng đợi là điều tra hiện tƣợng
tắc nghẽn xảy ra khi nhu cầu và khả năng cung cấp của một dịch vụ ngẫu nhiên
trong hoạt động hàng ngày.
Bƣớc 1: Học (Training). Mục đích của bƣớc này là xây dựng một mô hình xác
định một tập các lớp dữ liệu. Mô hình này đƣợc xây dựng bằng cách phân tích các
bộ dữ liệu của một cơ sở dữ liệu, mỗi bộ dữ liệu đƣợc xác định bởi giá trị của các
thuộc tính. Giả sử mỗi bộ dữ liệu đã thuộc về một trong các lớp đã đựơc định nghĩa
trƣớc, điều này đƣợc xác định bởi một trong các thuộc tính, gọi là thuộc tính phân
lớp. Trong ngữ cảnh của bài toán phân lớp, mỗi bộ dữ liệu đƣợc xem nhƣ là một
mẫu, một ví dụ, hay một đối tƣợng. Những bộ dữ liệu đƣợc phân tích để xây dựng
mô hình phân lớp đƣợc lấy từ trong tập dữ liệu học hay dữ liệu huấn luyện.
Những bộ dữ liệu riêng lẻ tạo thành tập dữ liệu huấn luyện còn gọi là những
mẫu huấn luyện (training samples) và đƣợc chọn ngẫu nhiên từ một kho các mẫu.
Bƣớc này đƣợc xem là học có giám sát, ngƣợc lại với học có giám sát là học không
có giám sát (unsupervised learing), tiêu biểu là bài toán gom cụm (clustering) trong
đó các lớp mà các mẫu huấn luyện thuộc về là không biết trƣớc và số lớp dữ liệu
cũng không đƣợc biết trƣớc.
Mô hình phân lớp đƣợc đƣa ra sau khi đã phân tích xong tập dữ liệu huấn
luyện thƣờng có dạng là những quy tắc phân lớp, cây quyết định hay các công thức
toán học.
Bƣớc 2: Phân lớp (classification). Bƣớc này sử dụng mô hình phân lớp đã
đƣợc xây dựng ở bƣớc 1 để kiểm tra, đánh giá và thực hiện phân lớp.
Trong mô hình phân lớp, thuật toán phân lớp giữ vai trò trung tâm, quyết định
tới sự thành công của mô hình phân lớp. Do vậy chìa khóa của vấn đề phân lớp dữ
liệu là tìm ra đƣợc một thuật toán phân lớp nhanh, hiệu quả, có độ chính xác cao và
có khả năng mở rộng đƣợc.
-21-
Bƣớc đầu tiên là đánh giá độ chính xác của mô hình phân lớp bằng cách sử
dụng một tập các mẫu đã đƣợc phân lớp để kiểm tra gọi là bộ thử (test set). Những
mẫu này đƣợc chọn ngẫu nhiên và độc lập với các mẫu đã đƣợc học ở bƣớc 1 gọi là
mẫu thử (test sample).
Nếu độ chính xác của một mô hình là chấp nhận đƣợc, thì mô hình đó có thể
B nếu có A". Đại lƣợng này gọi là khả năng (likelihood) xảy ra B khi biết A
đã xảy ra. Chú ý không nhầm lẫn giữa khả năng xảy ra A khi biết B và xác
suất xảy ra A khi biết B.
Khi biết ba đại lƣợng trên, xác suất của A khi biết B cho bởi công thức:
(1)
Từ đó dẫn tới:
A
i
P
B
A
j
P(A
)
n
j=1
2.3.3.2. Mô hình Phân lớp Naive Bayes (NBC)
Mô hình phân lớp Bayes [1],[3] đƣợc áp dụng nhiều nhất trong thực tế là mô
hình phân lớp Naive Bayes.
Phân lớp Naive Bayes ra đời giúp cho việc tính đơn giản hơn dựa trên việc
ứng dụng lý thuyết Bayes. Tính toán các xác suất đó với giả thiết là các thuộc tính
độc lập với nhau (không phụ thuộc nhau).
Cho {C1, C2,… Cn} là phân hoạch của không gian mẫu C (đƣợc xem là các
lớp Ci). Không gian thể hiện X bao gồm tất cả các thể hiện đƣợc mô tả trên tập
thuộc tính (a1, a2, …an) và hàm đích f(x) có thể nhận bất kỳ giá trị nào trong C
(f(x)=Ci | i=1,…,n). Không gian thể hiện X đƣợc xem là các ví dụ học. Khi có một
thể hiện mới với bộ giá trị <a1, a2,…,an>, bộ phân lớp sẽ dự đoán giá trị hàm đích
f(x) hoặc lớp cho thể hiện mới này (f(x){C1, C2,… Cn}).
> trên
mỗi lớp c
i
sẽ là tích của các khả năng của từng thuộc tính riêng biệt trên c
i
phân lớp trong công thức (4) đƣợc sử dụng để phân lớp thể hiện mới này.
2.3.3.3. Các bƣớc thực hiện thuật toán Naive Bayes
Bƣớc 1: Huấn luyện Naive Bayes (dựa vào tập dữ liệu), tính
và
.
Copyright: Tài liệu đại học ©