i

LỜI CẢM ƠN

Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Nguyễn Hải Minh - khoa
Công nghệ Thông tin - Trường Đại học Công nghệ Thông tin và Truyền
thông – Đại học Thái Nguyên cán bộ đã trực tiếp hướng dẫn cho tôi trong quá
trình thực hiện luận văn.
Tôi xin chân thành cảm ơn các thầy, cô giáo Viện Công nghệ thông tin,
Trường Đại học Công nghệ thông tin và Truyền thông thuộc Đại học Thái
Nguyên đã tham gia giảng dạy, tạo mọi điều kiện cho tôi được học tập, nâng
cao trình độ kiến thức để phục vụ cho công tác của tôi hiện tại và sau này.
Tôi xin cảm ơn Thạc sỹ, Bác sỹ chuyên khoa II Trương Đồng Tâm Bệnh viện trường Đại học Y Khoa Thái Nguyên, đã tạo điều kiện cho tôi tiếp
xúc trực tiếp tìm hiểu các thông tin liên quan trong ngành Y và giúp tôi tiếp
cận với kho dữ liệu khám chữa bệnh tại bệnh viện.
Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, bạn bè, đồng nghiệp đã
luôn động viên, hỗ trợ tôi trong quá trình học tập và nghiên cứu đề tài.
Mặc dù đã rất cố gắng, song luận văn này không thể tránh khỏi những
thiếu sót, kính mong được sự chỉ dẫn, góp ý của các quý thầy cô và các bạn.

Thái Nguyên, tháng 05 năm 2016
Tác giả

Lê Tiến Thành


ii

LỜI CAM ĐOAN

Tôi xin cam đoan nội dung và kết quả nghiên cứu trong luận văn này là

1.1.7 Những thách thức trong ứng dụng và nghiên cứu kỹ thuật KPDL ......... 13
1.2 Tổng quan về gian lận BHYT trong kê đơn cấp thuốc ................................ 17
1.2.1 Giới thiệu chung ................................................................................... 17
1.2.2 Các hình thức gian lận trong y tế .......................................................... 18
1.2.3 Gian lận trong kê đơn, cấp thuốc BHYT............................................... 18
1.2.4 Chức năng, nhiệm vụ của cơ quan Bảo hiểm trong y tế: ....................... 18
1.3 Khai phá dữ liệu bằng luật kết hợp .............................................................. 18
1.3.1 Lý thuyết về luật kết hợp ...................................................................... 18
1.3.2 Định nghĩa luật kết hợp ........................................................................ 19
1.4 Các tính chất của luật kết hợp ...................................................................... 20
1.4.1 Với tập mục phổ biến (3 tính chất) ....................................................... 20


iv

1.4.2 Với luật kết hợp (4 tính chất sau).......................................................... 21
Chương 2 GIẢI THUẬT APRIORI VÀ FP-GROWTH TRONG KHAI PHÁ DỮ
LIỆU ..................................................................................................................... 23
2.1 Thuật toán Apriori ....................................................................................... 23
2.2 Thuật toán PP-growth .................................................................................. 26
2.3 Cấu trúc cây FP-Tree ................................................................................... 28
2.4 Xây dựng cây FP-Tree ................................................................................. 29
2.5 Sinh tập phổ biến ........................................................................................ 31
Chương 3 ỨNG DỤNG THUẬT TOÁN FP-GROWTH KHAI PHÁ DỮ LIỆU
ĐƠN THUỐC BẢO HIỂM Y TẾ .......................................................................... 39
3.1 Thông tin dữ liệu mẫu và yêu cầu bài toán................................................... 39
3.2 Mô hình ứng dụng thuật toán FP-growth để phát hiện luật kê đơn ............... 41
3.3 Lựa chọn công cụ phát triển......................................................................... 41
3.4 Kết quả khai phá luật trên dữ liệu kê đơn thuốc bảo hiểm ............................ 44
3.5 Thử nghiệm chương trình hỗ trợ phát hiện gian lận kê đơn cấp thuốc .......... 62

Độ tin cậy

Supp

Support

Độ hỗ trợ

Item

Item

Khoản mục

Itemset

Itemset

Tập các khoản mục

K - itemset

K - itemset

Tập gồm K mục

TID

Transaction



Minsup

Minimum Support

Độ hỗ trợ tối thiểu

KPDL

Data Mining

Khai phá dữ liệu

BHYT

Bảo hiểm y tế


vi

DANH MỤC CÁC BẢNG
Trang
Bảng2.1 Ví dụ về một cơ sở dữ liệu giao dịch T .................................................... 32
Bảng 2.2 Các tập mục phổ biến ............................................................................. 38
Bảng 3.1 Bảng dữ liệu ........................................................................................... 39
Bảng 3.2 Danh mục các bệnh thường gặp .............................................................. 40
Bảng 3.3 Mã bệnh I15.0 : Cao huyết áp do mạch máu thận.................................... 44
Bảng 3.4 Mã bệnh J20: Viêm phế quản cấp ........................................................... 45
Bảng 3.5 Mã bệnh J30: Viêm mũi do vận mạch và dị ứng ..................................... 47
Bảng 3.6 Mã bệnh K35: Viêm ruột thừa cấp .......................................................... 48

khổng lồ, tăng lên không ngừng. Các cơ sở dữ liệu trong các đơn vị, tổ chức
kinh doanh, quản lý khoa học… chứa đựng nhiều thông tin tiềm ẩn, phong
phú và đa dạng, đòi hỏi phải có những phương pháp phù hợp, chính xác, hiệu
quả để lấy được những thông tin bổ ích. Tuy nhiên, theo thống kê thì chỉ có
một lượng nhỏ của những dữ liệu này là luôn được phân tích, số còn lại họ
không biết sẽ phải làm gì hoặc có thể làm gì. Vấn đề đặt ra là làm thế nào để
xử lý được khối lượng thông tin cực lớn như vậy để phát hiện ra các tri thức
tiềm ẩn trong nó. Những tri thức chiết suất từ nguồn cơ sở dữ liệu trên sẽ là
nguồn thông tin rất hữu ích hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt
động hoặc ra các quyết định chính xác. Để làm được điều đó người ta đã sử
dụng quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery
in Database – KDD). Nhiệm vụ của KDD là từ dữ liệu sẵn có phải tìm ra
những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện cũng như
tìm ra những xu hướng phát triển và các xu hướng tác động lên chúng. Các
kỹ thuật cho phép ta lấy được các tri thức từ cơ sở dữ liệu sẵn có đó được gọi
là kỹ thuật Khai phá dữ liệu (Data Mining).


2

Một trong các nội dung cơ bản nhất trong khai phá dữ liệu và rất phổ
biến là phát hiện các luật kết hợp. Phương pháp này nhằm tìm ra các tập
thuộc tính thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật
về ảnh hưởng của một tập thuộc tính dẫn đến sự xuất hiện của một hoặc một
tập thuộc tính khác như thế nào. Những luật kết hợp khai phá được có thể
giúp các tổ chức và các nhà quản lý đưa ra những quyết định kinh doanh
hiệu quả hơn.
Từ những lý do đó em đã tìm hiểu về đề tài “LUẬT KẾT HỢP TRONG
KHAI PHÁ DỮ LIỆU VÀ ỨNG DỤNG HỖ TRỢ PHÁT HIỆN GIAN LẬN
KÊ ĐƠN CẤP THUỐC BẢO HIỂM Y TẾ”. Nhằm phân tích các dữ liệu và

mục tiêu phát hiện ra quy luật kê đơn đối với một số bệnh thường gặp ở bệnh
viện, để từ đó làm cơ sở xây dựng chương trình hỗ trợ các cán bộ đại diện bảo
hiểm và phát hiện các trường hợp bất thường trong kê đơn, có nghi ngờ gian
lận hoặc lạm dụng bảo hiểm.


4

Chương 1
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ
GIAN LẬN BẢO HIỂM Y TẾ
1.1 Các kiến thức chung về khai phá dữ liệu
Trong thời đại ngày nay, với sự phát triển vượt bật của công nghệ
thông tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về
hoạt động hàng ngày của chúng. Từ khối dữ liệu này, các kỹ thuật trong Khai
Phá Dữ Liệu (KPDL) và máy học có thể dùng để trích xuất những thông tin
hữu ích mà chúng ta chưa biết. Các tri thức vừa học được có thể vận dụng để
cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu.
Khai phá dữ liệu là tiến trình khám phá tri thức tiềm ẩn trong các CSDL,
cụ thể hơn, đó là tiến trình lọc, sản sinh những tri thức hoặc các mẫu tiềm
ẩn, chưa biết những thông tin hữu ích từ các CSDL lớn. Tri thức đó thường ở
dạng các mẫu có tính chất không tầm thường, không tường minh (ẩn), chưa
được biết đến và có tiềm năng mang lại lợi ích. Về bản chất nó là giai đoạn
duy nhất rút trích và tìm ra được các mẫu, các mô hình hay thông tin mới, tri
thức tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Đây là
giai đoạn quan trọng nhất trong quá trình phát hiện tri thức từ CSDL, các tri
thức này hỗ trợ trong việc ra quyết định, điều hành trong khoa học và kinh
doanh. Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức trong cơ
sở dữ liệu (Knowledge Discovery in Database - KDD). Ở đây có thể coi KPDL
là cốt lõi của quá trình phát hiện tri thứ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à ứ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 hoặc các 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.
Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ liệu mà
trong đó khai phá dữ liệu là công đoạn quan trọng nhất.
1.1.2 Kiến trúc của một hệ thống khai phá dữ liệu
Kiến trúc của một hệ thống KPDL điển hình có thể có các thành
phần như hình 1.2
- CSDL, kho dữ liệu hoặc các lưu trữ thông tin khác (Databases, Data
warehouse,..): Đây là một hay một tập các CSDL, các kho dữ liệu, các trang
tính hay các dạng lưu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích
hợp dữ liệu có thể được thể hiện trên những dữ liệu này.
- Máy chủ CSDL hay máy chủ kho dữ liệu (Database or warehouse
server): Máy chủ này có trách nhiệm lấy những dữ liệu thích hợp dựa trên
các yêu cầu khai phá của người dùng.


7

Hình 1.2 Kiến trúc của một hệ khai phá dữ liệu điển hình
- Cơ sở tri thức (Knowledge base): Đây là miền tri thức được dùng
để hướng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết
quả.
- Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải
có một tập các modun chức năng để thực hiện công việc như: đặc trưng hoá,

và tạo ra một hoặc vài mô hình cho phép dự đoán các mẫu mới chưa biết
(unseen new examples).
1.1.5 Lợi thế của khai phá dữ liệu so với phương pháp cơ bản
Các phương pháp khai phá dữ liệu không có gì là mới và hoàn toàn dựa
trên các phương pháp cơ bản đã biết. Nhưng có một số điểm khác biệt và ưu
thế hơn so với các phương pháp cơ bản như sau:
1.1.5.1 Học máy (Machine Learning)
Mặc dù người ta đã cố gắng cải tiến các phương pháp học máy để có
thể phù hợp với mục đích khai phá dữ liệu nhưng sự khác biệt giữa cách thiết
kế, các đặc điểm của cơ sở dữ liệu đã làm cho phương pháp học máy trở nên
không phù hợp với mục đích này, mặc dù cho đến nay, phần lớn các phương


9

pháp khai phá dữ liệu vẫn đựa trên nền tảng cơ sở của phương pháp học máy.
Những phân tích sau đây sẽ cho thấy điều đó.
Trong quản trị cơ sở dữ liệu, một cơ sở dữ liệu là một tập hợp được tích
hợp một cách logic của dữ liệu được lưu trong một hay nhiều tệp và được tổ
chức để lưu trữ có hiệu quả, sửa đổi và lấy thông tin liên quan được dễ dàng.
Ví dụ như trong CSDL quan hệ, dữ liệu được tổ chức thành các tệp hoặc các
bảng có các bản ghi có độ dài cố định. Mỗi bản ghi là một danh sách có thứ tự
các giá trị, mỗi giá trị được đặt vào một trường. Thông tin về tên trường và
giá trị của trường được đặt trong một tệp riêng gọi là thư viện dữ liệu (data
dictionary). Một hệ thống quản trị cơ sở dữ liệu sẽ quản lý các thủ tục
(procedures) để lấy, lưu trữ, và xử lý dữ liệu trong các cơ sở dữ liệu đó.
Trong học máy, thuật ngữ cơ sở dữ liệu chủ yếu đề cập đến một tập các
mẫu (instance hay example) được lưu trong một tệp. Các mẫu thường là các
vector đặc điểm có độ dài cố định. Thông tin về các tên đặc điểm, dãy giá trị
của chúng đôi khi cũng được lưu lại như trong từ điển dữ liệu. Một giải thuật

nghiệm nhằm loại bỏ một số tác động của các tham số để nhấn mạnh độ biến
thiên của một hay một số tham số đích. Tuy nhiên, các cơ sở dữ liệu thương
mại điển hình lại ghi một số lượng thừa thông tin về các dự án của họ để đạt
được một số mục đích về mặt tổ chức. Độ dư thừa này (hay có thể gọi là sự
lẫn lộn – confusion) có thể nhìn thấy và cũng có thể ẩn chứa trong các mối
quan hệ dữ liệu. Hơn nữa, các nhà khoa học có thể tạo lại các thí nghiệm và
có thể tìm ra rằng các thiết kế ban đầu không thích hợp. Trong khi đó, các nhà
quản lý cơ sở dữ liệu hầu như không thể xa xỉ đi thiết kế lại các trường dữ
liệu và thu thập lại dữ liệu.
1.1.5.4 Phương pháp thống kê
Một câu hỏi hiển nhiên là khai phá dữ liệu khác gì so với phương pháp
thống kê. Một câu hỏi hiển nhiên là khai phá dữ liệu khác gì so với phương


11

pháp thống kê. Từ nhiều năm nay, con người đã sử dụng phương pháp thống
kê một cách rất hiệu quả để đạt được mục đích của mình.
Mặc dù các phương pháp thống kê cung cấp một nền tảng lý thuyết
vững chắc cho các bài toàn phân tích dữ liệu nhưng chỉ có tiếp cận thống kê
thuần túy thôi chưa đủ. Thứ nhất, các phương pháp thống kê chuẩn không phù
hợp đối với các kiểu dữ liệu có cấu trúc trong rất nhiều các CSDL. Thứ hai,
thống kê hoàn toàn theo dữ liệu (data driven), nó không sử dụng tri thức sẵn
có về lĩnh vực. Thứ ba, các kết quả phân tích thống kê có thể sẽ rất nhiều và
khó có thể làm rõ được. Cuối cùng, các 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.
Sự khác nhau cơ bản giữa khai phá dữ liệu và thống kê là ở chỗ khai phá
dữ liệu là một phương tiện được dùng bởi người sử dụng đầu cuối chứ không
phải là các nhà thống kê. Khai phá dữ liệu tự động quá trình thống kê một
cách có hiệu quả, vì vậy làm nhẹ bớt công việc của người dùng đầu cuối, tạo

(chẳng hạn: tỉ lệ trả trên thu nhập, mức thu nhập, mức học vấn, vùng dân
cư, lịch sử tín dụng,…) có thể ảnh hưởng mạnh hoặc yếu đến việc thực
hiện trả tiền vay và sự đánh giá mức độ tín nhiệm khách hàng. Các phương
pháp KPDL như lựa chọn đặc trưng, xếp hạng các thuộc tính liên quan có thể
giúp xác định các yếu tố quan trọng và loại bỏ những yếu tố không liên quan.
Do đó, ngân hàng có thể điều chỉnh chính sách cho vay đối với những khách
hàng mà trước đây ngân hàng đã từ chối nhưng nay tỉ mạo hiểm đối với họ là
thấp dựa vào các phân tích trên.
- Phát hiện các tội phạm tài chính: Để phát hiện việc chuyển tiền bất
chính vào ngân hàng và các tội phạm tài chính, việc tích hợp thông tin từ các
CSDL khác nhau (CSDL giao dịch ngân hàng, CSDL về lịch sử tội phạm) là


13

rất quan trọng. Sau khi có dữ liệu tổng hợp, chúng ta có thể dựa trên các
công cụ của KPDL để phát hiện ra các mẫu khác thường.
1.1.6.3 Phân tích các mẫu gian lận và xác định các mẫu khác thường
Việc xác định những người dùng gian lận tiềm năng và những mẫu sử
dụng không điển hình là rất quan trọng. Những mẫu này có thể được khám phá
bởi phân tích đa chiều, phân tích phân cụm, phân tích phần tử ngoài cuộc.
1.1.7 Những thách thức trong ứng dụng và nghiên cứu kỹ thuật KPDL
Một số vấn đề khó khăn trong việc nghiên cứu và ứng dụng kỹ thuật
khai phá dữ liệu như sau:
1.1.7.1 Các vấn đề về cơ sở dữ liệu
Đầu vào chủ yếu của một hệ thống khai thác tri thức là các dữ liệu thô
trong cơ sở phát sinh trong khai phá dữ liệu chính là từ đây. Do các dữ liệu
trong thực tế thường động, không đầy đủ, lớn và bị nhiễu. Trong những
trường hợp khác, người ta không biết cơ sở dữ liệu có chứa các thông tin cần
thiết cho việc khai thác hay không và làm thế nào để giải quyết với sự dư thừa

• Các trường không phù hợp: Một đặc điểm quan trọng khác là tính
không thích hợp của dữ liệu, nghĩa là mục dữ liệu trở thành không thích hợp
với trọng tâm hiện tại của việc khai thác. Một khía cạnh khác đôi khi cũng
liên quan đến độ phù hợp là tính ứng dụng của một thuộc tính đối với một tập
con của cơ sở dữ liệu. Ví dụ trường số tài khoản Nostro không áp dụng cho
các tác nhân.
• Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính
dữ liệu phù hợp có thể ảnh hưởng đến việc khai phá dữ liệu. Trong hệ thống
tương tác, sự thiếu vắng dữ liệu quan trọng có thể dẫn đến việc yêu cầu cho
giá trị của nó hoặc kiểm tra để xác định giá trị của nó. Hoặc cũng có thể sự
vắng mặt của dữ liệu được coi như một điều kiện, thuộc tính bị mất có thể
được coi như một giá trị trung gian và là giá trị không biết.


15

Các trường bị thiếu: Một quan sát không đầy đủ cơ sở dữ liệu có thể
làm cho các dữ liệu có giá trị bị xem như có lỗi. Việc quan sát cơ sở dữ liệu
phải phát hiện được toàn bộ các thuộc tính có thể dùng để giải thuật khai phá
dữ liệu có thể áp dụng nhằm giải quyết bài toán. Giả sử ta có các thuộc tính để
phân biệt các tình huống đáng quan tâm. Nếu chúng không làm được điều đó
thì có nghĩa là đã có lỗi trong dữ liệu. Đối với một hệ thống học để chuẩn
đoán bệnh sốt rét từ một cơ sở dữ liệu bệnh nhân thì trường hợp các bản ghi
của bệnh nhân có triệu chứng giống nhau nhưng lại có các chẩn đoán khác
nhau là do trong dữ liệu đã bị lỗi. Đây cũng là vấn đề thường xảy ra trong cơ
sở dữ liệu kinh doanh. Các thuộc tính quan trọng có thể sẽ bị thiếu nếu dữ liệu
không được chuẩn bị cho việc khai phá dữ liệu.
Độ nhiễu và không chắc chắn: Đối với các thuộc tính đã thích hợp, độ
nghiêm trọng của lỗi phụ thuộc vào kiểu dữ liệu của các giá trị cho phép. Các
giá trị của các thuộc tính khác nhau có thể là các số thực, số nguyên, chuỗi và

làm cho mô hình hoạt động rất kém đối với các dữ liệu thử. Các giải pháp
khắc phục bao gồm đánh giá chéo (cross-validation), thực hiện theo nguyên
tắc nào đó hoặc sử dụng các biện pháp thống kê khác.
Đánh giá tầm quan trọng thống kê: Vấn đề (liên quan đến overfitting)
xảy ra khi một hệ thống tìm kiếm qua nhiều mô hình. Ví dụ như nếu một hệ
thống kiểm tra N mô hình ở mức độ quan trọng 0,001 thì với dữ liệu ngẫu
nhiên trung bình sẽ có N/1000 mô hình được chấp nhận là quan trọng. Để xử
lý vấn đề này, ta có thể sử dụng phương pháp điều chỉnh thống kê trong kiểm
tra như một hàm tìm kiếm, ví dụ như điều chỉnh Bonferroni đối với các kiểm
tra độc lập.
Khả năng biểu đạt của mẫu: Trong rất nhiều ứng dụng, điều quan
trọng là những điều khai thác được phải cáng dễ hiểu với con người càng tốt.
Vì vậy, các giải pháp thường bao gồm việc diễn tả dưới dạng đồ họa, xây dựng


17

cấu trúc luật với các đồ thị có hướng (Gaines), biểu diễn bằng ngôn ngữ tự
nhiên (Matheus et al.) và các kỹ thuật khác nhằm biểu diễn tri thức và dữ liệu.
Sự tương tác với người sử dụng và các tri thức sẵn có: rất nhiều công
cụ và phương pháp khai phá dữ liệu không thực sự tương tác với người dùng
và không dễ dàng kết hợp cùng với các tri thức đã biết trước đó. Việc sử dụng
tri thức miền là rất quan trọng trong khai phá dữ liệu. Đã có nhiều biện pháp
nhằm khắc phục vấn đề này như sử dụng cơ sở dữ liệu suy diễn để phát hiện
tri thức, những tri thức này sau đó được sử dụng để hướng dẫn cho việc tìm
kiếm khai phá dữ liệu hoặc sử dụng sự phân bố và xác suất dữ liệu trước đó
như một dạng mã hóa tri thức có sẵn
1.2 Tổng quan về gian lận BHYT trong kê đơn cấp thuốc
1.2.1 Giới thiệu chung
Theo Luật Bảo hiểm y tế, chính phủ thống nhất quản lý nhà nước về

công cụ hữu hiệu cũng như chính sách rõ rang trong việc kiểm soát cũng như
phát hiện gian lận.
1.2.4 Chức năng, nhiệm vụ của cơ quan Bảo hiểm trong y tế:
- Giám định bảo hiểm y tế.
- Thanh toán chi phí khám bệnh, chữa bệnh BHYT
1.3 Khai phá dữ liệu bằng luật kết hợp
1.3.1 Lý thuyết về luật kết hợp
Một trong những chủ đề phổ biến của KPDL là khám phá luật kết
hợp. Mục đích của khám phá luật kết hợp là xác định mối quan hệ, sự kết
hợp giữa các item trong một CSDL lớn. Luật kết hợp là một luật dạng X
=> Y, với X, Y là tập các item. Một luật kết hợp được gọi là mạnh, nếu nó
thoả độ hỗ trợ và thoả độ tin cậy tối thiểu.