Tài liệu Khai phá dữ liệu cho dự báo di chuyển trong mạng không dây [tt]

1 A. MỞ ĐẦU Sự ra đời của mạng nội bộ không dây (Wireless Local Area Network – WLAN) đã tạo điều kiện thuận lợi cho người sử dụng thiết bị di động có thể truy cập các ứng dụng mạng Internet mọi lúc mọi nơi và duy trì kết nối Internet ngay cả khi họ đang di chuyển trong vùng phủ sóng. Trước đây, WLAN thường được triển khai ở các phạm vi địa lý hẹp như quán cà phê, nhà hàng, khách sạn, trung tâm thương mại,… Tuy nhiên, với sự phát triển nhanh chóng của thiết bị di động như điện thoại Internet (VoIP phone hay IP phone, iPhone ), điện thoại thông minh (smart phones), máy tính bảng (iPad), máy nghe nhạc (iPod),… và sự phát triển của công nghệ mạng không dây đã tạo điều kiện thuận lợi cho việc mở rộng phạm vi vùng phủ sóng và được gọi là mạng nội bộ không dây phạm vi rộng (Wide Wireless Local Area Networks - WWLANs) hay mạng nội bộ không dây công cộng (Public Wireless Local Area Networks – PWLANs). WWLANs thường được quan tâm xây dựng ở các thành phố lớn, như New York, London, Paris, St. Cloud, …và các trường đại học, như trường đại học Dartmouth, Học viện kỹ thuật Massachusetts (Massachusetts Institute of Technology – MIT), đại học Florida, … Tại Việt Nam, các thành phố du lịch như Hội An, Đà Nẵng, Huế, Hải Phòng, … đã được phủ sóng Wi-fi miễn phí nhằm đáp ứng nhu cầu truy cập Internet cùng lúc cho hàng ngàn người dân thành phố và khách du lịch. Riêng thành phố Hồ Chí Minh đã thí điểm lắp đặt WWLAN trên các tuyến xe buýt nhằm thu hút người dân thành phố sử dụng loại phương tiện công cộng này [nguồn: http://vnreview.vn]. Bên cạnh đó, một số trường đại học cũng đã triển khai WWLAN phục vụ cho hàng ngàn cán bộ, giảng viên và sinh viên như: ĐH Công nghiệp TPHCM, ĐH Quốc gia TPHCM, ĐH Việt Đức, ĐH Kiểm sát Hà Nội, ĐH Tài chính kế toán Quảng Ngãi, … Một mạng nội bộ không dây công cộng như vậy thường bao gồm hàng trăm điểm truy nhập mạng (Access Point – AP) và phục vụ cho hàng ngàn người sử dụng thiết bị di động tại mỗi thời điểm. Trong hệ thống mạng WWLAN, mỗi AP có vùng phủ sóng từ vài chục mét (indoor AP) đến vài trăm mét (outdoor AP). Do bán kính phủ sóng của các AP nhỏ nên mỗi khi nút di động (Mobile Node – MN) di chuyển, 2 nó thường đi qua nhiều vùng phủ sóng của nhiều AP khác nhau. Vì WWLAN phải phục vụ nhiều thiết bị di động và chúng thường xuyên thay đổi điểm kết nối mạng như vậy nên trong hệ thống mạng thường phát sinh những vấn đề về Quản lý vị trí và Cấp phát tài nguyên mạng cho thiết bị di động. Dự báo sự di chuyển của nút di động trong mạng không dây là xác định điểm truy nhập mạng nào mà nút di động có thể kết nối trong quá trình nó di chuyển xung quanh vùng phủ sóng. Theo đó, dự báo di chuyển có thể cung cấp cho hệ thống mạng tri thức về sự di chuyển kế tiếp của các MN cũng như tri thức về nhu cầu sử dụng tài nguyên mạng trong tương lai tại mỗi AP. Với những tri thức như vậy, dự báo di chuyển có thể hỗ trợ giải quyết các vấn đề về quản lý vị trí và cấp phát tài nguyên mạng. Trong hơn một thập niên qua, bài toán dự báo sự di chuyển của thiết bị di động trong mạng không dây thu hút được nhiều sự quan tâm của cộng đồng nghiên cứu. Cho đến nay, đã có nhiều công trình khảo sát về các phương pháp kỹ thuật được sử dụng trong dự báo di chuyển. Kết quả khảo sát cho thấy rằng phần lớn cơ chế dự báo được đề xuất trong những năm gần đây đều dựa trên khai phá dữ liệu (data mining). Do đặc trưng dữ liệu di chuyển của người dùng di động có nhiều nhiễu, không đầy đủ và biến đổi liên tục, nên kỹ thuật khai phá mẫu tuần tự (sequential pattern mining) được cho là thích hợp và thu hút nhiều quan tâm nghiên cứu. Tuy nhiên, những công trình trước đây còn tồn tại hai vấn đề chính như sau:  Trong các công trình trước đây, thuộc tính thời gian trong dữ liệu di chuyển hoặc là bị loại bỏ sau khi được sử dụng để tạo các mẫu di chuyển hợp lệ hoặc là không được sử dụng trong quá trình khai phá mẫu di chuyển phổ biến. Do đó, các cơ chế dự báo di chuyển này chưa khai thác được giá trị của thời điểm di chuyển trong quá trình thực hiện dự báo. Trong khi đó, hành vi di chuyển của con người thường có mối quan hệ mạnh với thời gian biểu của họ. Nghĩa là, vào một số thời điểm cố định trong ngày, con người thường xuất hiện ở một số nơi cố định.  Hạn chế thứ hai của những công trình trước đây là sử dụng hành vi di 3 chuyển trong quá khứ của cá nhân người dùng di động để dự báo sự di chuyển tương lai của họ. Trong những trường hợp người sử dụng mới gia nhập vào hệ thống mạng hoặc thay đổi hành vi di chuyển, dữ liệu di chuyển của cá nhân họ sẽ không nhiều. Do đó, các cơ chế này có thể không dự báo thành công trong những trường hợp như vậy. Mục tiêu và phạm vi của luận án Mục tiêu của luận án là nghiên cứu các giải pháp khai thác những tri thức ẩn chứa trong dữ liệu di chuyển để nâng cao độ chính xác của cơ chế dự báo di chuyển trong mạng không dây. Luận án tập trung vào hai chủ đề chính sau đây:  Nghiên cứu cách khai thác đồng thời cả hai đặc trưng không gian và thời gian của dữ liệu di chuyển nhằm nâng cao độ chính xác dự báo. Để đạt được mục tiêu này, luận án đề xuất một cách biểu diễn mẫu di chuyển theo hai thuộc tính không gian và thời gian. Cách biểu diễn này sau đó được áp dụng để đề xuất một cơ chế dự báo di chuyển dựa trên khai phá mẫu không gian – thời gian.  Nghiên cứu cách khai thác đặc trưng di chuyển theo nhóm của người dùng di động và đề xuất giải pháp dự báo cho những di chuyển thiếu thông tin. Để đạt mục tiêu này, trước hết luận án định nghĩa một độ đo tương tự nhằm xác định mức độ giống nhau về hành vi di chuyển của người dùng di động. Độ đo tương tự mới này sau đó được áp dụng để phát triển một giải pháp phân nhóm dữ liệu di chuyển của người dùng di động. Dựa trên giải pháp phân nhóm, luận án đề xuất một cơ chế dự báo di chuyển nhằm khắc phục tình trạng thiếu thông tin của dữ liệu di chuyển cá nhân. Những đóng góp chính của luận án Luận án đã đề xuất các cơ chế dự báo di chuyển dựa trên sự khai thác các đặc trưng của dữ liệu di chuyển nhằm nâng cao độ chính xác dự báo, bao gồm:  Mô hình biểu diễn sự di chuyển của thiết bị di động trong mạng không dây theo thuộc tính không gian và thời gian. Mô hình này đã được công bố trên Tạp chí Southeast-Asian Journal of Sciences, 2012 và đã được báo cáo tại 4 Hội nghị quốc tế International Conference in Mathematics and Applications – ICMA, Thailand, 2011.  Cơ chế dự báo di chuyển dựa trên khai phá mẫu tuần tự không gian – thời gian. Cơ chế dự báo này khai thác giá trị của thuộc tính thời gian trong cả bốn giai đoạn của quá trình dự báo di chuyển. Kết quả nghiên cứu đã được công bố trên kỷ yếu của Hội nghị quốc gia lần 5 về nghiên cứu Cơ bản và Ứng dụng (FAIR’05), 2011, trên Tạp chí Journal of Communication and Computer (JCC), 2012 và trên Tạp chí International Journal of Computer Science and Telecommunications (IJCST), 2012.  Độ đo tương tự giữa các mẫu di chuyển nhằm khai thác đặc trưng di chuyển theo nhóm trong dữ liệu di chuyển. Độ đo tương tự này là một sự kết hợp có trọng số theo hai thuộc tính không gian và thời gian của mẫu di chuyển. Luận án đã lập luận chứng minh tính đúng đắn của độ đo tương tự và kiểm định bằng thực nghiệm. Độ đo này đã được công bố trên Tạp chí International Journal of Computer Networks & Communications (IJCNC), 2012 (DBLB) và trên Tạp chí Khoa học và Công Nghệ của Viện Khoa học và Công nghệ Việt Nam, 2013.  Thuật toán gom nhóm hành vi di chuyển của người dùng di động trong mạng không dây dựa trên độ đo tương tự được đề xuất bởi luận án. Hiệu quả của thuật toán gom nhóm được đánh giá bằng thực nghiệm trên nhiều tham số khác nhau và thông qua nhiều phương pháp đo chất lượng gom nhóm chuẩn. Kết quả nghiên cứu này đã được công bố trên kỷ yếu của Hội nghị quốc gia lần 6 về nghiên cứu Cơ bản và Ứng dụng (FAIR’06), 2013 và trên Tạp chí International Journal of Innovative Computing, Information and Control (IJICIC), 2013, (Scopus| SJR impact factor = 0.812).  Cơ chế dự báo di chuyển dựa trên nhóm hành vi di chuyển tương tự. Cơ chế này khai thác sự giống nhau về hành vi di chuyển của người dùng di động nhằm khắc phục sự thiếu thông tin của dữ liệu di chuyển cá nhân. Kết quả nghiên cứu này đã được công bố trên kỷ yếu của Hội nghị quốc tế 5 International Conference on Context-Aware Systems and Applications – ICCASA, 2013, Lecture Notes of ICST (Springer) và trên kỷ yếu của Hội nghị quốc tế Science and Information Conference – SAI, London, 2015 (IEEE Xplore) và trên Tạp chí Journal of Communications and Networks (JCN), 2015 (ISI, impact factor = 1.007). Bố cục của luận án Về cấu trúc, luận án được trình bày trong 3 chương, có phần mở đầu, phần kết luận, phần các công trình đã công bố liên quan đến luận án, tài liệu tham khảo và phần phụ lục. Chương 1 trình bày tổng quan về những vấn đề liên quan đến dự báo di chuyển trong mạng không dây và những cơ sở lý thuyết cho các giải pháp được đề xuất trong các chương còn lại của luận án. Chương 2 tập trung nghiên cứu và đề xuất một cách biểu diễn mẫu di chuyển theo hai thuộc tính không gian và thời gian của dữ liệu di chuyển. Với cách biểu diễn mẫu di chuyển như vậy, chương này đề xuất một cơ chế dự báo di chuyển dựa trên khai phá mẫu không gian – thời gian. Phần còn lại của chương là xây dựng dữ liệu kiểm thử, phương pháp đánh giá thực nghiệm và các kịch bản thực nghiệm, cài đặt thực nghiệm trên các tập dữ liệu mô phỏng để phân tích và đánh giá hiệu quả của việc sử dụng đồng thời cả hai thuộc tính không gian và thời gian vào dự báo di chuyển. Hiệu quả của cơ chế dự báo đề xuất cũng được đánh giá so sánh với các công trình liên quan bằng thực nghiệm. Trong chương 3, luận án đề xuất một độ đo tương tự cho mẫu di chuyển nhằm xác định mức độ giống nhau giữa chúng. Độ đo tương tự này sau đó được áp dụng để đề xuất một giải pháp gom nhóm mẫu di chuyển. Dựa trên giải pháp gom nhóm, luận án đề xuất một cơ chế dự báo di chuyển với mục tiêu khai thác đặc trưng di chuyển theo nhóm của người sử dụng thiết bị di động nhằm khắc phục sự thiếu thông tin của dữ liệu di chuyển cá nhân. Hiệu quả của các giải pháp được đề xuất trong chương này đều được đánh giá bằng thực nghiệm và so sánh với các công trình liên quan. Do đó, phần còn lại của chương trình bày về tập dữ liệu kiểm thử, phương pháp đánh giá thực nghiệm và các kịch bản thực nghiệm, kết quả thực nghiệm. 6 B. NỘI DUNG Chương 1 – Tổng quan về dự báo di chuyển trong mạng không dây 1.1. Tổng quan về các cơ chế dự báo di chuyển Loại tri thức và kỹ thuật Đặc điểm Hạn chế được sử dụng Tôpô giao thông, tôpô đường đi, … - Dựa vào tôpô hay bản đồ khái niệm không gian cảnh mạng hay tôpô thay đổi. Bản đồ khái niệm để tính xác suất di chuyển không gian - Không dự báo tốt khi ngữ - Yêu cầu tập hợp và xử lý từ một vị trí đến các vị trí một lượng thông tin cực kỳ lớn. có thể. - Thích hợp cho các hệ thống mạng ổn định và có qui mô nhỏ Tri thức ngữ Độ mạnh tín hiệu cảnh nhận được - Dựa vào độ mạnh tín - Làm tăng lưu lượng mạng vì hiệu để theo dõi (tracking) các AP liên tục gửi tín hiệu liên tục khoảng cách giữa chứa thông tin về khoảng cách. MN và những AP lân cận. - Số vị trí dự báo thường - Độ mạnh tín hiệu nhận nhiều hơn một vì dự báo không được càng lớn nghĩa là theo hướng di chuyển. MN ở càng gần AP, do đó có khả năng MN đang di chuyển đến AP. Hành vi di chuyển trong quá khứ Mô hình xác suất - Sự di chuyển của MN - Sử dụng tài nguyên tính toán từ AP này đến AP khác lớn. được mô hình là một sự chuyển trạng thái. - Dựa vào ma trận xác - Cần huấn luyện lại mô hình định kỳ. - Không khai thác được thông suất chuyển trạng thái để tin di chuyển theo nhóm. 7 dự báo sự chuyển trạng thái kế tiếp của MN. Phân tích thống kê - Phân tích dữ liệu di - Khó mở rộng thêm đặc điểm ngữ cảnh. - Không thích nghi với dữ liệu chuyển để rút trích tri không đầy đủ hoặc biến đổi thức về hành vi di chuyển. liên tục. - Kết quả phân tích thường rất lớn và trừu tượng. Phân lớp Thích hợp cho các hệ Phải huấn luyện lại mô hình khi thống mạng ổn định và có thêm dữ liệu mới hay loại bỏ quy mô nhỏ. dữ liệu cũ. Gom nhóm Sử dụng đặc điểm di Kết quả dự báo sẽ không tốt chuyển theo nhóm của nếu dữ liệu di chuyển có tỷ lệ người dùng di động để di chuyển ngẫu nhiên cao. tiên đoán di chuyển tương lai. Khai phá dữ Khai phá Thích nghi tốt với dữ liệu mẫu tuần di chuyển có tỷ lệ di thời gian trong mẫu di chuyển. tự chuyển ngẫu nhiên cao. - Chưa khai thác thuộc tính - Không dự báo tốt khi dữ liệu Đề xuất giải pháp đáp ứng di chuyển cá nhân không đầy liệu thời gian thực khi sử dụng đủ. khai phá mẫu tuần tự. Khai phá Sử dụng thuộc tính thời mẫu tuần gian trong giai đoạn khai gian ở một giai đoạn của quá tự không phá mẫu di chuyển phổ trình dự báo di chuyển. gian – thời biến. gian - Chỉ khai thác thuộc tính thời - Không dự báo tốt khi dữ liệu Sử dụng ràng buộc thời di chuyển cá nhân không đầy gian để sinh tập chuỗi di đủ. chuyển có nghĩa. 8 1.2. Độ đo tương tự cho dữ liệu di chuyển 1.2.1. Các khái niệm về độ đo tương tự Cho S là một tập hợp khác rỗng, một hàm số d: S  S  R được gọi là một mêtric (metric) trên S nếu d thỏa các tính chất sau: Tiên đề 1 (tính phản xạ - self-identity): với mọi x thuộc S, d(x, x) = 0. Tiên đề 2 (tính luôn dương – positivity): với mọi x, y thuộc S, x ≠ y, d(x, y) > 0 Tiên đề 3 (tính đối xứng – symmetry): với mọi x, y thuộc S, d(x, y) = d(y, x) Tiên đề 4 (tính bất đẳng thức tam giác - triangle inequality): với mọi x, y, z thuộc S, d(y, z) ≤ d(y, x) + d(x, z) Độ đo tương tự (similarity measure) của hai đối tượng dữ liệu là độ sai khác (dissimilarity) của đối tượng dữ liệu này với đối tượng dữ liệu còn lại. Độ sai khác này được tính dựa trên một hàm số d. Nếu hàm số d chỉ thỏa các tính chất phản xạ, luôn dương và đối xứng (các tiên đề 1, 2, 3) thì độ đo tương tự là một nửa mêtric hay bán mêtric (semi-metric). Nếu hàm số d chỉ thỏa các tính chất phản xạ, đối xứng và bất đẳng thức tam giác (các tiên đề 1, 2, 4) thì độ đo tương tự là một giả mêtric hay gần mêtric (pseudo-metric). Nếu hàm số d chỉ thỏa các tính chất phản xạ và đối xứng (các tiên đề 1, 3) thì độ đo tương tự là nửa giả mêtric hay nửa gần mêtric (semipseudo-metric). 1.2.2. Tổng quan về các độ đo tương tự Việc xác định mức độ tương tự giữa các mẫu đường đi đóng vai trò quan trọng trong việc khai thác sự di chuyển giống nhau của các đối tượng di chuyển. Mặc dù đã có nhiều độ đo được đề xuất để tính độ tương tự giữa các mẫu đường đi nhưng phần lớn được tính dựa trên khoảng cách Ơ-clit (Euclidean distance). Tuy nhiên, cũng có một số độ đo được đề xuất cho không gian mạng thay cho không gian Ơclit nhưng chưa quan tâm thuộc tính thời gian của dữ liệu đường đi. Một số ít độ đo sử dụng khoảng cách mạng (network distance) và tính toán dựa trên đồng thời thuộc tính không gian và thời gian. Tuy nhiên, yếu tố thời gian được phản ảnh thông qua khía cạnh thời khoảng giữa hai vị trí liên tiếp tương ứng trong hai mẫu hoặc thứ tự 9 giữa các vị trí tương ứng trong hai mẫu, chưa quan tâm đến thời điểm của hai vị trí tương ứng trong hai mẫu. 1.3. Mở rộng thuật toán gom nhóm k-means Với ưu điểm đơn giản và độ phức tạp tính toán thấp, thuật toán gom nhóm kmeans ngày càng trở nên phổ biến. Độ phức tạp của thuật toán k-means là O(n.k.l) với k là số lượng nhóm được sinh ra, n là số phần tử của tập dữ liệu cần phân hoạch và l là số lần lặp của vòng lặp while trong thuật toán. Với độ phức tạp tính toán đa thức, thuật toán k-means thường được đề xuất sử dụng cho các tập dữ liệu lớn. Tuy nhiên, thuật toán k-means kinh điển tập trung vào dữ liệu định lượng (numerical data, còn gọi là dữ liệu số) và do đó sử dụng khoảng cách Ơ-clit để đo độ tương tự giữa các đối tượng dữ liệu. Nhiều công trình nghiên cứu đã chứng minh sự không hiệu quả khi sử dụng khoảng cách Ơ-clit để đo độ tương tự giữa các đối tượng dữ liệu định tính (categorical data, còn gọi là dữ liệu phân loại). Hơn nữa, thuật toán k-means kinh điển được đề xuất cho miền giá trị định lượng nên rất khó áp dụng trực tiếp cho miền giá trị định tính như trong hầu hết các ứng dụng khai phá dữ liệu. Để khắc phục hạn chế này, nhiều nhóm nghiên cứu đã đề xuất các giải pháp để áp dụng k-means cho miền giá trị định tính. Trong đó, một số công trình đề xuất chuyển miền giá trị định tính sang miền giá trị định lượng. Cách tiếp cận này khá đơn giản tuy nhiên sẽ có thể dẫn đến mất ngữ nghĩa trong các khái niệm định tính. Một cách tiếp cận khác là xây dựng các độ đo tương tự cho dữ liệu định tính và sử dụng độ đo tương tự để phân nhóm đối tượng dữ liệu, điển hình là k-modes và krepresentatives. Tuy nhiên, những giải pháp gom nhóm này có thể tạo ra các phân hoạch không ổn định do mỗi nhóm có nhiều hơn một trung vị như k-modes hoặc do khởi tạo đại diện nhóm ngẫu nhiên như k-representatives. 1.4. Tập dữ liệu kiểm thử Mặc dù các hệ thống mạng WWLAN phổ biến nhưng phần lớn chúng đều được phát triển dần dần theo sự phát triển của thành phố / trường đại học. Do đó, sơ 10 đồ bố trí tổng thể các điểm truy nhập mạng APs của một hệ thống mạng WWLAN thường thay đổi theo thời gian. Hơn nữa, vì lý do bảo mật hệ thống mạng nên các nhà quản trị hệ thống phải có trách nhiệm bảo mật sơ đồ bố trí tổng thể các điểm truy nhập mạng. Vì không thể tiếp cận được sơ đồ bố trí tổng thể các điểm truy nhập mạng của một hệ thống mạng trong thực tế nên phần lớn các nhóm nghiên cứu đều tự xây dựng tập dữ liệu kiểm thử từ các hệ thống mạng mô phỏng. Mặt khác, nhằm khảo sát mức độ ảnh hưởng của tỷ lệ di chuyển ngẫu nhiên trong dữ liệu di chuyển đối với độ chính xác dự báo của cơ chế đề xuất, luận án cần xây dựng các tập dữ liệu kiểm thử theo các tỷ số ngẫu nhiên khác nhau. Tỷ số ngẫu nhiên là tỷ lệ số đường đi ngẫu nhiên trên tổng số đường đi trong tập. Với tập dữ liệu thực (real dataset), số đường đi ngẫu nhiên trong tập là cố định và khó nhận diện nên việc điều chỉnh tỷ số ngẫu nhiên cho tập dữ liệu kiểm thử thực là khó thực hiện được. Từ những lý do trên, luận án thực hiện đánh giá các đề xuất bằng thực nghiệm trên các tập dữ liệu kiểm thử mô phỏng. Tập dữ liệu kiểm thử là tập những đường đi của thiết bị di động xung quanh vùng phủ sóng của một hệ thống mạng. Do đó, để xây dựng tập dữ liệu kiểm thử, trước hết luận án mô phỏng một hệ thống mạng có vùng phủ sóng (coverage region) bao gồm một số lượng điểm truy nhập mạng (APs) cụ thể và sơ đồ bố trí các điểm truy nhập cụ thể. Hệ thống mạng này được biểu diễn bởi một đồ thị di chuyển có số nút và cấu trúc mạng lưới các nút tương ứng với số điểm truy cập mạng và sơ đồ bố trí các điểm truy cập mạng trong hệ thống. Dựa trên đồ thị di chuyển, luận án xây dựng một bộ sinh dữ liệu để sinh ra tập đường đi mô tả sự đi qua các nút trên đồ thị nhằm mô phỏng sự di chuyển xung quanh vùng phủ sóng của hệ thống mạng mô phỏng. Cách xây dựng tập dữ liệu kiểm thử này cũng đã được nhiều công trình nghiên cứu trước đây thực hiện. 1.5. Phương pháp đánh giá thực nghiệm Để đảm bảo tính chính xác, ngẫu nhiên và khách quan, luận án tính toán các tiêu chí đánh giá thông qua phương pháp kiểm thử chéo (n-folds cross-validation) 11 trên các tập dữ liệu kiểm thử được sinh ra. Theo phương pháp này, tập dữ liệu kiểm thử được phân chia ngẫu nhiên thành n tập dữ liệu con có số lượng phần tử bằng nhau. Lần lượt từng tập dữ liệu con trong n tập dữ liệu con được chọn làm tập kiểm tra và (n-1) tập dữ liệu con còn lại được sử dụng làm tập huấn luyện. Tiến trình đánh giá chéo được thực hiện lặp lại n lần tương ứng với n bộ tập huấn luyện/tập kiểm tra. Kết quả thực nghiệm trên mỗi lần huấn luyện/kiểm tra được ghi lại và sau đó tính kết quả trung bình. Giá trị trung bình của n kết quả được sử dụng để đánh giá tổng thể kết quả thực nghiệm. Luận án sử dụng các độ đo đánh giá chuẩn để thực nghiệm trên nhiều tham số khác nhau và từ đó đánh giá hiệu quả của các cơ chế dự báo di chuyển và gom nhóm hành vi di chuyển. Cụ thể về các độ đo đánh giá được trình bày trong phần tiếp theo. Độ đo đánh giá độ chính xác dự báo Tương tự các công trình nghiên cứu trước đây, luận án đánh giá độ chính xác dự báo dựa trên hai độ đo chuẩn sau:  Độ đo đầy đủ (Recall): Số lần dự báo đúng chia cho tổng số lần yêu cầu dự báo. Như vậy, độ đo đầy đủ xem trường hợp “không dự báo được (noprediction)” như một lần dự báo sai.  Độ đo chính xác (Precision): Số lần dự báo đúng chia cho tổng số lần dự báo được thực hiện thành công. Nghĩa là độ đo chính xác bỏ qua trường hợp “không dự báo được”. Vì độ đo chính xác (precision measure) không xét trường hợp “không dự báo được” nên độ đo này thích hợp cho việc đánh giá độ chính xác dự báo trong trường hợp dữ liệu di chuyển không đầy đủ. Ngược lại, khi dữ liệu di chuyển hoàn thiện thì “không dự báo được” phải được xem là một lần dự báo sai, vì lúc này cơ chế dự báo đã không tìm được vị trí kết nối kế tiếp. Do đó, độ đo đầy đủ nên được sử dụng trong trường hợp này. Độ đo đầy đủ có giá trị càng lớn thì độ chính xác dự báo của cơ chế càng lớn. 12 Độ đo đánh giá chất lượng gom nhóm Kết quả gom nhóm được xem là tốt nếu khoảng cách giữa các đối tượng dữ liệu trong cùng nhóm là thấp, trong khi đó khoảng cách giữa các đối tượng dữ liệu trong các nhóm khác nhau là cao. Cho đến nay, có ba phương pháp thường được sử dụng để đánh giá chất lượng của kết quả gom nhóm:  Đánh giá dựa vào các độ đo Entropy (Entropy measures): Chất lượng gom nhóm được đánh giá bởi độ đo nội (internal measure) và độ đo ngoại (external measure). Độ đo nội phản ánh khoảng cách trung bình giữa các đối tượng dữ liệu trong cùng nhóm. Ngược lại, độ đo ngoại phản ánh khoảng cách trung bình giữa các nhóm với nhau.  Đánh giá dựa vào sự khác biệt thông tin (Variation of Information – VI): Ký hiệu C* = C1*  C2*  …Ck* là phân hoạch đúng của tập dữ liệu kiểm thử và C = C1  C2  …Ck là phân hoạch được sinh ra bởi thuật toán gom nhóm đề xuất. Giá trị của VI(C, C*) xác định sự khác nhau giữa hai phân hoạch C và C*. Giá trị của VI(C, C*) càng nhỏ thì phân hoạch C càng giống phân hoạch đúng C* nên chất lượng gom nhóm càng tốt. Giá trị của VI(C, C*) bằng 0 khi phân hoạch C giống hoàn toàn phân hoạch đúng C*.  Đánh giá dựa vào mức độ tương ứng của các phân hoạch (r): đo mức độ tương ứng giữa các nhóm được sinh ra bởi thuật toán gom nhóm cần đánh giá và các lớp đã được gán trước trong tập dữ liệu kiểm thử. Chương 2 – Dự báo di chuyển dựa trên khai phá mẫu không gian – thời gian 2.1. Biểu diễn di chuyển trong mạng không dây 2.1.1. Biểu diễn vùng phủ sóng Tương tự như các công trình trước đây, luận án biểu diễn vùng phủ sóng của một hệ thống mạng không dây tế bào dưới dạng một mạng hình lục giác như trong Hình 2.1. Mỗi lục giác là một tế bào được phục vụ bởi một AP. Để mô hình sự di chuyển của MNs xung quanh vùng phủ sóng, luận án sử dụng một đồ thị có hướng không trọng số (unweighted directed graph) G = (V, E). Trong đó, tập đỉnh V là tập 13 định danh của tất cả tế bào trong vùng phủ sóng và tập cạnh E biểu diễn sự lân cận của hai tế bào tương ứng. Hình 2.1. Vùng phủ sóng (a) và đồ thị di chuyển tương ứng (b) 2.1.2. Định nghĩa mẫu di chuyển và luật di chuyển Vì mục tiêu của luận án là phân tích hành vi di chuyển hàng ngày của người dùng di động nên luận án đề xuất chia chu kỳ thời gian một ngày (24 giờ) ra thành n khoảng thời gian [ai, bi] bằng nhau, mỗi thời khoảng [ai, bi] được gán một nhãn thời gian ti duy nhất. Khi đó, mỗi ngày đều có cùng một tập nhãn thời gian T = { t1, t2, … ti, … tn} với tính chất ti < tj khi và chỉ khi i < j, 1 ≤ i, j ≤ n. Ký hiệu c là định danh của tế bào trong vùng phủ sóng mà MN kết nối vào tại thời điểm t, luận án định nghĩa một điểm (point) như sau: Định nghĩa 2.1. Ký hiệu C và T tuần tự là tập định danh của tế bào và tập nhãn thời gian. Cặp có thứ tự p = (c, t), trong đó c  C và t  T, được gọi là một điểm. Ký hiệu P là tập tất cả điểm, P = C × T = {(c, t) | c  C và t  T}. Hai điểm pi = (ci, ti) và pj = (cj, tj) được gọi là bằng nhau nếu và chỉ nếu ci = cj và ti = tj. Điểm pi = (ci, ti) được gọi là điểm trước của điểm pj = (cj, tj) nếu và chỉ nếu ti < tj, và ký hiệu là (ci, ti) < (cj, tj) hoặc pi < pj. Ví dụ: điểm (8, t5) là điểm trước của điểm (2, t7) vì t5 < t7 Định nghĩa 2.2. Một đường đi (trajectory) của thiết bị di động được định nghĩa là một chuỗi có thứ tự hữu hạn các điểm trong không gian C × T, với pj = (cj, tj) sao cho 1 ≤ j ≤ k và hai tế bào của hai điểm liền kề là lân cận nhau trong vùng phủ sóng. Một đường đi gồm k điểm được gọi là một mẫu di chuyển tuần tự (sequential mobility pattern) chiều dài k và được ký hiệu là k-pattern. 14 Chú ý rằng thứ tự tăng dần của các điểm trong đường đi được sắp xếp theo nhãn thời gian ti của các điểm. Định nghĩa 2.3. Một mẫu di chuyển tuần tự B = được gọi là một mẫu di chuyển con (sub-pattern) của một mẫu di chuyển tuần tự A = , với ai và bj là những điểm, ký hiệu B  A, nếu và chỉ nếu tồn tại những số nguyên 1 ≤ i1 < … < im ≤ n sao cho bk = aik, cho tất cả k, với 1 ≤ k ≤ m. Và khi đó, A được gọi là mẫu di chuyển cha (super-pattern) của B. Định nghĩa 2.4. Cho một cơ sở dữ liệu giao tác D = {S1, S2, …, SN} chứa N mẫu di chuyển. Độ phổ biến (support) của mẫu di chuyển S là tỷ lệ phần trăm giữa số giao tác chứa S và tổng số giao tác trong cơ sở dữ liệu giao tác D, nghĩa là: support( S )  Si | S  Si , Si  D N  100 (2.1) Định nghĩa 2.5. Cho một ngưỡng hỗ trợ tối thiểu (minimum support threshold), suppmin, một mẫu di chuyển tuần tự S được định nghĩa là một mẫu di chuyển phổ biến nếu và chỉ nếu S có độ phổ biến thỏa mãn: support(S) ≥ suppmin (2.2) Định nghĩa 2.6. Một luật di chuyển có dạng R: A  B, trong đó, A và B là hai mẫu di chuyển phổ biến và A  B =. Khi đó, A và B lần lượt được gọi là phần đầu và phần đuôi của luật. Vì luật di chuyển R: A  B được sinh từ mẫu di chuyển phổ biến A  B, độ phổ biến của luật di chuyển là độ phổ biến của mẫu di chuyển A  B. Định nghĩa 2.7. Cho một cơ sở dữ liệu giao tác D = {S1, S2, …, SN} chứa N mẫu di chuyển. Độ phổ biến của luật kết hợp R: A  B là tỷ lệ phần trăm giữa số giao tác chứa A  B và tổng số giao tác trong cơ sở dữ liệu giao tác D, nghĩa là: (2.3) support( A  B )  Si | A  B  Si , Si  D N  100  support( A  B ) Định nghĩa 2.8. Cho một luật di chuyển R: A  B, độ tin cậy của luật (confidence value) được định nghĩa bởi công thức: 15 confidence ( R)  support(A  B)  100 support( A) (2.4) 2.2. Dự báo di chuyển dựa trên khai phá mẫu không gian – thời gian 2.2.1. Sinh cơ sở dữ liệu giao tác Để có thể khai phá mẫu di chuyển phổ biến từ dữ liệu di chuyển, trước hết luận án rút trích tất cả mẫu di chuyển có nghĩa từ tập tin nhật ký di chuyển (log file) của cá nhân MN. Mẫu di chuyển có nghĩa là một chuỗi vị trí mà MN lần lượt kết nối vào trong một phiên di chuyển, được gọi là một giao tác hợp lệ (valid transaction). Tập tất cả giao tác hợp lệ theo thứ tự thời gian được gọi là cơ sở dữ liệu giao tác (transactional database). Để khắc phục vấn đề mất kết nối hay thiếu dữ liệu trong lịch sử di chuyển, luận án đề xuất sử dụng ràng buộc thời gian giữa các vị trí kết nối của MN nhằm tạo ra các chuỗi di chuyển có nghĩa. Ràng buộc thời gian giới hạn khoảng thời gian giữa hai vị trí trong một giao tác. Nghĩa là, khi khoảng thời gian giữa hai vị trí kết nối liên tục của MN trong dữ liệu di chuyển của nó vượt quá ngưỡng thời gian tối đa, ký hiệu là gapmax, thì một giao tác hợp lệ sẽ được sinh ra. Ký hiệu tj và tj+1 lần lượt là thời điểm MN kết nối vào 2 vị trí liên tục thì tj+1 - tj ≤ gapmax. 2.2.2. Khai phá mẫu di chuyển không gian-thời gian Luận án đã khảo sát, đánh giá ưu và nhược điểm của một số thuật toán khai phá tập/mẫu tuần tự phổ biến điển hình như Apriori và các biến thể của nó, GSP, SPADE, FP-Growth và PrefixSpan. Nhóm thuật toán dựa trên nguyên lý Apriori duyệt lại CSDL nhiều lần nên thích hợp cho những hệ thống khai phá tương tác (thường xuyên thay đổi độ phổ biến) hoặc khai phá CSDL tăng dần (thường xuyên thêm các giao tác mới). Đồng thời, nhóm thuật toán này cũng được khuyến nghị chỉ nên áp dụng khi các mẫu tuần tự trong CSDL có độ dài ngắn và CSDL có kích thước nhỏ. Trong khi đó, nhóm thuật toán dựa trên phương pháp phát triển mẫu thích hợp cho các CSDL lớn và chuỗi dữ liệu dài. Tuy nhiên, vì chi phí cho việc xây dựng lại không gian tìm kiếm rất cao nên nhóm giải thuật này sẽ không hiệu quả khi áp dụng cho những hệ thống khai phá tương tác hoặc khai phá CSDL tăng dần. 16 Luận án phân tích hành vi di chuyển hàng ngày của con người nên mỗi phiên di chuyển của con người được thực hiện trong một ngày. Do đó, các mẫu di chuyển tuần tự trong CSDL giao tác của luận án có độ dài thường là ngắn. Vì CSDL giao tác trong luận án được xây dựng từ lịch sử di chuyển hàng ngày của tất cả người sử dụng gia nhập vào hệ thống mạng nên CSDL thường xuyên được thêm các giao tác mới. Từ những phân tích trên, nhóm thuật toán dựa trên nguyên lý Apriori tỏ ra thích hợp để khai phá tất cả mẫu di chuyển phổ biến không gian-thời gian từ CSDL giao tác D trong luận án. Tuy nhiên, để có kết quả đánh giá thực nghiệm về hiệu quả sử dụng của các nhóm thuật toán khai phá mẫu tuần tự phổ biến, luận án đề xuất cài đặt cả hai nhóm thuật toán (1) dựa trên nguyên lý Apriori và (2) dựa trên phương pháp phát triển mẫu. Cả hai thuật toán này đều được mở rộng trên cả hai thuộc tính không gian và thời gian nhằm khai phá tất cả mẫu di chuyển phổ biến không gian-thời gian từ cơ sở dữ liệu giao tác D. 2.2.3. Rút trích luật di chuyển theo trọng số thời gian Giả sử S là một mẫu di chuyển phổ biến, tất cả luật di chuyển có thể được sinh ra từ mẫu di chuyển phổ biến S là: A  (S-A) với tất cả A  S và A ≠ . Mỗi luật di chuyển có một độ tin cậy (confidence) được tính theo Định nghĩa 2.7. Tất cả luật di chuyển có độ tin cậy lớn hơn ngưỡng tin cậy tối thiểu confmin sẽ được chọn và được gọi là luật di chuyển phổ biến (frequent mobility rules). Luận án đề xuất mỗi luật ri được gán một giá trị trọng số wi dựa trên thuộc tính thời gian. Trọng số của mỗi luật được tính theo thủ tục sau. Ký hiệu MinDate và MaxDate lần lượt là ngày đầu tiên (first date) và ngày cuối cùng (last date) trong tập tin nhật ký di chuyển của MN. Ký hiệu RuleDate là ngày được xác định thông qua giá trị thuộc tính thời gian của điểm cuối cùng trong phần đuôi của luật. Luận án đề xuất cách tính giá trị trọng số của luật như Công thức (2.5). weight ( R)  RuleDate  MinDate  100 MaxDate  MinDate (2.5) 17 2.2.4. Dự báo di chuyển dựa trên luật di chuyển Luật di chuyển phổ biến được rút trích từ dữ liệu di chuyển của người dùng di động, mô tả hành vi di chuyển thường ngày của họ. Do đó, luật di chuyển phổ biến có thể được sử dụng để tiên đoán sự di chuyển tương lai của người dùng di động. Như phân tích ở trên, những luật di chuyển được rút trích từ tập dữ liệu di chuyển trong quá khứ xa sẽ kém quan trọng hơn những luật di chuyển mới được rút trích từ tập mẫu di chuyển hiện tại. Do đó, những luật di chuyển có thời gian tồn tại càng lâu thì càng ít phản ánh hành vi di chuyển hiện tại của người dùng di động. Theo đó, những luật di chuyển có thời gian tồn tại quá lâu thì cho dù chúng có độ phổ biến và độ tin cậy cao nhưng cũng không được ưu tiên chọn để dự báo vì có khả năng hành vi di chuyển hiện tại của con người đã thay đổi so với trước đây. Để giải quyết vấn đề này, luận án đề xuất tính điểm so khớp luật di chuyển với đường đi hiện tại cần dự báo dựa trên độ phổ biến, độ tin cậy và trọng số thời gian của luật. Chương 3 – Dự báo dựa trên nhóm hành vi di chuyển 3.1. Độ đo tương tự cho mẫu di chuyển Luận án đề xuất độ đo tương tự STPS (Spatial and Temporal Pattern Similarity) dựa trên hai nhân tố sau đây:  Số tế bào chung của hai mẫu di chuyển: hai mẫu di chuyển có càng nhiều tế bào chung thì chúng càng giống nhau về không gian.  Thời điểm kết nối vào các tế bào chung của hai mẫu di chuyển: Hai mẫu di chuyển có thời điểm kết nối vào cùng tế bào càng gần nhau thì chúng càng giống nhau về thời gian. Định nghĩa 3.1. Cho P là một tập mẫu di chuyển, một hàm số f: P  P  [0,1], ánh xạ từ một cặp mẫu di chuyển sang một số thực trong đoạn 0 và 1, được gọi là một độ đo tương tự trên P nếu f thỏa các tính chất sau: (i) Tính phản xạ: với mọi Pi  P f(Pi, Pi) = 0; (ii) Tính đối xứng: với mọi Pi,Pj  P f(Pi, Pj) = f(Pj, Pi); Dựa vào các khái niệm về độ đo tương tự được trình bày trong Phần 1.2.1, độ đo tương tự này là một nửa mêtric hay bán mêtric (semi-metric) 18 Độ đo tương tự theo không gian Định nghĩa 3.2. Ký hiệu g: P  P  R là một hàm số xác định số tế bào có trong mẫu Pa nhưng không có trong mẫu Pb. Theo đó, g được biểu diễn bởi công thức sau g ( Pa , Pb )  card ({cai | cai  Pa , cai  Pb }) (3.1) Mệnh đề 3.1. (i) 0  g(Pa, Pb)  L(Pa), với L(Pa) là chiều dài của mẫu di chuyển Pa; (ii) g(Pa, Pa) = 0, với mọi Pa  P; (iii) g(Pa, Pb) = L(Pa), nếu Pa và Pb không có chung bất kỳ một tế bào nào. Định nghĩa 3.3. dspace(Pa, Pb) giữa hai mẫu di chuyển Pa và Pb được định nghĩa như sau: d space( Pa , Pb )  g ( Pa , Pb )  g ( Pb , Pa ) L( Pa )  L( Pb ) (3.2) Mệnh đề 3.2. dspace(Pb, Pb) là một độ đo tương tự và được gọi là độ tương tự theo không gian. Độ đo tương tự theo thời gian Định nghĩa 3.4. Giả sử Pa = <(ca1, ta1), …, (can, tan)> và Pb = <(cb1, tb1), …, (cbm, tbm)> là hai mẫu di chuyển, với cai, cbj  V và tai, tbj  T với mọi i, j. Nếu hai mẫu Pa và Pb có tế bào chung thì dtime(Pa, Pb) giữa hai mẫu di chuyển Pa và Pb được tính bởi công thức sau: d time ( Pa , Pb )  tai  tbj 1 n ,m với cai = cbj  k i 1, j 1 max( tai , tbj ) (3.3) với k là số tế bào chung của Pa và Pb. Mệnh đề 3.3. dtime(Pb, Pb) là một độ đo tương tự và được gọi là độ đo tương tự theo thời gian. Độ đo tương tự kết hợp không gian và thời gian Định nghĩa 3.5. Một hàm u: [0,1]  [0,1]  [0,1] được gọi là một hàm kết hợp, ký hiệu là com-function, nếu và chỉ nếu nó thỏa mãn những điều kiện sau: (1) min(s, h)  u(s, h)  max(s, h); (2) u(s1, h)  u(s2, h) nếu s1  s2; 19 (3) u(s, h1)  u(s, h2) nếu h1  h2. Mệnh đề 3.4. Hàm u: [0,1]  [0,1]  [0,1] được định nghĩa bởi công thức: u(x, y) = wspacex + wtimey với wspace + wtime = 1 (3.4) là một hàm kết hợp. Định nghĩa 3.6. d(Pa, Pb) giữa hai mẫu di chuyển Pa và Pb được định nghĩa bởi công thức sau: d(Pa, Pb) = wspace dspace(Pa, Pb) + wtime dtime(Pa, Pb) với wspace + wtime = 1 (3.5) trong đó, dspace(Pa, Pb) và dtime(Pa, Pb) lần lượt là độ đo tương tự theo không gian và theo thời gian giữa hai mẫu di chuyển Pa và Pb. Mệnh đề 3.5. d(Pa, Pb) là một độ đo tương tự, là một hàm kết hợp và được gọi là độ đo tương tự kết hợp. 3.2. Gom nhóm hành vi di chuyển của thiết bị di động 3.2.1. Thuật toán gom nhóm mẫu di chuyển không gian – thời gian Mục đích của thuật toán gom nhóm là phân hoạch tập mẫu di chuyển thành k nhóm sao cho những mẫu di chuyển trong cùng nhóm giống nhau hơn so với những mẫu ở nhóm khác. Thuật toán gom nhóm mẫu di chuyển SMPC (Similarity Mobility Pattern based Clustering) được đề xuất trong luận án là một sự mở rộng của phương pháp k-means cho dữ liệu định tính (categorical data). Sự mở rộng tập trung vào cải tiến thủ tục khởi tạo nhằm hạn chế tối ưu cục bộ và xây dựng thủ tục cập nhật trung tâm nhóm nhằm tăng độ phân biệt giữa các nhóm thông qua việc gán mẫu vào nhóm gần nhất. Trong thuật toán gom nhóm SMPC, k trung tâm nhóm ban đầu được chọn bởi thủ tục khởi tạo được trình bày trong Phần 3.2.2 thay cho việc khởi tạo một cách ngẫu nhiên như k-means truyền thống. Sau khi chọn giá trị khởi tạo cho k trung tâm nhóm, mỗi mẫu di chuyển trong tập dữ liệu được gán vào một nhóm gần nó nhất theo nghĩa nó giống trung tâm của nhóm đó nhất trong k trung tâm nhóm như được trình bày trong thủ tục ở Phần 3.2.3. Sau khi tất cả mẫu di chuyển trong tập dữ liệu đều được gán vào nhóm tương ứng, trung tâm của mỗi nhóm sẽ phải được cập nhật 20 lại theo thủ tục được trình bày trong Phần 3.2.3. Dựa vào giá trị cập nhật của các trung tâm nhóm, mỗi mẫu di chuyển trong tập dữ liệu cần được gán lại vào nhóm gần nhất. Thủ tục cập nhật trung tâm nhóm và gán lại mẫu vào nhóm gần nhất sẽ được lặp lại cho đến khi không còn mẫu di chuyển nào được gán lại nhóm sau một chu kỳ kiểm tra toàn bộ tập dữ liệu. 3.2.2. Khởi tạo thuật toán gom nhóm mẫu di chuyển dựa trên độ đo tương tự Ký hiệu P = { P1, P2, …, Pn} là tập mẫu di chuyển và k là một số nguyên dương đặc tả số nhóm cần phân hoạch. Ký hiệu ci là trung tâm nhóm khởi tạo thứ i, với 1  i  k và C = {c1, c2, …, cl} là tập l trung tâm nhóm khởi tạo hiện tại, với 1  l  k. Định nghĩa 3.7. Trung tâm nhóm khởi tạo kế tiếp là một mẫu di chuyển Pi được chọn từ tập dữ liệu sao cho giá trị của tổng sau đạt cực đại: l Di   d ( Pi , c j ) (3.6) j 1 trong đó d(Pi, cj) là độ đo tương tự kết hợp giữa mẫu di chuyển Pi và trung tâm nhóm khởi tạo cj như trong Định nghĩa 3.6. Thủ tục khởi tạo được phác họa như sau: 1. Trung tâm nhóm khởi tạo thứ nhất c1 được chọn một cách ngẫu nhiên từ tập dữ liệu; 2. Với mỗi mẫu Pi trong tập dữ liệu, Pi  c1, 1  i  n, tính độ tương tự d(Pi, c1) giữa mẫu Pi và trung tâm nhóm khởi tạo c1; 3. Trung tâm nhóm khởi tạo thứ hai c2 là một mẫu di chuyển Pi được chọn từ tập dữ liệu sao cho d(Pi, c1) đạt giá trị lớn nhất. 4. Ký hiệu l là số trung tâm nhóm khởi tạo hiện tại. Với mỗi mẫu Pi trong tập dữ liệu, Pi  C, tính tổng độ tương tự Di giữa Pi và l trung tâm nhóm khởi tạo hiện tại trong C theo công thức trong Định nghĩa 3.7. Trung tâm nhóm khởi tạo kế tiếp cl+1 là mẫu Pi sao cho Di đạt giá trị lớn nhất. 5. Nếu l < k thì gán C = C  cl+1, l = l+1 và lặp lại bước 4. Ngược lại thì dừng.