Ứng dụng máy véc tơ hỗ trợ trong phân loại bệnh dựa trên kết quả xét nghiệm hóa nghiệm

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (6.3 MB, 26 trang )

Trang 1<div class="page_container" data-page="1">

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIÊN THÔNG

NGUYEN ANH TUẦN

ỨNG DỤNG MÁY VÉC TƠ HỖ TRỢ TRONG

Chun ngành: HỆ THĨNG THƠNG TIN

Mã số: 60.48.01.04

TĨM TẮT LUẬN VĂN THẠC SỸ KĨ THUẬT

HÀ NỘI - 2015

</div>Trang 2<div class="page_container" data-page="2">

Luận văn được hồn thành tại:

HỌC VIEN CƠNG NGHỆ BƯU CHÍNH VIỄN THONG

Người hướng dẫn khoa học: TS. VŨ VĂN THỎA

Phản biện 1: ...

Phản biện 2:_...

sĩ tại Học viện Cơng nghệ Bưu chính Viễn thơng

Vào lúc: ....ĐIỜ năm 2015

Có thê tìm hiệu luận van tại:

- Thư viện của Học viện Cơng nghệ Bưu chính Viễn thơng

</div>Trang 3<div class="page_container" data-page="3">

MỞ ĐẦU

Xét nghiệm đóng vai trị thiết u của y học hiện đại và đóng

vai trị chính trong các quyết định của các bác sĩ lâm sàng, điều

dưỡng và nhân viên y tế trong tồn bộ q trình điều trị, chăm sóc

sức khỏe.

Chan đốn là cả một q trình biện chứng. Hiện nay kiến thức về xét nghiệm chủ yếu được tích lũy qua kinh nghiệm lâm sàng của

bác sĩ nên dé bỏ qua việc cân nhắc các cơ sở chọn lọc, chỉ dẫn, diễn

giải các xét nghiệm.

Với tình trạng bệnh tật có xu hướng gia tăng thì việc đảm bảo

chất lượng khám và điều trị đang là một thách thức đối với các cơ sở

khám, chữa bệnh. Vi vậy, nghiên cứu xây dựng một hệ thống tổng

hợp, đánh giá các thơng tin xét nghiệm hóa nghiệm, trợ giúp các bác

sĩ phân loại bệnh một cách nhanh chóng, chính xác nhằm nâng cao

chất lượng điều trị là rất cần thiết.

Khai phá dữ liệu (KPDL) là một cơng nghệ giúp tìm ra các

mối quan hệ tiềm ấn dé đưa ra những quy luật, những tri thức mới từ

các dữ liệu đã thu thập được trong thực tế và đã được ứng dụng trên hầu hết các lĩnh vực trong đó có y tế như: Fibrotest đánh giá mức độ

xơ hóa của gan, Triple test đánh gia kha năng di tật của thai nhi...

Ở Việt Nam KPDL trong lĩnh vực y khoa cịn ít, gặp nhiều khó khăn, do hiện nay nhiều bệnh viện ở nước ta chưa có bệnh nhán

điện tử. Việc KPDL trong lĩnh vực này thực sự mang lại nhiều ý

nghĩa khi hỗ trợ cho các bác sĩ chân đốn bệnh sớm và điều trị bệnh

có hiệu quả, giảm bớt tử vong cũng như chỉ phí điều trị. Đây là một

nhu cầu thiết thực trong các bệnh viện

Hiện nay, đa số các phương pháp khai phá dữ liệu đều liên quan đến phân lớp do tính phổ dụng trong thực tiễn. Các kỹ thuật phân lớp vẫn luôn được nghiên cứu, cải tiến để khắc phục nhược

điểm và ứng dụng ngày càng hiệu quả trong các lĩnh vực khác nhau.

</div>Trang 4<div class="page_container" data-page="4">

Thực tế cho thấy mỗi kỹ thuật phân lớp đều có ưu, nhược điểm riêng khi ứng dụng trên những lĩnh vực cụ thê. Kỹ thuật phân lớp máy véc

tơ hỗ trợ (Support vector machines - SVM) được Cortes và Vapnik giới thiệu năm 1995 được mở rộng từ chuyên đề lý thuyết học thống kê, dựa trên nguyên tắc tối thiểu rủi ro cau trúc (structural risk minimization). SVM là một kỹ thuật dự báo sử dụng lý thuyết máy học để cho ra độ chính xác dự báo tối đa. Nhờ những ưu điểm là có thé xử lý các tập dit liệu lớn có số thuộc tính lớn với hiệu năng cao, đạt độ chính xác cao, có khả năng xử lý với dữ liệu thiếu, có thé ứng dụng cho cả phân lớp và hồi quy trên các kiểu dữ liệu liên tục cũng như rời rac nên SVMs đã được ứng dụng rất hiệu quả trong nhiều lĩnh vực, đặc biệt là phân loại văn bản, nhận dạng chữ viết tay, phân

loại ảnh và tin sinh học. Trong lĩnh vực y tế, SVM cũng đã được

nghiên cứu chuyên sâu, ứng dụng rất hiệu quả trong chân đoán và

phân loại mức độ bệnh. Nghiên cứu, khảo sát cũng cho thấy SVM là

một trong những kỹ thuật được lựa chọn thử nghiệm đầu tiên trong

khai phá dữ liệu.

Với những lý do trên, học viên chọn đề tài: “Ứng dụng máy véc tơ hỗ trợ trong phân loại bệnh dựa trên kết quả xét nghiệm hóa

nghiệm ”cho luận văn tốt nghiệp cao học.

Mục tiêu của luận văn là nghiên cứu phương pháp SVM và

ứng dụng SVM để phân loại bệnh dựa trên kết quả xét nghiệm hóa

Nội dung của luận văn được trình bày trong ba chương như

Chương 1: Tổng quan về khai phá dit liêu.

Chương 2: Phân lớp sử dụng máy véc tơ hỗ trợ.

Chương 3: Ứng dụng máy véc tơ hỗ trợ trong phân loại bệnh

dựa trên kết quả xét nghiệm hóa nghiệm.

</div>Trang 5<div class="page_container" data-page="5">

CHUONG I: TONG QUAN VE KPDL

1.1 KPDL, phat hiện tri thức

1.1.1 Khái niệm về khám phá tri thức va KPDL

Khám phá tri thức trong các cơ sở dữ liệu (Knowledge

Discovery in Database-KDD) là một qui trình nhận biết các mẫu

hoặc các mơ hình trong dt liệu với các tính năng: hợp thức, mới, khả

ich và có thé hiểu được.

KPDL (KPDL - Data Mining) là một khái niệm ra đời vào

những năm cuối của thập kỷ 1980. Cụm từ “Khai phá dữ liệu” bao

hàm 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.

Data Data Models

Mining |

Hình 1.1: Mơ hình khái qt về KPDL

Khai niệm KDD và KPDL được các nhà khoa học xem là

tương đương nhau. Tuy nhưng, nếu phân chia một cách rành mạch

và chỉ tiết thì KPDL là một bước chính trong q trình KDD.

KDD là lĩnh vực liên quan đến nhiều ngành như: Tổ chức dữ liệu, xác suất, thống kê, lý thuyết thơng tin, học máy, CSDL, thuật

tốn, trí tuệ nhân tạo, tính tốn song song và hiệu năng cao.

Một số định nghĩa về KPDL:

Trên thực tế, KPDL được xem là một bước thiết yếu trong quá trình KDD bao gồm các thụât toán KPDL chuyên dùng, dưới một sé

quy dinh về hiệu quả tính tốn chấp nhận được, để tìm ra các mẫu

hoặc các mơ hình trong dữ liệu.

1.1.2 Q trình khám phá tri thức

Quá trình KDD tiễn hành qua các giai đoạn như hình 1.3:

</div>Trang 6<div class="page_container" data-page="6">

nierpretaton ¿

Selection Transformation .evauabon

— le

Dateboze Tergei Preprooszed = Trensformed Petenz Ôizcoeved

‡ cata 4 deta 4 data ‡ ‡ knowledge

Hình 1.3: Các giai đoạn khám pha tri thức từ cơ sở dữ liệu

(1) Gom dữ liệu:

(2) Trích lọc dữ liệu.

(3) Tiền xử lý đữ liệu: Làm sạch DL, làm giàu DL, làm giảm chiều, biến đổi DL và rút gọn DL nếu cần thiết

(4) Chuyên đổi dir liệu: Dữ liệu sẽ được chuyên đôi về dạng

phù hợp cho việc khai phá.

(5) KPDL: Sử dụng nhiều thuật tốn khác nhau dé trích ra các

(6) Đánh giá các luật và biéu diễn tri thức: Đánh giá sự hữu

ích của các mẫu biéu diễn tri thức dựa trên một số phép đo. Sử dụng

các kỹ thuật trình diễn và trực quan hố đữ liệu dé biéu diễn tri thức

khai phá được cho người sử dụng.

Giai đoạn 5 - KPDL (hay cịn gọi đó là Data Mining) là giai

đoạn được quan tâm nhiều nhất.

1.1.3 Các van đề liên quan đến KPDL

</div>Trang 7<div class="page_container" data-page="7">

Dữ liệu cho KPDL

KPDL được áp dụng đối với bat kỳ loại DL lưu trữ nào: CSDL

quan hệ (Relational Databases), kho dữ liệu (DataWarehouses),

CSDL giao dịch(7ransactional Databases), hệ thong CSDL nâng

cao (Advanced Data andInformation Systems), DL dòng (Streamdata), World Wide Web...

Nhiém vu cua KPDL

+ Mơ tả: Mơ tả các tính chat hoặc các đặc tinh chung của DL

trong CSDL hiện có. Mục tiêu là để khám phá các mẫu trong DL và hiểu được mối quan hệ giữa các thuộc tính của DL đó.

+ Dự đốn: Tạo ra một mơ hình thống kê các hành vi tương

lai. Phân tích dự đốn liên quan đến dự báo xác suất và các xu hướng dựa vào các suy diễn trên CSDL hiện thời. Mục đích là dé tạo ra một mơ hình đề thực hiện phân loại, dự đoán hay ước lượng.

1.1.4 Một số thách thức trong KPDL và KDD:

1.1.5 Các lĩnh vực ứng dung cua KPDL1.2 Các phương pháp KPDL

+ Kỹ thuật mô tả: Có nhiệm vụ mơ tả về các tính chất hoặc các

đặc tính chung của dữ liệu.

+ Kỹ thuật dự đốn: Có nhiệm vụ đưa ra các dự đốn dựa vào

suy diễn trên dữ liệu hiện thời.

Với hai nhiệm vụ chính mơ tả và dự đốn, thường sử dụng các

kỹ thuật:

- Phân lớp và dự đốn (Classification and Prediction): Cịn

được gọi là q trình học có giám sát và gồm một số kỹ thuật: Mạng

Nơ-ron nhân tạo (Neural Network), cây quyết định (Decision tree),

máy véc tơ hỗ trợ (SVM).

- Phân cụm (Clustering/Segmentation): Con được gọi là q

trình học khơng giám sát và gồm một số kỹ thuật: K-Means, láng giềng gần nhất (Nearest Neighbor).

</div>Trang 8<div class="page_container" data-page="8">

- Phát hiện luật kết hợp (Association Rules Discovery): Được

sử dụng để tìm ra các sự kết hợp hoặc các mối quan hệ giữa các

thuộc tinh trong CSDL

- Phân tích hồi quy (Regression analysic): Là việc học một ham ánh xạ từ một tập dữ liệu thành một biến dự đốn có giá trị thực.

- Phân tích các mau theo thời gian (sequential/temporal

patterns): Tương tự như khai phá luật kết hợp nhưng có thêm tính

thứ tự và tính thời gian.

- Mơ tả khái niệm (Concept description and summarization):

Thiên về mô tả, tong hợp và tom tắt các khái niệm.

Phương pháp phân lớp được ứng dụng rất rộng rãi do tính chất

phổ dụng trong thực tế.

1.3 Ứng dụng KPDL trong y tế

KPDL ứng dung trong: Chan đoán và điều trị hiệu quả; Quản

lý y tế; Quan lý các mối quan hệ khách hang; Phát hiện gian lận va

lạm dụng y tế.

1.4 Kết luận chương

Trong chương | luận văn đã khảo sát các van đề chung nhất

của KPDL và khám phá tri thức. Các kết quả của KPDL được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống xã hội, trong đó có lĩnh vực y tế. Tuy nhiên, do đòi hỏi ngày càng cao của thực tiễn, KPDL còn gặp nhiều thách thức và đang là một trong những lĩnh vực thu hút sự quan tâm của các nhà khoa học và các tổ chức cũng như doanh nghiệp. Trong chương này luận văn cũng trình bày tổng quan

về các phương pháp KPDL. Có nhiều phương pháp và kỹ thuật trong

KPDL, trong đó phương pháp phân lớp được ứng dụng rất rộng rãi trong thực tế. Trong phương pháp phân lớp, kỹ thuật học máy SVM

là thuật toán phân loại được ứng dụng rộng rãi, đặc biệt là trong yhọc và tin sinh học.

</div>Trang 9<div class="page_container" data-page="9">

CHƯƠNG 2: PHAN LỚP SỬ DUNG MAY VECTO

HO TRO

2.1 Tổng quan về phân lớp 2.1.1 Khái niệm về phân lóp

Phân lớp (classification) là một tiến trình xử lý nhằm xếp các

mẫu dữ liệu hay các đối tượng vào một trong các lớp đã được định

nghĩa trước. Các mau đữ liệu hay các đối tượng được xếp về các lớp

dựa vào giá trị của các thuộc tính (attributes) cho một mẫu dữ liệu

hay đối tượng.

2.1.2 Mục tiêu của bài toán phan lop dữ liệu

Mục tiêu của bài tốn phân lớp là xây dựng mơ hình dự đoán

(Predictive Model) để xác định một đữ liệu mới thuộc lớp nào trong

các lớp đã biết.

Có nhiều bài tốn phân lớp đữ liệu. Trong luận văn chỉ xét bài

toán phân lớp nhị phân và phân lớp đa lớp.

- Phân lớp nhị phân là quá trình tiến hành việc phân lớp dữ liệu vao một trong hai lớp khác nhau dựa vào dấu hiệu dữ liệu đó có

hay khơng một số thuộc tính đặc trưng theo quy định của bộ phân

- Phân lớp đa lớp là quá trình phân lớp với số lượng lớp lớn

hơn hai. Khi đó, tập dữ liệu trong miền khảo sát được phân chia

thành nhiều lớp. Người ta thường quy bài toán phân lớp đa lớp về

giải quyết nhiều bài toán phân lớp nhị phân.

2.1.3 Các phương pháp phân lớp

Các thuật toán phân lớp tiêu biểu bao gồm: Mạng no-ron nhân tạo (neural network); Cây quyết định; Mạng Beyesian; Suy luận quy

nạp; K láng giềng gần (K- nearest neighbos); Máy véc tơ hỗ trợ

SVM được Cortes và Vapnik giới thiệu năm 1995 được mở

rộng từ chuyên đề lý thuyết học thống kê, dựa trên nguyên tắc tối thiểu rủi ro cấu trúc (structural risk minimization). Ở dạng chuẩn,

</div>Trang 10<div class="page_container" data-page="10">

SVM dùng dé phan loại nhị phân: với một bộ DL huấn luyện thuộc hai loại cho trước, SVM xây dựng một mơ hình dé phan loai cac DL khác vào hai loại đó. Day là phương pháp có nhiều tiềm năng phat triển về mặt lý thuyết cũng như ứng dụng trong thực tiễn.

2.1.4 Quy trình thực hiện phân lớp

- Giai đoạn học: Giai đoạn này xây dựng một mơ hình phân

lớp mơ tả tập các lớp DL hoặc các khái niệm được xác định trước.

- Giai đoạn phân lớp: Trong giai đoạn này mô hình có được

sẽ được sử dụng dé thực hiện phân lớp và đánh giá mơ hình.

Có nhiều phương pháp đánh giá mơ hình phân lớp nhưng phổ biến là holdout và k-fold cross-validation

2.1.5 Đánh gia mơ hình phân lớp

- Phương pháp holdout.

- Phương pháp k-fold cross validation.

Các thông số dùng dé đánh giá của mơ hình dự đốn:

Các giá tri Sensitivity (tương tự Recall), Specitivity, PredictiveAccuracy, FP rate, FN rate được sử dụng thông dung trong lĩnh vực

y tế dé giải thích lâm sàng các kết qua xét nghiệm chan đốn và dé

ước tính mức độ tốt và phù hợp khi chỉ định XN.

2.2 Phương pháp SVM phân lớp nhị phân

Xét bài toán phân lớp nhị phân với tập dữ liệu mẫu huấn luyện

T= {(x; yi), 1= l,2,..., n, xe RỶ),

Trong đó, các dữ liệu mẫu x; được biểu diễn dưới dạng véc to trong không gian véc tơ RỶ. Các mẫu dương được gan nhãn y, = +1;

các mẫu âm được gan nhãn y; = -1. Ta cần tìm ra một ranh giới dé

phân tách các mẫu thành hai lớp tương ứng +1 và -1. Độ chính xác

của bộ phân lớp phụ thuộc vào độ lớn khoảng cách của điểm DL gần

nhất của mỗi lớp đến ranh giới phân tách (cịn gọi là ranh giới quyết

định), khoảng cách đó còn gọi là biên. Tùy thuộc vào dạng của ranh

giới phân tách ta có SVM tuyến tính và SVM phi tuyến tính.

</div>Trang 11<div class="page_container" data-page="11">

2.2.1 SVM tuyến tính

Trong khơng gian véc tơ RỶ ranh giới phân tách hai lớp có dạng là một siêu phẳng. Mục đích của SVM là tim ra siêu phăng có khoảng cách biên lớn nhất, còn gọi là siêu phăng tối ưu.

Mỗi siêu phăng trong khơng gian RỶ có thể được biểu diễn

dưới dạng: w.x +b=0 (2.1)

Trong đó: w là vector pháp tuyến của siêu phang; b là một số

;„. D x 9 , ow kK A CA ta v

thực với Wil là khoảng cach giữa gôc toa độ và siêu phăng theo

hướng vector pháp tuyến w, cịn w.x biểu thị cho tích vơ hướng của

h(x;) phân DL thành hai lớp +1 và -1 theo (2.3).

Bản chất của SVM là tìm ra w và b sao cho siêu phăng (2.1)

phân tách tập dữ liệu HL có lề lớn nhất. Có 2 van đề đặt ra là:

- Làm thế nào đề tìm được siêu phăng với biên lớn nhất ?

- Nếu DL không phân tách tuyến tính được thì làm thé nào?

2.2.1.1 SVM tuyến tính với tập dữ liệu phân tách được

2.2.1.2 SVM tuyến tính với tap dit liệu không phân tách được 2.2.2 SVM phi tuyến tính

Trong thực tế các tap đữ liệu HL có ranh giới quyết định là

khơng tuyến tính vì vậy rất khó giải quyết. Có thé chuyên tập dữ liệu HL này về dạng tuyến tính bằng cách ánh xạ đữ liệu sang một khơng gian có số chiều lớn hơn gọi là không gian đặc trưng (feature space) để đữ liệu HL sẽ trở nên khả tuyến. Phương pháp SVM phi tuyến

phân thành 2 bước như sau:

Bước 1: Chuyên không gian DL ban đầu sang một không gian

đặc trưng khác (thường có số chiều lớn hơn), khi đó DL có thể phân

tách tuyến tính được.

</div>Trang 12<div class="page_container" data-page="12">

Bước 2: Áp dụng các công thức như với SVM tuyến tính.

$: R# > RTMx & p(x)

Tap huan luyén T ban đầu được ánh xạ thành tập

T? = {(6i, vì), (Đa, y2), ..., (HO), Yo)}

Khi đó x; trong khơng gian R° sẽ tương ứng với Q$;¡ trong khơng gian RTM. Bai tốn tối ưu trở thành:

miny p25 ||W||? + € Dis & (2.29)

gian. Vì (x) chỉ xuất hiện dưới dạng tích vơ hướng $(x).$(z) mà không xuất hiện riêng rẽ nên sử dụng hàm nhân có thể giải quyết

được vấn đề này. Hàm nhân có một số tính chất như sau:

- Một hàm nhân K được xác định khi tồn tại $ sao cho K(x,y)

= P(x).P(y). ¬

- Giả sử có m diém mau, ta lập một ma trận Ki,j = K(xixj) với

ij=1,...m. Người ta chứng minh được rằng: Nếu K là hàm nhân thì

ma trận K;; sẽ là ma trận nửa xác định dương(các giá tri riêng biệtcủa ma trận >0).

- Nếu K,(x,y) và K;(x,y) là hàm nhân thì K:(x,y) cũng là ham

K;(x,y) = Ki(,y) + K;(x,y)

nhân K3(x,y) = aK,(x,y) aeRt (2.33)

K3(x,y) = Ki(x,y). Koy)

Một sô ham nhân thường được sử dung:

- Hàm nhân đa thức: K(x,y) = (x.y + c)! với 1 là bậc đa thức.

</div>Trang 13<div class="page_container" data-page="13">

- Ham ban kinh co ban (Radial Basis Function) K(x,y) =

e 20 VỚI G0.

- Hàm nhân tuyến tinh (Linear Kernel) K(x,y) = (xF.y)'.

2.2.3 Thuật toán toi thiếu tuần tự SMO

Đây là thuật toán tối ưu dành riêng cho phương pháp SVM do

J. Platt đưa ra vào năm 1998. Thuật toán tối thiểu tuần tự SMO được

sử dụng trong hau hết tat cả bài toán cai đặt thuật toán SVM.

2.3 Phương pháp SVM phân lớp đa lớp

Ý tưởng giải quyết bài toán phân lớp đa lớp là chuyên về thực

hiện nhiều bài toán con phân lớp nhị phân. Bài toán phân lớp đa lớp

đặt ra như sau: Từ tập huấn luyện T đã cho, cần xây dựng bộ phân

lớp sao cho mỗi dữ liệu có thể thuộc một lớp trong k lớp {c, cạ,...,

Cy} với k> 2.

Các chiến lược phố biến: One-against-All và One-against-One

2.3.1 Chiến lược One-against-All (OAA — Chiến lược I/k)

OAA sử dụng (k-1) bộ phân lớp nhị phân với k lớp. Bài toán

phân lớp k lớp chuyền thành k-1 bài toán phân lớp hai lớp. Bộ phân

lớp nhị phân thứ ¡ được xây dựng trên mẫu thuộc lớp thứ ¡ là mẫu

dương (+1) và tất cả các mẫu thuộc các lớp còn lại là mẫu âm (-1).

Hàm quyết định thứ i dùng dé phân lớp thứ i và những lớp còn lại có

dang: D,(x) = w¡x + bị

Nhược điểm của OAA là phải xây dựng một siêu phang dé

tách một lớp ra khỏi các lớp cịn lại. Q trình này là phức tạp và có

thé khơng chính xác.

2.3.2 Chiến lược One-against-One (OAO — Chiến lược 1/1)

OAO sử dụng k(k-1)/2 bộ phân lớp nhị phân dé phân tách hai

lớp (i, j), i= 1, 2, .., k-1, j =i+1, ..., k. Mẫu thuộc lớp i là mẫu dương(+1) và mẫu thuộc lớp j là mẫu âm (-1). Sau đó, sử dung phương

pháp lựa chọn theo đa số dé kết hợp các bộ phân loại này dé xác định

được kết quả phân loại cuối cùng.

</div>