Luận Văn Giới thiệu một số thuật toán gom cụm mờ. ứng dụng thuật toán gom cụm mờ (fuzzy clustering), mô hình

MỤC LỤC . 1
1. ĐẶT VẤN ĐỀ CÁC BÀI TOÁN KHẢO SÁT .. 2

1.1 Bài toán phân loại kẹt xe . 3
1.1.1 Vấn đề bài toán 4
1.1.2 Các đại lượng ảnh hưởng đến trạng thái của luồng giao thông . 5
1.1.3 Lý thuyết về luồng giao thông . 6
1.2 Bài toán dự báo kẹt xe 7
1.2.1 Vấn đề bài toán 8
1.2.2 Một số hướng giải quyết . 9
2. CÁC KHÁI NIỆM, LÝ THUYẾT CƠ SỞ LIÊN QUAN, PHƯƠNG PHÁP GIẢI QUYẾT CÁC BÀI TOÁN . 10
2.1 Kỹ thuật gom cụm dữ liệu ( Clustering ) 11
2.1.1 Gom cụm là gì ? . 12
2.1.2 Các thuật toán gom cụm 13
2.1.2.1 Thuật toán K-Means . 14
2.1.2.2 Thuật toán K-Medoids . 15
2.1.2.3 Thuật toán ISODATA . 16
2.1.2.4 Thuật toán Phân cấp 17
2.1.2.5 Thuật toán dựa trên mô hình 18
2.1.2.6 Thuật toán dựa trên lưới 19
2.1.2.7 Thuật toán DBSCAN . 20
2.1.2.8 Các thuật toán gom cụm mờ 21
2.2 Các mô hình gom cụm mờ (Fuzzy clustering models) . 22
2.2.1 Mô hình Fuzzy C-Mean(FCM) . 23
2.2.2 Mô hình Fuzzy C-Elliptotype (FCE) . 24
2.2.3 Mô hình Fuzzy C-Mixed Prototype (FCMP) . 25
2.2.4 Mô hình Fuzzy Clustering Fuzzy Merging (FCFM) . 26
2.3 Các hệ thống mờ (Fuzzy system) . 27
2.4 Cách tạo một hệ thống điều khiển mờ 28
2.5 Cơ sở lý thuyết của Xích Markov 29
3. ỨNG DỤNG CÁC KỸ THUẬT ĐỂ GIẢI QUYẾT BÀI TOÁN ĐẶT RA. 30
3.1 Ứng dụng mô hình Xích Markov để dự báo tình trạng giao thông . 31
3.1.1 Bài toán 1 32
3.1.2 Bài toán 2 33
3.1.3 Bài toán 3 34
3.2 Ứng dụng mô hình gom cụm FCMP (Fuzzy C-Mixed Prototype) để phân lớp giao thông 35
3.2.1 Vấn đề bài toán . 36
3.2.2 Hướng giải quyết bài toán 37
4. KẾT LUẬN, HƯỚNG PHÁT TRIỂN 38
5. TÀI LIỆU THAM KHẢO . 39


1. ĐẶT VẤN ĐỀ CÁC BÀI TOÁN KHẢO SÁT
1.1 BÀI TOÁN PHÂN LOẠI KẸT XE
1.1.1 VẤN ĐỀ BÀI TOÁN
Mục tiêu của bài toán là phân lớp dữ liệu đặc trưng của luồng giao thông trong một thời điểm tại một hệ thống đo đạt được thiết lập tại một số vị trí nào đó trên đường như : tại các giao lộ. Thông thường người ta phân loại trạng thái của luồng giao thông thành 4 loại :
· Trạng thái thưa và bình thường: giao thông ổn định, những người điều khiển xe không bị ảnh hưởng bởi các xe khác.
· Trạng thái hơi đông: giao thông bình thường, nhưng việc lái xe bị ảnh hưởng nặng bởi các phương tịên giao thông khác.
· Trạng thái đông: trạng thái không ổn định, có thể dẫn đến kẹt xe.
· Trạng thái kẹt xe: hệ thống giao thông bị quá tải, các xe không thể lưu thông hoặc lưu thông chậm.
Dựa trên sự phân loại trạng thái của luồng giao thông chúng ta sẽ sử dụng kỹ thuật gì để phân lớp dữ liệu giao thông ?
1.1.2 CÁC ĐẠI LƯỢNG ẢNH HƯỞNG ĐẾN TRẠNG THÁI CỦA LUỒNG GIAO THÔNG
Lưu lượng xe (q): là số lượng xe đi qua một điểm nào đó (các giao lộ) trong một khoảng thời gian t.
Mật độ (k): số lượng xe trên một đoạn đường có chiều dài xác định.
Vận tốc (v): vận tốc trung bình của xe khi đi qua điểm quan sát trong một khoảng thời gian t.
Mục đích của ta là xác định trạng thái của luồng giao thông tại giao lộ dựa trên các đại lượng q, k, v.