Luận văn thạc sĩ: Nhận diện con người dựa trên hành vi di chuyển không thời gian

Luận văn thạc sĩ phân tích máy tính nhận diện con người dựa trên hành vi di chuyển không thời gian, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực tiễn.

• Tác giả: Phạm Minh Nghị
• Người hướng dẫn: PGS. Cao Hoàng Trụ
• Trường học: Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nhận diện con người qua hành vi di chuyển không thời gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CÁM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: XÁC ĐỊNH BÀI TOÁN. MỤC TIÊU VÀ PHẠM VI
• 2. CHƯƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Các phương pháp phân tích quá trình di chuyển
• 2.2. Phương pháp mô hình bằng quá trình ngẫu nhiên
• 2.2.1. Mô hình Random Walk
• 2.2.2. Mô hình Markov
• 2.3. Phương pháp khai phá luật kết hợp của các vị trí
• 2.4. Các phương pháp nhận diện
• 2.4.1. Phương pháp nhận diện bằng mô hình Markov
• 3. CHƯƠNG 3: CƠ SỞ LÝ THUYẾT
• 4. CHƯƠNG 4: PHƯƠNG PHÁP ĐỀ XUẤT
• 4.1. Mở rộng mô hình Markov
• 4.2. Xây dựng mô hình
• 4.2.1. Thêm yếu tố thời gian vào mô hình
• 4.3. Phương pháp nhận diện bằng mô hình Markov ẩn
• 4.3.1. Xây dựng mô hình
• 4.3.2. Nhận diện bằng mô hình Markov ẩn
• 4.3.3. Thêm yếu tố thời gian vào mô hình
• 5. CHƯƠNG 5: TẬP DỮ LIỆU VÀ THỰC NGHIỆM
• 5.1. Tập dữ liệu
• 5.2. Thực nghiệm và phân tích kết quả
• 5.2.1. Thực nghiệm với các thời khoảng ứng với buổi trong ngày
• 5.2.2. Thực nghiệm với các thời khoảng bất kỳ
• 5.2.3. Hạn chế của các phương pháp nhận diện
• 5.2.4. Hướng phát triển
• THAM KHẢO

Tóm tắt

I. Giới thiệu về nhận diện con người qua hành vi di chuyển

Nhận diện con người qua hành vi di chuyển không thời gian trong khoa học máy tính là một lĩnh vực nghiên cứu quan trọng. Hành vi di chuyển của con người được ghi lại thông qua các thiết bị di động, tạo ra những dấu vết vị trí có thể được phân tích để nhận diện cá nhân. Những thông tin này không chỉ mang tính chất không gian mà còn chứa đựng yếu tố thời gian, giúp tăng cường độ chính xác trong việc nhận diện. Công nghệ nhận diện hiện nay đã phát triển mạnh mẽ, với sự hỗ trợ của các thuật toán như machine learning và computer vision. Việc áp dụng các công nghệ này vào phân tích hành vi di chuyển giúp mở rộng khả năng nhận diện, từ đó phục vụ cho nhiều ứng dụng thực tiễn như an ninh, quản lý giao thông và nghiên cứu xã hội.

II. Phân tích hành vi di chuyển không thời gian

Phân tích hành vi di chuyển không thời gian là một quá trình phức tạp, bao gồm việc thu thập và xử lý dữ liệu từ các thiết bị di động. Dữ liệu di chuyển thường được biểu diễn dưới dạng chuỗi vị trí theo thời gian, cho phép nghiên cứu các đặc điểm của hành vi con người. Mô hình Markov là một trong những phương pháp phổ biến để mô phỏng quá trình di chuyển này. Mô hình này giúp xác định xác suất chuyển trạng thái giữa các vị trí, từ đó tạo ra một bức tranh rõ nét về hành vi di chuyển của cá nhân. Việc áp dụng mô hình này không chỉ giúp nhận diện mà còn hỗ trợ trong việc dự đoán hành vi trong tương lai.

III. Công nghệ và phương pháp nhận diện

Công nghệ nhận diện hiện nay sử dụng nhiều phương pháp khác nhau để phân tích hành vi di chuyển. Hệ thống giám sát và cảm biến chuyển động là những công cụ quan trọng trong việc thu thập dữ liệu. Các phương pháp như khai phá luật kết hợp và mô hình Markov ẩn được áp dụng để nhận diện dựa trên các đặc trưng của hành vi di chuyển. Những phương pháp này cho phép xây dựng các mô hình có tính đặc trưng cao, từ đó nâng cao khả năng nhận diện. Kết quả thực nghiệm cho thấy rằng một mô hình càng đặc trưng thì khả năng nhận diện càng cao, điều này chứng tỏ tầm quan trọng của việc phát triển các phương pháp mới trong lĩnh vực này.

IV. Ứng dụng thực tiễn của nhận diện hành vi di chuyển

Nhận diện hành vi di chuyển không thời gian có nhiều ứng dụng thực tiễn trong đời sống. Các ứng dụng này bao gồm quản lý giao thông, an ninh công cộng, và nghiên cứu hành vi xã hội. Việc phân tích dữ liệu di chuyển giúp các nhà quản lý đưa ra quyết định chính xác hơn trong việc quy hoạch đô thị và cải thiện hệ thống giao thông. Ngoài ra, trong lĩnh vực an ninh, việc nhận diện nhanh chóng và chính xác có thể giúp ngăn chặn các hành vi phạm tội. Các nghiên cứu cũng chỉ ra rằng việc áp dụng công nghệ này có thể cải thiện đáng kể hiệu quả trong việc theo dõi và quản lý các đối tượng di chuyển.

V. Kết luận và hướng phát triển

Nhận diện con người qua hành vi di chuyển không thời gian trong khoa học máy tính là một lĩnh vực đầy tiềm năng. Các nghiên cứu hiện tại đã chỉ ra rằng việc kết hợp yếu tố thời gian vào mô hình di chuyển có thể nâng cao khả năng nhận diện. Hướng phát triển trong tương lai có thể tập trung vào việc cải tiến các thuật toán nhận diện, mở rộng khả năng ứng dụng trong nhiều lĩnh vực khác nhau. Việc nghiên cứu sâu hơn về hành vi xã hội và trí tuệ nhân tạo cũng sẽ góp phần làm phong phú thêm cho lĩnh vực này, từ đó tạo ra những giải pháp hiệu quả hơn cho các vấn đề thực tiễn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh công nghệ thông tin phát triển mạnh mẽ, việc sử dụng điện thoại di động đã trở thành một phần thiết yếu trong cuộc sống hàng ngày. Theo báo cáo của ngành, hơn 80% người dùng điện thoại di động có thể được nhận diện dựa trên hành vi di chuyển của họ. Dữ liệu vị trí thu thập từ các thiết bị di động, đặc biệt là trong mạng GSM, chứa đựng thông tin không gian và thời gian về quá trình di chuyển của người dùng, được gọi là dấu vết di chuyển (mobility traces). Đây là loại dữ liệu nhạy cảm và đặc trưng cao, có thể được sử dụng để nhận diện cá nhân một cách chính xác.

Luận văn tập trung giải quyết bài toán nhận diện con người dựa trên hành vi di chuyển không-thời gian, bằng cách mở rộng mô hình Markov truyền thống để kết hợp yếu tố thời gian vào mô hình hóa quá trình di chuyển. Mục tiêu cụ thể là xây dựng một mô hình Markov không-thời gian có khả năng mô phỏng đầy đủ các đặc tính không gian và thời gian của hành vi di chuyển, từ đó nâng cao hiệu quả nhận diện cá nhân. Phạm vi nghiên cứu sử dụng dữ liệu thực tế từ dự án Reality Mining của MIT, thu thập trong khoảng thời gian từ tháng 9/2004 đến tháng 5/2005, với 106 đối tượng tham gia.

Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện tỉ lệ nhận diện đúng cá nhân dựa trên hành vi di chuyển, góp phần nâng cao các ứng dụng trong bảo mật thông tin, quản lý giao thông, và phân tích hành vi người dùng. Kết quả thực nghiệm cho thấy mô hình Markov không-thời gian vượt trội hơn so với mô hình Markov truyền thống, với tỉ lệ nhận diện đúng lên tới khoảng 88% trong một số trường hợp.

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

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Quá trình ngẫu nhiên (Stochastic Process): Là tập hợp các biến ngẫu nhiên được đánh thứ tự theo thời gian, dùng để mô phỏng sự tiến hóa của hệ thống theo thời gian. Quá trình ngẫu nhiên rời rạc được áp dụng để mô hình hóa hành vi di chuyển từng bước của người dùng.

• Mô hình Markov: Là quá trình ngẫu nhiên có tính chất Markov, trong đó xác suất chuyển trạng thái chỉ phụ thuộc vào trạng thái hiện tại, không phụ thuộc vào quá khứ. Mô hình Markov bậc nhất được sử dụng để mô phỏng chuỗi vị trí di chuyển của người dùng điện thoại trong mạng GSM.

• Mô hình Markov ẩn (Hidden Markov Model - HMM): Mở rộng mô hình Markov bằng cách cho phép trạng thái thực tế không quan sát được trực tiếp mà chỉ quan sát được các biểu hiện đầu ra. HMM được sử dụng để nhận diện người dùng dựa trên chuỗi quan sát vị trí.

• Khái niệm không-thời gian trong mô hình Markov: Mở rộng mô hình Markov truyền thống bằng cách kết hợp yếu tố thời gian (ví dụ: buổi sáng, chiều, tối, đêm) vào trạng thái, tạo thành mô hình Markov không-thời gian nhằm tăng tính đặc trưng của mô hình.

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

• Nguồn dữ liệu: Sử dụng tập dữ liệu Reality Mining của MIT, bao gồm chuỗi vị trí của 106 đối tượng sử dụng điện thoại di động trong mạng GSM, thu thập từ tháng 9/2004 đến tháng 5/2005. Dữ liệu có dạng chuỗi các cặp [thời điểm, vị trí trạm thu/phát sóng], với kích thước ô mạng từ 100 đến 200 mét.

• Phương pháp phân tích:

  1. Xây dựng mô hình Markov truyền thống dựa trên chuỗi vị trí không gian.
  2. Mở rộng mô hình Markov bằng cách thêm yếu tố thời gian vào trạng thái, tạo mô hình Markov không-thời gian.
  3. Áp dụng mô hình Markov ẩn để nhận diện người dùng dựa trên chuỗi quan sát vị trí.
  4. So sánh hiệu quả nhận diện giữa các mô hình và phương pháp nhận diện khác nhau như Residence Matching, Cell Sequence Matching, và phương pháp dựa trên HMM.

• Timeline nghiên cứu:

  • Giai đoạn huấn luyện (Atraining): Chọn một tháng bất kỳ trong tập dữ liệu để xây dựng cơ sở dữ liệu nhận dạng.
  • Giai đoạn đánh giá (Aevaluation): Chọn tháng kế tiếp để thử nghiệm nhận diện người dùng chưa biết.

• Cỡ mẫu: 106 đối tượng trong tập dữ liệu Reality Mining.

• Phương pháp chọn mẫu: Sử dụng toàn bộ dữ liệu có sẵn của dự án Reality Mining để đảm bảo tính đại diện và thực tế.

• Lý do lựa chọn phương pháp phân tích: Mô hình Markov và HMM phù hợp để mô phỏng và nhận diện các chuỗi vị trí tuần tự có tính chất ngẫu nhiên có điều kiện, đồng thời việc thêm yếu tố thời gian giúp tăng tính đặc trưng và độ chính xác của mô hình.

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

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

1. Hiệu quả của mô hình Markov không-thời gian:
   Thực nghiệm trên tập dữ liệu Reality Mining cho thấy mô hình Markov không-thời gian (kết hợp yếu tố thời gian vào trạng thái) có tỉ lệ nhận diện đúng cao hơn đáng kể so với mô hình Markov truyền thống. Ví dụ, trong tháng 02/2005, tỉ lệ nhận diện đúng của phương pháp SpatioTempSeq đạt 88%, trong khi phương pháp tương đương không có yếu tố thời gian chỉ đạt khoảng 80%.

2. So sánh các phương pháp nhận diện:

   • Phương pháp Cell Sequence Matching (SpatioSeq) cho hiệu quả nhận diện tốt hơn so với Residence Matching (SpatioRes), với tỉ lệ nhận diện đúng trung bình khoảng 70% so với 40%.
   • Phương pháp dựa trên mô hình Markov ẩn (SpatioHMM) có hiệu suất nhận diện đúng khoảng 60%, thấp hơn Cell Sequence Matching nhưng cao hơn Residence Matching.
   • Khi kết hợp yếu tố thời gian, các phương pháp không-thời gian (SpatioTempRes, SpatioTempSeq, SpatioTempHMM) đều cải thiện tỉ lệ nhận diện đúng từ 5-15% so với phiên bản không có yếu tố thời gian.

3. Ảnh hưởng của cách phân chia thời gian:
   Việc phân chia thời gian theo các buổi trong ngày (morning, afternoon, evening, night) giúp tối đa hóa tính đặc trưng của mô hình, nâng cao hiệu quả nhận diện. Ngược lại, phân chia thời gian thành các khoảng bất kỳ không trùng với thói quen sinh hoạt làm giảm hiệu quả nhận diện, ví dụ tỉ lệ nhận diện đúng giảm khoảng 5-10%.

4. Hạn chế của dữ liệu và mô hình:

   • Dữ liệu vị trí thu thập từ mạng GSM có độ chính xác thấp, bị nhiễu do hiện tượng chồng lấn phạm vi phủ sóng của các trạm thu/phát sóng.
   • Một số trường hợp nhận diện sai do thói quen di chuyển thay đổi theo thời gian hoặc dữ liệu không đủ độ mịn.
   • Mô hình Markov bậc nhất không bảo toàn được các đặc tính phụ thuộc vào nhiều trạng thái trước đó, có thể ảnh hưởng đến độ chính xác nhận diện.

Thảo luận kết quả

Kết quả thực nghiệm khẳng định rằng việc bổ sung yếu tố thời gian vào mô hình Markov giúp tăng tính đặc trưng của mô hình, từ đó nâng cao khả năng nhận diện cá nhân dựa trên hành vi di chuyển. Điều này phù hợp với nhận định trong các nghiên cứu trước rằng hành vi di chuyển của con người có tính đặc thù theo thời gian trong ngày.

So với các phương pháp truyền thống chỉ dựa trên không gian, mô hình không-thời gian cung cấp một cách tiếp cận toàn diện hơn, phản ánh đúng hơn thực tế hành vi di chuyển. Mô hình Markov ẩn tuy có hiệu quả nhận diện thấp hơn Cell Sequence Matching nhưng vẫn vượt trội so với Residence Matching, cho thấy tính khả thi của việc sử dụng HMM trong bài toán nhận diện.

Việc phân chia thời gian hợp lý là yếu tố quan trọng để khai thác tối đa đặc trưng hành vi. Tuy nhiên, tăng số lượng khoảng thời gian sẽ làm tăng độ phức tạp tính toán, đòi hỏi cân bằng giữa hiệu quả và chi phí xử lý.

Các hạn chế về dữ liệu và mô hình cũng được minh họa qua các trường hợp nhận diện sai, cho thấy cần có các biện pháp xử lý nhiễu và mở rộng mô hình Markov bậc cao hơn trong các nghiên cứu tiếp theo.

Dữ liệu và kết quả có thể được trình bày qua các biểu đồ so sánh tỉ lệ nhận diện đúng giữa các phương pháp và mô hình theo từng tháng, cũng như bảng thống kê chi tiết tỉ lệ nhận diện đúng tương ứng với từng phương pháp.

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

1. Áp dụng mô hình Markov không-thời gian trong các hệ thống nhận diện cá nhân:
   Khuyến nghị các tổ chức phát triển hệ thống bảo mật và quản lý người dùng điện thoại di động áp dụng mô hình Markov mở rộng kết hợp yếu tố thời gian để nâng cao độ chính xác nhận diện, đặc biệt trong các ứng dụng an ninh và quản lý truy cập.

2. Tối ưu phân chia khoảng thời gian phù hợp với đặc thù hành vi người dùng:
   Đề xuất nghiên cứu và lựa chọn các khoảng thời gian (ví dụ: buổi sáng, chiều, tối) dựa trên đặc điểm sinh hoạt thực tế của đối tượng để tối đa hóa tính đặc trưng của mô hình, đồng thời cân nhắc chi phí tính toán.

3. Phát triển các mô hình Markov bậc cao hơn và xử lý nhiễu dữ liệu:
   Khuyến nghị nghiên cứu mở rộng mô hình Markov bậc 2 hoặc bậc n để bảo toàn các đặc tính phụ thuộc vào nhiều trạng thái trước đó, đồng thời áp dụng các kỹ thuật lọc nhiễu để cải thiện chất lượng dữ liệu vị trí thu thập từ mạng GSM.

4. Xây dựng cơ sở dữ liệu nhận dạng liên tục cập nhật:
   Đề xuất xây dựng hệ thống cập nhật mô hình nhận dạng định kỳ để thích ứng với sự thay đổi hành vi di chuyển của người dùng theo thời gian, đảm bảo tính chính xác và độ tin cậy của hệ thống nhận diện.

5. Chủ thể thực hiện: Các nhà nghiên cứu trong lĩnh vực khoa học máy tính, các công ty viễn thông, tổ chức quản lý an ninh mạng và các đơn vị phát triển phần mềm quản lý người dùng.

6. Timeline thực hiện:

   • 6 tháng đầu: Nghiên cứu và phát triển mô hình Markov không-thời gian, thử nghiệm trên dữ liệu thực tế.
   • 6 tháng tiếp theo: Tối ưu phân chia thời gian, xử lý nhiễu và mở rộng mô hình.
   • 12 tháng tiếp theo: Triển khai hệ thống nhận diện thực tế và xây dựng cơ sở dữ liệu cập nhật.

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

1. Nhà nghiên cứu và sinh viên ngành Khoa học Máy tính:
   Luận văn cung cấp kiến thức chuyên sâu về mô hình Markov, mô hình Markov ẩn và ứng dụng trong nhận diện hành vi di chuyển, phù hợp cho nghiên cứu và phát triển các đề tài liên quan.

2. Chuyên gia phát triển hệ thống bảo mật và nhận diện cá nhân:
   Các giải pháp và phương pháp đề xuất trong luận văn giúp nâng cao hiệu quả nhận diện người dùng dựa trên dữ liệu vị trí, hỗ trợ phát triển các hệ thống an ninh mạng và quản lý truy cập.

3. Công ty viễn thông và nhà cung cấp dịch vụ di động:
   Thông tin về mô hình hóa hành vi di chuyển và nhận diện cá nhân có thể ứng dụng trong tối ưu mạng lưới, phân tích hành vi khách hàng và phát triển dịch vụ cá nhân hóa.

4. Nhà quản lý giao thông và quy hoạch đô thị:
   Dữ liệu và mô hình nhận diện hành vi di chuyển giúp dự báo lưu lượng giao thông, quy hoạch mạng lưới giao thông thông minh và nâng cao hiệu quả quản lý đô thị.

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

1. Mô hình Markov không-thời gian khác gì so với mô hình Markov truyền thống?
   Mô hình Markov không-thời gian mở rộng trạng thái bằng cách kết hợp yếu tố thời gian (ví dụ: buổi sáng, chiều) vào trạng thái, giúp mô hình phản ánh đầy đủ hơn đặc trưng hành vi di chuyển theo thời gian, từ đó tăng tính đặc trưng và độ chính xác nhận diện.

2. Tại sao dữ liệu vị trí từ mạng GSM lại có độ chính xác thấp?
   Dữ liệu vị trí từ mạng GSM dựa trên vị trí trạm thu/phát sóng, có phạm vi phủ sóng rộng từ vài trăm mét đến vài km, và bị nhiễu do hiện tượng chồng lấn phạm vi phủ sóng giữa các trạm, dẫn đến vị trí thu được không phải là vị trí tuyệt đối chính xác của người dùng.

3. Phương pháp nhận diện nào cho hiệu quả cao nhất trong nghiên cứu?
   Phương pháp Cell Sequence Matching kết hợp mô hình Markov không-thời gian (SpatioTempSeq) cho hiệu quả nhận diện đúng cao nhất, đạt tới khoảng 88% trong một số tháng thử nghiệm, vượt trội so với các phương pháp khác.

4. Ảnh hưởng của cách phân chia thời gian đến hiệu quả nhận diện như thế nào?
   Phân chia thời gian theo các buổi trong ngày phù hợp với thói quen sinh hoạt giúp mô hình khai thác tối đa đặc trưng hành vi, nâng cao hiệu quả nhận diện. Phân chia thời gian ngẫu nhiên hoặc không phù hợp làm giảm tính đặc trưng và hiệu quả nhận diện.

5. Có thể áp dụng mô hình này cho dữ liệu vị trí có độ chính xác cao hơn như GPS không?
   Có thể. Mô hình Markov không-thời gian và HMM có thể được áp dụng cho dữ liệu vị trí có độ chính xác cao hơn như GPS, dự kiến sẽ cải thiện hơn nữa độ chính xác nhận diện do dữ liệu chi tiết và ít nhiễu hơn.

Kết luận

• Luận văn đã xây dựng thành công mô hình Markov không-thời gian kết hợp yếu tố thời gian vào mô hình hóa hành vi di chuyển, nâng cao tính đặc trưng và hiệu quả nhận diện cá nhân dựa trên dữ liệu vị trí di chuyển trong mạng GSM.
• Phương pháp nhận diện dựa trên mô hình Markov ẩn và Cell Sequence Matching cho kết quả nhận diện đúng cao, với tỉ lệ lên tới khoảng 88% trong một số trường hợp thực nghiệm.
• Việc phân chia thời gian hợp lý theo các buổi trong ngày là yếu tố quan trọng để tối ưu hiệu quả nhận diện.
• Hạn chế về dữ liệu và mô hình hiện tại được nhận diện rõ, mở ra hướng nghiên cứu phát triển mô hình Markov bậc cao hơn và xử lý nhiễu dữ liệu.
• Đề xuất triển khai ứng dụng mô hình trong các hệ thống nhận diện cá nhân, bảo mật và quản lý hành vi người dùng, đồng thời tiếp tục nghiên cứu mở rộng và tối ưu mô hình.

Next steps: Tiếp tục phát triển mô hình Markov bậc cao, xử lý nhiễu dữ liệu, thử nghiệm trên các tập dữ liệu có độ chính xác cao hơn, và xây dựng hệ thống nhận diện thực tế.

Các nhà nghiên cứu và chuyên gia trong lĩnh vực khoa học máy tính, viễn thông và an ninh mạng nên áp dụng và phát triển các mô hình nhận diện không-thời gian để nâng cao hiệu quả và độ chính xác trong các ứng dụng thực tế.

Trích đoạn nội dung tài liệu

Chương 1, dấu vết vị trí của quá trình di chuyển thông thường có dạng một chuỗi tuân tự các vị trí theo thời gian. Những phương pháp mô hình hóa thường được sử dụng đối với dữ liệu dạng này gồm: mô hình Random Walk, mô hình Random Waypoint, mô hình Markov, v. Mô hình Random Walk. Mô hình Random Walk được giới thiệu để mô phỏng một quá trình mà sự chuyền động của nó mang tính ngẫu nhiên, gần như không thé đoán trước.

Trong mô hình Random Walk, một quá trình ngẫu nhiên sẽ tiến triển với các tham sô là phương hướng ngâu nhiên và vận toc ngau nhiên. Có thé hình dung một mô hình Random Walk như một đồ thị vô hướng trong hệ trục tọa độ vuông góc Oxy như sau: cho một điểm bắt kì trên hệ trục là đỉnh khởi đầu của một đồ thị. Sau đó, chọn một đỉnh mới trên hệ trục tọa độ sao cho khoảng cách giữa đỉnh mới và đỉnh ban đầu năm trong khoảng [đ„„, dnax| nào đó, rồi nối đỉnh ban đầu với đỉnh mới. Tiếp tục nối đỉnh mới này với một đỉnh mới theo cách tương tự.

Như vậy ta đã biểu diễn được hình ảnh hai chiều của một mô hình Random Walk với vận tốc ngẫu nhiên ở mỗi bước tiến triển là chiều dài của một cạnh trong đồ thị, hướng ngẫu nhiên là góc tạo bởi các cạnh trong đồ thị với hệ trục tọa độ, như minh họa trong hình 2. Biéu diễn mô hình Random Walk trên hệ trục toa độ hai chiêu Mô hình Random Walk với các thông số phù hợp về sự ngẫu nhiên của phương hướng và vận tốc sẽ giúp biểu diễn được các quá trình quan sát được trong tự nhiên như: sự di chuyển của chất lỏng, sự bay hơi của chất khí, sự dịch chuyển của các phân tử, v. Tuy nhiên, hau hết các quá trình chuyển động quan sát được hàng ngày xung quanh ta đều không phải là hoàn toàn ngẫu nhiên, ví dụ như sự thay đổi thời tiết, sự di chuyển của phương tiện giao thông trong thành phó, tỉ giá chứng khoán, v. Tất cả những quá trình này đều phan nào có thé du đoán được.

Sự tiến triển của các quá trình này phụ thuộc các ràng buộc và điều kiện bên ngoài cũng như dựa trên lịch sử tiến triển của chính nó. Sự tiến triển của mô hình Randon Walk là hoàn toàn ngẫu nhiên, không phụ thuộc vào một tri thức đã biết nào. Do đó mô hình Random Walk không đủ phù hợp dé có thé mô phỏng được các quá trình mà sự tiến triển của nó bi chi phôi bởi những điêu kiện phức tạp, ví dụ như sự di chuyền của con người. Mô hình Markov.

Là một mô hình cải tiến giúp loại bỏ phần nào yếu tố ngẫu nhiên của mô hình Random Walk [2]. Trong mô hình Markov, sự tiến triển của quá trình ngẫu nhiên được chi phối bởi trạng thái hiện tại của quá trình, hay thậm chí bị chi phối bởi N trạng thái trước đó của quá trình. Do đó, một quá trình Markov sẽ tránh được những sự thay đổi đột ngột về phương hướng và vận tốc, giúp mô hình trở nên phù hợp hơn cho những quá trình quan sát được trong thực tế. Ví dụ: trong thị trường chứng khoán giá cô phiêu của ngày hôm sau sẽ phụ thuộc vào giá và xu hướng mua bán của ngày hôm trước; hay vi trí của một người trong tương lai sẽ phụ thuộc vào vi tri hiện tại của họ.

Quá trình chuyển trạng thái trong mô hình Markov. Ở mỗi trạng thái, mô hình sẽ có một phân bố xác suất chuyển đến những trạng thái tiếp theo. Mô hình Markov được sử dụng trong [5] để biểu diễn quá trình di chuyển của người dùng điện thoại trong mạng GSM. Dữ liệu thu được từ quá trình di chuyển của người dùng thiết bị di động trong mang GSM có dạng chuỗi tuần tự theo thời gian vị trí của các trạm thu/phát sóng.

Chuỗi vị trí của các trạm thu/phát sóng này được xem như một chuỗi trạng thái của một quá trình Markov, mỗi trạng thái của quá trình này ứng với một vị trí; vi trí của một người ở một thời điểm nhất định được xem như trạng thái hiện tại của quá trình, và sự di chuyển của người dùng từ một vi tri sang vi trí ké tiép liền kể nó được xem như một sự chuyển trạng thái trong chuối Makov. Bang cách mô hình hóa quá trình di chuyển như một quá trình Markov như trên, ta có thé khai thác được những yếu tố đặc trưng của quá trình Markov này, và cũng là đặc trưng di chuyển của đối tượng tương ứng. Cụ thể, ta có thể tính toán được phân bố xác suất mà hệ chuyền từ trạng thái này sang một trạng thái khác — ung với xác suất mà đối tượng sẽ di chuyển từ vị trí hiện tại đến một vị trí kế cận nào đó. Các phân bố xác suất này được biểu diễn băng một ma trận chuyển đối (transition probability matrix).

Ngoài ra, ta còn tính được phân bố xác suất của chuỗi Markov trên từng trạng thái. Phân bố xác suất này được biểu diễn băng một vector phân bồ (stationary distribution vector). Moi đôi tượng sẽ có quá trình di chuyên khác nhau. Do đó, mô hình hóa qua trình di chuyên của các đôi tượng này sẽ giúp sinh ra các ma trận chuyên đôi và vector phân bố khác nhau đặc trưng cho mỗi đối tượng.

Phương pháp khai phá luật kết hợp của các vị trí Một phương pháp mô phỏng đặc trưng của một quá trình di chuyên là khai thác mối quan hệ giữa các địa điểm trên quãng đường mà một đối tượng đi qua [1]. Ví dụ về mối quan hệ này là: một đối tượng U; thường đi qua vị trí L; trước khi đến vị trí L, và L3, trong khi đó một đối tượng U> thường di qua vi trí L¿ rồi mới đến vị trí Lạ, v. Những mối quan hệ này được xem xét trong từng khoảng thời gian nhất định, ví dụ như budi trong ngày hay ngày trong tuần. Việc khai thác các đặc trưng này gồm hai bước chính: e Xây dựng đường di (path construction).

e Khai phá luật kết hợp trên đường đi nay (pattern discovery). Trong bước xây dựng đường di, độ quan trọng của một vi tri đối với một đối tượng được xem như tỉ lệ thuận với khoảng thời gian đối tượng này ở tại ví trí đó. Các vị trí trên chuỗi vị trí ban đầu được xem xét hay loại bỏ (để tránh nhiễu) dựa trên mức độ quan trọng này. Sau đó, giải thuật k-mean được áp dụng để gom nhóm các vị trí có liên quan với nhau thành một vị trí duy nhất.

Kết quả cuối cùng của giai đoạn này là chuỗi đường đi gồm những vị trí đặc trưng và quan trọng đối với một đối tượng di chuyền. Sau đó, giải thuật Apriori tuần tự được sử dụng để khai phá luật kết hợp giữa các vị trí trên đường đi này. Qua đó, các đặc trưng di chuyển của một người có thé được biéu diễn dang tập những mối kết hợp (hay còn gọi là kiểu mẫu — pattern) này. Ví dụ trình bày trong bảng sau là 5 kiểu mẫu di chuyển pho biến nhất của một người trong trong khoảng thời gian là các ngày làm việc trong tuân.

Người này có tần suất di chuyển từ địa điểm Home đến Media Lab (chuỗi <Home, Media Lab>) cao nhất, xác suất xuất hiện của chuỗi này trên đường đi là 0. Chuỗi pho biến thứ hai là <Media Lab, Home> va kế đến là chuỗi <Commonweath, Media Lab>, V. Các kiêu mau đặc trưng nhát cua một quá trình di chuyên. Những kiêu mâu này có thê được xem là đặc trưng của một người do môi người sẽ có các kiêu mâu và tân suát khác nhau # Mau Tan suat 1 <Home, Media Lab> 0.279 2 <Media Lab, Home> 0.265 3 <Commonweath, Media Lab> 0.133 4 <Home, Charles Hotel, Media Lab> 0.060 5 <Media Lab, Charles Hotel, Home> 0.053 Khai thác luật kết hợp trong những khoảng thời gian khác nhau sẽ cho kết quả là các kiểu mẫu khác nhau thé hiện đặc thù di chuyển của một người trong những khoảng thời gian này.

Ví dụ, cùng một đối tượng trên nếu xét trong khoảng thời gian ngày nghỉ (thứ bảy và chủ nhật) ta sẽ tìm được tập các mẫu đặc trưng khác trong đó không chứa các vi trí Media Lab và Commonwealth. Kết luận: nghiên cứu [1] không nhằm mục tiêu nhận diện hay so sánh các mô hình di chuyển với nhau mà chỉ đưa ra phương pháp khai thác những yếu tố đặc trưng trong một quá trình di chuyển. Tuy nhiên, có thé thay được rang: dữ liệu về chuỗi vị trí của một người có thé được mô hình hóa ở một mức độ đặc thù dé giúp phân biệt được người đó với những người khác. Ta cũng thấy được răng các đặc trưng này phụ thuộc đáng kế vào khoảng thời gian mà quá trình di chuyển được xem xét.

Cac phương pháp nhận diện 2. Phương pháp nhận diện bằng mô hình Markov Trong bài toán nhận diện, việc mô hình hóa quá trình di chuyển của một người là bước quan trọng vì dé có thé phân biệt được các quá trình di chuyên khác nhau thì cần phải mô phỏng được đây đủ và bảo toàn được tính đặc trưng của mỗi quá trình di chuyển này. Sau khi đã mô phỏng được quá trình di chuyển, van dé tiếp theo của bài toán nhận diện là: tính toán mức độ tương đồng giữa hai mô hình di chuyên dé xác định xem chúng có thuộc về cùng một đối tượng hay không. Hay nói cách khác, từ một mô hình di chuyển của một đối tượng chưa biết, so sánh với mô hình của những đối tượng đã biết để tìm ra mô hình tương đồng nhất từ đó suy ra đối tượng cần tìm.

Phương pháp nay can dựa trên những điều kiện sau: 1) Qua trình di chuyén cua mot người có tính đặc trưng cao. 2) Những đặc trưng này thay đối không đáng ké theo thời gian. Quá trình di chuyển của mỗi con người về cơ bản là duy nhất. Tuy nhiên, tính duy nhất này có thể không được bảo đảm trong một số trường hợp mà dữ liệu thu được không đủ độ mịn và chính xác.

Tuy nhiên, trong thực tế, cả hai điều kiện trên đều có xác suất đúng cao. Điều này đã được chứng minh trong [5] khi có tới hơn 80% người dùng điện thoại di động có thé được nhận diện dựa trên mô hình di chuyển của họ. Nghiên cứu [5] đã đưa hai ra phương pháp nhận diện dựa trên việc tính toán sự tương đồng giữa các mô hình di chuyển Markov. Phương pháp 1 — Residence Matching Xét hai đối tượng U, và , cùng di chuyển trong phạm vi m địa điểm.