Trước tiên tôi xin được gửi lời cảm ơn chân thành tới Ban Giám hiệu
nhà trường, Phòng sau đại học, các thầy cô giáo trong khoa Công nghệ thông
tin, trường đại học Lạc Hồng đã tạo điều kiện và môi trường học tốt nhất.
Các Giáo sư – Tiến sĩ đã tâm quyết không ngại đường xá xa, đến để truyền
đạt cho chúng tôi nguồn kiến thức vô cùng quý báu, cũng như cách học tập và
nghiên cứu khoa học.
Tôi xin chân thành cám ơn Ban Giám Đốc Bệnh viện Nhi Đồng –
Đồng Nai, TS.BS Nguyễn Trọng Nơi Phó Giám Đốc, BS.CKI Nguyễn Quang
Hinh Trưởng phòng Kế Hoạch Tổng Hợp, BS.CKI Nguyễn Văn Giai Trưởng
khoa Nhiễm, THs.BS Chu Văn Thiện trưởng khoa Hối sức tích cực chống độc
bệnh viện Nhi Đồng – Đồng Nai đã tư vấn và giúp đỡ tôi một cách chân
thành trong quá trình thực hiện nghiên cứu khoa học.
Đặc biệt, tôi xin gửi lời cảm ơn chân thành nhất tới Thầy giáo PGS. TS
Đặng Trần Khánh. Thầy đã hướng dẫn và định hướng, giúp tôi hoàn thành
tốt đề tài nghiên cứu khoa học này.
Trong quá trình thực hiện luận văn, tôi đã nhận được sự giúp đỡ của
các chuyên gia bác sĩ tại bệnh viện Nhi Đồng – Đồng Nai, của các bạn bè
trong ngành Công nghệ thông tin, đặc biệt là sự nghiêm khắc giáo huấn của
thầy Đặng Trần Khánh. Mặc dù rất cố gắng nhưng không thể tránh khỏi
những thiếu sót trong lúc thực hiện, tôi rất mong đón nhận những đóng góp ý
kiến từ bạn bè, thầy cô và các chuyên gia.
Một lần nữa tôi rất chân thành cảm ơn tất cả mọi người đã giúp tôi
hoàn thành nghiên cứu khoa học này.
Tác
LỜI MỞ ĐẦU 1
CHƯƠNG I: CƠ SỞ LÝ THUYẾT VỀ KHAI PHÁ DỮ LIỆU 5
1.1
KHAI
PHÁ
DỮ
LIỆU
LÀ
GÌ? 5
1.1.1 Khái niệm về khám phá tri thức và khai phá dữ liệu 5
1.1.2 Một số định nghĩa về khai phá dữ liệu 6
1.2
TẠI
SAO
PHẢI
DỮ
LIỆU 11
1.3.1 Khai phá dữ liệu là một bước thiết yếu trong quy trình khám phá tri
thức 11
1.3.2 Một số phương pháp khai phá dữ liệu 13
1.4
CHỨC
NĂNG
CHÍNH
CỦA
KHAI
PHÁ
DỮ
LIỆU 14
1.4.1 Mô tả (Descriptive) 14
1.4.2 Dự đoán (Predictive) 14
1.5.5 Giải thuật di truyền 16
1.5.6 Mạng nơ-ron (neural network) 16
1.5.7 Cây quyết định 16
1.6
MỘT
SỐ
THÁCH
THỨC
TRONG
KHAI
PHÁ
DỮ
LIỆU
VÀ
KHÁM
LIỆU
CÓ
CANH
TÁC
DỮ
LIỆU 19
2.1.1 Khái niệm 19
2.1.2 Mục đích và phương pháp luận của canh tác dữ liệu 20
2.1.3 Vai trò canh tác dữ liệu trong khám phá tri thức và khai phá dữ liệu 21
2.1.4 So sánh khai phá dữ liệu thông thường và canh tác dữ liệu 25
2.1.5 Khả năng ứng dụng của canh tác dữ liệu trong khai phá dữ liệu. 27
2.1.6 Quy trình canh tác dữ liệu 28
2.1.7 Phương pháp canh tác dữ liệu đánh giá đặc tính 30
2.1.7.1 Đặc tính chung của dữ liệu 30
2.1.7.2 Chọn lựa đặc tính và đánh giá đặc tính cho khai phá dữ liệu 30
2.2.2 Tập dữ liệu y khoa 32
2.2.3 Phương pháp giải quyết 32
2.2.3.1 Phương pháp giải quyết công việc 1 32
2.2.3.2 Phương pháp giải quyết công việc 2 33
2.2.3.3 Phương pháp giải quyết công việc 3 33
2.3
ỨNG
DỤNG
CANH
TÁC
DỮ
LIỆU
TRONG
KHAI
PHÁ
2.3.3 Tập thuộc tính sau khi canh tác dữ liệu 35
2.4
KẾT
CHƯƠNG 36
CHƯƠNGII: KỸ THUẬT KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH 37
3.1
CÂY
QUYẾT
ĐỊNH 37
3.1.1 Khái niệm 37
3.1.2 Biểu diễn cây quyết định 38
3.1.3 Các bước chính xây dựng cây quyết định 39
3.1.4 Cây quyết định so với kỹ thuật khai phá khác 40
3.1.4.1 Một số ưu điểm của cây quyết định 40
3.1.4.2 Một số điểm yếu của cây quyết định 42
3.2.2 Thuật toán C4.5 49
3.2.2.1 Lịch sử phát triển 49
3.2.2.2 Mã giã của thuật toán C4.5 50
3.2.2.3 Một số cải tiến của thuật toán C4.5 52
3.2.3. Thuật toán SPRINT 54
3.2.3.1 Lịch sử phát triển 54
3.2.3.2 Mã giã của thuật toán SPRINT 55
3.2.3.3. SPRINT sử dụng Gini-index làm độ đo tìm điểm phân chia tập
dữ liệu “tốt nhất” 56
3.3
KẾT
CHƯƠNG 57
CHƯƠNG IV: XÂY DỰNG HỆ THỐNG CHƯƠNG TRÌNH VÀ THỰC
NGHIỆM 60
4.1
MỤC
XÂY
DỰNG
HỆ
THỐNG 60
4.4.1 Tìm hiểu nghiệp vụ của bài toán 60
4.4.2 Thu thập dữ liệu 61
4.4.2.1 Nguyên tắc chọn lựa thuộc tính khai phá 61
4.4.2.2 Tiến hành thu thập dữ liệu 61
4.4.2.3 Xử lý dữ liệu-chuyển đổi dữ liệu 62
4.4.3 Chọn lựa kỹ thuật khai phá 63
4.4.4 Xây dựng chương trình 63
4.4.4.1 Dữ liệu đầu vào 63
4.4.4.2 Mô tả dữ liệu đầu vào 63
4.4.4.3 Dữ liệu đầu ra 64
4.4.4.4 Sử dụng thuật toán cho bài toán 64
KẾT
QUẢ
THỰC
NGHIỆM 67
CHƯƠNG V: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 69
5.1
KẾT
LUẬN 69
5.1.1 Kết quả đạt được 69
5.1.1.1 Lý thuyết 69
5.1.1.2 Thực nghiệm 70
5.1.2 Kết quả chưa đạt được 70
5.2
HƯỚNG
PHÁT
Bảng 3.1 Tập dữ liệu huấn luyện cho khái niệm mục tiêu Play tennis 45
Bảng 4.1 Bảng kết quả thực nghiệm của hệ thống 71
DANH SÁCH HÌNH VẼHình 1.1 Minh họa cho hình ảnh khai phá dữ liệu trong tập dữ liệu 5
Hình 1.2 Quy trình khám phá tri thức từ cơ sở dữ liệu 7
Hình 1.3 Chúng ta đang giàu dữ liệu nhưng nghèo tri thức 9
Hình 1.4 Biễu diễn chức năng chính của khai phá dữ liệu
14
Hình 2.1 Quá trình khám phá tri thức và khai phá dữ liệu
23
Hình 2.2 Canh tác dữ liệu tác động quy trình khám phá tri thức
24
Hình 2.3 So sánh khai phá dữ liệu có và không có canh tác dữ liệu 26
Hình 3.1 Biễu diễn cây quyết định cơ bản
37
Hình 3.2 Cây quyết định cho việc chơi Tennis
38
Hình 3.3 Tạo Node gốc Outlook
48
Hình 3.4 Thuộc tính kiểm tra cho con kế node gốc
48
Hình 4.1 Đơn xin mượn hồ sơ bệnh án nghiên cứu khoa học
62
Hình 4.2 Giao diện chính hệ thống chương trình 65
Hình 4.3 Màn hình hiển thị dữ liệu tập huấn 65
Bệnh SD/SXHD trở thành một bệnh dịch lưu hành ở nước ta. Bệnh không
chỉ xuất hiện ở đô thị mà cả vùng nông thôn, nơi có muỗi vectơ truyền bệnh.
Dịch lớn SD/SXHD bùng nổ theo chu kỳ khoảng 3-5 năm. Năm 1998, trên
toàn quốc bùng nổ vụ dịch lớn, số mắc bệnh và tử vong cao (mắc: 234.920
người, tử vong 377
[2]
)
[pl3]
Tham khảo phụ lục 3
[pl3]
Tham khảo phụ lục 3
2
Bệnh SXHD là bệnh truyền nhiễm gây dịch do virus Dengue gây nên.
Virus Dengue có 4 týp huyết thanh là DEN -1, DEN -2, DEN -3, DEN -4.
Virus truyền từ người bệnh sang người lành do muỗi đốt. Muỗi Aedes aegypti
là côn trùng trung gian truyền bệnh chủ yếu. Đặc điểm của SXH D là sốt, xuất
huyết và thoát huyết tương, có thể dẫn đến sốc giảm thể tích tuần hoàn và rối
loạn đông máu, nếu không được chẩn đoán sớm và xử trí kịp thời dễ dẫn đến
tử vong .
Công việc chẩn đoán SXH tương đối dễ dàng nhờ phác đồ hướng dẫn
của Tổ chức Y tế thế giới (WHO) năm 1997 và phát đồ điều trị bệnh SXH của
Bộ Y tế Việt Nam
[2],
nhưng để dự đoán một bệnh nhân sốt xuất huyết Dengue
vào sốc (SXHD-VS) thì còn nhiều khó khăn trong thực tế lâm sàng. Do đó
vẫn còn bệnh nhân tử vong cao, cũng như chi phí điều trị cao cho những bệnh
nhân vào sốc, đây là bài toán nan giải cho Y tế cộng đồng nói chung và tại
nhiều ý nghĩa cho y học chứng cớ và y học thực chứng, để hỗ trợ cho các bác
sĩ, chẩn đoán bệnh sớm và điều trị bệnh có hiệu quả, giảm bớt tử vong cũng
như chi phí điều trị, đây là một nhu cầu thiết thực trong các bệnh viện.
Xuất phát từ những thực tế trên, tác giả đã chọn đề tài “Khai phá dữ
liệu có canh tác dữ liệu và ứng dụng trong khai phá dữ liệu y khoa” để
nghiên cứu cho luận văn thạc sĩ của mình.
3/Mục đích và ý nghĩa nghiên cứu
- Giới thiệu về phương pháp khai phá dữ liệu có sử dụng tri thức chuyên gia
(lĩnh vực có liên quan) trong quá trình chọn lựa thuộc tính nhằm các mục
đích sau:
- Giảm bớt thuộc tính nhiễu, dư thừa trong khai phá dữ liệu.
- Giảm bớt thời gian và chi phí khai phá dữ liệu, giúp các thuật toán khai
phá dữ liệu chạy nhanh và chính xác hơn, từ đó các luật sinh ra trong quá
trình khai phá cũng tốt hơn. Giá trị chẩn đoán từ các luật cũng có độ tin
cậy cao hơn.
- Sử dụng kỹ thuật khai phá dữ liệu bằng cây quyết định với thuật toán
C4.5, tạo ra các luật, thông qua kiểm nghiệm thực tiễn, hỗ trợ bác sĩ chẩn
đoán và điều trị bệnh.
Với mục đích đặt ra cho đề tài nêu trên, việc nghiên cứu thực sự có ý
nghĩa rất to lớn cho nền y học, tạo ra các y học chứng cớ và y học thực chứng,
cải cách chẩn đoán, tạo công cụ hỗ trợ đắc lực trong quá trình chẩn đoán bệnh
(trong luận văn này nghiên cứu hỗ trợ chẩn đoán bệnh SXH), nhằm giảm
thiểu tử vong và giảm chi phí điều trị cho bệnh nhân.
4
Kỳ vọng của đề tài là giải pháp hỗ trợ, mong được áp dụng tại bệnh
viện Nhi Đồng – Đồng Nai, cũng như những bệnh viện tuyến huyện, thiếu
chuyên gia bác sĩ giỏi, nhằm hướng cải cách chẩn đoán và điều trị bệnh nhân,
cụ thể là bệnh SXHD
4/Đối tượng và phạm vi nghiên cứu
Gồm các hồ sơ bệnh án lưu trữ bằng giấy, thuộc đối tượng trẻ em từ 0
Database-KDD) là một qui trình nhận biết các mẫu hoặc các mô hình trong
dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được.
Khai phá dữ liệu (Data Mining-DM)
[6]
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” 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. Thuật ngữ này thực sự là một cái tên nhầm lẫn. Hãy nhớ
rằng việc khai thác vàng từ đá hoặc cát được gọi là khai thác vàng chứ không
phải là khai thác đá, cát. Như vậy, khai phá dữ liệu (KPDL) nên được đặt tên
thích hợp hơn là “khai thác kiến thức từ dữ liệu”.Tuy nhiên, “khai phá dữ
liệu” vẫn được dùng cách phổ biến. Hình 1.1 minh họa đơn giản và trực quan
cho khái niệm này
.
Hình 1-1: Minh họa cho hình ảnh khai phá dữ liệu trong tập dữ liệu
6
Khái 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à chi tiết thì KPDL là
một bước chính trong quá trình KDD.
Khám phá tri thức trong CSDL là lĩnh vực liên quan đến nhiều ngành
trong hình 1.2 và bao gồm một chuỗi lặp đi lặp lại các bước sau
[6]
:
• Làm sạch dữ liệu (loại bỏ dữ liệu nhiễu và dữ liệu không phù hợp).
• Tích hợp dữ liệu (nơi nhiều nguồn dữ liệu có thể được kết hợp).
• Lựa chọn dữ liệu (nơi mà các dữ liệu liên quan đến công việc phân tích
được lấy từ cơ sở dữ liệu).
• Chuyển đổi dữ liệu (nơi dữ liệu được chuyển đổi, hợp nhất thành các
hình thức thích hợp để khai thác bằng cách thực hiện các hoạt động tóm
tắt hoặc tập hợp).
• Khai phá dữ liệu (một quá trình cần thiết mà các phương pháp thông
minh được áp dụng để trích xuất mẫu dữ liệu).
• Đánh giá mẫu (xác định các mô hình thực sự quan tâm đại diện cho
kiến thức dựa trên một vài đo lường lưu tâm).
• Biểu diễn tri thức (nơi kỹ thuật biểu diễn tri thức và sự hình dung được
sử dụng để trình bày các tri thức được khai thác đến người dùng).
Hình 1.2 Quy trình khám phá tri thức từ cơ sở dữ liệu
8
1.2 TẠI SAO PHẢI KHAI PHÁ DỮ LIỆU?
1.2.1 Tại sao phải khai phá dữ liệu?
Trong thời đại ngày nay, việc nắm bắt được thông tin được coi là chìa
khóa của thành công. Ai thu thập, phân tích và hiểu được thông tin và hành
động được nhờ vào những thông tin đó là kẻ thắng cuộc. Chính vì vậy, việc
tạo ra thông tin và mức tiêu thụ thông tin ngày nay ngày càng gia tăng. Cùng
với sự phát triển vượt bậc của CNTT và việc ứng dụng CNTT trong nhiều
lĩnh vực khác nhau trong nhiều năm qua cũng đồng hành với lượng dữ liệu
lưu trữ ngày một nhiều lên. Những dữ liệu này thường ẩn chứa những giá trị
nhất định nào đó. Tuy nhiên, Trong thực tế thì chỉ có một ít dữ liệu là được
phân tích (cụ thể là hồ sơ bệnh án trong các bệnh viện), số còn lại họ không
thông tin là yếu tố then chốt để phục vụ cho mọi nhu cầu thiết thực trong hoạt
động hàng ngày của chúng ta. Vậy chúng ta làm gì với một khối DL này.
Hình 1.3 thể hiện sự băng khoăn đó. “Necessity is the mother of invention” - Data Mining ra đời như một
hướng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên. Khá nhiều định nghĩa
về Data Mining đã được trình bày ở trên. Data Mining được xem như là một
Hình 1.3. Chúng ta đang giàu dữ liệu nhưng nghèo tri thức
[6]
10
công nghệ tri thức, giúp khai thác những thông tin hữu ích từ những kho DL,
được tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó.
1.2.2 Khai phá dữ liệu được áp dụng trên loại dữ liệu nào?
Khai phá dữ liệu
được áp dụng trên nhiều loại DL khác nhau. Về nguyên
tắc, KPDL được áp dụng đối với bất kỳ loại DL lưu trữ nào, cũng như các DL
tạm thời
[6]
. Do đó, phạm vi DL của chúng ta sẽ bao gồm các CSDL quan
hệ(Relational Databases), kho dữ liệu (DataWarehouses), CSDL giao
dịch(Transactional Databases), hệ thống CSDL nâng cao(Advanced Data and
Information Systems), DL dòng (Stream data), World Wide Web …
Hệ thống CSDL nâng cao bao gồm các đối tượng CSDL quan hệ và
CSDL có tính định hướng theo ứng dụng cụ thể, chẳng hạn như CSDL đa
truyền thông, CSDL đa chiều, CSDL chuỗi thời gian, CSDL văn bản Những
thách thức và kỹ thuật KPDL có thể khác nhau cho mỗi hệ thống lưu trữ.
(3) Tiền xử lý dữ liệu.
(4) Lựa chọn chức năng KPDL
(5) Lựa chọn giải thuật KPDL phù hợp.
(6) Tiến hành KPDL
(7) Hậu xử lý và đánh giá mô hình
(8) Triển khai tri thức
Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa
trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình
KPDL là các nhà tư vấn (NTV) và nhà phát triển chuyên nghiệp trong lĩnh
vực KPDL.
(1) Xác định chính xác vấn đề cần giải quyết và tìm hiểu nghiệp vụ và
dữ liệu: Xác định chính xác vấn đề cần giải quyết (xác định và hình
thành bài toán của ứng dụng) sau đó nghiên cứu kiến thức về lĩnh vực
sẽ áp dụng, bao gồm các tri thức, cấu trúc về hệ thống và tri thức, các
12
nguồn DL hiện hữu, ý nghĩa, vai trò và tầm quan trọng của các thực
tể DL. 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 phép chọn
các phương pháp KPDL thích hợp với mục đích ứng dụng và bản chất
của DL.
(2) Chuẩn bị dữ liệu và thu thập: Chuẩn bị và thu thập DL phù hợp với
mục đích đề ra.
(3) Tiền xử lý dữ liệu: Là thu thập và xử lý thô, hay còn được gọi là tiền
xử lý DL bước này gồm một số công việc sau:
- Làm sạch DL: Loại bỏ DL nhiễu, DL dư thừa không phù hợp.
- Làm giàu DL: Các DL bị thiếu/mất sẽ được thay thế bởi các giá trị
thích hợp.
- Làm giảm chiều: Các thuộc tính chứa ít thông tin sẽ được loại bỏ
bớt.
- Biến đổi DL và rút gọn DL nếu cần thiết: bước này thường chiếm
tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định
nhằm tự động hoá quá trình này.
1.3.2 Một số phương pháp khai phá dữ liệu
KPDL là lĩnh vực liên ngành mà con người luôn tìm cách đạt được mục
đích sử dụng thông tin của mình. Quá trình KPDL là quá trình phát hiện mẫu,
trong đó phương pháp KPDL để tìm kiếm các mẫu đáng quan tâm theo dạng
xác định. Có thể kể ra đây một vài phương pháp như:
- Phương pháp sinh cây quyết định và luật (đây là phương pháp được
sử dụng trong luận văn này sẽ được trình bày kỹ trong chương III).
- Sử dụng công cụ truy vấn.
- Dựa theo khoảng cách (K-láng giềng gần).
- Các mạng nơ-ron(neural network)
- Các mạng xác xuất Bayes.
- Các thuật toán di truyền.
14
- Luật suy diễn.
- Trực quan hóa dữ liệu.
- Phát hiện luật kết hợp, …
1.4 CHỨC NĂNG CHÍNH CỦA KHAI PHÁ DỮ LIỆU
Khai phá dữ gồm hai chức năng chính sau đây: Mô tả và dự đoán
1.4.1 Mô tả (Descriptive)
Có nhiệm vụ mô tả các tính chất hoặc các đặc tính chung của DL trong
CSDL hiện có. Một số kỹ thuật khai phá trong nhóm này là: phân cụm dữ liệu
(Clustering), tổng hợp (Summarisation), trực quan hoá (Visualization), phân
tích sự phát triển và độ lệch (Evolution and deviation analyst)…
1.4.2 Dự đoán (Predictive)
Có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên CSDL hiện
thời. Một số kỹ thuật khai phá trong nhóm này là: phân lớp (Classification),
hồi quy (Regression), cây quyết định (Decision tree), thống kê (statictics),
mạng nơron (neural network), luật kết hợp…
Copyright: Tài liệu đại học ©