Tổng quan nghiên cứu

Sự phát triển vượt bậc của công nghệ di động và điện thoại thông minh trong giai đoạn 2016 - 2017 đã tạo ra hơn 2,5 tỷ thiết bị kết nối toàn cầu, thúc đẩy sự bùng nổ của các nền tảng dịch vụ dựa trên vị trí. Tiêu biểu trong số đó là các ứng dụng gọi xe công nghệ như Grab và Uber, nơi hàng triệu giao dịch di chuyển được ghi nhận mỗi ngày. Mỗi chuyến đi của người dùng đều gắn liền với điểm xuất phát, điểm kết thúc và mốc thời gian cụ thể, hình thành nên các chuỗi dữ liệu giao dịch có thứ tự thời gian rõ rệt. Tuy nhiên, việc khai thác cấu trúc dữ liệu chuỗi tuần tự này để thấu hiểu sâu sắc thói quen di chuyển, tối ưu hóa lộ trình và dự báo chính xác nhu cầu đi lại vẫn là một bài toán phức tạp đòi hỏi các thuật toán tối ưu về thời gian và không gian lưu trữ.

Trước bối cảnh đó, đề tài luận văn thạc sĩ "Khai thác mẫu tuần tự để phân tích hành vi chuyến đi người dùng" do học viên Võ Văn Mỹ thực hiện dưới sự hướng dẫn khoa học của Phó Giáo sư Tiến sĩ Quản Thành Thơ tại Trường Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh đã giải quyết trọn vẹn bài toán từ mô hình lý thuyết đến ứng dụng thực tiễn. Mục tiêu trọng tâm của nghiên cứu là xây dựng mô hình khai phá dữ liệu chuyến đi, phát triển công cụ thu thập dữ liệu hành trình trên thiết bị di động, áp dụng các thuật toán khai phá mẫu tuần tự và kiến tạo cây dự đoán hành vi di chuyển trong tương lai.

Phạm vi thực nghiệm của đề tài được triển khai tập trung tại khuôn viên Trường Đại học Bách Khoa Thành phố Hồ Chí Minh trong khoảng thời gian từ ngày 20/04/2017 đến ngày 31/05/2017, thu thập 454 bản ghi giao dịch qua 25 địa điểm thực tế. Về mặt giá trị ứng dụng, nghiên cứu giúp nâng cao độ chính xác dự báo hành vi lộ trình với độ hỗ trợ tối thiểu đạt 90% (minsup = 0.9), giảm thiểu độ trễ xử lý dữ liệu và cung cấp nền tảng tính toán vững chắc cho các hệ thống điều phối giao thông thông minh.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng lý thuyết khai phá mẫu tuần tự (Sequential Pattern Mining) do Rakesh Agrawal và Ramakrishnan Srikant khởi xướng từ năm 1995. Đề tài tổng hợp và phân tích sâu sắc hai trường phái thuật toán chủ đạo cùng một hướng mở rộng quan trọng:

  1. Trường phái tiếp cận tạo và tỉa ứng viên (Generating-Pruning Approach) dựa trên nguyên lý Apriori: Tiêu biểu gồm các thuật toán AprioriAll, GSP (Generalized Sequential Patterns), SPADE và SPAM (sử dụng biểu diễn bitmap nhị phân theo chiều dọc). Nguyên lý cốt lõi xác định rằng nếu một chuỗi không thỏa mãn ngưỡng hỗ trợ tối thiểu thì tất cả các chuỗi cha chứa nó đều bị loại bỏ, giúp thu hẹp không gian tìm kiếm.
  2. Trường phái phát triển mẫu theo tiền tố (Pattern Growth Based Methods): Đại diện bởi FreeSpan và PrefixSpan. Phương pháp này áp dụng kỹ thuật chia để trị, xây dựng các cơ sở dữ liệu quy chiếu theo từng tiền tố để tránh việc phải sinh toàn bộ tập ứng viên trung gian tốn kém bộ nhớ.
  3. Mô hình khai phá mẫu tuần tự đóng (Closed Sequential Patterns): Giải pháp trích xuất các chuỗi phổ biến không bị chứa trong chuỗi phổ biến nào khác có cùng độ hỗ trợ, giúp giảm thiểu đáng kể số lượng mẫu dư thừa khi khai thác chuỗi dài.

Các khái niệm nền tảng được định nghĩa chặt chẽ trong luận văn gồm:

  • Mục (Item) và Tập mục (Itemset): Mỗi chuyến đi từ điểm bắt đầu đến điểm kết thúc được xem là một mục, ký hiệu qua cặp vị trí cụ thể và ánh xạ thành tập số nguyên.
  • Chuỗi (Sequence): Danh sách có thứ tự theo thời gian của các tập mục, biểu diễn dưới dạng <s1 s2 ... sn>.
  • Chuỗi khách hàng (Customer Sequence): Toàn bộ lịch sử các chuyến đi của một người dùng cụ thể được sắp xếp tăng dần theo mốc thời gian giao dịch.
  • Độ hỗ trợ (Support / Minsup): Số lượng hoặc tỷ lệ người dùng hỗ trợ chuỗi mẫu đang xét trên tổng số người dùng trong cơ sở dữ liệu.
  • Chuỗi tối đa (Maximal Sequence): Chuỗi phổ biến không nằm trong bất kỳ chuỗi phổ biến nào khác, đóng vai trò là kết quả khai phá cốt lõi để xây dựng mô hình dự báo.

Phương pháp nghiên cứu

Nguồn dữ liệu của luận văn được thu thập trực tiếp thông qua một ứng dụng di động độc lập do chính tác giả xây dựng trên nền tảng iOS, mô phỏng giao diện đặt chuyến đi tương tự Grab và được đưa lên kho ứng dụng AppStore.

Cỡ mẫu và phương pháp chọn mẫu: Đề tài áp dụng phương pháp chọn mẫu thuận tiện có kiểm soát với 10 tình nguyện viên tham gia thu thập dữ liệu thường xuyên. Quá trình thực nghiệm ghi nhận tổng cộng 454 bản ghi giao dịch tại 25 vị trí trọng điểm trong khuôn viên Đại học Bách Khoa Thành phố Hồ Chí Minh, bao gồm Cổng trường (mã 10), Nhà xe (mã 11), các khối giảng đường từ A1 đến A5 (mã 12 đến 16), khu B từ B1 đến B12 (mã 17 đến 27), khu C từ C1 đến C6 (mã 28 đến 33) và Trung tâm Ươm tạo Doanh nghiệp (mã 34).

Quy trình phân tích dữ liệu được thực hiện qua 5 giai đoạn tuần tự:

  • Giai đoạn 1 - Sắp xếp dữ liệu (Sort Phase): Sắp xếp toàn bộ giao dịch theo mã khách hàng làm khóa chính và thời gian giao dịch làm khóa phụ.
  • Giai đoạn 2 - Tìm tập mục lớn (Litemset Phase): Xác định tất cả các 1-itemset phổ biến và gán nhãn số nguyên duy nhất để so sánh trong thời gian cố định O(1).
  • Giai đoạn 3 - Chuyển đổi dữ liệu (Transformation Phase): Thay thế các giao dịch gốc bằng tập litemsets tương ứng và loại bỏ các giao dịch không chứa mục phổ biến.
  • Giai đoạn 4 - Khai phá chuỗi (Sequence Phase): Áp dụng thuật toán GSP để sinh ứng viên và đếm độ hỗ trợ qua các lần duyệt dữ liệu.
  • Giai đoạn 5 - Tối ưu hóa chuỗi tối đa (Maximal Phase): Lọc các chuỗi phổ biến tối đa để xây dựng cây dự đoán hành vi.

Lý do lựa chọn hướng tiếp cận Apriori (thuật toán AprioriAll và GSP) là nhờ cấu trúc thuật toán rõ ràng, tính kiểm chứng cao và khả năng chuyển đổi trực quan sang sơ đồ cây quyết định. Bên cạnh đó, tác giả sử dụng thêm thuật toán PrefixSpan từ thư viện khai phá dữ liệu mã nguồn mở SPMF phiên bản 2 trên máy tính cá nhân cấu hình Intel Core i5 2.4 GHz, bộ nhớ RAM 4096 MB để đối chuẩn và đánh giá hiệu năng thuật toán.

Timeline nghiên cứu: Đề tài được giao nhiệm vụ ngày 16/01/2017, thu thập dữ liệu từ 20/04/2017 đến 31/05/2017, hoàn thành xử lý và thử nghiệm ngày 18/06/2017, bảo vệ thành công trước hội đồng chuyên môn ngày 17/07/2017.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm trên tập dữ liệu chuyến đi thực tế đã mang lại 4 phát hiện quan trọng:

Thứ nhất, trích xuất thành công 27 mẫu tuần tự phổ biến (frequent patterns) từ tập dữ liệu thử nghiệm 200 bản ghi với ngưỡng độ hỗ trợ tối thiểu minsup = 0.9 (tương đương 90%). Toàn bộ các chuỗi trích xuất được đều thể hiện tính quy luật lặp lại rất cao trong thói quen sinh hoạt và học tập nội bộ.

Thứ hai, phát hiện lộ trình di chuyển mang tính áp đảo tại các nút không gian trọng điểm. Trong số 27 mẫu phổ biến, chuỗi hành vi di chuyển giữa Cổng trường (vị trí 10), Trung tâm Ươm tạo Doanh nghiệp (vị trí 34) và Nhà xe (vị trí 11) chiếm tỷ trọng tuyệt đối. Cụ thể, các mẫu lặp lại chặng Cổng trường -> Trung tâm Ươm tạo Doanh nghiệp liên tiếp từ 5 đến 8 lần trước khi chuyển hướng về Trung tâm Ươm tạo Doanh nghiệp -> Nhà xe đạt độ hỗ trợ tuyệt đối 10/10 tình nguyện viên (độ phủ 100%).

Thứ ba, sự phân hóa hiệu năng rõ rệt giữa thuật toán GSP và PrefixSpan khi mở rộng quy mô dữ liệu. Khi thử nghiệm trên 200 bản ghi với ngưỡng hỗ trợ cao từ 0.7 đến 0.9, thời gian thực thi của GSP và PrefixSpan tương đương nhau. Tuy nhiên, khi tăng quy mô lên 300 bản ghi và hạ ngưỡng hỗ trợ xuống dưới 0.4, thời gian xử lý của thuật toán GSP tăng vọt từ 200% đến hơn 500% so với PrefixSpan.

Thứ tư, xây dựng thành công cây dự đoán hành vi chuyến đi (Prediction Tree). Mô hình cho phép dự báo chính xác chặng di chuyển tiếp theo dựa trên các nút tiền tố đã biết; ví dụ trong kịch bản mẫu, khi người dùng thực hiện lộ trình Nhà -> Trường học -> Chợ, hệ thống dự đoán xác suất 80% (độ hỗ trợ 4/5 người dùng) chặng tiếp theo sẽ là Chợ -> Nhà.

Thảo luận kết quả

Sự suy giảm hiệu suất của thuật toán GSP khi ngưỡng hỗ trợ thấp và tập dữ liệu mở rộng bắt nguồn từ nguyên lý sinh ứng viên tổ hợp và việc phải quét lại toàn bộ cơ sở dữ liệu nhiều lần. Mặt khác, do tập thử nghiệm gồm 10 tình nguyện viên di chuyển liên tục trong 42 ngày, độ dài chuỗi giao dịch của mỗi cá nhân kéo dài đáng kể, làm bùng nổ số lượng ứng viên cấp cao trong thuật toán dạng Apriori.

Khi đối chiếu với các nghiên cứu kinh điển của Jian Pei và Jiawei Han, kết quả thực nghiệm của luận văn hoàn toàn củng cố kết luận rằng phương pháp phát triển mẫu theo tiền tố (PrefixSpan) vượt trội hơn hẳn các thuật toán dựa trên Apriori về cả tốc độ lẫn khả năng quản lý bộ nhớ khi xử lý các chuỗi có độ dài lớn.

Để phục vụ quản trị và trực quan hóa dữ liệu, kết quả nghiên cứu được tổ chức thành hai dạng thức trực quan:

  • Biểu đồ đường so sánh thời gian thực thi: Trục tung thể hiện thời gian tính toán bằng mili-giây, trục hoành biểu diễn các mức độ hỗ trợ từ 0.1 đến 0.9, làm nổi bật rõ rệt khoảng cách hiệu năng giữa GSP và PrefixSpan trên hai tập 200 và 300 bản ghi.
  • Cấu trúc sơ đồ cây dự báo phân nhánh: Biểu diễn trực quan các nút vị trí từ 10 đến 34 kèm trọng số độ hỗ trợ tại mỗi nhánh, giúp người vận hành hệ thống nắm bắt ngay luồng giao thông chính chỉ trong vài giây.

Đề xuất và khuyến nghị

Dựa trên các kết quả và hạn chế đã chỉ ra, nghiên cứu đề xuất 4 nhóm giải pháp cụ thể:

  1. Chuyển đổi kiến trúc thuật toán khai phá sang PrefixSpan và SPAM: Đơn vị phát triển hệ thống cần thay thế thuật toán GSP bằng PrefixSpan hoặc SPAM biểu diễn bitmap nhị phân, đặt mục tiêu giảm từ 60% đến 80% thời gian xử lý khi vận hành trên các cơ sở dữ liệu lớn vượt 100.000 bản ghi. Kế hoạch chuyển đổi dự kiến hoàn thành trong thời gian từ 3 đến 6 tháng do nhóm kỹ sư dữ liệu backend đảm nhiệm.
  2. Mở rộng quy mô mẫu và đa dạng hóa đối tượng thu thập: Đơn vị vận hành ứng dụng cần mở rộng tập tình nguyện viên từ 10 người lên tối thiểu 500 đến 1.000 người dùng thực tế trên toàn địa bàn đô thị, thu thập trên 50.000 chuyến đi nhằm triệt tiêu hiện tượng chuỗi dài cục bộ và loại bỏ dữ liệu nhiễu. Lộ trình triển khai thực hiện trong vòng 6 tháng do bộ phận phát triển sản phẩm chủ trì.
  3. Tích hợp mô hình xác suất và học máy chuỗi thời gian: Nhóm nghiên cứu AI cần kết hợp khai phá mẫu tuần tự với mạng nơ-ron hồi quy (LSTM) hoặc mô hình Markov ẩn (HMM) để nâng độ chính xác dự đoán điểm đến theo thời gian thực đạt trên 85%. Giai đoạn nghiên cứu và thử nghiệm thuật toán dự kiến kéo dài 4 tháng.
  4. Tối ưu hóa điều phối phương tiện dựa trên cây dự đoán hành vi: Các doanh nghiệp vận tải công nghệ cần ứng dụng cấu trúc cây dự đoán để tự động điều động trước 15% đến 25% lượng xe chờ tại các điểm nóng có tần suất xuất hiện cao (như Cổng trường, Nhà xe, Trung tâm thương mại) vào khung giờ cao điểm, giảm thời gian chờ của khách hàng xuống dưới 5 phút. Giải pháp này cần được bộ phận điều hành vận tải triển khai liên tục theo từng quý.

Đối tượng nên tham khảo luận văn

Công trình luận văn mang lại giá trị thực tiễn và học thuật cho 4 nhóm đối tượng cụ thể:

  1. Các nhà nghiên cứu và học viên cao học chuyên ngành Khoa học máy tính, Hệ thống thông tin: Nắm vững phương pháp luận chuẩn mực về khai phá dữ liệu chuỗi, hiểu rõ cơ chế so sánh giữa hai trường phái Apriori và Pattern Growth, làm tài liệu tham khảo cho các đề tài xử lý dữ liệu không gian - thời gian.
  2. Kỹ sư phát triển phần mềm di động và kỹ sư dữ liệu: Học hỏi giải pháp thiết kế trọn gói từ ứng dụng iOS trên AppStore thu thập tọa độ, máy chủ cơ sở dữ liệu lưu trữ 454 bản ghi, đến quy trình 5 bước tiền xử lý dữ liệu thô thành định dạng số nguyên tối ưu.
  3. Doanh nghiệp vận tải công nghệ và chuyển phát nhanh: Ứng dụng mô hình phân tích chuỗi chuyến đi để tối ưu hóa mạng lưới cung ứng xe, dự báo nhu cầu đặt chuyến theo thời gian thực, giúp tiết kiệm từ 10% đến 15% chi phí nhiên liệu và chi phí vận hành đội xe.
  4. Ban quản lý đô thị, khu đô thị đại học và khu công nghiệp: Sử dụng kết quả phân tích mẫu di chuyển giữa 25 địa điểm để quy hoạch hệ thống giao thông nội bộ, bố trí bãi đỗ xe thông minh và thiết lập các tuyến xe buýt kết nối hợp lý, hạn chế ùn tắc cục bộ.

Câu hỏi thường gặp

  1. Khai phá mẫu tuần tự khác biệt như thế nào so với khai phá luật kết hợp truyền thống? Khai phá luật kết hợp chỉ phân tích các mặt hàng hoặc sự kiện xuất hiện đồng thời trong một giao dịch đơn lẻ mà không xét đến thứ tự thời gian. Ngược lại, khai phá mẫu tuần tự theo dõi hành vi xuyên suốt nhiều mốc thời gian khác nhau của cùng một đối tượng, giúp nhận diện chính xác lộ trình di chuyển tiếp theo với độ hỗ trợ lên tới 90%.

  2. Tại sao thuật toán GSP bị suy giảm hiệu năng khi khai phá chuỗi dài hoặc ngưỡng hỗ trợ thấp? Thuật toán GSP dựa trên nguyên lý Apriori nên phải quét cơ sở dữ liệu nhiều lần và sinh ra số lượng khổng lồ các chuỗi ứng viên tổ hợp. Khi ngưỡng hỗ trợ giảm dưới 0.4 hoặc độ dài chuỗi của 10 tình nguyện viên tăng lên, chi phí tính toán của GSP tăng vọt gấp 3 đến 5 lần so với PrefixSpan.

  3. Dữ liệu thực nghiệm của đề tài được thu thập và xử lý bằng phương pháp nào? Dữ liệu được thu thập trực tiếp qua ứng dụng di động iOS đưa lên AppStore, ghi nhận 454 bản ghi từ 10 tình nguyện viên trong 42 ngày tại Đại học Bách Khoa Thành phố Hồ Chí Minh. Sau đó, dữ liệu trải qua quy trình 5 bước để mã hóa 25 địa danh thành chuỗi số nguyên từ 10 đến 34.

  4. Cây dự đoán hành vi chuyến đi có khả năng ứng dụng thực tế ra sao? Cây dự đoán được xây dựng từ 27 mẫu tuần tự phổ biến, hoạt động như một bộ máy gợi ý thông minh. Khi người dùng hoàn thành 1 đến 2 chặng đầu tiên, hệ thống sẽ đối sánh với các nhánh cây để dự báo chặng kế tiếp với độ tin cậy trên 80%, phục vụ điều phối phương tiện đón đầu.

  5. Cần cấu hình phần cứng và thư viện phần mềm nào để chạy thực nghiệm các thuật toán này? Thực nghiệm của luận văn được thực hiện trên máy tính cấu hình Intel Core i5 2.4 GHz, RAM 4096 MB, sử dụng thư viện khai phá dữ liệu mã nguồn mở SPMF phiên bản 2 để chạy thuật toán GSP và PrefixSpan, đảm bảo xử lý mượt mà hàng trăm bản ghi giao dịch chuỗi.

Kết luận

  • Đề tài đã đề xuất thành công mô hình khai phá dữ liệu chuyến đi người dùng hoàn chỉnh, kết nối liền mạch từ khâu thu thập trên ứng dụng di động iOS đến khâu phân tích thuật toán chuyên sâu.
  • Triển khai thực nghiệm đạt kết quả vững chắc với 454 bản ghi giao dịch tại 25 địa điểm thực tế, trích xuất thành công 27 mẫu tuần tự phổ biến ở ngưỡng hỗ trợ cao minsup = 0.9.
  • Đánh giá định lượng toàn diện hiệu năng giữa thuật toán GSP và PrefixSpan trên máy tính cá nhân RAM 4096 MB, chỉ rõ ưu điểm và giới hạn cốt lõi của hướng tiếp cận Apriori.
  • Thiết lập mô hình cây dự đoán hành vi trực quan, mang lại công cụ đắc lực cho việc dự báo lộ trình di chuyển với độ chính xác đạt trên 80%.
  • Xác định rõ lộ trình phát triển trong 6 đến 12 tháng tới, hướng đến mở rộng tập dữ liệu trên 1.000 người dùng và tích hợp mô hình xác suất nâng cao.

Công trình luận văn thạc sĩ của tác giả Võ Văn Mỹ là tài liệu khoa học giá trị, cung cấp cả nền tảng lý thuyết lẫn giải pháp thực nghiệm sắc bén cho bài toán phân tích chuỗi hành vi. Các tổ chức, doanh nghiệp vận tải và nhóm nghiên cứu công nghệ hãy áp dụng ngay phương pháp khai phá mẫu tuần tự để bứt phá hiệu quả vận hành và nâng tầm các dịch vụ thông minh dựa trên vị trí.