交通大學資訊科學與工程研究所學位論文
國立交通大學,正常發行
選擇卷期
- 學位論文
本論文中，我們提出了一個Fuzzy AdaBoost.MH 演算法，而且將此Fuzzy AdaBoost.MH 方法運用在文件分類上。Boosting 的主要觀念為利用許多weak hypotheses，透過Boosting 架構得到這些weak hypothesis 權重，最後將這些 weak hypotheses 予以合併，形成一個高準確度的強分類法。我們使用fuzzy rule 作為weak hypothesis，利用decision stump rule 為基礎的方法來當作我們判 別的依據，而每一個fuzzy rule 則是以文件中的term 為依據。在文件特徵表示 法中，每一個n-gram term 常作為文件最基本的特徵;然而每一文件所包含的 n-gram 數目常會是一個巨大的數量，因此在系統的設計中，我們使用term 出現 的頻率來當作term 篩選的方法，並且將通過篩選的term 放入我們的rule pool 中。每一回合，Fuzzy AdaBoost.HM 從rule pool 中挑選出最好的fuzzy rule， 所有fuzzy rule 的集合則是系統分類的依據。 同時，我們提出了一個Fuzzy Number 的表示法，來表示每一條fuzzy rule 的信心度。這些fuzzy rule 的信心度訊息是我們做為推論分類結果的依據。當 訓練的過程結束之後，我們可以經由程度轉化的過程推論我們最後的模糊化分類 結果。本論文中也使用了三種文章集進行實驗，而在實驗的數據中，Fuzzy AdaBoost.MH 皆能有不錯的分類結果。
- 學位論文
近年來越來越多人關注如何透過人體區域慣性感測器來感測人體的動作，並將其應用於計算物理電子遊戲中。當計算物理電子遊戲越來越普及後，探討如何增加與改善計算物理電子遊戲的物理輸入（例如：慣性感測器）已經成為一個趨勢。基於這樣的趨勢，我們開發一個部屬於人體上之人體區域慣性感測網路來感測人體的姿勢及多螢幕的計算物理電子遊戲，讓玩家可以更真實的體驗遊戲。我們設計一套多螢幕遊戲引擎。其中包含人體區域慣性感測網路平台，計算物理遊戲控制器及一組遊戲引擎。我們的遊戲可以讓玩家與虛擬物件互動。 人體追蹤系統是基於加速度計。而其中一個基本的議題為，不管人體是否在移動，重力加速度的方向是否可以準確地得到。假設一個人體的剛體上部屬多個加速度感測器，近期的研究透過資料融合的法來預測該剛體上的重力加速度方向。然而，如何將加速度感測器部屬在最佳的位置來減少預測誤差仍然是一個開放問題。在這篇論文中，我們將部屬最佳化的問題公式化，展示部屬方式的方針及兩種部署策略virtual-force-based (VF-based) method 及 Metropolis-based。
- 學位論文
隨著行動裝置的普及，我們可以由多種的設備及來源收集使用者的軌跡資 料。由於這些軌跡資料中含有使用者的移動資訊，因此由這些資料中可以探勘使 用者的移動行為，此即為本篇論文中所提及之軌跡模式。這些模式在開發新的應 用或是增加既有的位置感知應用上都極具價值。在本篇論文中，我們提出了一連 串有關於軌跡模式探勘相關之演算法。我們首先提出如何大規模地收集使用者的 軌跡資料。緊接著，我們提出兩個探勘軌跡模式的演算法。最後，我們利用使用 者的軌跡模式來判斷使用者間的隱性社群關係。 在本篇論文的第一個主題，我們研究如何在由車輛所構成之感測網路中進行 大規模收集軌跡資料的方式。我們提出了一個架構MDC 來降低資料傳輸量以及 車輛的回報數目。在MDC 中，車輛利用模型來代表其感測到之讀數，並且利用 匯集之方式使得有相類似模型的車輛只需回傳一份至伺服器，因此可以在收集軌 跡資料時的資料傳輸量。 在本篇論文的第二個主題中，我們利用迴歸的方式自通聯記錄中探勘使用者 的軌跡模式。由於通聯記錄只能夠反應使用者部份的行為，因此在本主題中，我 們主要利用迴歸的方式自通聯記錄中復原使用者的軌跡模式。首先，我們先粹取 出具有相同移動行為的通聯記錄，並將具有時間空間相關性的通聯記錄群聚起 來。最後，使用者的移動模式便可以用數條迴歸曲線表示。 在本篇論文的第三個主題中，我們提出了利用軌跡中的線索(Clue) 探勘軌跡 模式的演算法。在實際的軌跡中，有許多因素會造成其無法完整表達使用者的移 動路徑。但是，縱使這些軌跡只能表達使用者部份的移動行為，但是我們依然可 利用這些軌跡所隱含的資訊來進行使用者移動行為之探勘。因此，我們首先提出 一利用兩軌跡中所含線索的多寡來衡量兩個軌跡相似度的方式，並利用這個相似 度將具有相同移動行為的軌跡群聚起來，最後再將每一群中的軌跡之時間空間資 訊匯集，推導出使用者的移動模式。 最後，我們利用使用者的軌跡模式來判斷使用者的隱性社群關係。我們可以 觀察出，有相同移動行為的使用者極有可能在位置感知服務上或是現實生活上有 所互動。因此，在這個主題中我們將判斷並比較使用者的軌跡模式，並將相同軌 跡模式的使用者視為是一社群。首先，我們先將使用者的軌跡模式建成一個樹狀 結構。利用Editing distance 的概念，我們設計出比較使用者軌跡模式的距離函數。利用此距離函數，我們便可以推得出使用者的社群關係。
- 學位論文
令n為正整數m與λ的乘積。一個長度為n、最小距離為d的頻率排列碼(frequency permutation array，簡稱FPA)是一個包含若干個由m個符號各重複出現λ次所形成的排列，並且其中相異的兩個排列的距離至少為d。FPA是排列碼(permutation array，簡稱PA)的一般化，PA即是FPA取λ=1時的特例。目前PA已有許多領域的應用，諸如電力線通訊、快閃記憶體資料儲存以及密碼學。FPA具有比PA更大的設計彈性，因此在各方面應用上均有較PA更高的潛力。 在本篇論文中，吾人透過估計特定半徑內的頻率排列個數，證明了在柴比雪夫距離(Chebyshev distance)下，FPA元素數量之Sphere-packing類型上界以及Gilbert-Varshamov類型下界。此外，吾人亦提出兩個有效率的演算法，用以正確計算出特定半徑內的頻率排列個數。其中之一能在O((2dλ取dλ)^(2.376)logn)的時間複雜度以及O((2dλ取dλ)^(2))的空間複雜度完成計算。另外一個則僅需O((2dλ取dλ)(dλ+λ取λ)n/λ)的時間與O((2dλ取dλ))的空間資源便能完成。當λ與d均為常數時，這兩個演算法均能有效率的求出特定半徑內的頻率排列個數。 吾人發明數個建造FPA的方法，並藉由此推導出對應的FPA元素數量下界。這些建造的方法中，有些類型的FPA具有高效率的編碼與解碼方式，而其中一個更具有區域可解碼演算法以及列表可解碼演算法。吾人展示了如何在僅讀取λ+1個符號的情況下，解出一個資訊符號，以及針對一個任意給定的排列，如何找出所有特定距離內FPA中的元素。此外，藉由區域可解碼演算法，吾人亦造出一個私密資料取回的安全協定。 吾人透過研究子群碼(subgroup code)的性質，證明了在一般情況下，計算出任一FPA的最小距離是困難的。子群碼是PA的一個特例，其中任兩個元素，在函數合成的運算下，具有封閉性。吾人證明，在柴比雪夫距離下，計算子群碼的最小距離，等價於計算其中非(non-identity permutation)之最小權重。更進一步的，吾人證明了後者係為一NP-complete問題，以及對任一常數ε，逼近子群碼之最小距離至2-ε的倍率，亦為NP-hard。
- 學位論文
隨著網路技術的進步，人們對於網路的依賴程度也與日俱增，對網路服務提供業者來說，如何提供一個具有高可用度的網路環境，讓使用者在進行網路存取時不會感覺有網路中斷的情形發生，是一個很重要並且亟待解決的問題。在本論文中，我們利用連續時間馬可夫鏈推導得到一個可用度方程式，根據此方程式，當路由器要達到電信服務等級時，網路服務提供業者只需要提供主要路由器個數(M)、路由器錯誤率(λ)、路由器修復率(μ)以及路由器錯誤偵測與回復率(δ)這四個參數，本方程式就可以計算並且告知需要配置的備用路由器數量(N)。根據數值分析的結果，我們發現錯誤偵測與回復率是用來減少建置備用路由器數量最主要的參數，當錯誤偵測與回復率愈大，備用路由器的需求數量將會減少。 當備用路由器接手封包轉送的工作時，備用路由器會重新與鄰居路由器進行網路連結資訊交換，用以重新建立網路拓樸表，此一動作將會造成封包轉送服務中斷。為了能夠減少網路服務中斷的時間，使得錯誤偵測與回復率能夠增加，我們利用了完整狀態回復(Stateful backup)技術，主要的技術為，當主要路由器在運作時，就會將其網路連結狀態資料庫同步至備用路由器，如此，當備用路由器進行接手封包轉送工作時，備用路由器就可以根據先前收到的網路連結資料庫立刻建立網路拓樸，並且得到路由路徑表，此時，備用路由器便可以立刻上線運作，而不需要再向其他鄰居路由器索取網路連結資料，如此將可以有效地減少備用路由器接手封包轉送的中斷時間。 為了能夠讓主要路由器同步網路連結資料庫至備用路由器，我們參考並修改OpenAIS系統，提出了一套高可用度管理中介軟體(HAM middleware)，此中介軟體可以有效地減少備用路由器接手封包轉送時的網路中斷時間，以達到增加錯誤偵測與回復率之目的。 我們將此高可靠度管理中介軟體安裝於個人電腦(PC)的機器上，並實際進行數值量測，以OSPF為例，根據實驗結果得知，當備用路由器進行換手時，其網路中斷時間將可以比Cisco-ASR 1000、Juniper MX系列路由器與VRRP路由器減少約6%、37.3%與98.6%。 此外，我們也將此高可用度管理中介軟體安裝於ATCA的機器上，ATCA是一個可以提供工業標準模組化架構的平台，可以提供我們一個高效能、靈活調整與可靠的路由器設計。假設路由器的錯誤率與修復率分別為7年與4小時，當發生軟體類型的錯誤時，其備用路由器接手封包轉送工作的網路中斷時間為217 ms ，而當發生硬體類型的錯誤時，其中斷時間為1066 ms。也就是說，架設於ATCA的高可用度路由器的可用度為99.99999905%與99.99999867%，皆能夠達到電信等級可用度的標準。 根據以上我們可以得知，我們所提的高可用度路由器相較於商用的路由器而言，因為我們所提的路由器是架構於一個開放式標準的規格，所以花費會較少將更具有成本效益，且其備援方式可以根據網路架設與使用狀況更靈活地與有效地進行調整。
- 學位論文
遊戲的回饋提供玩家訊息來了解遊戲、了解自己，因此回饋機制的設計將影響了玩家的自我評估與思考過程，而不同的玩家又會有不同的反應，這些過程將影響玩家的遊戲經驗，致使玩家對遊戲產生不同的情感。然而，遊戲設計者若僅基於過往經驗來設計遊戲回饋機制以迎合大多數玩家的喜好，則並不是每位玩家都能認同遊戲設計者的設定而得到最佳的遊戲經驗。因此本研究認為遊戲設計者應針對遊戲類型及玩家特性，提供不同類型的回饋。 本研究以音樂節奏遊戲為平台，探討在玩家與遊戲互動下，提供「立即回饋」與「摘要回饋」對玩家自我調節歷程的影響，並觀察其遊戲表現、遊戲學習歷程與心流經驗的程度。本研究發現玩家需要「立即回饋」來幫助其於行為與結果之中建立連結，讓玩家更容易產生控制感以幫助遊戲表現，比起「摘要回饋」更容易提升其學習效果。實驗結果也發現自我調節者能透過自我調節的歷程中，展現自己的韌性，於遊戲情境中取得技能與挑戰的平衡，自成目標經驗並全神貫注於其中，進一步獲得心流體驗。
- 學位論文
軟體安全日漸成為重要的研究主題，起因於越來越多的軟體攻擊行為發生，這些狀況有一部份是源自於程式語言本身的缺陷，而另一方面也是程式設計師本身的粗心所導致。因此，我們將藉由軟體偵測技術以減少這些問題。在論文中探討目前被廣泛運用的的程式漏洞-緩衝區溢位(Buffer overflow)，例如西元2003年八月造成重大損失的疾風(Blaster)病毒即利用此種漏洞進行破壞。為了防止此類型的漏洞，本論文使用KLEE的符號執行模組(symbolic execution model)並引入新的記憶體對映機制(memory map)來探測緩衝區溢位。相較於傳統的檢測工具，本論文所提出的工具可確實產生、可利用的測資來觸發漏洞的行為，進而證實漏洞的存在。這些測資事實上就是一組攻擊字串，有別於駭客手動方式產生，我們將提出自動產生的方法。
- 學位論文
在此篇論文裡, 我們提出了兩層式路況系統的分析模型。兩層式路況系統是在兩層式架構下，藉由車子間彼此分享資訊的機制，進而取得路況資訊的系統。其中，兩層式架構是由下層的車間隨意通訊網路 (Vehicular Ad-Hoc Network) 及上層的點對點網路(Peer-to-Peer Network) 所組成。所有的車子透過主動緊急訊息廣播協定(Inter-Vehicle Communication) 組成車間隨意通訊網路，而由部份的車子透過3G等行動通訊技術組成點對點網路。我們針對在兩層式架構下作路況搜尋的效能分析。採用的搜尋效能指標包括：搜尋路況的成功率及搜尋成功情形下的平均搜尋時間。基於這種兩層式架構提出的分析模型，只需修改部分參數即可成為單純的車間隨意通訊網路的分析模型或是單純的點對點網路的分析模型。最後，我們透過模擬實驗來驗證我們的分析模型。此外；根據網路拓樸的不同，以Chord Network代表結構化點對點網路而以Gnutella Network代表非結構化點對點網路。
- 學位論文
以往生態系統的研究，多半集中在物種與物種間的兩兩交互作用特性上。然而，一旦生態系統的規模擴大，物種間的交互作用就越顯複雜，其複雜性可能到達難以估算的程度。隨著小世界網路、無尺度網路等複雜網路研究的興起，可將物種與物種間的交互作用簡化為物種與物種間的關係，並用統計的方式去觀察生態網路整體的性質。但這種方式卻接連遭遇到生態網路既不是小世界網路，也不是無尺度網路的定位問題。 本研究站在前人複雜網路的研究基礎上，從流量網路的角度出發，重新納入複雜系統中物種與物種間的交互作用，發現生態網路在連結數分布上與流量分布上並不一致，而流量分布則具有無尺度網路的冪次律特性，可將生態網路重新給與無尺度網路的定位。 進一步，本研究以流量網路分析來探討外來物種的影響。以往研究外來物種對生態系統的影響多集中在外來物種本身的特性上，一個與原生物種習性、食性相似，卻在生殖與掠食能力上具有優勢者，可預期會對生態系統造成影響，但每個物種在生態系統中的角色不盡相同，其受外來物種影響的程度與影響擴散的範圍亦不盡相同。 因此，本研究從生態保育的角度出發，鎖定觀察外來物種對生態系統中指標物種之影響，並評估指標物種受影響之程度與影響擴散的範圍。進而從其影響程度與範圍得出指標物種間的相關性及保育上的優先性，期望透過保育指標物種的方式，減低外來物種對生態系的威脅。
- 學位論文
隨著智慧型手機與平板電腦的普及，行動裝置的續航力與效能越來越被重視，而其裝置之中的微處理器更是影響其續航力與效能的關鍵。而相對而言，一般使用的個人電腦與工作站雖然效能比較強但在用電效率上就差了許多。而且由於省電微處理器的成熟發展與其針對性，他們每單位瓦特所能得到的效能甚至比其他效能取向的核心更佳。另外就如同其他注重結果的程式一般EDA工具在縮短執行時間的同學希望能取得最好的結果。所以本篇論文我們在比較在不同取向之微處理器上執行EDA工具時平台的行為並使用多核心平行處理的方式來增進省電核心之效能且分析其行為。