Tài liệu Đề tài Phát hiện luật bằng cách sử dụng siêu phẳng tối ưu theo hướng tiếp cân tập thô: TÓM TĂT KHOÁ LUẬN TỐT NGHIỆP
Cùng với sự phát triển của Công Nghệ Thông Tin ngày nay, khai phá tri thức
trong các cơ sở dư liệu lớn là một trong nhưng lĩnh vực được rất nhiều nhà nguyên cứu
và ứng dụng tin học đặc biệt quan tâm. Việc nguyên cứu những phương pháp có thể tự
động phát hiện những tri thức mới trong cơ sở dư liệu trên máy tính đã tỏ ra thực sự
hữu ích trong việc hỗ trợ quyết định cho con người.
Hiện nay, trên thế giới có rất nhiều thuật toán khai phá tri thức bằng cách phân
lớp và rời rạc dữ liệu như: Sử dụng cây quyết định, phương pháp thống kê, các mạng
nơ ron, thuật toán di truyền,...Trong một vài năm gần đây, lý thuyết tâp thô được nhiều
nhóm nguyên cứu hoạt động trong lĩnh vực tin học nói chung và khai phá tri thức nói
riêng nguyên cứu và áp dụng trong thực tế. Lý thuyết tập thô được xây dựng trên nền
tảng toán học vững chắc giúp cung cấp những công cụ hữu ích để giải quyết những bài
toán phân lớp dữ liệu và khai phá luật,...Với đặc tính có thể ...
63 trang |
Chia sẻ: hunglv | Lượt xem: 1281 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Đề tài Phát hiện luật bằng cách sử dụng siêu phẳng tối ưu theo hướng tiếp cân tập thô, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
TÓM TĂT KHOÁ LUẬN TỐT NGHIỆP
Cùng với sự phát triển của Công Nghệ Thông Tin ngày nay, khai phá tri thức
trong các cơ sở dư liệu lớn là một trong nhưng lĩnh vực được rất nhiều nhà nguyên cứu
và ứng dụng tin học đặc biệt quan tâm. Việc nguyên cứu những phương pháp có thể tự
động phát hiện những tri thức mới trong cơ sở dư liệu trên máy tính đã tỏ ra thực sự
hữu ích trong việc hỗ trợ quyết định cho con người.
Hiện nay, trên thế giới có rất nhiều thuật toán khai phá tri thức bằng cách phân
lớp và rời rạc dữ liệu như: Sử dụng cây quyết định, phương pháp thống kê, các mạng
nơ ron, thuật toán di truyền,...Trong một vài năm gần đây, lý thuyết tâp thô được nhiều
nhóm nguyên cứu hoạt động trong lĩnh vực tin học nói chung và khai phá tri thức nói
riêng nguyên cứu và áp dụng trong thực tế. Lý thuyết tập thô được xây dựng trên nền
tảng toán học vững chắc giúp cung cấp những công cụ hữu ích để giải quyết những bài
toán phân lớp dữ liệu và khai phá luật,...Với đặc tính có thể xử lý được những dữ liệu
mơ hồ, không chắc chắn tập thô tỏ ra rất hữu ích trong việc giải quyết những bài toán
thực tế. Từ những bảng dữ liệu lớn với dữ liệu dư thừa, không hoàn hảo, dữ liệu liên
tục, hay dữ liệu dưới dạng ký hiệu lý thuyết tập thô cho phép khai phá tri thức từ
những khối dữ liệu này nhằm phát hiện những luật tiềm ẩn từ khối dữ liệu này.
Trong khoá luân tốt nghiệp chúng tôi đã trình bày một số phương pháp rời rạc
hoá dữ liệu theo hướng tiếp cận tập thô. Và xây dựng chương trình thử nghiệm: phát
hiện luật bằng cách sử dụng siêu phẳng tối ưu theo hướng tiếp cân tập thô. Chương
trình được xây dựng để thử nghiệm trên bộ dữ liệu chứa thông tin về 768 bệnh nhân bị
bệnh tiểu đường cung cấp bởi tổ chức “National Institute of Diabetes and Digestive
and Kidney Diseases”. Từ đó xây dựng hệ thống các luật dựa trên cây quyết định dùng
để hỗ trợ việc khám bệnh của các bác sĩ.
MỤC LỤC
MỤC LỤC .......................................................................................................................2
PHẦN MỞ ĐẦU .............................................................................................................5
Chương 1 TỔNG QUAN VỀ KHAI PHÁ TRI THỨC ...............................................8
1.1 . Khai phá tri thức....................................................................................................8
1.1.1. Định nghĩa khai phá tri thức .........................................................................8
1.1.2. Các giai đoạn của quá trình khai phá tri thức ...............................................8
1.1.3. Khai phá dữ liệu..........................................................................................10
1.2 . Khai phá tri thức theo cách tiếp cận tập thô........................................................12
1.2.1. Một số khái niệm ........................................................................................12
1.2.1.1. Khái niệm hệ thông tin ..................................................................12
1.2.1.2. Khái niêm về bảng quyết định.......................................................13
1.2.1.3. Khái niệm quan hệ không phân biệt được trong hệ thông tin. ......15
1.2.1.4. Khái niệm tập các nhát cắt, nhát cắt trong bảng quyết định..........16
1.2.1.5. Tập thô trong không gian xấp xỉ. ..................................................17
1.2.2. Khai phá tri thức theo cách tiếp cận tập thô. ..............................................19
1.2.2.1. Sự rời rạc hoá dữ liệu theo cách tiếp cận tập thô. .........................19
1.2.2.2. Lựa chọn thuộc tính dựa trên tập thô.............................................19
1.2.2.3. Khám phá luật bới bảng phân bố tổng quát dựa trên tập thô. .......20
1.2.2.4. Khám phá mẫu trong hệ thông tin. ................................................20
1.3 . Kết luận. ..............................................................................................................21
Chương 2 KHAI PHÁ LUẬT KẾT HỢP...................................................................22
2.1 . Khai phá luật kết hợp trong cơ sở dữ liệu. ..........................................................22
2.1.1. Bài toán xuất phát. ......................................................................................22
2.1.2. Mô hình hoá bài toán. .................................................................................22
2.1.3. Thuật toán khai phá luật kết hợp. ...............................................................25
2.1.3.1. Tập phổ biến. .................................................................................25
2.1.3.2. Khai phá luật dựa trên tập mục phổ biến.......................................25
2.1.4. Kết luận.......................................................................................................28
2.2 . Sinh cây quyết định từ hệ thông tin.....................................................................29
2.2.1. Thuật toán học cây quyết định....................................................................29
2.2.2. Một số phương pháp giải quyết vấn đề rời rạc hoá. ...................................35
2.2.2.1. Maximal Discernibility (MD) Heuristic........................................35
2.2.2.2. Sự rời rạc hoá định nghĩa bằng siêu phẳng. ..................................36
2.2.2.3. Những tính chất của phương thức MD..........................................39
2.2.2.4. Xây dựng cây quyết định không đối xứng. ...................................43
2.2.3. Kết luận.......................................................................................................50
Chương 3 CHƯƠNG TRÌNH THỬ NGHIỆM. .........................................................51
3.1 . Mô tả dữ liệu. ......................................................................................................51
3.2 . Xây dựng chương trình. ......................................................................................53
3.3 . Kết quả thử nghiệm. ............................................................................................57
3.4 . Nhận xét. .............................................................................................................61
KẾT LUẬN. ..................................................................................................................62
Tài liêu tham khảo: ........................................................................................................63
CÁC KÝ HIỆU SỬ DỤNG TRONG LUẬN VĂN
Ký hiệu Mô tả
A Hệ thông tin hay bảng quyết định
A, B Tập các thuộc tính trong hệ thông tin
D Tập thuộc tính quyết định trong hệ thông tin
a Một thuộc tính điêu kiện trong hệ thông tin
Va Tập giá trị của thuộc tính điều kiện a
U Tập tất cả các đối tượng
∅ Tập rỗng
⊆ Bị chứa trong
∈ Thuộc (phần tử thuộc tập hơp)
≥ Lớn hơn hoặc bằng
≤ Nhỏ hơn hoặc bằng
≠ Khác
∪, ∩ phép lấy giao và hợp của tập hợp
PHẦN MỞ ĐẦU
Trong một vài năm gần đây, ngành công nghệ thông tin trên toàn thế giới đã
phát triển mạnh mẽ với một tốc độ rất nhanh. Song song với điều đó chúng ta cũng
phải đối mặt với một thách thức mới là sự bùng nổ về lượng thông tin. Tuy nhiên, một
thực tế diễn ra rất phổ biến là mặc dù có một lượng dữ liệu rất lớn nhưng thông tin mà
thực sự chúng ta có là rất ít, những hiểu biết thực sự của chúng ta về lượng dữ liệu mà
chúng ta có còn rất hạn chế.
Xuất phát từ thực tế đó mà trong một vài năm gần đây các nhà nguyên cứu và
ứng dụng tin học phải nguyên cứu, tìm kiếm những phương pháp mới để khai thác triệt
để nhưng thông tin có trong cơ sở dữ liệu. Từ cuối những năm của thập kỷ 1980 khái
niệm phát hiện tri thức trong cơ sở dữ liệu lần đầu tiên được nói đến, đây là quá trình
phát hiện tri thức tiềm ẩn, không biết trước và hữu ích trong các cơ sở dữ liệu lớn.
Khắc phục hạn chế của những mô hình cơ sở dữ liệu truyền thống chỉ với
những công cụ truy vấn dữ liệu không có khả năng tìm kiếm các thông tin mới, các
thông tin tiềm ẩn trong cơ sở dữ liệu. Khai phá tri thức trong cơ sở dữ liệu là một quá
trình có thể tìm ra những thông tin mới, những thông tin hữu ích, và tiềm ẩn trong cơ
sở dữ liệu. Quá trình phát hiện tri thức gồm nhiều giai đoạn, trong đó giai đoạn khai
phá dữ liệu là quan trọng nhất. Đây là giai đoạn chính tìm ra những thông tin mới
trong cơ sở dữ liệu. Quá trình phát hiện tri thức là sự tiếp thu, sử dụng và phát triển các
thành tựu của nhiều lĩnh vực nguyên cứu ứng dụng tin học trước đó như: lý thuyết
nhận dạng, hệ chuyên gia, trí tuệ nhân tạo, thống kê, v.v.
Từ đầu những năm 80 Z. Pawlak đã đề xuất ra lý thuyết tập thô với một cơ sở
toán học rất chắc chắn. Trong những năm gần đây, lý thuyết tập thô được nhiều nhóm
nguyên cứu hoạt động trong lĩnh vực tin học nói chung và khai phá tri thức trong cơ sở
dữ liệu nói riêng nguyên cứu và áp dụng trong thực tế [2,4,6,10,12]. Lý thuyết tập thô
ngày càng được áp dụng rộng rãi trong lĩnh vực phát hiện tri thức. Nó tỏ ra rất hữu ích
trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật và đặc biệt hữu ích
trong các bài toán phải xử lý các dữ liệu mơ hồ, không chắc chắn. Các mối quan hệ
giữa dữ liệu trong mô hình này được biểu diễn qua mối quan hệ “không phân biệt
được”, các tập dữ liệu là mơ hồ, không chắc chắn được biểu diễn thông qua tập xấp xỉ
trên và xấp xỉ dưới của nó. Nhờ vào những điều này mà dữ liệu có thể phân tích và xử
lý bằng những công cụ toán học.
Cụ thể trong lý thuyết tập thô dữ liệu được biểu diễn thông qua hệ thông tin
hay bảng quyết. Từ trong thực tế, với những bảng dữ liệu lớn với dữ liệu không hoàn
hảo, có dữ liệu dư thừa, dữ liệu liên tục hay biểu diễn dưới dạng các ký hiệu, lý thuyết
tập thô cho phép khai phá tri thức trong những cơ sở dữ liệu như thế này nhằm phát
hiện những tri thức tiềm ẩn từ những khối dữ liệu “thô” này. Tri thức tìm được được
thể hiện dưới dạng các luật, các mẫu. Sau khi tìm được những quy luật chung nhất để
biểu diễn dữ liệu, người ta có thể tính toán độ mạnh và độ phụ thuộc giữa các thuộc
tính trong hệ thông tin.
Theo Skowron và NingZong [2], cách tiếp cận tập thô để phân tích dữ liệu có
rất nhiều điểm lợi quan trọng như sau:
− Cho phép xử lý hiệu quả bảng dữ liệu lớn, loại bỏ dữ liệu dư thừa, dữ liệu
không hoàn hảo, dữ liệu liên tục.
− Hiệu quả trong việc tìm kiếm những mẫu tiềm ẩn trong cơ sở dữ liệu.
− Sử dụng được tri thức kinh nghiệm.
− Nhận ra được những mối quan hệ mà khi sử dụng các phương pháp thống
kê khác không phát hiện được.
− Sử dụng quan hệ thứ lỗi trong quá trình phát hiện mẫu.
− Làm việc hiệu quả trên tập rút gọn.
− Cách giải thích rõ ràng và dễ hiểu.
Với những đặc điểm trên thì tập thô đã chứng tỏ là một trong những lý thuyết
rất hiệu quả trong lĩnh vực khai phá dữ liệu. Trong khoa luận tốt nghiệp này chúng tôi
xin trình bày một số ứng dụng và lý thuyết cơ bản của tâp thô. Việc phát hiện tri thức
được thực hiện bằng cách phân lớp, rời rạc hoá dữ liệu từ đó sinh ra các luật, các tri
thức mới. Phương pháp nguyên cứu chủ yếu của khoá luận tốt nghiệp là tìm hiểu và
phân tích nội dung các bài báo được công bố về lĩnh vực khai phá tri thức trong những
năm gần đây. Từ những kiến thức thu được chúng tôi đã xây dựng được chương trình
thử nghiệm mô phỏng thuật toán xây dựng cây quyết định tối ưu bằng cách sử dụng
siêu phẳng tối ưu được trình bày trong [9]. Chương trình tiến hành khai phá tri thức
trong cớ sở dữ liệu lưu thông tin về 678 bệnh nhân tiểu đường cung cấp bởi tổ chức
“National Institute of Diabetes and Digestive and Kidney Diseases”. Từ đó sinh ra các
luật quyết định hỗ trợ trong quá trình khám bệnh của bệnh nhân.
Khoá luận tốt nghiệp được trình bày gôm 3 phần: Phần mở đầu, 3 chương và
phần kết luận. Trong đó:
Chương 1: Khóa luận trình bày những kiến thức chung nhất về khai phá tri
thức và khai phá tri thức theo cách tiếp cận tập thô.
Chương 2: Khóa luận trình bày về chi tiết một số thuật toán khai phá tri thức,
chủ yếư là khai phá các luật trong các cơ sở dữ liệu. Trong đó đáng chú ý là thuật toán
xây dựng cây quyết định tối ưu bằng cách sử dụng siêu phẳng tối ưu.
Chương 3: Khóa luận trình bày kết quả thử nghiệm bài toán khai phá luật
trong cây quyết định tối ưu trình bày ở chương 2 và áp dụng trên cơ sở dữ liệu bệnh
nhân bị tiểu đường được lấy về từ trên mạng. Qua đó đánh giá được sự hiệu quả của
thuật toán được trình bày trong [9].
Khóa luận được hoàn thành duới sự giúp đỡ của Tiến Sĩ. Hà Quang Thuỵ , Bộ
môn các hệ thông thông tin, Khoa Công Nghệ, ĐHQG Hà Nội. Em xin bày tỏ lòng
kính trọng và sự biết ơn sâu sắc tới Thầy đã hướng dẫn, động viên và tạo điều kiện cho
em trong quá trình làm khoá luận tốt nghiệp. Em xin chân thành cảm ơn Thầy Đỗ
Văng Thành, Văn phong chính phủ, người đã truyền thụ cho em những kiến thức nền
tảng và cơ sở để em có thể hoàn thành bản khoá luận tôt nghiệp này. Em xin chân
thành cảm ơn các thầy cô giáo trong bộ môn Các Hệ Thống Thông Tin, nhóm
“Seminar Data Mining and KDD”. Cuối cùng em xin chân thành cảm ơn tới những
người thân trong gia đình, bạn bè đã giúp đỡ và động viên em rất nhiều trong quá trình
nguyên cứu và học tập.
Chương 1 TỔNG QUAN VỀ KHAI PHÁ TRI THỨC
1.1 . Khai phá tri thức
Phát hiện tri thức là khái niệm ra đời vào những năm cuối của thập kỷ 80 và đã
trở thành một lĩnh vực được nguyên cứu rộng rãi trên toàn cầu. Sự ra đời của phát hiện
tri thức là sự kết hợp kết quả nguyên cứu của nhiều ngành khoa học khác lại với nhau
như: Quản trị cơ sở dữ liệu, học máy, thống kê v.v.
1.1.1. Định nghĩa khai phá tri thức
Khai phá tri thức (Khai phá tri thức-Knowledge Discovery in Databases) trong
các cơ sở dữ liệu là quá trình phát hiện những tri thức tiềm ẩn, không biết trước, và có
ích trong trong cơ sở dữ liệu. Thực chất đó là quá trình tìm kiếm những thông tin có
trong cơ sở dữ liệu nhưng bị che giấu trong các khối dữ liệu.
Tri thức ở đây có thể được hiểu là một biểu thức trong một ngôn ngữ nào đó
diễn tả một hoặc nhiều mối quan hệ giữa các thuộc tính trong các dữ liệu đó. Các ngôn
ngữ thường dùng để biểi diễn tri thức trong việc biểu diễn tri thức trong quá trình phát
hiện tri thức từ cơ sở dư liệu là các khung (frames), các cây và đồ thị, các luật, các
công thức trong logic mệnh đề hoặc logic tân từ cấp một . . .
Việc khai phá tri thức thường được áp dụng để giả quyết một loạt những yều
cầu phục vụ những mục đích nhất định. Do vậy nên quá trình phát hiện tri thức mang
tính chất hướng nhiệm vụ, không phải là phát hiện mọi tri thức mà phát hiện những tri
thức phục vụ tốt một nhiệm vụ đề ra. Vì vậy, quá trình phát hiện tri thức là một hoạt
động tương tác giữa một người sử dụng hoặc một chuyên gia phân tích với các công cụ
tin học.
1.1.2. Các giai đoạn của quá trình khai phá tri thức
Mục đích của quá trình khai phá tri thức: Từ những cơ sở dữ liệu ngoài cuộc
sống thực tế sau một hoặc một số bước của quá trình sẽ rút ra được những tri thức mới.
Các bước trong quá trình này có thể lặp đi lặp lại nhiều lần và được mô tả theo hình
sau [4,8]:
Hình 1. Mô hình mô tả quá trình khai phá tri thức.
Giai đoạn 1:Xác định và định nghĩa vấn đề.
− Tìm hiểu lĩnh vực ứng dụng và nhiệm vụ đề ra, xác định các tri
thức đã có và các mục tiêu của người sử dụng.
− Tạo và chọn lựa cơ sở dữ liệu.
Giai đoạn 2: Thu nhập và tiền xử lý dữ liệu.
− Xử lý và làm sạch dữ liệu trước: Bỏ đi các dữ liệu tạp bao gồm các
lỗi và các dạng không bình thường. Xử lý dữ liệu bị mất, chuyển đổi
dữ liệu phù hợp.
− Rút gọn kích thước dữ liệu nhận được: Nhận ra các thuộc tính hữu
ích cho quá trình phát hiện tri thức.
Giai đoạn 3: Khai phá dữ liệu.
− Chọn nhiệm vụ khai phá dữ liệu.
− Lựa chọn các phương pháp khai phá dữ liệu.
− Khai phá dữ liệu để rút ra các mẫu, các mô hình.
Giai đoạn 4:Giải thích kết quả và đánh giá các mẫu, các mô hình tìm được ở
giai đoạn 3.
Xác định và định
nghĩa vấn đề
Thu nhập và tiền
xử lý dữ liệu
Khai phá dữ liệu
Giải thích kết quả
và đánh giá
Sử dụng tri thức
phát hiện được
1
2
3
4
5
Giai đoạn 5: Sử dụng tri thức phát hiện được.
− Các tri thức phát hiện được tích hợp chặt chẽ trong hệ thống. Tuy
nhiên để sử dụng được tri thức đó đôi khi cần đến các chuyên gia
trong các lĩnh vực quan tâm vì tri thức rút ra có thể chỉ có tính chất hỗ
trợ quyết định.
− Tri thức tìm được có thể được sử dụng cho một quá trình khai phá
tri thức khác.
Như vậy khai phá tri thức gồm 5 giai đoạn chính, trong 5 giai đoạn trên thì
giai đoạn khai phá dữ liệu là quan trọng nhất. Đây là giai đoạn duy nhất tìm được các
thông tin tiềm ẩn trong cơ sở dữ liệu.
1.1.3. Khai phá dữ liệu
Khai phá dữ liệu (hay data mining) được định nghĩa như là quá trình phát hiện
các tri thức mới, có giá trị từ những dữ liệu lớn được lưu trữ trong cơ sở,
datawarehouse hay các kho chứa thông tin khác. Khai phá dữ liệu là một giai đoạn
quan trọng trong quá trình phát hiện tri thức. Về bản chất nó là giai đoạn duy nhất tim
ra được thông tin mới, thông tin tiềm ần có trong cơ sở dữ liệu. Mục đích nguyên thủy
của khai phá dữ liệu là mô tả và dự đoán [4]. Các kỹ thuật khai phá dữ liệu được chia
thành những mảng chính sau:
• Phân cụm và phân lớp dữ liệu: Quá trình này có thể xem là quá trình phân
tích một tập dữ liệu và sinh ra một tập nhóm các luật mà chúng ta có thể sử
dụng để phân lớp dữ liệu trong tương lai. Khi phân lớp dữ liệu người ta
thường dựa trên một tập các mẫu huấn luyện để sinh ra các luật. Có rất nhiều
phương pháp để phân lớp dữ liệu được nguyên cứu như: Các phương pháp
học cây quyết định, phương pháp thông kê, các mạng nơ ron, các mạng xác
xuất Bayes,. . .
• Khai phá luật kết hợp: Mong muốn tìm ra những mối quan hệ giữa các
thuộc tính hoàn toàn độc lập với nhau trong cơ sở dữ liệu. Luật kết hợp có thể
dùng để hỗ trợ quyết định. Ví dụ như các bài toán kinh doanh.
• Khai phá chuỗi: Luật chuỗi và khai phá chuỗi có thể coi như là một cách
trừu tượng của luật kết hợp và phát hiện các luật kết hợp trong cơ sở dữ liệu
phụ thuộc thời gian.
Có rất nhiều phương pháp để có thể tiến hành khai phá dữ liệu đã được nguyên
cứu và đề ra như:
− Các phương pháp sinh cây quyết định.
− Các phương pháp thống kê.
− Các mạnh nơ ron.
− Các mạng xác suất Bayes.
− Các thuật toán di truyền.
− Phương pháp người láng giềng gần nhất.
− Luật suy diễn.
− Trực quan hoá dữ liệu.
− .v.v.
Như vậy, khai phá dữ liệu là một giai đoạn quan trọng trong quá trình khai phá
tri thức và nó đang được áp dụng rộng rãi trong nhiều lĩnh vực như:
− Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision
support)
− Điều trị y học (medical treatment)
− Text mining & Web mining
− Tài chính và thị trường chứng khoán (finance & stock market)
− Bảo hiểm (insurance)
− Nhận dạng (pattern recognition)
− .v.v.
1.2 . Khai phá tri thức theo cách tiếp cận tập thô
1.2.1. Một số khái niệm
1.2.1.1. Khái niệm hệ thông tin
Trong hầu hết các hệ quản trị cơ sở dữ liệu thông thương thì thông tin thường
được biểu diễn dưới dạng các bảng, trong dó mỗi hang biểu diễn thông tin về một đối
tượng, mỗi cột biểu diễn thông tin về một thuộc tính của đối tượng. Tứ đầu những năm
80 Pawlak đã định nghĩa một khái niệm mới là hệ thông tin (infomation system) dựa
trên khái niệm bảng truyền thống như sau [2,5,10,12]:
Đinh nghĩa 1: Hệ thông tin là một cặp A = (U,A).
Trong đó:
U : là một tập hữu hạn khác rỗng các đối tượng.
A : là một tập hữu hạn khác rỗng các thuộc tính.
a: U → Va với mọi a ∈ A. Tập Va được gọi là tập giá trị của
thuộc tính a.
Ví dụ: Có một hệ thông tin được biểu diễn như bảng sau: Trong bảng có 7 đối tượng
và có 3 thuộc tính là số lần mang thai của bệnh nhân (1), lượng glucose trong huyết
tương sau 2 giờ uống thuốc (2), tuổi của bệnh nhân (8).
Mỗi đối tượng của bảng là một bệnh nhân đang tham gia khám bệnh tiểu
đường, trong đó các bác sĩ dựa vào một số chỉ số tương ứng với các thuộc tính sau để
xác định tình trạng của bệnh nhân.
Để thuận tiện cho việc trình bày từ giờ chúng ta chỉ ký hiệu các thuộc tính là
(1), (2), (8).
(1) (2) (8)
X1 2 102 31
X2 4 146 70
X3 3 102 28
X4 2 90 37
X5 2 90 31
X6 2 146 28
X7 2 102 31
Bảng 1. Ví dụ về hệ thông tin.
Trong ví dụ trên thì ta có một hệ thông tin A =(U, A).
U={X1, X2, X3, X4, X5, X6, X7}.
A={1,2,8,9}.
Nhìn vào các đối tượng trong ví dụ trên ta thấy X1 và X7 là có các giá trị của
các thuộc tính là giống nhau. Như vậy, X1 và X7 là không phân biệt được theo các
thuộc tính trong bảng trên. Chúng ta sẽ tiếp tục đề cập đến điều này trong các ví dụ
sau.
Định nghĩa 2: Với một hệ thông tin bất kỳ A = (U,A) và một tập không rỗng
các thuộc tính B⊆A định nghĩa một hàm thông tin B như sau:
InfB = {(a, a(x)): a∈ B} với mọi x ∈ A.
Trường hợp đặc biệt B=A, khi đó tập {InfA(x): x ∈ A} được gọi là tập thông tin
A, viết tắt là INF(A).
1.2.1.2. Khái niêm về bảng quyết định.
Để có thể biểu diễn một dữ liệu thực tế, trong đó có những thuộc tính quyết
đinh, chúng ta xét một trường hợp đặc biệt của hệ thông tin được gọi là bảng quyết
định được định nghĩa như sau[9].
Định nghĩa 3: Bảng quyết định là một hệ thông tin có dạng
A = (U, A∪{d})
Trong đó: d ∉A là thuộc tính phân biệt, được gọi là thuộc tính quyết định.
Các thành phần của A được gọi là các thuộc tính điều kiện.
Ví dụ:
Bảng 2 mô tả một bảng quyết định, với các thuộc tính điều kiện lấy ở bảng 1 và
thêm vào thuộc tính quyết đinh (9).Trong đó thuộc tính thứ (9) chỉ nhận hai giá trị là
1(ứng với trường hợp bị bệnh), và 2(ứng với trường hợp không bị bệnh)
(1) (2) (8) (9)
X1 2 102 31 1
X2 4 146 70 2
X3 3 102 28 1
X4 2 90 37 2
X5 2 90 31 1
X6 2 146 28 2
X7 2 102 31 2
Bảng 2. Ví dụ một bảng quyết định.
Nhìn vào bảng 2 ta tiếp tục xét các đối tượng X1 và X7 ta thấy chúng có giá trị
của các thuộc tính điều kiện là giống nhau, nhưng đối với kết quả quyết định đối với 2
đối tượng là khác nhau. Như thế chỉ dùng các thuộc tính điều kiện xét trong ví dụ trên
thì không thể xác định rõ tính chất bị bệnh hay không bị bệnh của một đối tượng bất
kỳ. Sẽ tồn tại trường hợp mà với những giá trị điều kiện được đưa ra ta không thể xác
định đối tượng đó có bị bệnh hay không.
Chúng ta giả sử rằng tập các giá trị của giá trị quyết định d tương đương với tập
{1, . . ., r(d)} là các số nguyên dương từ 1 đến r(d), tập này được gọi là phạm vi của
thuộc tính quyết đinh d. Ta định nghĩa một lớp quyết định thứ k như sau:
Địng nghĩa 4: Một lớp quyết định thứ k (ký hiệu là Ck) là một tâp các đối tượng
thoả mãn: Ck ={u ∈ U: d(u)=k}. Trong đó 1≤ k ≤r(d).
Khi đó giá trị quyết định d sẽ chia tập các đối tượng thành r(d) lớp quyết định
phần:{C1,..., Cr(d)}.
Chú ý: Trong trường hợp tổng quát thì có thể có nhiểu thuộc tính quyết định, khi dó
bảng quyết định có dạng [10]
A=(U, Con∪Dec).
Trong đó:
Con: là tập các thuộc tính điều kiện.
Dec: là tập các thuộc tính quyết định.
1.2.1.3. Khái niệm quan hệ không phân biệt được trong hệ thông tin.
Một trong những đặc điểm cơ bản của lý thuyết tập thô là dùng để lưu giữ và
sử lý các dữ liệu trong đó có sự mập mờ, không phân biệt được [2,5,12]. Trong một hệ
thông tin theo định nghĩa trên cũng có thể có những đối tương không phân biệt được.
Trước tiên ta nhắc lại định nghĩa quan hệ tương đương như sau:
Định nghĩa 5: Một quan hệ hai ngôi (quan hệ nhị phân) R ⊆ U × U trên U là
một quan hệ tương đương khi nó có cả 3 tính chất:
• Phản xạ: Mọi đối tượng đều quan hệ với chính nó.
• Đối xứng: Nếu xRy thì yRx.
• Bắc cầu: Nếu xRy và yRz thì xRz.
Quan hệ tương đương R sẽ chia tập các đối tượng U thành các lớp tương
đương. Lớp tương đương của phần tử x∈U, ký hiệu là [x], chứa tất cả các đối tượng y
mà xRy.
Bây giờ chúng ta bắt đầu định nghĩa một quan hệ tương đương trên hệ thông
tin. Quan hệ này sau này được sử dụng đê biểu diễn những thông tin mập mờ, không
rõ ràng.
Định nghĩa 6: Một quan hệ tương đương (ký hiệu là INDA(B)), được định
nghĩa như sau:
INDA(B)={(x,x’) ∈ U2 ⏐∀a ∈ B: a(x) = a(x’)}
Trong đó:
B: là một tập thuộc tính của các đối tượng, B∈A.
x, x’: là hai đối tượng bất kỳ thuộc U.
Khi đó INDA(B) là một quan hệ không phân biệt được B. Khi đó thì hai đối
tượng x, x’, mà (x, x’)∈INDA(B) thì khi đó hai đối tượng x, x’ được gọi là không phân
biệt được bởi các thuộc tính trong B. Khi xét trên một hệ thông tin xác định thì ký hiệu
A thường được bỏ qua, ta sẽ viết là IND(B) thay cho INDA(B).
Lớp tương đương chứa x của quan hệ không phân biệt được trên B được ký
hiệu là [x]B.
Ví dụ:Tiếp tục xét ví dụ trong bảng 2, ta xem xét các tập thuộc tính điều kiện
là: |(1)|, |(2)|, |(1), (2)|. Khi đó các quan hệ không phân biệt được trên các tập thuộc
tính điều kiện trên sẽ chia tập các đối tương trên thành các tập sơ cấp tương ứng như
sau:
IND(|(1)|)=| | X1, X4, X5, X6, X7 |, | X2 |, |X3| |.
IND(|(2)|)=| | X1, X3, X7 |, | X4, X5 |, |X2, X6| |.
IND(|(2)|, |(1)|)=| | X1, X7 |, | X4, X5 |, |X2|, |X3|, |X6| |.
Định nghĩa 7: Với một hệ thông tin bất kỳ A = (U,A) và một tập không rỗng
các thuộc tính B⊆A ta định nghĩa một hàm σB=U→2{1, . . .,r(d)} gọi là quyết định phổ
biến như sau:
σB(u)={i:∃u’∈U[(u IND(B) u’)∧d(u’)=i]}.
Một bảng quyết định A được gọi là thống nhất nếu card(σa(u)) với mọi u∈ U,
ngược lại thì A được coi là không thống nhất.
1.2.1.4. Khái niệm tập các nhát cắt, nhát cắt trong bảng quyết định
Trong quá trình phân lớp và rời rạc dữ liệu, ta có thể dùng nhiều phương pháp.
Tuy nhiên, sử dụng nhát cắt để phân lớp dữ liệu là một trong những phương pháp phổ
biến. Ta xét đinh nghĩa nhát cắt dưới đây.
Định nghĩa 8: Xét một bảng quyết định A =(U, A ∪ {d} ).
Trong đó:
U= {x1, . . . ,xn}, A={a1, . . . ,ak} và d:U→{1,. . .,r}
Giả sử Va=[la, ra) ⊂ R với mọi a thuộc A Chúng ta giả sử rằng A là một bảng
quyết định thống nhất.
Xét Pa là một cách chia Va thành các khoảng con như; { }),[.,.),.,[),,[ 12110 akakaaaaa aa ccccccP += với ka là một số nguyên khi:
a
a
k
a
k
aa
a rccccl aa =<<<<= +110 K
và
).,[...),[),[ 12110
a
k
a
k
aaaa
a aa
ccccccV +∪∪∪=
Khi đó Pa sẽ định nghĩa duy nhất tập các nhát cắt trên Va : { }akaaa acccC ,,, 10 K=
và bộ (a,c) trong đó a∈A và c ∈ Ca được gọi là một nhát cắt trên Va.
Định nghĩa nhát cắt trên đây cho thấy mỗi nhát cắt sẽ phân hoạch tập các đối
tượng thành hai tập con các đối tượng rời rạc nhau. Khái niệm nhát cắt sẽ được sử
dụng để rời rạc hoá dữ liệu trong thuật toán được trình bày ở chương 2 phần 2.2.2.1.
1.2.1.5. Tập thô trong không gian xấp xỉ
Để hiểu rõ về việc hệ thông tin biểu diễn và xử lý dữ liệu thô như thế nào ta
xét định nghĩa dưới đầy. Ta xét R là một quan hệ tương đương theo định nghĩa 6 với
trường hợp đặc biệt B=A gồm tất cả các thuộc tính. Lớp tương đương theo quan hệ R
được gọi là các tập sơ cấp [2,10] và gọi E là tập các tập sơ cấp. Z. Pawlak đã đưa ra
khái niệm tập mô tả được như sau [10].
Định nghĩa 9: Một tập con X khác rỗng các đối tượng được gọi là mô tả được
khi và chỉ khi X là tập hợp của các tập sơ cấp trong hệ thông tin (trong trường hơp đặc
biệt tập rỗng cũng được coi là tập mô tả được).
Như vậy một tập các đối tượng bất kỳ có thể là mô tả được hoặc không mô tả
được theo các tập sơ cấp E. Một vấn đề đặt ra là làm sao có thể tìm ra một cách để biểu
diễn các tập không mô tả được theo các tập sơ cấp E.
Nhìn vào bảng quyết định, ta xét một tập các đối tượng X có cùng một giá trị
của thuộc tính quyết định là d, khi đó sẽ có nhiều trường hợp X không mô tả được theo
các tập sơ cấp. Ta chỉ tìm được một tập mô tả được (có số đối tượng là nhỏ nhất)
không những chứa tất cả các phần tử thuộc X mà còn chứa các phần tử không thuộc X.
Ví dụ:Ta tiếp tục xét bảng 2, và tập B là tâp các thuộc tính điều kiện. Khi đó
thì tập các tập sơ cấp của quan hệ không phân biệt được trên tập thuộc tính B là:
[X1]B=[X7]B={X1, X7},
[X2]B={X2},
[X3]B={X3},
[X4]B={X4},
[X5]B={X5},
[X6]B={X6}
Ta xét một tập X các bệnh nhân là bị bệnh (thuộc tính quyết định có giá trị 1)
X={X1, X3, X5}. Khi đó tập X là không mô tả được theo tập các tập sơ cấp trên. Hai
bệnh nhân X1 và X7 thuộc cùng một tập sơ cấp nhưng có giá trị quyết định khác nhau.
Khi diễn tả tập X có bênh nhân X1 thì phải chứa tập sơ cấp [X1]B. Mà tập [X1]B thì lại
chứa bênh nhân X7 là không bị bệnh (thuộc tính quyết định có giá trị là 2). Như vậy
tập X là không mô tả được theo các tập sơ cấp trên.
Khắc phục hạn chế trên ta có thể dùng tính chất của lý thuyết tập thô để biểu
diễn tập X ở trên. Chúng ta không trực tiếp biểu diễn tập X mà đi tìm các tập là mô tả
được là tập xấp xỉ trên và tập xấp xỉ dưới của X. Tập xấp xỉ dưới của X là tập bao gồm
những người chắc chắn bị bệnh {X3, X5}, còn tập xấp xỉ trên của X là tập những
người có khả năng bị bệnh {X1, X3, X5, X7}. Ta xem xét các bệnh nhân không thuộc
tập những người chắc chắn bị bệnh mà lại thuộc tập những người có khả năng bị
bệnh {X1, X7}.Tập này là vùng ranh giới giữa trường hợp chắc chắn và trường hợp
có khả năng bị bệnh. Nếu tập ranh giới này không rỗng thì tập này được gọi là thô. Ta
có định nghĩa sau [10]:
Định nghĩa 10: Giả sử A =(U,A) là một hệ thông tin và B ⊆ A và X ⊆ U, thì
các tập xấp xỉ của X theo thông tin có từ B, được tính theo các công thức sau:
(1) Tập B-xấp xỉ dưới của X, ký hiệu là XB , là tập XB ={x∈U: [x]B ∈ X}.
(2) Tập B-xấp xỉ trên của X, ký hiệu là XB , là tập XB ={x∈U:[x]B∩X≠∅}.
Theo định nghĩa trên thì khi gặp một tập X mà ta không thể mô tả được bằng
các tập sơ cấp E là các lớp tương đương của quan hệ INDA(B), ta chỉ có thể có được
xấp xỉ trên và xấp xỉ dưới của nó.
a) Các tính chất của sự xấp xỉ[2,12]:
(1) XB ⊆ X ⊆ XB ,
(2) B (∅) = B (∅), B (U) = B (U) = U,
(3) B (X ∪ Y) = B (X) ∪ B (Y),
(4) B ( X ∩ Y) = B (X) ∩ B (Y),
(5) Nếu X ⊆Y thì B (X) ⊆B (Y) và B (X) ⊆ B (Y),
(6) B ( X ∪ Y) ⊇ B (X) ∪ B (Y),
(7) B (X ∩Y) ⊆ B (X) ∩B (Y),
(8) B (-X) = - B (X),
(9) B (-X) = - B (X),
(10) B ( B (X)) = B ( B (X)) = B (X),
(11) B ( B (X)) = B ( B (X)) = B (X).
Ký hiệu –X biểu thi thay cho U-X.
b) Bốn loại tập thô cơ bản:
Người ta phân tập thô thành 4 loại [9]:
• X là xác định thô thực sự theo B nếu XB ≠ ∅ và XB ≠ U.
• X là không xác định bên trong theo B nếu XB = ∅ và XB ≠ U.
• X là không xác đinh bên ngoài theo B nếu XB ≠ ∅ và XB = U.
• X là không xác định thực sự theo B nếu XB = ∅ và XB = U.
c) Độ đo liên quan biên xấp xỉ:
Tập thô được chỉ số hoá bởi hệ số sau:
Trong đó:
)(XBα : gọi là độ đo liên quan xấp xỉ của X.
|X| : là lực lượng của X.
Ta có thể thấy 0≤ )(XBα ≤1. Nếu )(XBα =1 thì X đúng hoàn toàn đối với tập
thuộc tính B, ngược lại thì )(XBα <1 thì X là thô đối với B.
1.2.2. Khai phá tri thức theo cách tiếp cận tập thô.
Như đã trình bày ở trên, khai phá tri thức từ cơ sở dữ liệu đang là vấn đề được
rất nhiều người quan tâm [2,12]. Việc tìm kiếm tri thức trong các cơ sở dữ liệu được
tiến hành theo rất nhiều phương pháp khác nhau. Trong đó khai phá tri thức theo cách
tiếp cân tập thô là một phương pháp tỏ ra đặc biệt hiệu quả đối với những dữ liệu lớn
và nhiều kiểu khác nhau. Hơn thế nữa nó con có thể làm tốt với những cơ sở dữ liệu
không chắc chắn, có tính mơ hồ, không phân biệt được.
1.2.2.1. Sự rời rạc hoá dữ liệu theo cách tiếp cận tập thô
Trong lĩnh vực khai phá tri thức, một vấn đề đặt ra là làm sao chúng ta có thể
xử lý cả được những dữ liệu hỗn tạp với những giá trị liên tục. Có rất nhiều thuật toán
được sử dụng trong lĩnh vực rời rạc hoá dữ liệu như: Các phương pháp lập luận logic,
thuật toán NAIVE, . . . tuy nhiên không có một thuật toán được gọi là tối ưu và hiệu
quả nhất. Việc lưa chọn thuật toán vẫn còn phụ thuộc vào dạng dữ liệu mà chúng ta
cần xử lý. Các tác giả trong [1,2] đã đưa ra một số phương pháp rời rạc hoá dữ liệu
dựa trên tập thô và lập luận logic.
Khi sử dụng phương pháp rời rạc hoá dữ liệu thì có nghĩa là chúng ta đã chấp
nhận sai số trong dữ liệu. Một ví dụ là khi đo về nhiệt độ của cơ thể thì ta thương gặp
những số thực nhưng chúng ta thường phải quy về giá trị nguyên hay những khoảng
khác nhau tuỳ từng bài toán cụ thể. Việc phân chia các giá trị thực thành các khoảng
hợp lý là rất phức tạp. Khi đó thường cần phải có các chuyên gia trong các lĩnh vực cụ
thể tham gia cùng.
1.2.2.2. Lựa chọn thuộc tính dựa trên tập thô
Các cơ sở dữ liệu trong thực tế thương có rất nhiều thuộc tính, những thuộc
tính cần thiết cho lĩnh vực mà bài toán khai phá dữ liệu mà chúng ta đang xử lý không
phải là tất cả. Việc lựa chọn những thuộc tính phù hợp để tiến hành các phương pháp
khai phá dữ liệu là rất cần thiết. Các thuộc tính dư thừa không cần thiết trong quá trình
khai phá tri thức không chỉ làm cho bài toán trở lên phức tạp mà còn dẫn đền một thực
,
)(
)(
)(
XB
XB
XB =α
tế là số tri thức được phát hiện sẽ không nhiều vì phải phụ thuộc vào cả những thuộc
tính không được coi là đặc trưng của bài toán. Mục tiêu của việc lựa chọn thuộc tính là
phải đưa ra được một tập tối ưu các thuộc tính trong cơ sở dữ liệu. Từ đó các luật sinh
ra trong cơ sở dữ liệu sẽ đạt được hiệu quả cao nhất, dữ liệu mà chúng ta thực sự phải
làm việc sẽ nhỏ đi rất nhiều.
Có hai phương pháp lựa chọn thuộc tính thường được sử dụng là lọc và bọc.
Trong đó thì phương pháp lọc thực chất là tìm những thuộc tính tối thiểu trong tập các
thuộc tính, chọn ra các thuộc tính có độ phù hợp cao hơn theo tiêu chuẩn sau:
− Lựa chọn những thuộc tính là cho số trường hợp thoả mãn tăng
nhanh.
− Chọn những thuộc tính có it giá trị khác nhau.
Phương pháp này là khá đơn giản và tốc độ là tương đối nhanh. Phương pháp
thứ hai sử dụng thuật toán quy nạp đánh giá. Tư tưởng của thuật toán này là sử dụng 3
cách tìm kiếm: tìm kiếm toàn bộ, tìm kiếm kinh nghiệm và tìm kiếm không xác định.
Phương pháp này sử dụng các thuật toán quy nạp nên độ phức tạp lớn nhưng bù lại thì
kết quả mang lại sẽ chính xác và toàn diện hơn.
1.2.2.3. Khám phá luật bới bảng phân bố tổng quát dựa trên tập thô
Bảng phân bố tổng quát có những đặc điểm sau:
− Bảng phân bố tổng quát mô tả quan hệ xác suất giữa các trường hợp có
thể và các bộ sinh có thể.
− Những trường hợp không thấy trong quá trình khai phá dữ liệu sự không
chắc chắn của luật bao gồm cả khả năng dự đoán trước các trường hợp
nó không được thể hiện rõ ràng trong độ mạnh của luật.
− Có thể sử dụng tri thức nền làm cơ sở cho việc lập bảng phân bố tổng
quát và quá trình khai phá.
A. Skowronvà Ning Zong [2] đã đưa ra phương pháp khám phá luật sư dụng
bảng phân bố tổng quát dựa trên tập thô với ý tưởng như sau:
− Từ bảng quyết định xây dựng bảng phân bố tổng quát.
− Dựa trên các bảng phân bố tổng quát này sinh các vector phân biệt được.
− Tạo ra các tập rút gọn được từ các tập vector phân biệt được.
− Sinh ra các luật bao phủ tất cả các trường hợp.
1.2.2.4. Khám phá mẫu trong hệ thông tin
Việc tìm những mẫu quan hệ phức tạp được phát hiện trong những cơ sở dữ
liệu lớn một cách tự động là một trong những hướng nghiên cứu đang được chú trọng
trên thế giới. Trong trường hợp đơn giản thì mẫu chỉ là một vector có giá trị độ dài đủ
lớn của một sô thuộc tính được hỗ trợ của một lượng đủ lớn các đối tượng. Các bài
toán tìm mẫu thường có độ phức tạp lớn đòi hỏi những thuật toán tối ưu, thuật toán
đánh giá kinh nghiệm đủ tốt để có thể rút ra các mẫu gần tối ưu từ những cơ sở dữ liệu
lớn. Một lớp quan trọng của của phương pháp tìm kiếm mẫu là dựa trên những khuôn
mẫu quan hệ. Những khuôn mẫu này được xác định từ một bảng dữ liệu cho trước sử
dụng quan hệ thứ lỗi trong một số lớp quan hệ thứ lỗi giả định trước. Một quan hệ thứ
lỗi là tối ưu nếu tập các tham số miêu tả quan hệ này cho phép xây dựng những khuôn
mẫu dữ liệu thích hợp trên những bảng dữ liệu cho trước.
Có rất nhiêu ứng dụng cho việc phát hiện những khuôn mẫu trong hệ thông
tin. Một số có thể dùng để tách các bảng dữ liệu lớn, bảng dữ liệu lớn có thể được
phân chia thành một cây nhị phân của các mẫu và khuôn mẫu. Mỗi nút của cây phụ
thuộc vào một bước phân tách. Quá trình phân chia dừng lai khi thu được những bảng
có kích thước đủ nhỏ để có thể áp dụng nhưng phương pháp khai phá tri thức khác.
Người ta áp dụng những phương pháp tìm kiếm mẫu quyết định từ những bảng quyết
đinh gắn với các lá đã có dựa trên cách tiếp cận tập thô. Quá trình phân lớp cho một
đối tượng mới bắt đầu bằng việc tìm ra đường đi trên cây bằng cách so sánh các mẫu.
Sau đó, đối tượng được phân lớp dựa trên luật quyết định được sinh ra từ bảng con gắn
với các lá ở trên đường đó.
Việc lựa chon một chiến lược tìm kiếm khuôn mẫu có trong các lớp quyết định
đã được thảo luận rất nhiều. Quá trình này có thể coi là quá trình tìm luật quyết định
xấp xỉ mạnh ngầm định.
Các phương pháp này cũng có thể dùng để tìm luật quyết định xấp xỉ tổng hợp
từ các bảng dữ liệu. Bản chất xấp xỉ của những luật này được mô tả bởi một số rằng
buộc.
1.3 . Kết luận
Trên đây chúng tôi đã trình bày một số khái niêm cơ bản về khai phá tri thức,
và đăc biệc là khai phá tri thức theo cách tiếp cận tập thô. Khai phá tri thức có thể
được hiểu đơn giản là quá trình tìm kiếm nhưng thông tin mới trong cơ sở dữ liêu. Nó
bao gồm 5 quá trình, trong đó quá trình khai phá dữ liệu là quan trong nhất. Các kỹ
thuật khai phá tri thức được chia thành 3 mảng chính: phân cụm và phân lớp dữ
liệu,khai phá các luật kết hợp, khai phá chuỗi.
Lý thuyết tập thô do P. Pawlak đưa ra trong những năm đầu của thập kỷ 80 đã
tỏ ra là rất hiệu quả trong lĩnh vực khai phá tri thức. Nó tỏ ra thực sự hiểu quả trong
các bài toán thực tế, những bài toán có dữ liệu thương ở dạng thô, chưa qua xử lý,
trong dữ liệu có nhiều thông tin dư thừa.
Chương 2 KHAI PHÁ LUẬT KẾT HỢP
Khai phá luật kết hợp là một kỹ thuật quan trọng và phát triển mạnh mẽ trong
những năm gần đây. Lần đầu tiên được Rakesh Agrawal, Tomasz Imielinski, Arun
Swami đề xuất năm 1993 [6]. Sau đó được nhiều nhà khoa học phát triển và cải tiến.
2.1 . Khai phá luật kết hợp trong cơ sở dữ liệu
2.1.1. Bài toán xuất phát
Cho trước một cơ sở dữ liệu lưu thông tin bán hàng của một siêu thị. Với
lượng dữ liệu được lưu giữ là tương đối lớn, người sử dụng mong muốn có những tri
thức từ cơ sở dữ liệu trên để có thể hoạch định kế hoạch kinh doanh phù hợp: Những
câu hỏi được đặt ra như nên đầu tư cho những mặt hàng nào, số lượng là bao nhiêu?
Sắp xếp các mặt hàng trong siêu thị như thế nào là hợp lý v . v ?
Với những câu hỏi như trên thì người sử dụng mong muốn có những thông tin
như là: ”75% những người mua bánh mì sẽ mua sữa”, hoặc “5% những người mua
rượu sẽ mua lạc”. Những phát biểu trên được gọi là các luật kết hợp. Bản thân nó
ngầm định một số quan hệ kết hợp một tập các đối tượng cùng tham gia mua hàng. Từ
những luật dạng trên thì người sử dụng có thể dùng để hỗ trợ những quyết định của họ
trong kinh doanh. Họ sẽ có chiến lược chẳng hạn như đầu tư lượng bánh mi và sữa gần
bằng nhau sao cho hiệu quả.
Trong phần này chúng tôi chỉ giải quyết ở mức độ là người khách hàng đó có
mua mặt hàng đó hay không, khi đó thì mỗi thuộc tính chỉ có 2 giá tri khác nhau là 0
ứng với trường hợp người đó không mua mặt hàng này và bằng 1 nếu người đó có mua
mặt hàng đó.
2.1.2. Mô hình hoá bài toán
Trước tiên ta có một số định nghĩa như sau:
I = {i1,i2,....,im} là tập toàn bộ các mục (chính là các mặt hàng trong bài toán
trên).
D : là cơ sở dữ liệu, nó bao gồm các tác vụ, trong đó mỗi tác vụ có thể coi như
là một vector t=(t1, t2, . . .,tm) với ti = 0 nếu tác vụ t mua mặt hàng i, i=1, . . .,m.
Với những định nghĩa trên thì cơ sở dữ liệu bán hàng của một siêu thị sẽ được
biệt diễn là một tập D các tác vụ t. Trong đó I là tập các thuộc tính hay tập các mặt
hàng. Ta có định nghĩa luật kết hợp như sau:
Định nghĩa 11: Luật kết hợp là biểu thức có dạng X⇒Y trong đó X ⊂ I, Y ⊂ I
và X∩Y=∅.
Trong đinh nghĩa trên thì
X được gọi là tiên đề.
Y được gọi là kết quả của luật.
Định nghĩa 12: Độ hỗ trợ của một tập mục X, ký hiệu là Supp(X), là tỉ số giữa
số các tác vụ mà tập mục đó xuất hiện trên tổng số các tác vụ.
Với định nghĩa trên thì ta dễ dàng có tính chất: Nếu A ⊆ B thì
Supp(A)≥Supp(B).
Định nghĩa 13: Độ hỗ trợ của luật X⇒Y , ký hiệu là Supp(X⇒Y) được xác
định như sau: Supp(X⇒Y)= Supp(X∪Y).
Định nghĩa 14: Độ tin cậy của luật dạng r=X⇒Y, ký hiệu là conf(X⇒Y)
được định nghĩa: Conf(X⇒Y)=Supp(X∪Y)/Supp(X).ư
Ta thấy độ tin cậy của một luật chính là xác suất có điều kiện của tác vụ chứa
Y xét trong điều kiện chứa X
Ví dụ: Để hiểu rõ hơn các định nghĩa trên chúng ta xét ví dụ sau:
Cho một cơ sở dữ liệu như bảng sau:
ID Tác vụ Các mục
T1 A, C, D
T2 B, E
T3 A, B, C, E
T4 B, E
T5 B, D, F
Bảng 3. Ví dụ về một cơ sở dữ liệu.
Trong cơ sở dứ liệu trên gồm 5 tác vụ thao tác trên 6 tập mục là A, B, C, D, E,
F. Khi đó thì độ hỗ trợ tương ứng của từng mục sẽ là: Ở đây tổng số tác vụ là 5, trong
khi mục A xuất hiện trong 2 tác vụ là T1 và T3 nên có độ hỗ trợ là 2/5=40%
{ }( )
)(
:
)(
Dcard
TXTcard
XSupp
∈=
Mục Số tác vụ chứa mục Độ hỗ trợ
A 2 40%
B 3 80%
C 2 40%
D 2 40%
E 3 60%
F 1 20%
Bảng 4. Độ hỗ trợ tương ứng của từng mục đơn.
Tiếp tục tính độ hỗ trợ của các tập mục lớn hơn với mỗi tập gồm 2 mục ta có
bảng :
Mục Số tác vụ chứa mục Độ hỗ trợ
A, C 2 40%
A, B 1 20%
B, D 1 20%
C, D 1 20%
A, B, C 1 20%
A, B, E 1 20%
A, C, D 1 20%
B, D, F 1 20%
A, B, C, E 1 20%
Bảng 5. Độ hỗ trợ tương ứng của các tập mục khác
Ta xét một số luật sinh từ các tập mục phổ biến trên trong bảng sau. Trong các
luật của bảng ta xét luật A⇒B thì supp({A, B})=20%, supp(A)=40% vì vậy
conf(A⇒B)=50%.
Luật kết hợp Độ tin cậy conf(X⇒Y)
A⇒C 100%
A⇒B 50%
B⇒D 25%
A,B⇒C 100%
A,C⇒B 50%
B,E⇒A 33%
Bảng 6. Độ tin cậy của các luật.
2.1.3. Thuật toán khai phá luật kết hợp.
2.1.3.1. Tập phổ biến.
Định nghĩa 15: Tâp mục X⊆I được gọi phổ biến nếu thoả mãn supp(X) ≥
minsup. Trong đó minsup là một độ hỗ trợ tối thiểu cho trước.
Khái niệm phổ biến này cho phép chúng ta chỉ xét những tập mục xuất hiện
trong cơ sở dữ liệu là đủ lớn, lớn hơn một minsup nào đó. Khi đó luật của chúng ta
sinh ra sẽ đáng tin cậy hơn.
Ta có hệ quả sau:
Cho A và B là hai tập mục, A⊆B.
a. Nếu B là tập mục phổ biến thì A cũng là tập mục phổ biến.
b. Nếu A là tập mục không phổ biến thì B cũng là tập mục không phổ biến.
2.1.3.2. Khai phá luật dựa trên tập mục phổ biến.
Việc tìm kiếm luật kết hợp trong cơ sở dữ liệu được quy về 2 giai đoạn [7]:
− Tìm tất cả các luật có độ hỗ trợ lớn hơn một minssup. Các tập mục
này chính những tập mục phổ biến. Các thuật toán Apriori và
AprioriTid nhằm giải quyết vấn đề này.
− Từ các tập mục tìm được ở trên tiến hành sinh những luật có độ tin
cậy lớn hơn một minconf nào đó.
Hai tham số minsupp và minconf được người sử dụng đưa vào khi hệ thống
khai phá tri thức. Các giá trị này thường được đưa ra bởi các chuyên gia kinh tế hoặc
những người có kinh nghiệm.
Ở trong giai đoạn nhất việc phát hiện những tập mục phổ biến tiến hành duyệt
dữ liệu rất nhiều lần. Việc tìm các tập mục phổ biến thực hiện dựa trên hệ quả của định
nghĩa 14 trình bày ở trên. Và thực hiện lần luợt các bước sau:
− Đầu tiên người ta khởi tạo một tập thật giống các tập mục phổ biến
và sinh các tập mục phổ biến dựa trên tập mục hạt giống này.
− Từ các tập mục phổ biến người ta thực hiện ghép các tập mục phổ
biến để được các tập mục lớn hơn, các tập mục này được gọi là tập
ứng cử viên.
− Để tính được độ hỗ trợ của các tập mục phổ biến người ta phải thực
hiện duyệt toàn bộ dữ liệu. Khi đó sẽ tìm được những tập mục ứng cử
viên là tập mục phổ biến.
− Tập các tập mục ứng cử viên là phổ biến này được sử dụng là tập
hạt giống cho bước tiếp theo.
Cụ thể các thuật toán Apriori và AprioriTid sinh ra các tập ứng cử viên đó
được tính trong một lần duyệt bằng việc sử dụng các tập mục được coi là phổ biến
trong lần duyệt trước mà không cần quan tâm tới các tác vụ trong cơ sở dữ liệu. Việc
chỉ xét các tập mục là phổ biến trong lần trước để sinh các tập mục ứng cử viên dựa hệ
quả rút ra từ định nghĩa 14 đã trình bày ở trên: “Bất kỳ tập con của một tập mục phổ
biến nào cũng là tập mục phổ biến”. Vì vậy tập ứng cử viên có k mục có thể sinh ra
bởi tập các tập mục phổ biến có k-1 mục. Điều này có thể dẫn đến việc giảm đáng kể
các tập mục ứng cử viên, là giảm độ phức tạp trong tính toán.
Thuật toán Apriori: Đây là thuật toán dùng để phát sinh các tập mục phổ
biến.
− Lk là tập các tập mục phổ biến có kích thước k.
− Ck là tập ứng cử viên, là các tập mục có tiềm năng trở thành tập
mục phổ biến.
− Thuật toán được tiến hành cho đến khi không tìm được một tập
mục phổ biến nào trong một lần duyệt.
Các bước của thuật toán được trình bày dưới đây:
Lần duyệt 1
1. Phát sinh các ứng cử viên C1. Thực chất tất cả các tập mục đơn
của cơ sở dữ liệu.
2. Kiểm tra và ghi lại những tập mục thuộc C1 là tập mục phổ biến
và L1.
Lần duyệt thứ k:
1. Phát sinh các tập ứng cử viên từ các tập mục phổ biến Lk-1.
a. Kết hợp các Lk-1 để được tất cả các Ck.
b. Với mỗi ứng cử viên Ck phát sinh tất cả k-1 tập con của Ck.
c. Tỉa tất cả các ứng cử viên từ Ck trong đó có tập con (k-1)
của nó không có trong tập mục phổ biến Lk-1.
2. Duyệt trong cơ sở dữ liệu để xác định độ hỗ trợ của các tập ứng
cử viên Ck.
3. Ghi lại các tập mục phổ biến Lk.
Trong bước thứ 2 của mỗi lần duyệt, để có thể tính độ hỗ trợ của các tập ứng
cử viên thì thuật toán phải tiến hành duyệt lại toàn bộ cớ sở dữ liệu. Quá trình này là
thực sự đáng kể với những cơ sở dữ liệu lớn. Khắc phục hạn chế trên thuật toán
ApriporiTid đã lưu lai thông tin về các tác vụ gắn liền với mỗi tập mục phổ biến. Điều
này có thể giúp chúng ta khắc phục được hạn chế về việc phải đọc dữ liệu nhiều lần
tuy nhiên lại gây khó khăn hơn cho chúng ta khi tổ chức bộ nhớ chương trình.
Ở giai đoạn 2, giai đoạn sinh luật với mỗi tập mục phổ biến l ta tiến hành xây
dựng những luật dạng ( )ala −→ ở đây a là tập con của l sao cho
( )
( ) confap
lp min
sup
sup ≥
Ta có, với một tập aa ⊂* thì ( ) ( )apap sup*sup ≥ nên độ tin cây của luật
dạng ( )** ala −→ không thể lớn hơn luật dạng ( )ala −→ . Do đó nếu luật ( )ala −→ không được chấp nhận thì luật dạng ( )** ala −→ cũng không thể chấp
nhận được. Nhờ tính chất này mà ta có thể tiến hành xây dựng các luật chỉ có một tập
mục ở phía phải sau đó kết hợp các luật thành dạng có 2 mục, 3 mục, ... ở phia phải
2.1.4. Kết luận.
Việc tìm kiếm các luật kết hợp trong cơ sở dữ liệu được thực hiện theo thuật
toán nguyên thuỷ Apriori và AprioriTid. Tuy nhiên một thực tế là số tập mục phổ biến
có thể là rất nhiều, khắc phục hạn chế này chúng ta có thể dùng thuật toán CHARM
được Mohammed .J Zaki và Ching-jui Hsiao đưa ra trong năm 2000 [13]. Thuật toán
CHARM không tiến hành tìm những tập mục phổ biến mà tiến hành tìm những tập
mục phổ biến đóng. Điều này dẫn đến số tập mục phổ biến tìm được là giảm đi rất
nhiều và tại các bước của thuật toán việc cắt nhánh trong quá trình thực hiện là rất hiệu
quả.
Một hạn chế đáng kể của các thuật toán trình bày ở trên là chỉ làm việc với dữ
liệu ở dạng nhị phân, tức là giá trị của các thuộc tính chỉ nhận 2 giá trị là 0 và 1. Điều
đó dẫn đến việc thuật toán khó có thể áp dụng trực tiếp trên những cơ sở dữ liệu tự
nhiên. Muốn thực hiện được thuật toán cần phải định lượng các thuộc tính thành dạng
nhị phân. Quá trinh này làm giảm tính chính xác của kết quả thu được. Trong chương
sau chúng tôi sẽ trình bày một thuật toán có thể làm việc được với dữ liệu là đa trị, dữ
liêu là dạng số thực.
2.2 . Sinh cây quyết định từ hệ thông tin.
2.2.1. Thuật toán học cây quyết định.
Phương pháp học cây quyết định là một trong những phương pháp được sử
dụng rông rãi nhất cho việc học quy nạp từ một tập mẫu lớn [11]. Đây là phương pháp
xấp xỉ các hàm mục tiêu có giá trị rời rạc. Mặt khác cây quyết định còn có thể chuyển
sang dạng biểu diễn tương đương dưới dạng tri thức là các luật Nếu – Thì (if ... then).
Xét một ví dụ về cây quyết định.
Cho một bảng dữ liệu sau:
Doc ai timetable system patallel relation database process graphic Class AI
D1 1 1 0 0 0 0 0 0 1
D2 1 0 0 0 0 0 0 0 1
D3 0 1 0 0 1 1 1 1 1
D4 1 0 0 0 0 0 0 1 1
D5 1 1 1 1 1 0 0 1 1
D6 0 0 1 1 0 0 0 0 0
D7 0 0 1 0 0 0 0 1 0
D8 0 0 1 0 1 1 0 0 0
D9 1 0 1 1 0 1 0 0 0
D10 1 1 0 0 1 1 1 0 0
Bảng 6. Các ví dụ huấn luyện tron cây quyết định.
Ta có cây quyết định:
Hình trên là một ví dụ về cây quyết định phân lớp AI các mẫu đưa vào theo
bảng 5. Mỗi nút của cây biểu diễn một thuộc tính trong các mẫu, mỗi một nhánh tới
nút tương ứng với một trong những giá trị cụ thể cho thuộc tính này. Để đơn giản ta
chỉ xét các thuộc tính nhị phân, tức là chỉ lấy giá trị là 0 và 1.
Trong bảng 5, dữ liệu huấn luyện là 10 văn bản (trong các bài toán thực tế thì
số lượng văn bản có thể lên tới hàng nghìn). Mỗi văn bản có 8 thuộc tính nhị phân
tương ứng với việc văn bản đó có hay không có từ đó. Đó là các thuộc tính ai, system,
paralell, relation, database, process, graphics.Thuộc tính cuối Class AI cùng là thuộc
tính quyết định. Đó là hàm mục tiêu của chúng ta, nó nhận giá trị 1 tức là văn bản đó
thuộc lớp AI, 0 tức là văn bản đó không thuộc lớp AI.
Mặt khác, từ cây quyết định trên chúng ta có thể sinh ra được các luật như sau:
1) Nếu (System=1) và (Timetable =1 ) thì class AI =Yes.
2) Nếu (System=1) và (Timetable =0 ) thì class AI =No.
3) Nếu (System=0) và (Process =1 ) thì class AI =No.
4) Nếu (System=0) và ( Process=0 ) thì class AI =Yes.
System
Process Timetable
0 1
0 1
0 1
Yes No Yes No
Hình 2.Một ví dụ về cây quyết đinh.
Giải thích cụ thể hơn ta có:
1) Nếu văn bản có từ System và từ Timetable thì thuộc lớp AI.
2) Nếu văn bản có từ System và không có từ Timetable thì không thuộc lớp AI.
3) Nếu văn bản không có từ System và có từ Process thì không thuộc lớp AI.
4) Nếu văn bản không có từ System và không có từ Process thì thuộc lớp AI.
Những bài toán nên sử dụng việc học cây quyết định:
Trong [10], Mitchel đã chỉ việc sử dụng cây quyết định phù hợp với việc giải
quyết các bài toán sau:
− Các mẫu huấn luyện được biểu diễn thành những cặp giá trị - thuộc tính,
các thuộc tính là một tập cố định. Các giá trị thuộc tính là rời rạc. Tuy nhiên
trong các thuật toán sinh cây quyết định cải tiến sau này cho phép các thuộc
tính nhận giá trị là giá trị thực. Đặc biệt là thuật toán sinh cây quyết định sử
dụng siêu phẳng được đưa ra trong[9] sẽ được trình chi tiết sau.
− Hàm mục tiêu phải có giá trị rời rạc, trong bài toán phân lớp văn bản trên
thì hàm mục tiêu có thể mở rộng thành nhiều giá trị đầu ra.
− Trong trường hợp cần biểu diễn kết quả thu được dưới dạng các mô tả:
Chẳng hạn như là dưới dạng luật thì cấu trúc cây quyết định có thể chuyển
sang một cách dễ dàng.
− Tập dữ liệu huấn luyện có thể chứa lỗi: Phương pháp học cây quyết định có
thể thực hiện tốt trên các tập dữ liệu chứa lỗi, cả trên các lỗi trong phân lớp ví
dụ huấn luyện cũng như lỗi trên các giá trị thuộc tính trong các ví dụ này.
− Tập dữ liệu có thể có những giá trị bị thiếu. Phương pháp cây quyết định có
thể được sử dụng trong các trường hợp các ví dụ huấn luyện có những giá trị
chưa biết.
Thuật toán ID3
Đây là một thuật toán cơ bản nhất trong lĩnh vực học cây quyết đinh, hầu hết
các thuật toán học cây quyết đinh cải tiến sau này đều dựa trên nó. ID3 và các thuật
toán cải tiến của nó đều dựa vào cách tiếp cận từ trên xuống.
Trong các thuật toán học cây quyết định thì thuật toán ID3 và thuật toán C4.5
là phổ biến nhất. Thuật toán ID3 lần đầu tiên được Quinlan giới thiệu năm 1975 trong
tạp trí Machine Learning, Vol 1, No.1.Sau đây chúng tôi trình bày thuật toán ID3,
thuật toán được mô tả như sau [9]:
ID3(Examples, Target attribute, Attributes)
Examples: Tập các ví dụ huấn luyện.
Target attribute: là thuộc tính đầu ra cho cây quyết định.
Attributes:Danh sách các thuộc tính.
Kết quả trả về là một câu quyết định phân lớp đúng các mẫu ví dụ đưa ra.
• Tạo một nút gốc Root cho cây quyết định.
• Nếu toàn bộ Examples là ví dụ dương. Trả về cây Root một nút đơn, với
nhãn +.
• Nếu toàn bộ Examples là ví dụ âm. Trả về cây Root một nút đơn, với nhãn
- .
• Nếu tập thuộc tính là rỗng thì trả lại cây Root một nút đơn với nhãn bằng
giá trị phổ biến nhất của Target_attribute trong Examples.
• Ngược lại:Begin
o A ←Thuộc tính từ tập Attributes mà phân lớp tốt nhất tập
Examples.
o Thuộc tính quyết định cho Root ←A.
o For Mỗi giá trị cụ thể vi của A,
Thêm một nhánh cây con ở dưới Root, phù hợp với biểu thức
kiểm tra A=vi .
Đặt Examplesvi là tập các ví dụ có giá trị của thuộc tính A là vi
.
Nếu Examplesvi rỗng
• thì dưới nhánh mới thêm gán một nút lá với nhãn = giá trị
phổ biến nhất của Target_attribute trong tập Examples.
• ngược lại thì dưới nhánh mới này thêm một cây con:
ID3(Examplesvi,Target_attribute,Attribute-{A}.
• End.
• Return Root.
Chọn lựa thuộc tính tốt nhất
Vấn đề quan trọng nhất của thuật toán ID3 là làm sao chọn lựa được thuộc tính
tốt nhất để đưa vào các nút của cây. Để giải quyết vấn đề này, người ta sử dụng kết
quả của lý thuyết thông tin là các độ đo là infomation gain và entropy.
Entropy:
Đây là đại lượng hết sức quan trọng trong lý thuyết thông tin. Entropy là đại
lượng đo tính đồng nhất hay thuần tuý của các mẫu. Trước tiên ta xem xét trường hợp
các thuộc tính của tập các mẫu huấn luyện S của cây quyết định chỉ có hai lớp phân
biệt là mẫu ví dụ dương (possotive) và mẫu ví dụ âm (Negative). Khi đó Entropy của
tập S được định nghĩa như sau:
Entropy(S)≡-p⊕ log2p⊕--pΘ log2pΘ.
Trong đó:
p⊕ : là phân bố của các ví dụ dương trong S.
pΘ : là phân bố của các ví dụ dương trong S.
Chúng ta quy đinh 0log20 =0.
Ví dụ: Xét trong ví dụ bảng 5, có10 mẫu huấn luyện, trong đó có 5 mẫu huấn
luyện dương(Class AI=1) và 5 ví dụ âm (Class Ai=0). Khi đó đại lương Entropy S liên
quan tới sự phân bố 2 lớp dương và âm của tập S là:
Entropy(S) = -(5/10)log2(5/10)-(5/10)log2(5/10)=
=1.0
Trong trường hợp tổng quát thì đại lượng Entropy được tính như sau:
Trong đó:
pi :là phân bố của lớp thứ i trong S.
c : là số lớp trong S.
Tương tự:
Entropy(Sai=1) = -(4/6)log2(4/6)-(2/6)log2(2/6)=0,918.
Entropy(Sai=0) = -(1/4)log2(1/4)-(3/4)log2(3/4)=0,812.
( ) ∑
=
−= c
i
ii ppSEntropy
1
2log
Information Gain
Trong khi Entropy là đại lượng đo độ không đồng nhất của các mẫu, người ta
đưa ra một độ đo sự ảnh hưởng của một thuộc tính trong mẫu đó trong việc phân lớp là
information gain.
Information gain của một thuộc tính A được tính như sau:
Trong đó Sv là tập các phần tử mà thuộc tính A có giá trị là
v.
Ví dụ: Tiếp tục xét ví dụ trong bảng 5 ta có.
Gain(S,ai) = Entropy(S)-(6/10)Entropy(Sai=1)-(4/10)Entropy(Sai=0)
= 1.0-(6/10).0,918-(4/10).0,812
= 0,1244
Tương tự ta có thể xét các Gain của các thuôc tính khác có giá trị như bảng
sau.
Attribute ai timetable system parallel relation database process graphic
Gain 0,1244 0,1244 0,2871 0,0349 0,0 0,1244 0,0 0,1244
Bảng 7. Giá trị informatin Gain của các thuộc tính.
Khi đó theo thuật toán ID3 thì thuộc tính đầu tiên được chọn là thuộc tính
system vì có giá trị information Gain là lớn nhất.
∑
∈
−≡
)(
)()(),(
AValuesV
V
V SEntropy
S
S
SEntropyASGain
( ) )()(,
}1,0{
v
v
v SEntropy
S
S
SEntropyaiSGain ∑
∈
−=
2.2.2. Một số phương pháp giải quyết vấn đề rời rạc hoá
2.2.2.1. Maximal Discernibility (MD) Heuristic
Theo như định nghĩa 8 được trình bày trong Chương 1 phần 1.2.1.4 trên một
bảng quyết định bất kỳ ta luôn có thể định nghĩa một tập các nhát cắt. Từ tính chất này
ta có thể xây dựng thuật toán sau:
Từ một bảng quyết định A =(U, A∪{d}), chúng ta xây dựng một bẳng quyết
định mới.
A* =(U*, A*∪{d*})
như sau:
• U* ={(u, v)∈ U2 : d(u)≠d(v)} ∪ {⊥}.
• A* ={c: c là một nhát cắt trên A}.
c(⊥)=0;
c((ui, uj))=1 nếu c phân biệt được ui và uj.
0 nếu ngược lại.
• d(⊥) và d*(ui, uj)=1.
Ta thu được bảng quyết định dạng sau:
A* c1 c2 . . . ck . . . d*
(u1, u2) 1 0 . . . 0 . . . 1
(u1, u2) 1 1 . . . 1 . . . 1
.
.
(u1, u2) 0 1 1
. . . .
⊥ 0 0 . . . 0 . . . 0
Bảng 8. Một dạng của bảng quyết định dạng A*
Như vậy việc tìm kiếm một sự rời rạc hoá tối ưu bảng quyết định A tương
đương với việc tìm tập rút gọn nhỏ nhất trong bảng quyết định A*. Thuật toán MD[9]
được xây dựng dựa trên việc tìm kiếm nhát cắt với số cặp đối tượng được phân biệt
bởi nhát cắt là nhỏ nhất được mô tả như sau:
Từ tập tất cả các nhát cắt A*, nhát cắt phân biệt số lớn nhất các cặp đối tượng
thuộc những lớp quyết định khác nhau sẽ được chọn. Quá trình thực hiện đến khi hai
đối tượng bất kỳ từ những lớp quyết định khác nhau đều bị phân biệt bởi một hoặc vài
nhát cắt.
Phương pháp này rất hiệu quả vì để tìm được nhát cắt với sự phân biệt là lớn
nhất chúng ta chỉ cần O(nk) bước, trong đó n là số đối tượng và k là số thuộc tính.Vì
thế tổng thời gian rời rạc hoá là O(nk.| P |), với P là tập nhát cắt cuối cùng tìm được.
2.2.2.2. Sự rời rạc hoá định nghĩa bằng siêu phẳng
Ở trên chúng ta đã trình bày một phương pháp khá đơn giản để rời rạc hóa dữ
liệu bằng nhát cắt theo định nghĩa 8. Chúng ta xét một chiến lược tương tự, nhưng
thay vì tập các nhát cắt như trên chúng ta dùng tập các siêu phẳng [9].
Ta xét một bảng quyết định A =(U, A∪{d})
Trong đó:
U={u1,. . ., un}
A={f1, . . ., fk}
d:U→{1,. . .,m}
Giả sử rằng những đối tượng ui được phân biệt bởi thuộc tính điều kiện chúng
ta có thể diễn tả chúng trong không gian quan hệ k chiều như sau:
Pi=(f1(ui), f2(ui), . . .,fk(ui)) với i ∈{1, 2, 3, . . ., n}.
Như vậy ta có thể coi mỗi đối tượng như một điểm trong không gian quan hệ k chiều.
Và các điểm đó lập thành các lớp quyết định:
Ci={u∈U :d(u)=i}. với i=1,. .,m
Ta xét một siêu phẳng H được diễn tả đầy đủ bởi một bộ (k+1) số (a, a1,. . .,ak) ∈Rk:
H={(x1,. . ., xn)∈Rk: a1x1+. . .+akxk+a=0}
Khi đó siêu phẳng H chia lớp Ci thành hai lớp con sau đây:
Chúng ta thêm một số đọ đo để đo chất lượng của siêu phẳng trong mỗi quan
hệ giữa các lớp quyết định C1,C2,. . .,Cm.
Ta xét độ đo sau để tính toán chất lượng của siêu phẳng:
Nếu award(H)>award(H') thì số cặp đối tượng từ những lớp quyết định khác
nhau bị phân biệt bởi siêu phẳng H sẽ nhiều hơn siêu phẳng H'.
0}a(u)fa...(u)fa: C{u kk11i
, ≥+++∈=HUiC
0}a(u)fa...(u)fa: C{u kk11i
, <+++∈=HLiC
∑
≠
=
ji
HL
j
HU
i CcardCcardHaward )().()(
.,
Đặt )( ,HUii Ccardu = và )( ,HLii Ccardl = với i=1,. . ., r và
u=u1 + u2 + . . . +ur ;l=l1 + l2 + . . . +lm
Khi đó , ta có công thức:
Chúng ta tiếp định nghĩa hàm sau:
Như vậy thì chất lượng của siêu phẳng H có thể được tính theo công thức sau:
porwer1(H) =award(H).
Để hiểu rõ cách tính đại lượng này chúng ta cùng xét ví dụ sau:
Cho bảng dữ liệu sau gồm 6 đối tượng và mỗi đối tượng có 4 thuộc tính, trong
đó thuộc tính thứ (9) là thuộc tính quyết định. Ở trong ví dụ này chỉ có hai lớp quyết
định tương ứng với các giá trị 1 và 2 của thuộc tính quyết định (9).
(1) (2) (8) (9)
X1 2 102 31 1
X2 4 146 70 2
X3 3 102 28 1
X4 2 90 37 2
X5 2 90 31 1
X6 2 146 28 2
Bảng 9. Ví dụ về bảng quyết đinh.
∑∑
=≠
−== m
i
ii
ji
ji lululuHaward
1
.)(
( ) ( ) ( ) ∑∑
==
=⋅= m
i
ii
HU
i
m
i
HU
i juCcardCcardHpenalty
1
,
1
,
Ta xét 2 siêu phẳng
( ) ⎭⎬
⎫
⎩⎨
⎧ =+−++∈= 124
2
146102.0.1.0:,, 321
3
3211 xxxRxxxH
và
( ) ⎭⎬
⎫
⎩⎨
⎧ =+−++∈= 96
2
90102.0.1.0:,, 321
3
3212 xxxRxxxH
Thực chất 2 siêu phẳng trên là xét giá trị của thuộc tính thứ (2) và giá trị của
thuộc tính đó so sánh với điểm giữa của các giá trị đó. Khi đó ta có:
1H các chia lớp quyết định của tập các đối tượng trên thành các tập con là:
{ }=1,1 HUC , { }5,3,11,1 XXXC HL = , { }2,61,2 XXC HU = , { }4,21,2 XXC Hl = .
{ }3,12,1 XXC HU = , { }51,1 XC HL = , { }2,61,2 XXC HU = , { }41,2 XC Hl = .
Như vậy:
( ) ( ) ( ) ( ) ( )
62.02.3
.. 1111 ,2
,
1
,
2
,
11 =+=
+= HLHUHUHL CcardCcardCcardCcardHpower
và
( ) ( ) ( ) ( ) ( )
41.22.1
.. 2222 ,2
,
1
,
2
,
12 =+=
+= HLHUHUHL CcardCcardCcardCcardHpower
Vậy ta có ( ) ( )21 HpowerHpower > nên trong quá trình rời rạc hoá dữ liệu thì
siêu phẳng 1H được ưu tiên hơn.
Ngoài ra ta còn có thể xét một số hàm sau cũng như là hàm xác định chất
lượng của siêu phẳng:
và
( ) ( )( ) ;2 cHpenalty
HawardHporwer +=
( ) ( ) ( ).. 213 HpenaltywHawardwHporwer −=
Cả 3 hàm power1(H), power2(H), power3(H) trên đều có thể được dùng để
tính chất lượng của siêu phẳng. Cả 3 độ đo này đều có thể áp dụng cho thuật toán kinh
nghiệm sẽ được trình bày sau.
2.2.2.3. Những tính chất của phương thức MD.
Xét bảng quyết định A =(U, A∪{d}, các đối tượng trong U được chia thành m
lớp quyết định C1, C2, . . ., Cm. Chúng ta xem xét một đặc tính mới f của các đối tượng
trong U với giá trị từ tập V={v0, v1, . . .,vk} ⊂ R(với v0 < v1< . . .<vk).
Tập các nhát cắt trên V được định nghĩa là một tập P = {c1, c2, . . ., ck} trong
đó
2
1 ii
i
vvc += − với i=1,. . .,k.
Đặt :
( ) ( )( ) ( )( )( )judcufUucardcl iij =∧<∈= : là số đối tượng của lớp quyết
định Ci nằm ở bên trái của nhát cắt ci
( ) ( )( ) ( )( )( )judcufUucardcl iij =∧>∈= : là số đối tượng của lớp quyết định
Ci nằm ở bên phải của nhát cắt ci.
conf(A) =card {(u, v)∈U2 :d(u) ≠d(v)}, là số cặp đối tượng thuộc những lớp
quyết định khác nhau.
Theo như được trình bày trong [2] chúng ta có các định lý sau:
Định lý 1:Hàm conf(A) có thể tính bằng công thức dưới đây.
1. Xét nj = card(Cj) với j=1,. . .,m ta có:
⎥⎥⎦
⎤
⎢⎢⎣
⎡
=⎟⎟⎠
⎞
⎜⎜⎝
⎛= ∑∑
==
m
j
j
m
j
j nnAconf
1
2
2
12
1)(
2. Với một nhát cắt bất kỳ c ∈ P :
( ) ( ) ( )( ) ( ) ( )( )∑
<
++=
ji
jjii crclcrclAconf .
Đinh nghĩa 16: Hàm “Discernible pair” dp:P→N (với N là tập các số nguyên
không âm) như sau:
( ) ( ) ( ) ( )( ) ( ) ( )( ){ }vdudvfcufUvucardcdp ≠∧<<∈= :, 2
với mọi nhát cắt c thuộc P.
Khi đó dp(c) chính là số cặp đối tượng từ cùng một lớp quyết định bị phân biệt
bởi nhát cắt c∈P.
Định lý 2: Với một nhát cắt bất kỳ c∈P ta có:
( ) ( ) ( ) ;.
1 ,1
∑ ∑
= ≠= ⎟
⎟
⎠
⎞
⎜⎜⎝
⎛= m
j
m
jll
lj crclcdp
( ) ( ) ( ) ( ) ( )∑∑∑
===
−= m
j
jj
m
j
j
m
j
j crclcrclcdp
111
. .
Theo định lý trên thì giá trị của hàm dp có thể tính theo công thức trên.
Xét { }mi .,..,1⊆∂ là tập giá trị quyết định của tất cả các đối tượng nằm trong
khoảng ( )1, +ii cc :
( )( ) ( )( ){ }1: +∈ <<∧=∃=∂ iiUui cufctudt
Định lý 3: Nếu ( ) ( ) 11 =∂=∂ =ii cardcard và ci là cực đai địa phương định
nghĩa trên hàm dp ( ) ( ) ( ) ( ) ( ) ( ) ( )( )1111 2,, −++− +≥≥≥ iiiiiii cdpcdpcdpcdpcdpcdpcdp thì
ii ∂≠∂ −1 .
Chứng minh:
Theo định lý 2 ta có:
( ) ( ) ( ) ( ) ( )∑∑∑
===
−= m
j
jj
m
j
j
m
j
j crclcrclcdp
111
.
Nếu ii ∂=∂ −1 (Không làm giảm tính tổng quát ta có thể coi 11 =∂=∂ − ii ) thì:
( ) ( )( )⎩⎨
⎧ ≠
=−= 1
111
jkhicl
jkhiclcl
j
i
ij
và
( ) ( )( )⎩⎨
⎧ ≠
=+= 1
111
jkhicr
jkhicrcr
j
i
ij
Do đó:
( ) ( ) ( ) ( )[ ] ( )[ ] ( ) ( )∑∑∑
===
−+−−⎟⎟⎠
⎞
⎜⎜⎝
⎛ +⎟⎟⎠
⎞
⎜⎜⎝
⎛ −= m
j
jjjjii
m
j
jj
m
j
jji crclcrclcrclcdp
1
11
11
.1111
( ) ( ) ( ) ( ) ( ) ( )[ ]∑∑∑∑
====
−+−= 1
1111
..
j
ijij
m
j
ijij
m
j
ij
m
j
ij crclcrclcrcl
( ) ( ) ( )[ ]∑
=
−+= 1
1j
ijiji crclcdp .
Áp dụng tương tự với tham số là ( )1+icdp ta có:
( ) ( ) ( ) ( )[ ] ( )[ ] ( ) ( )∑∑∑
===
+ −−+−⎟⎟⎠
⎞
⎜⎜⎝
⎛ −⎟⎟⎠
⎞
⎜⎜⎝
⎛ += m
j
jjjjii
m
j
jj
m
j
jji crclcrclcrclcdp
1
11
11
1 .1111
( ) ( ) ( ) ( ) ( ) ( )[ ]∑∑∑∑
====
−−−= 1
1111
..
j
ijij
m
j
ijij
m
j
ij
m
j
ij crclcrclcrcl
( ) ( ) ( )[ ]∑
=
−−= 1
1j
ijiji crclcdp .
Như vậy ( ) ( ) ( )iii cdpcdpcdp .211 =+ −− , suy ra ic không thể là cực đại địa
phương trên hàm dp.
Sau đây ta sẽ xét một số tính chất đáng chú ý của siêu phẳng tốt nhất với một
số điều kiện đặt ra.
Định lý 4: Nếu một nhát cắt ic là cực đại địa phương của hàm dp, m=1 (số giá
trị của thuộc tính quyết định chỉ là 2, giả sử là 1 và 2) và ( ) ( ) 111 =∂=∂ −− ii cardcard
thì ( ) ( )Aconfcdp i .2
1≥ .
Chứng minh:
Từ định lý 4 ta có 1−∂≠∂ ii , không mất tính tổng quát chúng ta có thể giả sử
rằng { }11 =∂ −i và { }2=∂ i .
Từ định lý 2 ta có:
( ) ( ) ( )[ ] ( ) ( )[ ]iiii crclcrclAconf 2211 . ++=
Từ định lý 3 ta có:
( ) ( ) ( ) ( ) ( )iiiii crclcrclcdp 1221 .. +=
( ) ( )[ ] ( ) ( ) ( )[ ]( ) ( ) ( )iii iiiii crclcdp crclcrclcdp 22 12211 1..1 −+= ++−=−
( ) ( )[ ] ( ) ( ) ( )[ ]( ) ( ) ( )iii iiiii crclcdp crclcrclcdp 22 12211 1..1 −+= ++−=−
Nhát cắt ic là cực đại địa phương của hàm dp khi ( ) ( )1−≥ ii cdpcdp và ( ) ( )1+≥ ii cdpcdp ;
Điều kiện ( ) ( )1−≥ ii cdpcdp tương đương với: ( ) ( ) 022 ≤− ii crcl
Điều kiện ( ) ( )1+≥ ii cdpcdp tương đương với: ( ) ( ) 011 ≤− ii crcl
Ta suy ra được bất đẳng thức sau:
( ) ( )[ ] ( ) ( )[ ] 0. 1122 ≤−− iiii crclcrcl .
Khai triển ra ra được:
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 0.... 12212121 ≤−−+ iiiiiiii crclcrclcrcrclcl
⇔ ( ) ( )[ ] ( ) ( )[ ] ( ) ( ) ( ) ( )[ ]iiiiiiii crclcrclcrclcrcl 12212211 ...2. +≤++ .
Từ đó suy ra:
( ) ( )icdpAconf .2≤
Dẫn đến ( ) ( )Aconfcdp i .2
1≥ là điều phải chứng minh.
Trên đây chúng tôi đã trình bày một số tính chất của bài toán rời rạc hoá dữ
liệu. Đó là những cơ sở toán học để chúng tôi tiến hành xây dựng thuật toán xây dựng
cây quyết định không đối xứng sẽ được trình bày sau đây.
2.2.2.4. Xây dựng cây quyết định không đối xứng
Theo nhận định của nhiều nhà nghiên cứu về học máy, thông thường tính cân
bằng của các tập con được chia thường cho kết quả phân lớp tốt. Tuy nhiên, trong
nhiều trường hợp cách thức phân hoạch không cân bằng lại cho kết quả tốt hơn, và
tương ứng là phương pháp xây dựng cây quyết định không đối xứng. Để đủ đơn giản
ta chỉ xét các bảng quyết định { }( )dAUA ∪= , , khi tập U các đối tượng chỉ gồm 2 lớp
quyết định, giá trị của thuộc tính quyết định d chỉ là 1 và 2 ( { }2,1: →Ud ).
Sử dụng theo ý tưởng thực hiện trong thuật toán ID3, các đối tượng là các lá
của cây quyết định và siêu phẳng là nhãn của các nút khác (Nút trong). Một siêu phẳng
bất kỳ:
( ){ }0...:,...,, 221121 =++++∈= axaxaxaRxxxH kkkk
Ta định nghĩa một hàm RRH k →: như sau:
( ) axaxaxaxxxH kkk ++++= ...,..,, 221121
Một đối tượng trong kRu∈ có thể bị phân loai theo cách sau đây:Chúng ta bắt
đầu từ gốc của cây quyết định. Xét H là một siêu phẳng được đánh nhãn ở gốc.
Nếu ( ) 0>uH chúng ta sẽ đi theo hướng cây con bên phải và nếu ( ) 0<uH chúng ta sẽ
đi theo nhánh cây bên trái. Quá trình tiến hành với tất cả trong khi các nút của cây
quyết định đến khi tập các đối tượng được đánh nhãn không có cùng một giá trị quyết
định.
H
L R
H(u)>0 H(u)<0
u
Hình 3. Hình ảnh cây quyế định nhị phân được thành lập.
Chi tiết các bước của thuật toán xây dựng cây quyết định không đối xứng
được trình bày sau đây:
1. Khởi tạo cây nhị phân trống T.
2. .Đánh nhãn gốc của cây bằng tập tất cả các đối tượng của thuộc U và
đặt trạng thái của gốc là chưa sẵn sàng.
3. For mỗi trạng thái chưa sẵn sàng của lá L của T:
a. Nếu tất cả các đối tượng của nhãn L có cùng giá trị quyết định
thì
Thay thế tập tất cả các đối tượng với giá trị quyêt định
chung đó. Đặt trạng thái của L là săn sàng
b. ngược lại:
Tìm siêu phẳng HL tốt nhất cho tập các đối tượng của L.
Thay thế nhãn của L bằng HL.-Khởi tạo 2 nút mới L1 và
L2 với trạng thai là chưa săng sàng đánh nhãn như sau:
L1={ x∈L : HL(x) < 0 } và
L2={ x∈L : HL(x) > 0 }
4. Lặp lại bước 3 cho đến khi tất cả các lá của T là sẵn sàng.
4. Return T
//Siêu phẳng tốt nhất là siêu phẳng với giá trị một trong các của hàm power1,
power2, power3 là lớn nhất.
Cây quyết định đưa ra bởi tập U các dữ liệu huấn luyên được gọi là tối ưu khi
chiều cao và số lá là nhỏ nhất. Thuật toán trên hướng tới việc là nhỏ nhất số siêu phẳng
có thể. Nó chỉ ra rằng số là (số luật) được sinh ra là nhỏ. Trong một cách khác cũng có
thể chỉ rằng chiều cao của cây giành được là nhỏ nhất.
Định lý 5 [9]:Chiều cao của cây quyết định xây dựng trong trường hợp dùng
độ đo là power1 se không lớn hơn 2.log2n –2, khi n là số đối tượng đưa ra bởi bảng
quyết định.
Chứng minh:
Đặt conf(h) là tổng của conf của tất cả các nút ở chiều cao h của cây quyết
định. Chúng ta có:
( ) ( )1.2 −≥ hconfhconf
Đặt n là số đối tượng của đưa ra bởi bảng quyết định và n1 và n2 là số đối
tượng tương ứng với từng lớp quyết định.Sử dụng định lý 2 ta có:
( ) ( )
42
0
22
21
21
nnnbnconfAconf =⎟⎠
⎞⎜⎝
⎛ +≤==
Đặt ( )Th là chiều cao của cây quyết định T. thì chúng ta có ( )( ) 0=Thconf . Vì
vây:
( ) ( )( ) 2log.2
4
loglog 2
2
22 −=⎟⎟⎠
⎞
⎜⎜⎝
⎛≤≤ nnTconfTh
Giả sử rằng mọi nút trong của cây đều có cấu trúc thoả mãn điều kiện sau:
( ) ( )RL NconfNconf =
Ta có:
( ) ( )( ) ( )NconfNconfNconf RL 4
1,max ≤
khi NL vaf NR là các nhánh con trái và phải của nút N. Suy ra:
( ) ( )( ) nnTconfTh 2
2
44 log14
log1log =+⎟⎟⎠
⎞
⎜⎜⎝
⎛≤+≤
Và chiều cao của siêu phẳng có thể giảm khi chúng ta sử dụng hàm sau để tính
độ mạnh của siêu phẳng:
( ) ( ) ( ) ( ) ( ) ( )( )⎥⎦
⎤⎢⎣
⎡ −⎥⎦
⎤⎢⎣
⎡ −= RL NconfNconfnconfnconfHawardHpower ,max2.24
với một siêu phẳng bất kỳ.
Một vấn đề đặt ra với thuật toán trên là làm sao lựa chọn được tập các siêu
phẳng để tìm được siêu phẳng có độ mạnh là lớn nhất. Sau đây chúng tôi đưa ra một
cách lựa chọn siêu phẳng để thực hiện thuật toán trên trong chương trình thử nghiệm
của mình.
Để tìm được siêu phẳng tốt nhất cho thuật toán trên chúng tôi đã đưa ra một
cách lựa chọn siêu phẳng gồm 2 bước sau:
Bước 1: Chọn một thuộc tính tốt nhất a∈A theo cách chọn của thuật toán ID3
đã trình bày ở trên (Thuộc tính có Information Gain lớn nhất).
Bước 2: Chọn một siêu phẳng trong các siêu theo cách định nghĩa sau:
Định nghĩa 17 : Siêu phẳng H được định nghĩa như sau:
Xét một thuộc tính bất kỳ a∈A.
Va={v0, . . .,vk} là tập các giá trị của thuộc tính a.
Đặt P={c1, . . .,ck} khi ci=(vi-1+vi)/2 với i=1,. . .,k
ta có một siêu phẳng H={(x1,. . ., xk)∈ Rk: a((x1,. . .,xk))-ci=0} trong đó a(u)
là phép lấy giá trị của thuộc tính a của đối tượng u ∈ U.
Như vậy một siêu phẳng H thực tế là một bộ gồm 2 số (a,c) trong đó a là thuộc
tính tốt nhất được chọn và c là một nhát cắt trên tập giá trị của thuộc tinh a.
Để hiểu rõ các bước của thuật toán trên chúng ta sẽ xét ví dụ sau:
Cho bảng quyết định như sau:
(1) (2) (8) (9)
X1 2 102 31 1
X2 4 146 70 2
X3 3 102 28 1
X4 2 90 37 2
X5 2 90 31 1
X6 2 146 28 2
Bảng 10. Ví dụ về bảng quyết định.
Bảng trên chính là thông tin về 6 bệnh nhân đang khám bệnh tiểu đường.
Trong đó thuộc tính (9) là thuộc tính quyết định giá trị thuộc tính này bằng 1 nếu
người đó bị bệnh và bằng 2 nếu người đó không bị bệnh. Các thuộc tính (1) tương ứng
với số lần mang thai của bệnh nhân đó, (2) lượng đường trong huyết tương sau 2 giờ
chịu thuốc, (8) tương ứng với tuổi của bệnh nhân.
Ta có Information Gain của 3 thuộc tính điều kiện được tính trong bảng sau:
(1) (2) (8)
Gain 0,3333 0,6667 0,6667
Bảng 11. Bảng giá trị infomation gain của các thuộc tính của các đối tượng trong bảng
10
(2),124
X1,X3,X4,X5 X2,X6 (d=2)
Khi đó thuộc tính được chọn tốt nhất theo ID3 là thuộc tính (2) hoặc(8). Ta
chọn thuộc tính (2) để tiếp tục thuật toán.
Tâp giá trị của thuộc tính (2) là {90, 102, 146} suy ra một tập các nhát cắt cần
xét là: {((2),124), ((2), 96). Khi đó độ mạnh của các siêu phẳng tương ứng với những
nhát cắt trên sẽ là:
siêu phẳng H (2),124 (2), 96
power1 6 4
Bảng 12. Bảng giá trị hàm power1 của các siêu phẳng chọn theo thuộc tính (2)
Như vậy siêu phẳng được chọn sẽ tương ứng với nhát cắt ((2), 124) và cây
quyết định khi đó sẽ là:
Hình 4. Các nhánh cây bị phân theo thuật toán đối với các đối tượng ở bảng 10.
Khi đó tập đối tượng được phân thành 2 tập gồm những đối tượng trong đó tập
gồm 2 đối tượng {X2, X6} là hai đối tượng thuôc cùng một lớp quyết định nên ta
không xét tiếp, ta xét các đối tượng còn lai trong bảng sau:
(1) (2) (8) (9)
X1 2 102 31 1
X3 3 102 28 1
X4 2 90 37 2
X5 2 90 31 1
Bảng 13. Bảng quyết định ứng với nhánh trái của cây quyết định hình 4.
Khi đó thì information gain sẽ được tính theo bảng sau:
(1) (2) (8)
Gain 0,1226 0,3112 0,8112
Bảng 14.
Bảng giá trị infomation gain của các thuộc tính của các đối tượng trong bảng 13
Và độ mạnh tương ứng của các siêu phẳng là:
sieu phẳng H (8),34 (8), 19,5
power1 3 1
Bảng 15. Bảng giá trị hàm power1 của các siêu phẳng chọn theo thuộc tính (8)
Và cây quyết định sẽ có dạng:
Hinh 5. Cây quyết định sau khi áp dụng thuật toán với nhánh trái của cây hình 4
Nhìn vào hình 5 ta thấy tại tât cả các nút lá các đối tượng đều có cùng giá trị
quyết định. Đến đây thuật toán có thể dùng lại. Sau khi kết thúc thuật toán thì cây
quyết định có dạng:
(2),124
(8), 34 X2,X6 (d=2)
X1,X3, X5(d=1) X4(d=2)
(2),124
(8), 34 (d=2)
(d=1) (d=2)
Hình 6. Cây quyết định được thành lập sau khi thực hiện thuật toán.
và từ cây quyết định trên ta có thể có được các luật sau:
Nếu ((2)>124) thì (9)=2.
Nếu ((2)<124) và ((8)<43) thì (9)=1.
Nếu ((2)43) thì (9)=2.
Như vậy từ tập các mẫu huấn luyện ta có thể huấn luyên được cây quyết định
theo thuật toán trên, từ cây quyết đinh đó ta có thể sinh ra được các luật.
2.2.3. Kết luận
Chương này chúng tôi đã trình bày một số thuật toán khai phá dữ liệu. Trong
đó thuật toán khai phá luật kết hợp theo hướng tiếp cận thông thường tỏ ra rất hiệu quả
với những dữ liệu rõ ràng, giá trị của các thuộc tính là nhị phân. Do đó rất khó áp dụng
cho các bài toán thực tế với những dữ liệu thường ở dạng thô, giá trị của các thuộc tính
thường là các số thực,ở dang liên tục. Chương này cũng trình bày thuật toán rời rạc
hóa dữ liệu sử dụng siêu phẳng tối ưu theo hướng tiếp cận tập thô. Đây là thuật toán có
thể xử lý được trên dữ liệu thô, có các thuộc tính có giá trị thực. Vì vậy có thể áp dụng
cho các bài toán thực tế mà không cần phải có những bước tiền xử dữ liệu phức tạp.
Từ thuật toán xây dựng cây quyết định dùng siêu phẳng tối ưu được trình bày
trong [9], chúng tôi đã đưa ra một cách lựa chọn siêu phẳng gồm hai bước (chúng tôi
đề xuất định nghĩa 17 phục vụ cho cách lựa chọn của mình), để xây dựng chương trinh
thử nghiêm cho thuật toán mà kết quả thử nghiệm sẽ được trình bày trong Chương 3.
Khóa luận sẽ đưa ra các đánh giá về hiệu quả của thuật toán nói trên (đoạn 2.2.2.4) với
cách lựa chọn siêu phẳng do chúng tôi đề xuất.
Chương 3 CHƯƠNG TRÌNH THỬ NGHIỆM
Chương trình thử nghiệm xây dựng cây quyết định dựa trên thuật toán đã trình
bày trong phần 2.2.2.4 . Kết quả thử nghiệm của chương trình thực hiện trên cơ sở dư
liệu khám bệnh tiểu đường được cung cấp bởi tổ chức “National Institute of Diabetes
and Digestive and Kidney Diseases” (31KB), từ đó sinh ra các luật trên cây quyết định
hỗ trợ quyết định khám bệnh cho các bác sĩ.
3.1 . Mô tả dữ liệu
Chương trình tiến hành khai phá dữ liệu trong cơ sở dữ liệu bệnh nhân bị bệnh
tiểu đường. Dữ liệu đầu vào là một file text có cấu trúc như sau:
− Mỗi dòng là thông tin về một bệnh nhân. Cuối mỗi dòng có dấu kết
thúc là dấu ‘.’.
− Trên mỗi dòng một bệnh nhân thể hiện qua 9 thuộc tính, giữa 2
thuộc tính có dấu ‘,’ ngăn cách.
− Thuộc tính thứ 9 là thuộc tính quyết định tương ứng với 2 trường
hợp là bị bệnh (có giá trị là 1) và không bị bệnh (có giá trị là 2).
Ví dụ về cơ sở dữ liệu:
1, 172, 68, 49, 579, 42.4, 0.702, 28, 2.
0, 173, 78, 32, 265, 46.5, 1.159, 58, 1.
6, 111, 64, 39, 0, 34.2, 0.260, 24, 1.
9, 152, 78, 34, 171, 34.2, 0.893, 33, 2.
0, 189, 104, 25, 0, 34.3, 0.435, 41, 2.
1, 122, 64, 32, 156, 35.1, 0.692, 30, 2.
3, 111, 56, 39, 0, 30.1, 0.557, 30, 1.
2, 125, 60, 20, 140, 33.8, 0.088, 31, 1.
Các thuộc tính tương ứng với một số đại lượng mà các bác sĩ dùng để xác định
tình trạng bệnh của bệnh nhân.
− Thuộc tính (1): Số lần mang thai.
− Thuộc tính (2): Plasma glucose concentration a 2 hours in an oral
glucose tolerance test.
− Thuộc tính (3) : Diastolic blood pressure (mm Hg).
− Thuộc tính (4): Triceps skin fold thickness (mm).
− Thuộc tính (5): 2-Hour serum insulin (mu U/ml).
− Thuộc tính (6): Body mass index (weight in kg/(height in m)^2)
− Thuộc tính (7): Diabetes pedigree function
− Thuộc tính (8):Tuổi của bệnh nhân.
− Thuộc tính (9): bằng 1 nếu bị bệnh và bằng 2 nếu không bị bệnh.
Bộ dữ liệu gồm thông tin về 768 bệnh nhân, trong đó:
• 500 (65.1%) người là bị bệnh.
• 268 (34.9%) người là không bị bệnh.
Trong ví dụ trên thì bệnh nhân có thông tin lưu trữ ở dòng 1 là một người
không bị bệnh vì có thuộc tính thứ (9) có giá trị là 2.
Một đặc điểm quan trọng trong cơ sở dữ liệu này là có thể có những dữ liệu là
số thực, điều này khiến nhiều thuật toán không thể thực hiện được trước khi định
lượng các giá trị đó. Thuật toán xây dựng cây quyết định nhờ sử dụng siêu phẳng được
trình bày trong Chương 2 phần 2.2.2.4 có thể thực hiện trên loại dữ liệu này.
3.2 . Xây dựng chương trình
Chương trình được xây dựng trên ngôn ngữ lập trình Visual C++ 6.0 theo
phương pháp lập trình hướng đối tượng hoàn toàn, thực hiện thuật toán được trình bày
trong Chương 2 phần 2.2.2.4.
Chương trình có cấu trúc như sau:
• Lớp các đối tượng CObj:
class CObj
{
public:
int FindTheBestAttribute();
int DelObject();
//hàm lấy thông tin về một đối tượng ở đầu danh sách.
int GetObject(int &iNAttribute,float *arrAttri);
//hàm thêm một đối ở đầu danh sách.
void AddObject(int iNAttribute,float *arrAttr);
// sô thuộc tính của đối tượng.
int iNumberAttribute;
//mảng giá trị của các thuộc tính.
float *arrAttribute;
//con trỏ đến đối tượng tiếp theo.
CObj *pntNext;
CObj();
virtual ~CObj();
};
Mỗi biến thuộc lớp này lưu thông tin về một danh sách các đối tượng, tại mỗi
nút lưu thông tin về một đối tượng, con trỏ pntNext là con trỏ chỉ đến đối tượng tiếp
theo thuộc danh sách.
• Lớp siêu phẳng CHyperPlane:
Khai báo:
class CHyperPlane
{
public:
float fPower; //độ mạnh của siêu phẳng
// Thông tin về nhát cắt gồm thuộc tính iAttribute và giá trị nhát cắt trên thuộc
tính đó fCut.
float fCut;
int iAttribute;
CHyperPlane();
virtual ~CHyperPlane();
};
Mỗi đối tượng thuộc lớp này chứa thông tin về một siêu phẳng. Môt siêu
phẳng đặc trưng bởi 2 giá trị là iAttribute là tên thuộc tính được chọn và fCut là giá trị
trên nhát cắt đó được chọn.
• Lớp tập giá trị của một thuộc tính CValueSet:
class CValueSet
{
public:
float arrValue[1000];
int iNumberValue;
CValueSet();
virtual ~CValueSet();
};
Mỗi đối tượng chứa thông tin về các giá trị của một thuộc tính được tính bằng
hàm GetValueSet() trong lớp CDecisionTree sẽ được trình bày sau đây.
• Lớp cây quyết định CDecisionTree:
class CDecisionTree
{
public:
// Các biến của lớp
float fValueDecision;
CHyperPlane hypBest;
CValueSet ValueSetCurrent;
CObj *pntObjects ;
CDecisionTree *pntLeft,*pntRight;
// Các hàm thực hiện trên các biến của lớp
int testObject(CObj *pntObj);
void SinhLuat(char *strRule);
void MDAlgoritthm();
float GetPower(float fCut,int iAttribute);
void FindTheBestHyperPlane();
float GetGain(int iAttribute);
int FindTheBestAttri();
void GetValueSet(int iAttribute);
int GetNumberObject(int iAttribute=0, float fValue=0.0);
float GetEntropy(int iAttribute=0,float fValueAttri=0);
int DelObject();
void AddObjects(int iNAttribute,float *arrAttr);
CDecisionTree();
virtual ~CDecisionTree();
};
Mỗi đối tượng thuộc lớp này thể hiện một nút trong cây quyết định. Các biến
thuộc lớp có ý nghĩa như sau:
Các biến:
− fValueDecision là một biến kiểu float lưu giá trị quyết định ở các nút
lá của cây quyết định.
− hypBest là biến kiểu CHyperPlane lưu thông tin về siêu phẳng được
chọn tại các nút trong của cây quyết định. Trong trường hợp là nút lá thì
biến này không được xét đến.
− ValueSetCurrent là biến kiểu CValueSet lưu thông tin về tập giá trị
của thuộc tính tai thời điểm xét.
− Con trỏ pntObjects là biến kiểu CObj lưu thông tin về tập các đối
tượng thuộc nút. Trong trường hợp là nút là thì con trỏ có giá trị NULL.
− Hai con trỏ pntLeft và pntRight là biến kiểu CDecisionTree chính là
2 nút con của nút hiện tại trong thuật toán.
Các hàm:
− testObject(CObj *pntObj) là hàm thực hiện kiểm tra xem đối tượng
pntObj có được phân lớp đúng theo cấy quyết định được tạo ra không.
− SinhLuat(char *strRule) thực hiện sinh luật dựa trên cây quyết định.
− MDAlgoritthm() đây là hàm thực hiện thuật toán chính.
− GetPower(float fCut,int iAttribute) là hàm trả về độ mạnh của siêu
phẳng.
− FindTheBestHyperPlane() là hàm tìm siêu phẳng tốt nhất.
− GetGain(int iAttribute) là hàm lấy độ đo thông tin của thuộc tính
iAttribute.
− FindTheBestAttri() là hàm tìm thuộc tính tốt nhất.
− GetValueSet(int iAttribute) là hàm lấy về tập giá trị của thuộc tính
iAttribute trả về biến ValueSet.
− GetNumberObject(int iAttribute=0, float fValue=0.0) trả về số đối
tượng thuộc nút tai thời điểm gọi.
− GetEntropy(int iAttribute=0,float fValueAttri=0) hàm tính Entropy.
− DelObject() thực hiện xoá một đối tượng thuộc pntObjects.
− AddObjects(int iNAttribute,float *arrAttr) thực hiện thêm một đối
tượng thuộc pntObjects.
Trong các hàm trên chú ý nhất là hàm MDAlgoritthm() là hàm thực hiện thuật
toán.
void CDecisionTree::MDAlgoritthm()
{
. . .
}
Hàm này thực hiện thuật toán chính của chương trình.
Chương trình được xây dựng để có thể chạy không chỉ trên bộ dữ liệu về bệnh
tiểu đường mà còn có thể thực hiện khai phá luật trên cả những bộ dữ liệu khác chỉ cần
thoả mãn những điều kiện sau đây:
− Giá trị của thuộc tính quyết định chỉ có 2 loại.
− Tệp dữ liệu phải có câu trúc như đã trình bày ở trên. Tuy nhiên, số
thuộc tính có thể nhiều hơn hoặc ít hơn 9 thuộc tính.
Giao diện của chương trình:
Chương trình cho phép bạn lựa chọn giữa việc sinh luật hoặc là kiểm tra độ
chính xác trong phân lớp của thuật toán. Để sư dụng bạn thực hiện các bước sau:
− Nhập tên file huấn luyện vào.
− Nhập tên file dữ liệu kiểm thử.
− Ấn nút tạo cây để chương trình tạo cây quyết định.
− Ấn nút kiểm thử để chương trình thực hiện việc kiểm thử.
− Ấn nút sinh luật để chương trình sinh luật ra một file dữ liệu luat.txt.
3.3 . Kết quả thử nghiệm
Kết quả kiểm thử khai phá dữ liệu bệnh tiểu đường đã trình bày được ở trên.
Bộ dữ liệu gồm 768 ví dụ được chia thành 2 bộ dữ liệu huấn luyện và dữ liệu kiểm thử
như sau. Chúng tôi lấy 200 đối tượng đầu tiên để làm dữ liệu kiểm thử, còn lại 568
mẫu ví dụ khác chúng tôi lần lượt lấy số mẫu huấn luyện tương ứng là 50, 100, ...500
và tập huấn luyện cuối cùng là 568. Khi đó thu được kết quả như sau:
Trương hợp 1:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 50 ví dụ: huanluyen1.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 114 mẫu kiểm thử là phân lớp đúng (62,00%).
− 86 mẫu kiểm thử là phân lớp sai(38,00%).
Trương hợp 2:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 100 ví dụ: huanluyen2.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 133 mẫu kiểm thử là phân lớp đúng (67,00%).
− 67 mẫu kiểm thử là phân lớp sai(33,00%).
Trương hợp 3:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 150 ví dụ: huanluyen3.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 134 mẫu kiểm thử là phân lớp đúng (64,50%).
− 66 mẫu kiểm thử là phân lớp sai(35,50%).
Trương hợp 4:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 200 ví dụ: huanluyen4.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 142 mẫu kiểm thử là phân lớp đúng (68,50%).
− 58 mẫu kiểm thử là phân lớp sai(31,50%).
Trương hợp 5:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 250 ví dụ: huanluyen5.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 124 mẫu kiểm thử là phân lớp đúng (62,50%).
− 76 mẫu kiểm thử là phân lớp sai(37,50%).
Trương hợp 6:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 300 ví dụ: huanluyen6.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 137 mẫu kiểm thử là phân lớp đúng (62,50%).
− 63 mẫu kiểm thử là phân lớp sai(37,50%).
Trương hợp 7:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 350 ví dụ: huanluyen7.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 132 mẫu kiểm thử là phân lớp đúng (62,50%).
− 68 mẫu kiểm thử là phân lớp sai(37,50%).
Trương hợp 8:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 400 ví dụ: huanluyen8.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 137 mẫu kiểm thử là phân lớp đúng (62,50%).
− 63 mẫu kiểm thử là phân lớp sai(37,50%).
Trương hợp 9:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 450 ví dụ: huanluyen9.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 130 mẫu kiểm thử là phân lớp đúng (62,50%).
− 70 mẫu kiểm thử là phân lớp sai(37,50%).
Trương hợp 10:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 500 ví dụ: huanluyen10.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 132 mẫu kiểm thử là phân lớp đúng (62,50%).
− 68 mẫu kiểm thử là phân lớp sai(37,50%).
Trương hợp 11:
Dữ liệu đầu vào:
− Dữ liệu huấn luyện là 568 ví dụ: huanluyen11.txt .
− Dữ liệu kiểm thử là 200 ví dụ: kiemthu.txt .
Kết quả:
− 133 mẫu kiểm thử là phân lớp đúng (62,50%).
− 67 mẫu kiểm thử là phân lớp sai(37,50%).
Ta có bảng tổng kết sau:( số mẫu kiểm thử là 200).
Số mẫu đúng Số mẫu sai %Đúng
50 mẫu HL 114 86 57,00
100 mẫu HL 133 67 66,50
150 mẫu HL 134 66 67,00
200 mẫu HL 142 58 71,00
250 mẫu HL 124 76 62,00
300 mẫu HL 137 63 68,50
350 mẫu HL 132 68 66,00
400 mẫu HL 137 63 68,50
450 mẫu HL 130 70 65,00
500 mẫu HL 132 68 66,00
568 mẫu HL 133 67 66,50
Bảng 16. Kết quả thử nghiêm chương trình.
3.4 . Nhận xét đánh giá kết quả thực nghiệm
Qua kết quả thực nghiệm của chương trình trong bảng 16 chúng tôi nhận thấy
rằng thuật toán đã phần nào phân lớp được các đối tượng bị bệnh và không bị bệnh. Tỉ
lệ số đối tượng được phân lớp đúng khoảng 65% đến 70%. Qua đó khẳng định thuật
toán trình bày trong Chương 2 phần 2.2.2.4. là có khả năng phân lớp được dữ liệu dựa
trên một cách chọn siêu phẳng khá đơn giản. Để nâng cao được kết quả thực nghiệm
chúng ta cần có một phương pháp chọn siêu phẳng tổng quát hơn, hiệu quả hơn. Cách
chọn siêu phẳng được trình bày trong Chương 2 phần 2.2.2.4. của khoá luận tốt
nghiệp là khá đơn giản để lập trình, tuy nhiên chưa thực sự hiệu quả cho việc phân lớp.
Nhất là với dữ liệu kiểu thực thì việc lựa chọn siêu phẳng dựa trên cách chọn thuộc
tính tốt nhất dùng hàm độ đo thông tin Infomation Gain là không hiệu quả khi tập giá
trị của thuộc tính đó của các đối tượng khác nhau là rất lớn, gần như bằng chính số đối
tượng.
Chương trình của chúng tôi đã thành công trong việc mô phỏng thuật toán của
tác giả [1] với một cách chọn siêu phẳng khá đơn giản. Tuy nhiên, chương trinh còn có
một số hạn chế như:
− Chỉ làm việc được với một loại cấu trúc dữ liệu đầu vào.
− Chưa đưa ra được một cách chọn siêu phẳng đủ mạnh để phân lớp dữ
liệu theo thuật toán trình bày trong Chương 2 phần 2.2.2.4
− Thuộc tính quyết định chỉ được phép nhận 2 giá trị.
− Tâp thuộc tính quyết định chỉ là một thuộc tính quyết định.
KẾT LUẬN
Sau một thời gian nguyên cứu và tìm hiểu trong quá trình làm luận văn
Tài liêu tham khảo:
[1]. Aleksander. Discernibility and Rough Sets in Medicine: Tools and
Applications Knowledge Systems Group, Dept. of Computer and Information Science,
Norwegian University of Science and Technology, Trondheim, Norway.
[2]. Andrzej Skowron, Ning Zong (2000). Rough Sets in KDD. Tutorial Notes.
[3]. Ho Tu Bao (1996). Introduction to Knowledge Discovery and Data
mining. Institute of Information Technology National Center for Natural Science and
Technology.
[4]. Fayyad, Piatetsky-Shapiro, Smyth, “From Data Mining to Knowledge
Discovery: An Overiew”, in Fayyad, Piatetsky-Shapiro, Smyth, Uthurusamy,
Advances in Knowl\ledge Discovery and Data Mining, AAAI Press/ The MIT Press,
Menlo Park, CA, 1996, pp,1-34
[5]. Sinh Nguyen Hoa, Andrzej Skowron, Piotr Synak (1998). Discovery of
Data Patterns with Application to Decomposition and Classification Problems.
[6]. Jan Komorowski, Zdzislaw Pawlak, Lech Polkowski, Andrzej Skowron
(2000). Rough sets: A tutorial
[7]. Rakesh Agrawal, Tomasz Imielinski, Arun Swami (1993). Mining
Assosication Rules between Sets of item in Large Databases. Proceedings of the 1993
ACM SIGMOD conference Washington DC, USa, May 1993
[8] Ronald J.Branchman and Tej Anand. The Process of Knowledge Discoery
inDatabases, 1996
[9] Nguyen Hung Son, Nguyen Sinh Hoa. From Optimal Hyperplanes to
Optimal Decision Trees: Rough Set and Boolean Reasoning Approaches, Institute of
Computer Sciences Warsaw University 02-097, Banacha 2, Warsaw, Poland
[10] Hà Quang Thuỵ (1996). Một số vấn đề về không gian xấp xỉ, tập thô đối
với hệ thông tin. Luận án Phó tiến sĩ Khoa học Toán Lý. ĐHKHTN, 1996
[11] Tom M. Mitchen. Machine Learning. Mc Graw Hill, pp52-76
[12]. Wojciech P. Ziarko (Ed., 1994). Rough Sets, Fuzzy Sets and Knowledge
Discovery. Proceedings of the International Workshop on Rough Sets and Knowledge
Discovery (RSKD'93), Banff, Alberta, Canada, 12-15 October 1993. Springer-Verlag.
Các file đính kèm theo tài liệu này:
- K44_Nguyen_Danh_Hoan_Thesis.pdf