 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：43 、訪客IP：3.144.8.68
姓名 黃景詮(Ching-Chuan Huang) 查詢紙本館藏 畢業系所 資訊工程學系 論文名稱 網路虛擬環境化身路徑群組
(Avatar Path Clustering for Networked Virtual Environments)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 近年來隨著網路與3D繪圖技術的進步，網路虛擬環境(Networked Virtual Environment, NVE)已成為熱門的研究之一，其中應用最廣的就是多人線上遊戲(Massively Multi-user Online Game, MMOG)，例如第二人生(Second Life, SL)與魔獸世界(World of Warcraft, WoW)。網路虛擬環境的使用者以虛擬化身(avatar)的方式在虛擬環境中遊覽(navigate)並且彼此互動。由於網路虛擬環境上部分使用者的興趣或習慣相近，使得虛擬環境中的化身會有相似的行為特性，進而在網路虛擬環境中產生相近的移動路徑。例如在Second Life中，各種商店總會吸引各式各樣的使用者(玩家)聚集，部分的玩家可能對相同的商店感興趣因而會前往共同的目的地，促使玩家之間會有相近的移動路徑。
本研究提出兩個網路虛擬環境上化身路徑群組(Path Clustering) 的演算法，分別是Average Distance of Corresponding Points-Density Clustering(ADOCP-DC)和Longest Common Subsequence-Density Clustering(LCSS-DC)。其中ADOCP-DC演算法以ADOCP方法計算出路徑的相似度，然後以密度群組方法歸納網路虛擬環境中的路徑，以尋求行為模式相近的使用者或社群；而LCSS-DC演算法是以LCSS方法計算出路徑的相似度，然後同樣以密度群組方法歸納網路虛擬環境中的路徑，以得到數個相似度高且數量多的路徑群組。各個路徑群組中可以找出一條與最多路徑相似的代表路徑(Representative Path)，可以協助改進以下研究：同儕式網路虛擬環境(P2P-NVE)設計、使用者的狀態管理(State Management)、使用者的移動模組探討(Behavior Model)、叢集式伺服器的負擔平衡(Load Balance on Server Cluster)以及虛擬世界的切割(Partitioning on NVE)等。另外亦可提供遊戲開發者進行虛擬環境中場景佈置與改善的參考，以及在虛擬世界中讓廣告看板宣傳效益最大化的調整。本論文以Second Life虛擬世界裡化身的位置追蹤資料(trace data)來作為ADOCP-DC和LCSS-DC的模擬實驗資料來源，並展示如何在不同實驗設定下，藉由調整演算法參數來達成較佳的路徑群組品質。
摘要(英) With the increase of network bandwidth and the advance of 3D graphics technology, networked virtual environments (NVEs) have become one of the most popular research topics. Massively multiplayer online games (MMOGs), like Second Life and World of Warcraft (WoW), are well known examples of NVEs. Because users’ interests or habits may be similar, avatars, the representative of users on the NVE, may have similar behavior patterns, which leads to similar paths on the NVE. For instance, different kinds of virtual shops in Second Life attract a variety of users to drop by, and thus users with similar interests usually head toward common destinations and produce similar paths.
This research proposes two avatar path clustering algorithms for NVEs, namely, Average Distance of Corresponding Points-Density Clustering (ADOCP-DC) and Longest Common Subsequence-Density Clustering (LCSS-DC). In ADOCP-DC algorithm, the path similarities are computed with the ADOCP mechanism first, and then paths are clustered with Density-Based Clustering to find users with similar paths. LCSS-DC algorithm uses the LCSS mechanism to compute the path similarities and then clusters paths with Density-Based Clustering. Both algorithms will produce a Representative Path (RP) for each cluster of paths. They can be applied to several research areas like peer-to-peer networked virtual environments (P2P-NVEs), avatar state management, avatar behavior analysis and server load balancing. Game developer can also apply the algorithms to find out popular paths for improving the game design. We take Second Life user trace data as input of the algorithms to demonstrate the algorithms’ execution. We also show how to adjust algorithm parameters to obtain high-quality path clustering.
關鍵字(中) ★ LCSS
★ 密度群組
★ 網路虛擬環境
★ Second Life
★ 路徑群組關鍵字(英) ★ Second Life
★ Path Clustering
★ LCSS
★ Density-Based Clustering
★ Network Virtual Environment論文目次 中文摘要..................................................I
Abstract................................................III
目錄..................................................... V
圖目錄.................................................. VI
表目錄................................................. VII
一、緒論..................................................1
二、相關研究 .............................................7
2-1 NVE路徑資料蒐集與分析 .............................7
2-2 路徑相似度.........................................9
2-3 路徑群組..........................................10
三、網路虛擬環境化身路徑群組 ............................14
3-1. 路徑切割.........................................15
3-2. ADOCP-DC ........................................16
3-3. LCSS-DC..........................................19
四、實驗驗證與效能分析...................................23
4.1效能評估...........................................24
4.2 ADOCP-DC的參數設定................................26
4.3 LCSS-DC的參數設定.................................28
五、結論.................................................34
參考文獻.................................................36
參考文獻 [1] D. C. Miller and J. A. Thorpe, "SIMNET: the advent of simulator networking," Proceedings of the Ieee, vol. 83, pp. 1114–1123, 1995.
[2] "Secnod Life http://secondlife.com/."
[3] "Wold of WarCraft http://www.worldofwarcraft.com/index.xml."
[4] Z.Fu, W.Hu, T.Tan, "Similarity Based Vehicle Trajectory Clustering and Anomaly Detection," in Proc. ICIP’05, vol 2, pp. 602–605, Sept. 2005.
[5] M.Vlachos, G.Kollios, D.Gunopulos, "Discovering Similar Multidimensional Trajectories," in Proc. 18th Intl. Conf. on Data Engineering (ICDE’02), pp.673–685, 2002.
[6] R. Ng and J. Han. "Efficient and Effective Clustering Method for Spatial Data Mining," in Proc. of the 20th VLDB Conference, pp. 144–155, 1994
[7] L. Kaufman and P. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis: Wiley, 1990.
[8] S. A. Tan, W. Lau, and A. Loh, "Networked game mobility model for first-person-shooter games," in Proc. of NetGames’05, pp. 1–9, 2005.
[9] A. Bharambe, J. Pang, and S. Seshan, "Colyseus: a distributed architecture for online multiplayer games," in Proc. of NSDI ’06, pp. 12–12, 2006.
[10] D. Pittman and C. GauthierDickey, "A measurement study of virtual populations in massively multiplayer online games," in Proc. of NetGames ’07, pp. 25–30, 2007.
[11] H. Liang, I. Tay, M. F. Neo, W. T. Ooi, and M. Motani, "Avatar mobility in networkedvirtual environments: Measurements, analysis, and implications," CoRR, abs/0807. 2328, 2008.
[12] J. Han and M. Kamber, Data Mining: Concepts and Techniques: Morgan Kaufmann, 2000.
[13] T. Zhang, R. Ramakrishnan, and M. Livny, "BIRCH: An Efficient Data Clustering Method for Very Large Databases," In Proc. of the ACM SIGMOD Conference on Management of Data pp. 103–114, 1996.
[14] J. MacQueen, "Some methods for classification and analysis of multivariate observations, " in Proc. of 5th Berkeley Symp., vol. 1, pp. 281–297, 1967.
[15] Z. Huang, "Extensions to the K-means algorithm for clustering large data sets with categorical values," Data Mining Knowl. Discov., vol. 2, pp. 283–304, 1998.
[16] M. Ester, H.P. Kriegel and X. Xu, "Knowledge Discovery in Large Spatial Databases: Focusing Techniques for Efficient Class Identification," in Proc. of the 4th International Symposium on Large Spatial Databases (SSD 95), Portland, Maine, August 6-9, 1995, in: Lecture Notes in Computer Science, Vol. 951, Springer, pp.67–82., 1995.
[17] P.S Bradley, U. Fayyad, and C. Reina, "Scaling clustering algorithms to large databases," in Proc. of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD 98), pp. 9–15, 1998.
[18] M. Ester, H.P. Kriegel and X. Xu, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise," in Proc. of the Second International Conference on Knowledge Discovery and Data Mining (KDD 96), pp.226–231, 1996.
[19] M. Ankerst, M. Breunig, H.P. Kriegel, and J. Sander. "Optics: Ordering points to identify the clustering structure," in Proc. of ACM SIGMOD International Conference on Management of Data, pp.49–60, June 1999.
[20] J. Lee, J. Han, and K. Whang, "Trajectory Clustering: A Partition-and-Group Framework," in Proc. of SIGMOD, pp.593–604, 2007.
[21] C. Piciarelli and G. L. Foresti, "On-line trajectory clustering for anomalous events detection, " Pattern Recognit. Lett., vol. 27, no. 15, pp. 1835–1842, Nov. 2006.
指導教授 江振瑞(Jehn-Ruey Jiang) 審核日期 2010-5-13 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit