Luận văn:Ứng dụng cây quyết định mờ trong khai phá dữ liệu : Luận văn ThS. Công nghệ thông tin: 1 01 10

Mô tả lý thuyết về khai phá dữ liệu (KPDL), cây quyết định và độ đo mờ nói chung, kỹ thuật về KPDL. Trình bày thuật toán quy nạp cây quyết định mờ: biểu diễn của nhận thức không chắc chắn trong bài toán phân loại, định lượng nhận thức không chắc chắn, luật phân loại mờ và nhập nhằng phân loại, quy nạp cây quyết định mờ, đưa ra những ưu khuyết điểm của thuật toán. Giới thiệu về cài đặt thuật toán và chương trình mô phỏng thuật toán quy nạp xây dựng cây quyết định mờ
Luận văn ThS. Công nghệ thông tin -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2007
CHƢƠNG 1. HỆ PHÂN TÁN............................................................................................... 9
1.1. Khái niệm hệ phân tán.......................................................................................9
1.2. Vai trò của hệ phân tán......................................................................................9
1.3. Đặc trƣng của các hệ phân tán.........................................................................11
1.4. Mô hình hóa các hệ phân tán...........................................................................12
1.4.1. Mô hình chuyển thông báo........................................................................13
1.4.2. Mô hình với bộ nhớ dùng chung ...............................................................13
1.4.3. Mô hình xen kẽ .........................................................................................14
1.4.4. Thực hiện và những tính chất của thực hiện..............................................14
1.5. Đánh giá độ phức tạp ......................................................................................16
1.6. Khả năng kháng lỗi và tính tự ổn định.............................................................17
1.6.1. Khả năng kháng lỗi...................................................................................17
1.6.2. Tính chất tự ổn định..................................................................................17
1.6.3. Vai trò của tự ổn định...............................................................................18
1.6.4. Đánh giá độ phức tạp ...............................................................................19
CHƢƠNG 2. CÁC GIẢI THUẬT SƠ ĐẲNG ................................................................... 21
2.1. Giới thiệu........................................................................................................21
2.2. Bài toán...........................................................................................................23
2.3. Đánh giá độ phức tạp ......................................................................................24
2.4. Giải thuật Phát tỏa Đầy đủ ..............................................................................25
2.5. Giải thuật Cập nhật Tăng trƣởng [4]................................................................27 CHƢƠNG 3. GIẢI THUẬT CẬP NHẬT VỚI TRI THỨC BỘ PHẬN [3]...................... 32
3.1. Tƣ tƣởng.........................................................................................................32
3.2. Giải thuật ........................................................................................................33
3.3. Tính đúng đắn và độ phức tạp .........................................................................37
3.4. Ví dụ một thực hiện ........................................................................................38
CHƢƠNG 4. GIẢI THUẬT AS CẢI TIẾN ........................................................................ 44
4.1. Đặt vấn đề.......................................................................................................45
4.2. Thực hiện cải tiến............................................................................................45
4.3. Tính đúng đắn và độ phức tạp .........................................................................49
4.4. Ví dụ một thực hiện ........................................................................................52
CHƢƠNG 5. GIẢI THUẬT DUY TRÌ DỮ LIỆU CHUNG PHÂN TÁN ÁP DỤNG
TRONG THỰC TIỄN ........................................................................................................... 58
5.1. Hệ thống động với tôpô bất kỳ ........................................................................58
5.2. Dữ liệu chung phân tán ...................................................................................59
5.3. Độ dài dữ liệu không cố định ..........................................................................59
5.4. Khả năng kháng lỗi và tính tự ổn định.............................................................60
KẾT LUẬN ............................................................................................................................ 63
TÀI LIỆU THAM KHẢO..................................................................................................... 64 CHƯƠNG 1. HỆ PHÂN TÁN
1.1. Khái niệm hệ phân tán
Có rất nhiều khái niệm khác nhau về hệ phân tán. Một cách tổng quan, hệ phân tán
là tập hợp các thiết bị tính riêng rẽ có thể giao tiếp với nhau. Đây là một khái niệm hết
sức tổng quát, bao trùm một phạm vi rộng các hệ thống máy tính ngày nay, từ các bộ
chíp VLSI đến các bộ đa xử lý, các mạng cục bộ, và Internet. Nếu nhƣ hệ song song
phối hợp nhiều bộ xử lý nhằm giải quyết một vấn đề cho trƣớc một cách nhanh nhất
thì hệ phân tán bao gồm một tập các bộ xử lý có chƣơng trình làm việc riêng bán độc
lập, vì những lý do gì đó, ví dụ chia sẻ tài nguyên, tăng tính sẵn sàng, khứ lỗi, các bộ
xử lý cần phối hợp hành động với nhau.
Ta có thể thấy các hệ phân tán ở khắp mọi nơi. Điển hình, các hệ phân tán đƣợc sử
dụng để chia sẻ tài nguyên và chia sẻ dữ liệu. Các máy tính kết nối mạng với nhau có
thể dùng chung máy in, máy quét, chia sẻ các tệp tài liệu, chƣơng trình… Tính toán
ngang hàng là một kiểu thực hiện của hệ phân tán ngày càng trở nên phổ biến cho việc
cung cấp các thiết bị và dịch vụ tính toán. Các hệ phân tán nhiều tham vọng hơn cho
hiệu năng hoạt động cao bằng cách kết hợp giải các bài toán con một cách song song,
đồng thời tăng tính sẵn sàng của hệ thống trong trƣờng hợp một số thiết bị gặp lỗi.
1.2. Vai trò của hệ phân tán
Ngày nay hệ phân tán đang trở nên phổ biến vì những vai trò ứng dụng quan trọng
của chúng. Trƣớc hết, phải kể đến đó là vai trò trao đổi thông tin. Các hệ phân tán cho
khả năng chia sẻ thông tin rộng rãi và tức thời. Lấy ví dụ, thông tin từ hệ thống máy
tính đặt tại Sở giao dịch chứng khoán TPHCM có thể đƣợc sử dụng bởi hệ thống máy
tính đặt tại trụ sở của các công ty chứng khoán thành viên hay cũng có thể chia sẻ đến
tận các nhà đầu tƣ. Các thông tin chứng khoán cũng luôn yêu cầu phải có tính chính
xác cũng nhƣ tức thời rất cao, và hệ phân tán cũng có thể cung cấp những khả năng
đảm bảo đƣợc điều này.
Hệ phân tán cũng cho khả năng chia sẻ thông tin giữa các thiết bị hỗn tạp. Một máy
tính có thể "nói chuyện" với các máy tính khác loại, các điện thoại cố định, di động các PDA, … Các hệ phân tán cho khả năng chia sẻ tài nguyên cả phần cứng lẫn phần
mềm. Các máy tính kết nối mạng có thể dùng chung máy in, có thể chia sẻ các tệp dữ
liệu, các tệp chƣơng trình.
Thứ hai, bằng việc sao lặp, nhân bản, các hệ phân tán cho độ tin cậy cao. Nếu toàn
bộ dữ liệu của một chi nhánh ngân hàng lƣu trong máy tính đột nhiên biến mất, ngƣời
ta có thể khôi phục lại bằng cách sao phần nhân bản đã đƣợc lƣu tại một nơi khác trên
hệ thống máy tính của ngân hàng.
Thứ ba, thông qua song song hóa, các thực thể trong hệ phân tán có thể chia sẻ
công việc, thực hiện đồng thời công việc chung, do vậy làm tăng hiệu suất hoạt động
của hệ thống.
Thứ tư, hệ phân tán làm đơn giản việc thiết kế các hệ thống phức tạp. Ngƣời ta
thƣờng phân một hệ thống phức tạp thành các hệ thống con chuyên dụng và hợp tác
với nhau. Làm nhƣ vậy, không những việc thiết kế đơn giản mà việc thực hiện cũng
đơn giản.
Các ƣu điểm của hệ phân tán so với máy tính cá nhân và so với hệ tập trung đƣợc
chỉ ra ngắn gọn trong các bảng sau.
Bảng 1.1. Ưu điểm của hệ phân tán so với máy tính cá nhân.
Ưu điểm Mô tả
Chia sẻ dữ liệu Cho phép nhiều người dung cùng truy cập vào một cơ
sở dữ liệu chung
Chia sẻ thiết bị Cho phép nhiều người dung dung chung các thiết bị đắt
tiền như máy in màu, máy quét, ...
Truyền thông Giúp truyền thông giữa người với người dễ dàng hơn,
ví dụ bằng thư điện tử
Mềm dẻo Phân công việc cho bất kỳ máy nào sẵn sàng phải tiếp tục làm việc để đạt đƣợc kết quả nhƣ mong muốn. Những đặc trƣng này thực
sự là những khó khăn khi thiết kế các hệ phân tán.
1.4. Mô hình hóa các hệ phân tán
Trong một hệ phân tán, mỗi thực thể (máy tính, bộ xử lý, tiến trình) chạy một
chƣơng trình riêng bao gồm tập các lệnh. Khi thực hiện lệnh, thực thể thay đổi trạng
thái cục bộ của nó. Ta có thể mô hình hóa sự thay đổi này bằng cách xem mỗi thực thể
là một máy trạng thái. Một hệ phân tán đƣợc mô hình hóa bằng tập n máy trạng thái.
Ký hiệu máy thứ i là Pi.
Truyền thông giữa các thực thể có thể thực hiện bằng cách chuyển thông báo hay
sử dụng bộ nhớ dùng chung. Truyền thông bằng cách ghi vào và đọc ra từ bộ nhớ dùng
chung thƣờng hạn chế hệ thống với các thực thể gần nhau về mặt địa lý, ví nhƣ hệ
thống đa bộ xử lý hay các máy tính đa nhiệm. Truyền thông theo cách chuyển thông
báo không có giới hạn nhƣ vậy, có thể thực hiện trong cả hệ thống mà các thực thể rất
xa nhau về mặt địa lý nhƣ các mạng máy tính. Hình 1.1. dƣới đây là minh họa mô hình
tổng quát của các hệ thống phân tán.
Hinh 1.1. Mô hình tổng quát hệ thống phân tán.
Tùy theo phƣơng pháp truyền thông đƣợc sử dụng, ta có mô hình chuyển thông báo
hay mô hình với bộ nhớ dùng chung.



ReftZa0h2v49Di6

---