chương 1, luận văn tập trung vào những bài toán cụ thể sau: Phân vùng và phân cụm các cung đường di chuyển theo thời gian để tìm ra quy luật di chuyển của các phương tiện vận tải: Cụ thể ở đây luận văn tiến hành phân tích dữ liệu của nhiều taxi trong cùng một ngày, trong một khoảng thời gian nhất định để tìm ra các cụm (các cung đường chung), loại bỏ những dữ liệu nhiễu, cụm không đặc trưng, phục vụ cho bài toán mô phỏng luồng di chuyển, tìm ra các đường đi chung, các đường đi tối ưu phục vụ cho bài toán gợi ý di chuyển. Phương pháp phân cụm thường chia thành [7]: không giám sát, giám sát, bán giám sát. Luận văn lựa chọn phương pháp không giám sát, cụ thể là mô hình và thuật toán Trajectory clustering của Jae-Gil Lee và cộng sự [6] sẽ trình bày bên dưới. Mô phỏng luồng di chuyển của các phương tiện vận tải theo vùng: Nhằm đạt mục tiêu khái quát hóa và tăng hiệu năng tính toán luận văn sử dụng tư tưởng chia vùng theo công trình của Naoto [8] và cách chia cung thời gian theo công trình của Xiaomeng Wang và cộng sự [15] và đề xuất cách biểu diễn mật độ theo vận tốc Xếp hạng các khu vực đón, trả khách: Luận văn thực hiện khái quát hóa khu vực đón, trả khách theo tư tưởng chia vùng trong công trình của Naoto [8] và cách chia cung thời gian trong công trình của Xiaomeng Wang và cộng sự [15] Dự đoán luồng giao thông trong các vùng: Luận văn thực hiện dự đoán vùng đến kế tiếp theo công trình của S´ebastien Gambs và cộng sự [11, 12] với cách gán nhãn dựa trên xếp hạng và mật độ, phục vụ cho bài toán gợi ý di chuyển tiếp theo Đưa ra gợi ý di chuyển cho tài xế dựa vào mật độ giao thông và kết quả xếp hạng của các vùng: Dựa trên bài toán dự đoán luồng giao thông và xếp hạng đón khách, luận văn thực hiện đưa ra các gợi ý di chuyển cho tài xế, sử dụng các cung đường đã phân cụm để gợi ý cung đường tốt nhất.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Thuật toán phân cụm TRACLUS Phân cụm là cách chia các đối tượng dữ liệu thành các nhóm sao cho các đối tượng trong cùng một nhóm gần nhau hơn và các đối tượng của hai nhóm khác nhau thì khác nhau rất nhiều. Trong luận văn, bài toán phân cụm cho phép tìm hiểu các quy luật quãng đường của từng taxi. Các quy luật đường đi của taxi gồm có các đoạn đường được taxi dùng để di chuyển nhiều nhất, các cụm quãng đường sẽ được phân ra dựa trên khoảng cách thực tế. Để giải quyết hai bài toán trên luận văn sử dụng công trình của Jae-Gil Lee và cộng sự [6], đó là thuật toán TRACLUS.
Để làm rõ thuật toán, giả sử có 5 quãng đường như trong Hình 2.1, có thể nhìn rõ rằng có một đặc điểm chung, biểu diễn bằng mũi tên trong hình chữ nhật. Tuy vậy, nếu nhóm những quãng đường này làm một, chúng ta không thể khám phá đặc điểm chung này khi mà chúng di chuyển đi các hướng khác nhau, vì vậy sẽ bị mất một số thông tin quý giá.1 Mô hình quãng đường con chung Giải pháp ở đây sẽ là phân chia các quãng đường thành tập hợp các phân đoạn đường và sau đó nhóm các phân đoạn đường. Công việc này nằm trong khuôn khổ phân vùng và cụm. Mục tiêu chính của việc phân vùng và cụm này là khám phá các quãng đường con (phân đoạn đường) chung từ bộ dữ liệu quãng đường đầu vào.
Việc khám phá các quãng đường con là rất hữu ích do chúng ta có những vùng quan tâm đặc biệt để phân tích. Trong trường hợp này, chúng ta tập trung vào những hành vi cụ thể trong khu vực đó. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Phương pháp phân vùng và cụm sẽ gồm 2 giai đoạn: Bước phân vùng: Mỗi quãng đường được tối ưu phân chia làm các phân đoạn đường. Các phân đoạn đường này sẽ là dữ liệu đầu vào cho bước tiếp theo.
Bước phân cụm: các phân đoạn đường giống nhau được nhóm vào một cụm. Trong bài báo này, thuật toán phân cụm dựa trên mật độ được sử dụng.2 miêu tả toàn bộ quá trình phân cụm quãng đường trong phương pháp phân vùng và cụm. Đầu tiên, mỗi quãng đường được chia ra làm các phân đoạn đường. Sau đó, các phân đoạn đường mà chúng ở gần nhau dựa trên tiêu chí khoảng cách được nhóm thành một cụm.
Cuối cùng, đoạn đường tiêu biểu được tạo ra cho mỗi cụm. Thuật toán này được viết lại chi tiết như trong Thuật toán 1.2 Ví dụ về phân vùng và cụm quãng đường Thuật toán 1: TRACLUS (TRAjectory CLUStering) Input: Tập hợp quãng đường I = {TR1, · · · , T Rnumtra } Output: (1) tập hợp các cụm O = {C1, · · · , Cnumclus } (2) tập hợp các đoạn đường tiêu biểu LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Thuật toán: /* BƯỚC PHÂN VÙNG */ 01: for each (TR ∈ I) do /* Thuật toán 2 */ 02: Thực hiện thuật toán phân vùng quãng đường; Nhận tập hợp L của các phân đoạn đường; 03: Tích lũy L vào trong một tập hợp D; /* BƯỚC PHÂN CỤM */ /* Thuật toán 3 */ 04: Thực hiện phân cụm phân đoạn đường cho D; kết quả gồm một tập hợp O gồm các cụm; 05: for each (C ∈ O) do 06: Thực hiện việc tạo đoạn đường tiêu biểu; kết quả gồm có đoạn đường tiêu biểu; 2.1 Phân vùng quãng đường Chúng ta muốn tìm những điểm mà hành vi của các quãng đường thay đổi nhanh chóng, chúng ta gọi những điểm này là những điểm đặc trưng. Đối với mỗi TRi = p1 p2 p3…pleni, chúng ta xác định một tập hợp các điểm đặc trưng {pc1, pc2, pc3,…,pcpari } (c1 < c2 < … < cpari). Mỗi điểm pi tương ứng với một tọa độ gồm kinh độ và vĩ độ (X và Y trong tệp dữ liệu đầu vào).
Sau đó TRi được phân vùng tại mỗi điểm đặc trưng, và mỗi vùng được biểu diễn bởi phân đoạn đường.3 miêu tả một ví dụ về quãng đường và cách nó được phân đoạn.3 Ví dụ về quãng đường và các phân đoạn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Việc phân chia tối ưu cần phải có hai tính chất sau: chính xác và súc tích. Tính chính xác có nghĩa rằng sự khác nhau giữa quãng đường và một tập hợp phân đoạn đường càng nhỏ càng tốt. Tính súc tích đồng nghĩa với số lượng phân đoạn càng ít càng tốt. Để thực hiện điều này chúng ta dùng thuật toán 2.
Thuật toán 2: Approximate Trajectory Partitioning Input: TRi = p1 p2 p3….pj…pleni Output: Tập hợp các điểm đặc trưng CPi Thuật toán: 01: Thêm p1vào tập hợp CPi; /* điểm bắt đầu */ 02: startIndex:= 1, length:= 1; 03: while (startIndex + length ≤ leni) do 04: currIndex:= startIndex + length; 05: costpar := MDLpar(pstartIndex, pcurrIndex); 06: costnopar := MDLnopar(pstartIndex, pcurrIndex); /* kiểm tra nếu phân vùng ở điểm hiện tại làm MDL lớn hơn khi không phân vùng */ 07: if (costpar> costnopar) then /* phân vùng điểm trước đo */ 08: Thêm pcurrIndex−1 vào trong CPi; 09: startIndex := currIndex − 1, length := 1; 10: else 11: length := length + 1; 12: Thêm điểm pleni vàoCPi; /* điểm kết thúc */ Chiều dài tối thiểu mô tả (MDL - Minimum Description Length) được sử dụng để phân vùng đoạn đường. MDL sẽ được đo dựa trên L(H) (độ đo tính súc tích) và L(D|H) (độ đo tính chính xác). Công thức tính của L(H) và L(D|H) lần lượt như sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 trong đó d┴ và dθ lần lượt là khoảng cách vuông góc và khoảng cách góc giữa 2 phân đoạn đường Li = si ei và Lj = sj ej.4 Cách tính độ đo MDL Dựa vào công thức trên, và ví dụ trong Hình 2.4, tính được L(H) và L(D|H) cho quãng đường {p1 p2 p3 p4 p5 .2 Phân cụm Trong thuật toán TRACLUS, thuật toán phân cụm DBSCAN được sử dụng. Đối với thuật toán DBSCAN, chúng ta cần xác định 2 tham số: ε (tương ứng với khoảng cách nhỏ nhất giữa 2 điểm để có thể gọi là điểm hàng xóm) và minPts (tương ứng với số lượng điểm hàng xóm).
Phân đoạn đường Li∈ D được gọi là phân đoạn đường với điều kiện ε và MinLns thỏa mãn nếu |Nε(Li)| ≥ MinLns và sẽ gọi là ngoại bên nếu không thỏa mãn điều kiện này. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Một phân đoạn đường Li∈ D được coi là có khả năng truy cập mật độ trực tiếp (directly density reachable) từ một phân đoạn đường khác Lj∈ D với điều kiện ε và MinLns thỏa mãn nếu Li∈ Nε(Lj ) và |Nε(Lj )| ≥ MinLns. Một phân đoạn đường Li∈ D được gọi là có khả năng truy cập mật độ từ một phân đoạn đường khác Lj∈ D với điều kiện ε và MinLns thỏa mãn nếu có một chuỗi các đoạn đường Lj , Lj−1, · · · , Li+1, Li∈ D sao cho Lk là mật độ truy cập trực tiếp từ Lk+1 với điều kiện ε và MinLns thỏa mãn. Một phân đoạn đường Li∈ D được gọi là mật độ kết nối (density-connected) tới một phân đoạn đường khác Lj∈ D với điều kiện ε và MinLns thỏa mãn nếu có một phân đoạn đường Lk∈ D sao cho cả hai Livà Ljlà có khả năng truy cập mật độ từ Lk.
Chúng ta hãy nghiên cứu ví dụ trong Hình 2.5 sau được áp dụng DBSCAN cho bài toán phân cụm các đoạn đường. Ở đây minPts = 3 và ε là các hình eclipse, dựa vào định nghĩa trong DBSCAN chúng ta sẽ có: Hình 2.5 Ví dụ về mật độ truy cập và mật độ kết nối ● L1, L2, L3, L4, và L5 là phân đoạn đường chính ● L2 và L3 có mật độ truy cập trực tiếp từ L1 ● L6 có mật độ truy cập từ L1 nhưng ngược lại không đúng ● L1, L4 và L5 là mật độ kết nối. Thuật toán phân cụm trong TRACLUS được viết lại như trong thuật toán 3: Thuật toán 3: Phân cụm Input: (1) Một tập hợp phân đoạn 𝐷 = {𝐿1, …. , 𝐿𝑛𝑢𝑚𝑙𝑛 }, (2) Hai tham số ε and MinLns Đầu ra: Một tập hợp cụm 𝑂 = {𝐶1, … , 𝐶𝑛𝑢𝑚𝑐𝑙𝑢𝑠 } LUAN VAN CHAT LUONG download : add luanvanchat@agmail.