Tiểu Luận Trí tuệ nhân tạo nâng cao Nội dung phương pháp khai phá luật kết hợp song song trong khai phá dữ liệ

PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP SONG SONG TRONG KHAI PHÁ DỮ LIỆU
I.Các thuật toán song song
1.1. Nguyên lý thiết kế thuật toán song song
Những thuật toán, trong đó có một số thao tác có thể thực hiện đồng thời được gọi là thuật toán song song. Tổng quát hơn, thuật toán song song là một các tập tiến trình hoặc các tác vụ có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp cùng giải một bài toán đặt ra . Có năm nguyên lý chính trong việc thiết kế thuật toán song song:
1. Các nguyên lý lập lịch: Giảm thiểu các bộ xử lý sử dụng trong thuật toán sao cho thời gian tính toán không tăng (xét theo khía cạnh độ phức tạp).
2. Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy các thao tác {T1, T2, , Tn}, trong đó Ti+1 thực hiện sau khi Ti kết thúc.
3. Nguyên lý chia để trị: Chia bài toán thành những phần nhỏ hơn, tương đối độc lập với nhau và giải quyết chúng một cách song song.
4. Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đó để xây dựng thuật toán song song.
5. Nguyên lý điều khiển tranh đua: Nếu hai tiến trình cùng muốn truy cập vào cùng một dữ liệu thì chúng phải tương tranh với nhau, nghĩa là chúng có thể cản trở lẫn nhau.
Ngoài ra, khi thiết kế thuật toán song song cần quan tâm đến các vấn đề sau:
- Hiệu quả thực hiện của thuật toán song song có thể rất khác nhau, mà yếu tố quan trọng nhất ảnh hưởng tới độ phức tạp tính toán là cấu hình tôpô liên kết mạng của các đơn vị xử lý.
- Thuật toán song song phải được thiết kế dựa trên những kiến thức về kiến trúc máy tính, ngôn ngữ lập trình song song và các phương pháp tính toán.
1.2. Hướng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song
Hai hướng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song đó là:
(1) Mô hình song song dữ liệu và
(2) Mô hình song song thao tác.
1.2.1. Mô hình song song dữ liệu