lOMoARcPSD|17343589
TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO CHUYÊN ĐỀ HỌC PHẦN
KHAI PHÁ DỮ LIỆU
ĐỀ TÀI:
ỨNG DỤNG THUẬT TOÁN SVM
ĐỂ DỰ ĐOÁN BỆNH UNG THƯ PHỔI
Sinh viên thực hiện:
LƯU VĂN QUÂN
TRẦN VĂN HÀO
Giảng viên hướng dẫn:
Ngành:
Chuyên ngành:
Lớp:
Khóa:
Ts.NGUYỄN THỊ THANH TÂN
CÔNG NGHỆ THÔNG TIN
CÔNG NGHỆ PHẦN MỀM
D13CNPM4
2018-2023
Hà Nội, tháng 06 năm 2021
PHIẾU CHẤM ĐIỂM
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
STT Họ và tên
Nội dung thực hiện
1
Lưu Văn Quân
MSV: 18810310032
- Dữ liệu
- Chương trình
- Báo cáo
2
Trần Văn Hào
MSV: 18810310076
- Dữ liệu
- Chương trình
- Báo cáo
Họ và tên giảng viên
Chữ ký
Điểm
Ghi chú
Giảng viên chấm 1:
Giảng viên chấm 2:
Downloaded by v? ngoc (
[email protected])
Chữ ký
lOMoARcPSD|17343589
MỤC LỤC
LỜI NÓI ĐẦU
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1
1.1. Khái niệm cơ bản
1
1.1.1. Khai phá dữ liệu là gì ?
1
1.1.2. Khai phá tri thức từ CSDL
1
1.1.3. Các ứng dụng của khai phá dữ liệu:
2
1.1.4. Các bước của quá trình khai phá dữ liệu:
2
1.2. Một số kỹ thuật khai phá dữ liệu:
3
1.2.1. Kỹ thuật khai phá luật kết hợp
3
1.2.2. Kỹ thuật phân lớp
4
1.2.3. Kỹ thuật phân cụm
4
CHƯƠNG 2: THUẬT TOÁN SVM
5
2.1 Giới thiệu chung SVM
5
2.2 SVM làm việc như thế nào
5
2.3 Cách chọn siêu phẳng tối ưu
6
2.4 Tính m (margin)
6
2.5 Phương trình của SVM
9
2.5.1 Sai số dự đoán
9
2.5.2 Hàm mất mát
10
2.5.3 Hàm đánh giá
10
CHƯƠNG 3: SVM VÀ BÀI TOÁN DỰ ĐOÁN BỆNH UNG THƯ PHỔI
11
3.1 Phân tích bài toán
11
3.2 Đọc và xây dựng dữ liệu, chương trình
12
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
KẾT LUẬN
17
TÀI LIỆU THAM KHẢO
18
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
LỜI NÓI ĐẦU
Trong thời buổi hiện đại ngày nay, công nghệ thông tin cũng như những ứng
dụng của nó không ngừng phát triển, lượng thông tin và cơ sở dữ liệu được thu
thập và lưu trữ cũng tích lũy ngày một nhiều lên. Con người cũng vì thế mà cần có
thông tin với tốc độ nhanh nhất để đưa ra quyết định dựa trên lượng dữ liệu khổng
lồ đã có. Các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày
càng không đáp ứng được thực tế. Vì thế, một khuynh hướng kỹ thuật mới là kỹ
thuật phát hiện tri thức và khai phá dữ liệu nhanh chóng được phát triển.
Khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực
khác nhau ở các nước trên thế giới. Ở Việt Nam, kỹ thuật này đang được nghiên
cứu và dần đưa vào ứng dụng. Khai phá dữ liệu là một bước trong quy trình phát
hiện tri thức. Hiện nay, mọi người không ngừng tìm tòi các kỹ thuật để thực hiện
khai phá dữ liệu một cách nhanh nhất và có được kết quả tốt nhất.
Trong bài tập lớn này, chúng em tìm hiểu và trình bày về một kỹ thuật trong
khai phá dữ liệu để phân lớp dữ liệu cũng như tổng quan về khai phá dữ liệu, với
đề tài “Ứng dụng thuật toán SVM để dự đoán bệnh ung thư phổi”. Trong quá trình
làm bài tập lớn này, chúng em xin gửi lời cảm ơn đến cô Nguyễn Thị Thanh Tân.
Cô đã rất tận tình hướng dẫn chi tiết cho chúng em, những kiến thức thầy cung cấp
rất hữu ích. Chúng em rất mong nhận được những góp ý từ cô.
Chúng em xin chân thành cảm ơn!
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Khái niệm cơ bản
1.1.1. Khai phá dữ liệu là gì ?
Khai phá dữ liệu là một quá trình xác định các mẫu tiềm ẩn có tính hợp lệ,
mới lạ, có ích và có thể hiểu được trong một khối dữ liệu rất lớn.
1.1.2. Khai phá tri thức từ CSDL
Khai phá tri thức từ CSDL gồm 5 bước
- B1: Lựa chọn CSDL
- B2: Tiền xử lý
- B3: Chuyển đổi
- B4: Khai phá dữ liệu
- B5: Diễn giải và đánh giá
Khai phá dữ liệu là 1 bước trong quá trình khai phá tri thức từ CSDL
PAGE \* MERGEFORMAT
5
Hình 1.1: Quá trình khai phá tri thức
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
1.1.3. Các ứng dụng của khai phá dữ liệu:
Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh
vực: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán, tính toán song song và tốc
độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu... Đặc biệt phát
hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các
phương pháp thống kê để mô hình dữ liệu và phát hiện các mẫu, luật ... Ngân hàng
dữ liệu (Data Warehousing) và các công cụ phân tích trực tuyến (OLAP- On Line
Analytical Processing) cũng liên quan rất chặt chẽ với phát hiện tri thức và khai
phá dữ liệu.
Khai phá dữ liệu có nhiều ứng dụng trong thực tế, ví dụ như:
⮚ Bảo hiểm, tài chính và thị trường chứng khoán: phân tích tình hình tài chính và
dự báo giá của các loại cổ phiếu trong thị trường chứng khoán. Danh mục vốn
và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận, …
⮚ Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.
⮚ Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh lưu trong
các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu chứng
bệnh, chẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc, ...)
⮚ Sản xuất và chế biến: Quy trình, phương pháp chế biến và xử lý sự cố.Text
mining và Web mining: Phân lớp văn bản và các trang Web, tóm tắt văn bản,...
⮚ Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm
kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một số
bệnh di truyền, ...
⮚ Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi, sự
cố, chất lượng dịch vụ, ...
1.1.4. Các bước của quá trình khai phá dữ liệu:
PAGE \* MERGEFORMAT
5 toán. Là tìm hiểu lĩnh
Bước thứ nhất: Hình thành, xác định và định nghĩa bài
vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn
thành. Bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và
bản chất của dữ liệu.
Bước thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn
được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc
thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết,
bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri
thức. Do dữ liệu được lấy từ nhiều nguồn khác nhau, không đồng nhất, … có thể
gây ra các nhầm lẫn. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và
rời rạc hoá.
Bước thứ ba: Khai phá dữ liệu, rút ra các tri thức. Là khai phá dữ liệu, hay nói
cách khác là trích ra các mẫu hoặc/và 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
nhất của dữ liệu, các 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ó. Tuỳ theo bài toán xác định được mà ta lựa chọn các phương
pháp khai phá dữ liệu cho phù hợp.
Bước thứ tư: Sử dụng các tri thức phát hiện được. Là hiểu tri thức đã tìm
được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp
lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực
hiện. Các kết quả của quá trình phát hiện tri thức có thể được đưa vào ứng dụng
trong các lĩnh vực khác nhau do các kết quả có thể là các dự đoán.
1.2. Một số kỹ thuật khai phá dữ liệu:
1.2.1. Kỹ thuật khai phá luật kết hợp
Trong khai phá dữ liệu, mục đích của luật kết hợp là tìm ra các mối quan hệ
giữa các đối tượng trong khối lượng lớn dữ liệu. Để khai phá luật kết hợp có rất
PAGE \* MERGEFORMAT
nhiều thuật toán, nhưng dùng phổ biến nhất là thuật toán Apriori.
Đây là thuật toán
5
khai phá tập phổ biến trong dữ liệu giao dịch để phát hiện các luật kết hợp dạng
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
khẳng định nhị phân và được sử dụng để xác định, tìm ra các luật kết hợp trong dữ
liệu giao dịch. Ngoài ra, còn có các thuật toán FP-growth, thuật toán Partition,…
1.2.2. Kỹ thuật phân lớp
Trong kỹ thuật phân lớp gồm có các thuật toán:
- Phân lớp bằng cây quyết định (giải thuật ID3, J48): phân lớp dữ liệu dựa
trên việc lập nên cây quyết định, nhìn vào cây quyết định có thể ra quyết định dữ
liệu thuộc phân lớp nào.
- Phân lớp dựa trên xác suất (Naïve Bayesian): dựa trên việc giả định các
thuộc tính độc lập mạnh với nhau qua việc sử dụng định lý Bayes.
- Phân lớp dựa trên khoảng cách (giải thuật K – láng giềng): làm như láng
giềng làm, dữ liệu sẽ được phân vào lớp của k đối tượng gần với dữ liệu đó nhất.
- Phân lớp bằng SVM: phân lớp dữ liệu dựa trên việc tìm ra một siêu phẳng
“tốt nhất” để tách các lớp dữ liệu trên không gian nhiều chiều hơn.
1.2.3. Kỹ thuật phân cụm
Phân cụm dữ liệu là cách phân bố các đối tượng dữ liệu vào các nhóm/ cụm
sao cho các đối tượng trong một cụm thì giống nhau hơn các phần tử khác cụm,
gồm có một số phương pháp phân cụm cơ bản như:
+ Phân cụm bằng phương pháp K-mean: tìm ra tâm của các cụm mà khoảng cách
của tâm đó đến các đối tượng, dữ liệu khác là ngắn.
+ Phân cụm trên đồ thị
Ngoài ra, khai phá dữ liệu có rất nhiều kỹ thuật, nhưng đây là những kỹ thuật
cơ bản và đơn giản trong khai phá dữ liệu mà chúng em được tìm hiểu.
PAGE \* MERGEFORMAT
5
Downloaded by v? ngoc (
[email protected])
lOMoARcPSD|17343589
CHƯƠNG 2: THUẬT TOÁN SVM
2.1 Giới thiệu chung SVM
SVM (Support Vector Machine) là một thuật toán học máy có giám sát được sử
dụng rất phổ biến ngày nay trong các bài toán phân lớp (classification) hay hồi qui
(Regression).
SVM được đề xuất bởi Vladimir N. Vapnik và các đồng nhiệp của ông vào năm
1963 tại Nga và sau đó trở nên phổ biến trong những năm 90 nhờ ứng dụng giải
quyết các bài toán phi tuyến tính (nonlinear) bằng phương pháp Kernel Trick.
2.2 SVM làm việc như thế nào
Ý tưởng của SVM là tìm một siêu phẳng (hyper lane) để phân tách các điểm dữ
liệu. Siêu phẳng này sẽ chia không gian thành các miền khác nhau và mỗi miền sẽ
chứa một loại dữ liệu.
Hình 1.2 Hình ảnh mặt phẳng hyper lane trong không gian 2 chiều
PAGE \* MERGEFORMAT
Siêu phẳng được biểu diễn bằng hàm số
= 5b (W và X là các vector
là tích vô) Hay WT (WT là ma trận chuyễn vị).
Vấn đề là có rất nhiều siêu phẳng, chúng ta phải chon cái nào để tối ưu nhất.
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
2.3 Cách chọn siêu phẳng tối ưu
Siêu phẳng phân tách hai lớp dữ liệu H0 thỏa mã + b =0. Siêu phẳng
này tạo ra hai nửa không gian (half space) dữ liệu :
Không gian các dữ liệu lớp âm Xi thỏa mãn và không gian dữ liệu lớp
dương Xj thỏa mãn
Tiếp theo ta chọn hai siêu phẳng lề H1 đi qua điểm thuộc lớp âm và H2 đi qua
điểm thuộc lớp dương đều song song với H0
● H1: + b =1
● H2: + b =1
Khoảng cách từ H1 đến H0 là
Khoảng cách từ H2 đến H0 là
m = + được gọi là mức lề
Siêu phẳng tối ưu mà chúng ta cần chọn là siêu phẳng phân tách có lề lớn
nhất. Lý thuyết học máy đã chỉ ra rằng một siêu phẳng như vậy sẽ cực tiểu hóa giới
hạn lỗi mắc phải.
2.4 Tính m (margin)
Khoảng cách từ một điểm Xk đến siêu phẳng H0 là: . Trong đó là độ dài của
vector W: .
Khoảng cách từ một điểm Xi nằm trên H1 đến H0 :
Khoảng cách từ một điểm Xj nằm trên H2 đến H0 :
Từ đó ta có thể tính được mức lề :
Giờ thì bạn đã hiểu vì sao các điểm nằm trên hai siêu phẳng H1 và H2 được
gọi là các Support Vector.
Vậy việc training trong giải thuật SVM tương được với bài toán cực tiểu hóa
PAGE \* MERGEFORMAT
có ràng buộc sau đây :
5
Cực tiểu hóa :
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
Với điều kiện: Nhân hai vế bất đẳng thức của (1) và (2) với yi ta được điều kiện thu
gọn :
Bài toán tương đương với
Minimize:
Subject to: (3)
Với điều kiện này, đây chính là bài toán hard-margin của SVM
Việc giải bài toán trên liên quan đến một số lý thuyết toán học tương đối phức
tạp như điều kiện Karush-Kuhn-Tucker, hàm đối ngẫu Lagrange, Convex
optimization … Mình sẽ không nói ở bài này.
Việc xác định siêu phẳng H0 được giả sử trong điều kiện lý tưởng tập dữ liệu
có thể phân tách tuyến tính, tìm được hai siêu phẳng lề H1 và H2 mà không có điểm
dữ liệu nào nằm giữa chúng. Vậy trong trường hợp tập dữ liệu có nhiều điểm gây
nhiễu, các điểm này không thỏa mãn điều kiện (3), bài toán không tìm được lời
giải.
Hình 1.3 Hình ảnh cho bài toán hard-margin
Đối với các trường hợp này chúng ta cần nới lỏng các điều kiện lề bằng việc
sử dụng các biến slack
PAGE \* MERGEFORMAT
5
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
Bài toán trong trường hợp này trở thành:
Minimize:
Subject to:
Trong đó C là tham số xác định mức độ phạt của (penalty degree) đối với các
lỗi (đây là mà một tham số khá quan trọng mà các bạn cần phải tối ưu trong quá
trình huấn luyện SVM)
Đây chính là bài toán Soft-margin của SVM.
Một vấn đề cuối cùng mà mình muốn nhắc đến trong bài này là đối với các
bài toán có không gian dữ liệu là phi tuyến tính (non-linear) chúng ta không thể tìm
được một siêu phẳng H0 thỏa mãn bài toán.
Hình 1.4 Hình ảnh cho bài toán soft-margin
Để giải quyết bài toán trong trường hợp này chúng ra cần biểu diễn (ánh xạ ) dữ
liệu từ không gian ban đầu X sang không gian F bằng một hàm ánh xạ phi tuyến:
PAGE \* MERGEFORMAT
5
Trong không gian F tập dữ liệu có thể phân tách tuyến tính. Nhưng nãy sinh một
vẫn đề lớn đó là trong không gian mới này số chiều của giữ liệu tăng lên rất nhiều
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
so với không gian ban đầu làm cho chi phí tính toán vô cùng tốn kém. Rất may
trong bài toán SVM người ta đã tìm ra một cách không cần phải tính , và hàm ánh
xạ mà vẫn tính được . Phương pháp này gọi là Kernel Trick
, K(x,z) là một hàm nhân (Kernel functions)
Một số hàm nhân thường dùng:
● Polynomial:
d
● Gaussian RBF:
● Sigmoidal:
2.5 Phương trình của SVM
Phương trình tuyến tính có dạng:
Trong đó w thuộc Rn là vector hệ số ứng với các chiều của vector
b là hệ số tự do trong không gian hai chiều thì được gọi
là đường thẳng, không gian 3 chiều là mặt phẳng.
2.5.1 Sai số dự đoán
Sai số dự đoán được tính bằng công thức sau:
Trong đó, e là sai số dự đoán, y là giá trị thực và là giá trị dự đoán (hay còn
gọi là y_pred). Hàm bình phương để tránh phương trình có thể ra kết quả âm và vì
e là sai số, nên giá trị này càng nhỏ càng tốt.
2.5.2 Hàm mất mát
PAGE \* MERGEFORMAT
5
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
2.5.3 Hàm đánh giá
- Accuracy : (ACC)
Cách đơn giản và hay được sử dụng nhất là accuracy (độ chính xác). Cách
đánh giá này đơn giản tính tỉ lệ giữa số điểm được dự đoán đúng và tổng số điểm
trong tập dữ liệu kiểm thử:
Trong đó TP, TN là dự đoán đúng
FP, FN là dự đoán sai
● Precision - bao nhiêu cái đúng được lấy ra
● Recall - bao nhiêu cái được lấy ra là đúng
PAGE \* MERGEFORMAT
5
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
CHƯƠNG 3: SVM VÀ BÀI TOÁN DỰ ĐOÁN BỆNH UNG THƯ
PHỔI
3.1 Phân tích bài toán
Về dữ liệu chúng ta sẽ sử dụng bộ dữ liệu được thu thâp trên Kaggle về bệnh
ung thư phổi “Lung Cancer Prediction”.
- Input X: gồm Age, Smokes, Areaq, Alkhol
PAGE \* MERGEFORMAT
5
⮚ Age: độ tuổi được khảo sát.
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
⮚ Smokes: số lượng thuốc lá hút mỗi ngày
⮚ AreaQ: kích thước khối u.
⮚ Alkhol: Lượng sử dụng rượi.
- Output Y:
⮚ Y là dạng nhị phân 0/1.
⮚ 0 là biểu thị tượng trưng cho người không mắc bệnh, 1 là biểu thị tượng trưng
cho người mắc bệnh.
3.2 Đọc và xây dựng dữ liệu, chương trình
❖ Liên kết dữ liệu và hiển thị
PAGE \* MERGEFORMAT
5
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
❖ Max, min, giá trị trung bình, biến phân (variant), độ lêch chuẩn (std) …
❖ Phân phối chuẩn đoán
PAGE \* MERGEFORMAT
5
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
❖ Chia tập train và test
❖ Mô hình huấn luyện
❖ Hệ số sau khi huấn luyện
PAGE \* MERGEFORMAT
5
Downloaded by v? ngoc ([email protected])
lOMoARcPSD|17343589
❖ Kết quả, độ chính xác của ma trận
❖ Làm rõ hơn cách tính độ chính xác
=> 100% nhãn 0 được dự đoán đúng là 0 trên tổng số nhãn 0
=> 100% nhãn 1 được dự đoán đúng là 1 trên tổng số nhãn 1
PAGE \* MERGEFORMAT
5
=> 100% nhãn 0 được dự đoán đúng là 0 trên tổng số dự đoán là 0
=> 100% nhãn 1 được dự đoán đúng là 1 trên tổng số dự đoán là 1
Downloaded by v? ngoc ([email protected])