fightforthefutureteam
New Member
Download Luận văn Nghiên cứu cải tiến thuật toán phân lớp sử dụng cây quyết định đệ quy
MỤC LỤC
LỜINÓI ĐẦU. 2
DANHMỤC CÁCKÝ HIỆU VÀ CHỮVIẾT TẮT . 3
DANHMỤC CÁCBẢNG. 4
DANHMỤC CÁCHÌNHVẼ, ĐỒ THỊ . 5
CHƯƠNG 1. TỔNG QUAN . 7
1.1 GIỚI THIỆU. 7
1.2 TỔNG QUANVỀKHAIMỎDỮLIỆU VÀ PHÂN LỚP. 9
1.2.1 Giới thiệu vềkhai mỏdữliệu . 9
1.2.2 Cáchướng nghiên cứu trong khai mỏdữliệu. 14
1.2.3 Tổng quan vềbài toán phân lớp . 17
1.2.4 Cácphương pháp phân lớp . 19
1.3 NỘI DUNG LUẬN VĂN . 25
CHƯƠNG 2. PHÂN LỚPDỮLIỆU BẰNG CÂY QUYẾT ĐỊNH. 27
2.1 PHƯƠNG PHÁP PHÂN LỚPDỰA TRÊN CÂY QUYẾT ĐỊNH
(CLASSIFIER BY USING DECISION TREE) . 27
2.2 MỘT SỐNGHIÊN CỨU GẦN ĐÂY . 39
2.2.1 Cácthuật toán cũ . 39
2.2.2 Cácthuật toán sửdụng chỉsốGini. . 39
CHƯƠNG 3. THUẬT TOÁN HYBRID DATA. 44
3.1 GIỚI THIỆU THUẬT TOÁN HYBRID DATA. 44
3.2 SONG SONGHOÁ THUẬT TOÁN HYBRID DATA. . 57
3.3 MỘT SỐCẢI TIẾN KHÁC . 65
3.3.1 Cải tiến điều kiệndừng của thuật toán . 65
3.3.2 Bổsung tiêu chí chọn lựathuộctính ứng viên . 66
CHƯƠNG 4. ỨNG DỤNGKIỂM CHỨNG. 71
4.1 TỔNG QUANVỀ ỨNG DỤNG . 71
4.2 ỨNGDỤNG TRÊN MÁY ĐƠN (XỬLÝ TUẦN TỰ) . 73
4.4 ỨNGDỤNGXỬLÝ SONG SONG. 78
CHƯƠNG 5. KẾTLUẬN VÀ HƯỚNG PHÁT TRIỂN . 82
5.1 KẾT LUẬN . 82
5.2 HƯỚNG PHÁT TRIỂN . 83
DANHMỤC CÔNG TRÌNH VÀ BÀI BÁO CỦA TÁCGIẢ . 84
TÀILIỆU THAMKHẢO . 85
PHỤLỤC1: MỘT SỐTHUẬT NGỮTHƯỜNG SỬDỤNG TRONG CÁCTÀI
LIỆU CHUYÊN MÔN. . 87
PHỤLỤC2: THUẬT TOÁN CÀI ĐẶT TRONG ỨNG DỤNG . 88
v Phiên bản xửlý tuần tự. 88
v Phiên bản xửlý song song. 88
v Hàm kiểm tra (cảitiến) điều kiện dừng. 89
v Hàm kiểm travà chọn ứng viên (tránh lỗi lặpvô tận) . 89
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
mà vẫn đảm bảo tính chính xác như các thuật toán trước đây. Ngoài ra thuật toán
này cũng đảm bảo tính mở rộng trong trường hợp dữ liệu rất lớn.
1.2 TỔNG QUAN VỀ KHAI MỎ DỮ LIỆU VÀ PHÂN LỚP
Phần này sẽ giới thiệu các khái niệm cơ bản cũng như tổng quan tất cả các giai
đoạn trong toàn bộ quá trình khai mỏ dữ liệu, các hướng nghiên cứu trong bài toán
khai mỏ dữ liệu (thực chất lĩnh vực khai mỏ dữ liệu bao gồm rất nhiều hướng
nghiên cứu khác nhau).
1.2.1 Giới thiệu về khai mỏ dữ liệu
Trong những thập niên gần đây, lượng dữ liệu của các tổ chức gia tăng rất nhiều.
Để đáp ứng nhu cầu lưu trữ và quản trị lượng dữ liệu lớn này, phần cứng máy
tính cũng phát triển rất nhanh song song với việc các phần mềm chuyên về xử lý dữ
liệu, các hệ quản trị Cơ sở dữ liệu ngày càng được cải tiến.
Xa hơn nữa, nhu cầu của các công ty, các tập đoàn và những người sử dụng cao
cấp muốn thông qua “đống dữ liệu lớn trong quá khứ” này để tìm kiếm các
thông tin “thật sự hữu ích còn ẩn chứa bên trong”, muốn tìm kiếm “các quy luật”,
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
10
các “hành vi” của các đối tượng nào đó hay thậm chí có thể đoán tương lai.
Trong ngành công nghệ tin học có một nhánh con là công nghệ tri thức, ngành này
luôn quan tâm tìm tòi và giải quyết các câu hỏi trên và vấn đề trên được gọi là khám
phá tri thức từ dữ liệu (Knowledge Discovery from Data – KDD).
Hình 1.2 – Quá trình “khai mỏ” để khám phá tri thức từ dữ liệu
Một quá trình khám phá tri thức từ dữ liệu thông thường luôn bao gồm năm bước
như sau:
v Xác định vấn đề và lựa chọn nguồn dữ liệu: Đây là quá trình đầu tiên của toàn
bộ quá trình. Ở giai đoạn này các chuyên gia trong lĩnh vực (domain experts)
cần ngồi lại thảo luận với các chuyên gia tin học, chúng ta phải xác định
được chúng ta mong muốn khám phá những gì hay chí ít thì cũng phải xác định
được các thuật ngữ chuyên môn, chuyên ngành, thống nhất giải pháp cho quá
trình khám phá dữ liệu (muốn có các luật hay muốn phân lớp, gom nhóm dữ
liệu…). Đây là một giai đoạn hết sức quan trọng vì nếu xác định sai vấn đề thì
Dữ
liệu
Tri thức
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
11
toàn bộ quá trình phá sản, nó trở nên vô ích; điều này cũng giống như ngành
công nghệ phần mềm thất bại ở giai đoạn xác định yêu cầu người dùng. Do vậy
giai đoạn này có lẽ là giai đoạn tốn nhiều thời gian nhất.
v Chuẩn bị dữ liệu: Dựa trên các thông tin ở bước xác định, phải tổ chức dữ liệu,
lấy dữ liệu như thế nào thì để được xem là cần thiết và đủ. Đây cũng là một giai
đoạn rất quan trọng vì nếu dữ liệu đầu vào không chính xác thì hiển nhiên sẽ
không thể nào có một kết quả chính xác được. Giai đoạn này sẽ bao gồm các
bước nhỏ sau :
§ Chọn lựa dữ liệu (Data selection): chọn lựa các nguồn dữ liệu cần lấy để
khám phá tri thức, giai đoạn này rất cần sự hỗ trợ của các chuyên gia trong
lĩnh vực, các nhà quản trị Cơ sở dữ liệu và các chuyên gia công nghệ tin
học. Các dữ liệu sẽ được lựa chọn theo tiêu chí đã thống nhất ở bước trên và
nên có sự kiểm tra, giám sát và góp ý của các chuyên gia trong lĩnh vực
hay có sự góp ý của người dùng thì càng tốt.
§ Tích hợp dữ liệu (Data integration): Thông thường có thể dữ liệu bao gồm
nhiều nguồn khác nhau như: từ tập tin bảng tính Excel, từ Cơ sở dữ liệu
Microsoft SQL Server, Oracle hay thậm chí từ các tập tin văn bản. Các dữ
liệu này phải được tích hợp và tổ chức lại thành các bảng dữ liệu bao gồm
các cột (các thuộc tính dữ liệu) và các dòng (các giá trị dữ liệu). Các dữ liệu
này nên được tích hợp vào một nguồn dữ liệu duy nhất như tập tin bảng tính
Excel hay tốt nhất là một hệ quản trị Cơ sở dữ liệu duy nhất để tiện quản lý
và truy xuất. Lưu ý việc lưu trữ dữ liệu như thế nào cho tốt, tối ưu cùng với
việc thao tác dễ dàng cũng là một trong những cách làm giảm chi phí thực
thi của các thuật toán.
§ Làm sạch và rút gọn dữ liệu (Data cleaning and reduction): đây cũng là một
giai đoạn tinh chỉnh dữ liệu. Các dữ liệu nhiễu, dữ liệu không chính xác
hay dữ liệu thiếu (missing data – thường trong cơ sở dữ liệu gọi là dữ liệu
rỗng hay null) phải được loại bỏ hay thay thế; thậm chí các thuộc tính phụ
dư thừa (ví dụ như thuộc tính ghi chú…) có thể cũng sẽ được loại bỏ tại giai
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
12
đoạn này. Giai đoạn này cũng cần có sự tham gia chặt chẽ của các chuyên
gia trong lĩnh vực và thậm chí cả người dùng.
§ Rời rạc hóa gom nhóm và biến đổi dữ liệu (Data discretization, reduce data
by grouping and transformation): Các thuộc tính liên tục có thể được thay
thế bằng các giá trị tiệm cận (gần đúng) và có thể được rời rạc hóa thành các
thuộc tính có kiểu dữ liệu rời rạc (phần dưới sẽ giải thích rõ về thuộc tính
liên tục và thuộc tính rời rạc). Các giá trị thuộc tính có thể được gom nhóm
để làm giảm tính phức tạp (ví dụ thuộc tính địa chỉ có thể loại bỏ số nhà,
loại bỏ tên đường và chỉ nhóm theo phường, quận….). Ngoài ra, cũng có thể
tổng quát hóa dữ liệu (ví dụ như thuộc tính nghề nghiệp có thể tổng quát
hóa vào các ngành như kỹ thuật, lao động phổ thông thuần tuý, nhân viên
văn phòng, nhân viên quản trị…).
v Thực hiện khai mỏ dữ liệu (data mining process): đây là bước trung tâm của
toàn bộ quá trình khám phá tri thức. Quá trình này dựa trên các phương pháp và
thuật toán đã chọn sẽ tiến hành khám phá tri thức từ các tập dữ liệu (hay còn gọi
là tập huấn luyện – training data). Kết quả của quá trình này sẽ tìm ra các tri
thức, mô hình hay các quy luật tiềm ẩn bên trong dữ liệu. Tuy nhiên chưa hẳn
các kết quả này có thật sự đáng giá để sử dụng, có thật sự là các tri thức mà
người dùng mong muốn tìm thấy hay không.
v Đánh giá lại chất lượng của tri thức vừa khám phá (Evaluation of the discovered
knowledge): Bước này được đưa ra để xem xét tri thức được tìm thấy có phải là
tri thức mới, tri thức này có cần thiết hay có giá trị hay không. Lưu ý là việc
đánh giá này được thực hiện thông qua các chuyên gia trong lĩnh vực và người
dùng là chính chứ không phải là các chuyên gia tin học. Tuy nhiên, với một số
bài toán vẫn có thể đánh giá được tính chính xác theo một cách nào đó, ví dụ
như bài toán phân lớp ta có thể đánh giá được mô hình phân lớp được tạo ra có
tốt không bằng cách đánh giá tỷ lệ dữ liệu thỏa mãn mô hình này dựa trên thông
tin từ tập huấn luyện và dĩ nhiên tỷ lệ này càng cao thì càng tốt.
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
13
v Sử dụng các tri thức được khám phá (Using the discovered knowledge): Nếu các
bước trên đều đúng, đây là bước cuối cùng. Kết quả của tri thức sẽ được mô tả
sao cho dễ hiểu và dễ cập nhật khi dữ liệu thay đổi. Mô ...
Download miễn phí Luận văn Nghiên cứu cải tiến thuật toán phân lớp sử dụng cây quyết định đệ quy
MỤC LỤC
LỜINÓI ĐẦU. 2
DANHMỤC CÁCKÝ HIỆU VÀ CHỮVIẾT TẮT . 3
DANHMỤC CÁCBẢNG. 4
DANHMỤC CÁCHÌNHVẼ, ĐỒ THỊ . 5
CHƯƠNG 1. TỔNG QUAN . 7
1.1 GIỚI THIỆU. 7
1.2 TỔNG QUANVỀKHAIMỎDỮLIỆU VÀ PHÂN LỚP. 9
1.2.1 Giới thiệu vềkhai mỏdữliệu . 9
1.2.2 Cáchướng nghiên cứu trong khai mỏdữliệu. 14
1.2.3 Tổng quan vềbài toán phân lớp . 17
1.2.4 Cácphương pháp phân lớp . 19
1.3 NỘI DUNG LUẬN VĂN . 25
CHƯƠNG 2. PHÂN LỚPDỮLIỆU BẰNG CÂY QUYẾT ĐỊNH. 27
2.1 PHƯƠNG PHÁP PHÂN LỚPDỰA TRÊN CÂY QUYẾT ĐỊNH
(CLASSIFIER BY USING DECISION TREE) . 27
2.2 MỘT SỐNGHIÊN CỨU GẦN ĐÂY . 39
2.2.1 Cácthuật toán cũ . 39
2.2.2 Cácthuật toán sửdụng chỉsốGini. . 39
CHƯƠNG 3. THUẬT TOÁN HYBRID DATA. 44
3.1 GIỚI THIỆU THUẬT TOÁN HYBRID DATA. 44
3.2 SONG SONGHOÁ THUẬT TOÁN HYBRID DATA. . 57
3.3 MỘT SỐCẢI TIẾN KHÁC . 65
3.3.1 Cải tiến điều kiệndừng của thuật toán . 65
3.3.2 Bổsung tiêu chí chọn lựathuộctính ứng viên . 66
CHƯƠNG 4. ỨNG DỤNGKIỂM CHỨNG. 71
4.1 TỔNG QUANVỀ ỨNG DỤNG . 71
4.2 ỨNGDỤNG TRÊN MÁY ĐƠN (XỬLÝ TUẦN TỰ) . 73
4.4 ỨNGDỤNGXỬLÝ SONG SONG. 78
CHƯƠNG 5. KẾTLUẬN VÀ HƯỚNG PHÁT TRIỂN . 82
5.1 KẾT LUẬN . 82
5.2 HƯỚNG PHÁT TRIỂN . 83
DANHMỤC CÔNG TRÌNH VÀ BÀI BÁO CỦA TÁCGIẢ . 84
TÀILIỆU THAMKHẢO . 85
PHỤLỤC1: MỘT SỐTHUẬT NGỮTHƯỜNG SỬDỤNG TRONG CÁCTÀI
LIỆU CHUYÊN MÔN. . 87
PHỤLỤC2: THUẬT TOÁN CÀI ĐẶT TRONG ỨNG DỤNG . 88
v Phiên bản xửlý tuần tự. 88
v Phiên bản xửlý song song. 88
v Hàm kiểm tra (cảitiến) điều kiện dừng. 89
v Hàm kiểm travà chọn ứng viên (tránh lỗi lặpvô tận) . 89
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
ạn chế việc truy xuất đọc/ghi trên đĩa cứngmà vẫn đảm bảo tính chính xác như các thuật toán trước đây. Ngoài ra thuật toán
này cũng đảm bảo tính mở rộng trong trường hợp dữ liệu rất lớn.
1.2 TỔNG QUAN VỀ KHAI MỎ DỮ LIỆU VÀ PHÂN LỚP
Phần này sẽ giới thiệu các khái niệm cơ bản cũng như tổng quan tất cả các giai
đoạn trong toàn bộ quá trình khai mỏ dữ liệu, các hướng nghiên cứu trong bài toán
khai mỏ dữ liệu (thực chất lĩnh vực khai mỏ dữ liệu bao gồm rất nhiều hướng
nghiên cứu khác nhau).
1.2.1 Giới thiệu về khai mỏ dữ liệu
Trong những thập niên gần đây, lượng dữ liệu của các tổ chức gia tăng rất nhiều.
Để đáp ứng nhu cầu lưu trữ và quản trị lượng dữ liệu lớn này, phần cứng máy
tính cũng phát triển rất nhanh song song với việc các phần mềm chuyên về xử lý dữ
liệu, các hệ quản trị Cơ sở dữ liệu ngày càng được cải tiến.
Xa hơn nữa, nhu cầu của các công ty, các tập đoàn và những người sử dụng cao
cấp muốn thông qua “đống dữ liệu lớn trong quá khứ” này để tìm kiếm các
thông tin “thật sự hữu ích còn ẩn chứa bên trong”, muốn tìm kiếm “các quy luật”,
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
10
các “hành vi” của các đối tượng nào đó hay thậm chí có thể đoán tương lai.
Trong ngành công nghệ tin học có một nhánh con là công nghệ tri thức, ngành này
luôn quan tâm tìm tòi và giải quyết các câu hỏi trên và vấn đề trên được gọi là khám
phá tri thức từ dữ liệu (Knowledge Discovery from Data – KDD).
Hình 1.2 – Quá trình “khai mỏ” để khám phá tri thức từ dữ liệu
Một quá trình khám phá tri thức từ dữ liệu thông thường luôn bao gồm năm bước
như sau:
v Xác định vấn đề và lựa chọn nguồn dữ liệu: Đây là quá trình đầu tiên của toàn
bộ quá trình. Ở giai đoạn này các chuyên gia trong lĩnh vực (domain experts)
cần ngồi lại thảo luận với các chuyên gia tin học, chúng ta phải xác định
được chúng ta mong muốn khám phá những gì hay chí ít thì cũng phải xác định
được các thuật ngữ chuyên môn, chuyên ngành, thống nhất giải pháp cho quá
trình khám phá dữ liệu (muốn có các luật hay muốn phân lớp, gom nhóm dữ
liệu…). Đây là một giai đoạn hết sức quan trọng vì nếu xác định sai vấn đề thì
Dữ
liệu
Tri thức
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
11
toàn bộ quá trình phá sản, nó trở nên vô ích; điều này cũng giống như ngành
công nghệ phần mềm thất bại ở giai đoạn xác định yêu cầu người dùng. Do vậy
giai đoạn này có lẽ là giai đoạn tốn nhiều thời gian nhất.
v Chuẩn bị dữ liệu: Dựa trên các thông tin ở bước xác định, phải tổ chức dữ liệu,
lấy dữ liệu như thế nào thì để được xem là cần thiết và đủ. Đây cũng là một giai
đoạn rất quan trọng vì nếu dữ liệu đầu vào không chính xác thì hiển nhiên sẽ
không thể nào có một kết quả chính xác được. Giai đoạn này sẽ bao gồm các
bước nhỏ sau :
§ Chọn lựa dữ liệu (Data selection): chọn lựa các nguồn dữ liệu cần lấy để
khám phá tri thức, giai đoạn này rất cần sự hỗ trợ của các chuyên gia trong
lĩnh vực, các nhà quản trị Cơ sở dữ liệu và các chuyên gia công nghệ tin
học. Các dữ liệu sẽ được lựa chọn theo tiêu chí đã thống nhất ở bước trên và
nên có sự kiểm tra, giám sát và góp ý của các chuyên gia trong lĩnh vực
hay có sự góp ý của người dùng thì càng tốt.
§ Tích hợp dữ liệu (Data integration): Thông thường có thể dữ liệu bao gồm
nhiều nguồn khác nhau như: từ tập tin bảng tính Excel, từ Cơ sở dữ liệu
Microsoft SQL Server, Oracle hay thậm chí từ các tập tin văn bản. Các dữ
liệu này phải được tích hợp và tổ chức lại thành các bảng dữ liệu bao gồm
các cột (các thuộc tính dữ liệu) và các dòng (các giá trị dữ liệu). Các dữ liệu
này nên được tích hợp vào một nguồn dữ liệu duy nhất như tập tin bảng tính
Excel hay tốt nhất là một hệ quản trị Cơ sở dữ liệu duy nhất để tiện quản lý
và truy xuất. Lưu ý việc lưu trữ dữ liệu như thế nào cho tốt, tối ưu cùng với
việc thao tác dễ dàng cũng là một trong những cách làm giảm chi phí thực
thi của các thuật toán.
§ Làm sạch và rút gọn dữ liệu (Data cleaning and reduction): đây cũng là một
giai đoạn tinh chỉnh dữ liệu. Các dữ liệu nhiễu, dữ liệu không chính xác
hay dữ liệu thiếu (missing data – thường trong cơ sở dữ liệu gọi là dữ liệu
rỗng hay null) phải được loại bỏ hay thay thế; thậm chí các thuộc tính phụ
dư thừa (ví dụ như thuộc tính ghi chú…) có thể cũng sẽ được loại bỏ tại giai
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
12
đoạn này. Giai đoạn này cũng cần có sự tham gia chặt chẽ của các chuyên
gia trong lĩnh vực và thậm chí cả người dùng.
§ Rời rạc hóa gom nhóm và biến đổi dữ liệu (Data discretization, reduce data
by grouping and transformation): Các thuộc tính liên tục có thể được thay
thế bằng các giá trị tiệm cận (gần đúng) và có thể được rời rạc hóa thành các
thuộc tính có kiểu dữ liệu rời rạc (phần dưới sẽ giải thích rõ về thuộc tính
liên tục và thuộc tính rời rạc). Các giá trị thuộc tính có thể được gom nhóm
để làm giảm tính phức tạp (ví dụ thuộc tính địa chỉ có thể loại bỏ số nhà,
loại bỏ tên đường và chỉ nhóm theo phường, quận….). Ngoài ra, cũng có thể
tổng quát hóa dữ liệu (ví dụ như thuộc tính nghề nghiệp có thể tổng quát
hóa vào các ngành như kỹ thuật, lao động phổ thông thuần tuý, nhân viên
văn phòng, nhân viên quản trị…).
v Thực hiện khai mỏ dữ liệu (data mining process): đây là bước trung tâm của
toàn bộ quá trình khám phá tri thức. Quá trình này dựa trên các phương pháp và
thuật toán đã chọn sẽ tiến hành khám phá tri thức từ các tập dữ liệu (hay còn gọi
là tập huấn luyện – training data). Kết quả của quá trình này sẽ tìm ra các tri
thức, mô hình hay các quy luật tiềm ẩn bên trong dữ liệu. Tuy nhiên chưa hẳn
các kết quả này có thật sự đáng giá để sử dụng, có thật sự là các tri thức mà
người dùng mong muốn tìm thấy hay không.
v Đánh giá lại chất lượng của tri thức vừa khám phá (Evaluation of the discovered
knowledge): Bước này được đưa ra để xem xét tri thức được tìm thấy có phải là
tri thức mới, tri thức này có cần thiết hay có giá trị hay không. Lưu ý là việc
đánh giá này được thực hiện thông qua các chuyên gia trong lĩnh vực và người
dùng là chính chứ không phải là các chuyên gia tin học. Tuy nhiên, với một số
bài toán vẫn có thể đánh giá được tính chính xác theo một cách nào đó, ví dụ
như bài toán phân lớp ta có thể đánh giá được mô hình phân lớp được tạo ra có
tốt không bằng cách đánh giá tỷ lệ dữ liệu thỏa mãn mô hình này dựa trên thông
tin từ tập huấn luyện và dĩ nhiên tỷ lệ này càng cao thì càng tốt.
PDF created with pdfFactory Pro trial phiên bản www.pdffactory.com
13
v Sử dụng các tri thức được khám phá (Using the discovered knowledge): Nếu các
bước trên đều đúng, đây là bước cuối cùng. Kết quả của tri thức sẽ được mô tả
sao cho dễ hiểu và dễ cập nhật khi dữ liệu thay đổi. Mô ...