臺灣博碩士論文加值系統

本研究提出一個以社群互動為基礎的共乘推薦模式，希望透過以人際關係權
重高低作為信任因子以促使共乘行為，並且配合Web GIS 與空間資料庫的應用，
分析使用者路線規劃上的相似路徑，改善共乘系統的可用性與易用性。
在人際關係權重部份，我們運用階層式語意關係網路的概念做為屬性權重的
計算依據，同時考慮線上社群的互動頻率以及內在感受的關係因子，將人際關係權
重值量化，或透過共同朋友的推薦，以產生新的關係連結並提升信任因子；在共乘
系統部份，我們進行路徑規畫的空間資訊儲存，並且在不失路徑規劃的特性下，將
簡化路徑資料的描述；再以擴展地理上的空間範圍，找尋設定區域中擁有相似路徑
的使用者。
經由本研究計算而得的人際關係權重，在關係網格與關聯係數的計算上可以
得到合理的驗證；最後，我們將人際權重值與相似的共乘旅程，透過天際線運算
(Skyline Operation)，以推薦感興趣的共乘對象，提升使用者的信任程度進而促成更
多的共乘行為，創造出合乎使用者經驗與信任關係之共乘核心價值。

In this study, we propose a carpooling recommendation model based on the interpersonal
relationships derived from social networks. We believe the interpersonal trust is a
critical factor to inspire the ride behavior in a carpooling recommendation system. By
using the concept of hierarchical semantic network for calculating the attribute weights
based on the frequency of interaction in online social networks, interpersonal relationships
can be reasonably evaluated.
The other parts, we analyze similar path using Web GIS and spatial database to
search whose travel similar with the others. Using these path from users provided travel,
we will store and reduce it in spatial database. Then, buffing the target path and key point
from the others path, and then pick out the key point which have intersection with the
target path. Thus, our system will output the similar travel for carpool users.
By taking into account recommendations from common friends, new relationships
can be established, and the degree of trust can be promoted, which implies the trust
weights of interpersonal relationships can be rationally verified. Finally, our approach
collects the similar itineraries and generates the recommendation result by using the skyline
operation. Our model enhances the degree of trust for users and in turn encourages
more ride behaviors, which creates a core value of carpooling in terms of the user experience
and trust relationships.

摘要 ...................................................................................................................................i
ABSTRACT .......................................................................................................................... ii
誌謝 ................................................................................................................................. iii
目錄 ................................................................................................................................. iv
圖目錄 ............................................................................................................................. vii
表目錄 .............................................................................................................................. xi
壹、 緒論 ...................................................................................................................... 1
一、 研究背景 .......................................................................................................... 1
二、 研究動機 .......................................................................................................... 6
三、 研究目的 .......................................................................................................... 7
四、 研究流程 .......................................................................................................... 8
五、 論文結構 .......................................................................................................... 9
貳、相關研究與文獻探討 ............................................................................................ 10
一、社群網路關係 .................................................................................................... 10
二、分層語意相似性計算 ......................................................................................... 11
（一） 計算路徑長度 ........................................................................................ 12
（二） 衡量深度影響 (Scaling Depth Effect) .................................................. 13
（三） 考慮局部語意密度 (Local Semantic Density) ..................................... 13
（四） 獲取資訊來源 ........................................................................................ 14
三、關係網格 (Relation Grid) .................................................................................. 15
（一） 關係網格元素 ........................................................................................ 15
（二） 路徑關聯係數 (Path Correlation Factor) .............................................. 16
四、地理資訊系統 .................................................................................................... 16
（一） 網頁地理資訊系統 (Web Geography Information System) ................. 16
（二） 各式地理標記語言 ................................................................................ 16
（三） 地理資訊擷取架構 ................................................................................ 20
（四） 地理資訊呈現架構 ................................................................................ 21
五、地圖方磚系統 (Maps Tile System) ................................................................... 21
（一） LOD (Levels of Detail) .......................................................................... 21

（二） 磚瓦座標 (Tile Coordinates) ................................................................. 21
（三） 四鍵值 (Quad Keys) .............................................................................. 22
六、 相似路徑查詢 ................................................................................................ 23
（一） 簡化軌跡 ................................................................................................ 24
（二） 轉換為Quad Key ................................................................................... 24
（三） 找出最長的共同前置子字串 (Common Prefix) .................................. 24
（四） 建置Prefix Tree ..................................................................................... 25
（五） 查詢相似路徑 ........................................................................................ 25
（六） 排名路徑相似程度 ................................................................................ 26
七、聲望系統 ............................................................................................................ 26
（一） 聲望網路的建構 (Reputation Network Architectures) ......................... 27
（二） 聲望計算引擊 (Reputation Computation Engines) .............................. 28
八、天際線運算 (Skyline Operation) ....................................................................... 29
參、研究架構與方法 .................................................................................................... 31
一、研究架構 ............................................................................................................ 31
二、人際關係模型 .................................................................................................... 31
（一） 屬性權重計算 ........................................................................................ 32
（二） 互動權重計算 ........................................................................................ 33
（四） 人際關係權重 (Relationship Weight) 與正規化 ................................. 35
三、路徑處理模型 .................................................................................................... 35
（一） 輸入資料處理 ........................................................................................ 37
（二） 路徑處理部份 ........................................................................................ 39
四、天際線查詢 ........................................................................................................ 41
五、地理資訊格式轉換 ............................................................................................ 43
肆、實驗結果與討論 .................................................................................................... 45
一、 實驗資料描述 ................................................................................................ 45
（一） 人際關係權重資料 ................................................................................ 45
（二） 路徑資料描述 ........................................................................................ 46
二、人際權重計算實驗 ............................................................................................ 47
（一） 屬性權重計算部份 ................................................................................ 47
-vi-
（二） 互動權重計算部份 ................................................................................ 49
（三） 人際關係權重計算與正規化部份 ........................................................ 49
（四） 自評權重計算 ........................................................................................ 50
三、關係網格 ............................................................................................................ 51
（一） 屬性權重考量 ........................................................................................ 51
（二） 人際關係權重考量 ................................................................................ 52
（三） 人際間推薦關係 .................................................................................... 52
四、權重族群 ............................................................................................................ 53
五、路徑處理實驗 .................................................................................................... 54
（一） 路徑簡化實作 ........................................................................................ 54
（二） 分割點位實作 ........................................................................................ 55
（三） 擴展空間查詢 ........................................................................................ 56
（四） 相似路徑分析 ........................................................................................ 57
（五） 里程計算 ................................................................................................ 58
（六） 路徑分析結果 ........................................................................................ 59
六、天際線查詢實驗 ................................................................................................ 59
伍、結論與未來研究 .................................................................................................... 61
一、結論 .................................................................................................................... 61
二、未來研究 ............................................................................................................ 62
參考文獻 ........................................................................................................................ 68
附錄一：A~G 的屬性權重計算 ................................................................................... 68
附錄二：互動值計算結果 ............................................................................................ 69
附錄三：自評權重計算 ................................................................................................ 72
附錄四：經緯度呈現格式轉換：WKT 轉KML ........................................................ 73
附錄五：格式轉換—WKT LINSTRING 轉WKT POINT ......................................... 73
附錄七：輸出為KML 格式 ......................................................................................... 75

[1] Aitchison, A. (2009). Beginning Spatial with SQL Server 2008: Apress.
[2] Amey, A. (2011). “Real-Time” Ridesharing–The Opportunities and Challenges of
Utilizing Mobile Phone Technology to Improve Rideshare Services. The Ohio State
University.
[3] Bandara, H., & Dias, D. (2009). A Multi-Agent system for dynamic ride sharing.
Paper presented at the Industrial and Information Systems (ICIIS), 2009
International Conference on.
[4] Bergroth, L., Hakonen, H., & Raita, T. (2000). A survey of longest common
subsequence algorithms. Paper presented at the String Processing and Information
Retrieval, 2000. SPIRE 2000. Proceedings. Seventh International Symposium on.
[5] Borzsony, S., Kossmann, D., & Stocker, K. (2001). The skyline operator. Paper
presented at the Data Engineering, 2001. Proceedings. 17th International
Conference on.
[6] Cho, E.-J. (2011). Interpersonal interaction for pleasurable service experience.
Paper presented at the Proceedings of the 2011 Conference on Designing
Pleasurable Products and Interfaces.
[7] Douglas, D. H., & Peucker, T. K. (1973). Algorithms for the reduction of the
number of points required to represent a digitized line or its caricature.
Cartographica: The International Journal for Geographic Information and
Geovisualization, 10(2), 112-122.
[8] Gambetta, D. (2000). Can we trust trust. Trust: Making and breaking cooperative
relations, 2000, 213-237.
[9] Hochheiser, H., & Shneiderman, B. (2010). From bowling alone to tweeting
together: technology-mediated social participation. interactions, 17(2), 64-67.
[10] Josang, A., Ismail, R., & Boyd, C. (2007). A survey of trust and reputation systems
for online service provision. Decision support systems, 43(2), 618-644.
[11] Jsang, A., & Ismail, R. (2002). The beta reputation system. Paper presented at the
Proceedings of the 15th bled electronic commerce conference.
-65-
[12] Kucera, H., & Francis, W. N. (1982). Frequency analysis of English usage:
Lexicon and grammar: Boston: Houghton Mifflin.
[13] Lee, D., & Liang, S. H. (2011). Crowd-sourced carpool recommendation based on
simple and efficient trajectory grouping. Paper presented at the Proceedings of the
4th ACM SIGSPATIAL International Workshop on Computational Transportation
Science.
[14] Levofsky, A., & Greenberg, A. (2001). Organized Dynamic Ridesharing: The
potential Environmental Benefits and the Opportunity for Advancing the Concept.
Retrieved January, 11, 2009.
[15] Li, Y., Bandar, Z. A., & McLean, D. (2003). An approach for measuring semantic
similarity between words using multiple information sources. Knowledge and Data
Engineering, IEEE Transactions on, 15(4), 871-882.
[16] McKnight, D. H., & Chervany, N. L. (1996). The meanings of trust.
[17] Miller, G. A. (1995). WordNet: a lexical database for English. Communications of
the ACM, 38(11), 39-41.
[18] Mui, L., Mohtashemi, M., & Ang, C. (2001). A probabilistic rating framework for
pervasive computing environments. Paper presented at the Proceedings of the MIT
Student Oxygen Workshop (SOW’2001).
[19] Mui, L., Mohtashemi, M., Ang, C., Szolovits, P., & Halberstadt, A. (2001). Ratings
in distributed systems: A bayesian approach. Paper presented at the Proceedings of
the Workshop on Information Technologies and Systems (WITS).
[20] Mui, L., Mohtashemi, M., & Halberstadt, A. (2002). A computational model of
trust and reputation. Paper presented at the System Sciences, 2002. HICSS.
Proceedings of the 35th Annual Hawaii International Conference on.
[21] Mukherjee, D., Banerjee, S., & Misra, P. (2012). Ad-hoc ride sharing application
using continuous SPARQL queries. Paper presented at the Proceedings of the 21st
international conference companion on World Wide Web.
[22] Preece, J. (2001). Sociability and usability in online communities: determining and
measuring success. Behaviour & Information Technology, 20(5), 347-356.
-66-
[23] Rada, R., Mili, H., Bicknell, E., & Blettner, M. (1989). Development and
application of a metric on semantic nets. Systems, Man and Cybernetics, IEEE
Transactions on, 19(1), 17-30.
[24] Resnick, P., & Zeckhauser, R. (2002). Trust among strangers in Internet
transactions: Empirical analysis of eBay''s reputation system. Advances in applied
microeconomics, 11, 127-157.
[25] Resnik, P. (1999). Semantic similarity in a taxonomy: An information-based
measure and its application to problems of ambiguity in natural language. J.
Artificial Intelligence Research, 11, 95-130.
[26] Schneider, J., Kortuem, G., Jager, J., Fickas, S., & Segall, Z. (2000). Disseminating
trust information in wearable communities. Personal Technologies, 4(4), 245-248.
[27] Schwartz, J. (2009). Bing maps tile system. Microsoft Developer network
Available: http://msdn. microsoft. com/en-us/library/bb259689. aspx.
[28] Shao, J., & Greenhalgh, C. (2010). DC2S: a dynamic car sharing system. Paper
presented at the Proceedings of the 2nd ACM SIGSPATIAL International
Workshop on Location Based Social Networks.
[29] Shepard, R. N. (1987). Toward a universal law of generalization for psychological
science. Science, 237(4820), 1317-1323.
[30] Shneiderman, B. (2000). Designing trust into online experiences. Communications
of the ACM, 43(12), 57-59.
[31] Song, J., Liu, W., & Chen, S. (2005). Relation Grid: A Social Relationship Network
Model. Paper presented at the Semantics, Knowledge and Grid, 2005. SKG''05.
First International Conference on.
[32] Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and
applications (Vol. 8): Cambridge university press.
[33] Whitby, A., Josang, A., & Indulska, J. (2005). Filtering out unfair ratings in
bayesian reputation systems.
[34] Xiang, R., Neville, J., & Rogati, M. (2010). Modeling relationship strength in
online social networks. Paper presented at the Proceedings of the 19th international
conference on World wide web.
-67-
[35] Zack, M. H. (2000). Researching organizational systems using social network
analysis. Paper presented at the System Sciences, 2000. Proceedings of the 33rd
Annual Hawaii International Conference on.
[36] 陳怡靜, 胡學誠, & 徐牧群. (2010). 共乘媒合網站使用行為之結構化模式分
析. 資訊管理展望, 12(2), 148-175.
[37] 顏鴻祥. (2009). 影響小汽車共乘行為因子之研究—以新竹市地區為例. 交通
大學運輸科技與管理學系學位論文(2009 年), 1-89.