• 學位論文

探勘智慧環境下電器之共相關行為模式及其應用

基於現今感測儀器製作能力的先進，收集家中、商業大樓或大型工廠內的所有電力、水力及其他能源的日常使用資料已成為一件並不是技術上困難之事情。然而，對於這些居住者或是能源使用者而言，如何將這些能源的消耗利用適當的圖像化、圖表化等等視覺化技術呈現出來是一個不小的挑戰。因此，新的資料探勘演算法技術更需要發展並用以發現電能消耗模式。但是目前當代的模式探勘演算法主要聚焦在分析單一電器而鮮少去了解電器間的共相關行為模式。本論文中提出嶄新的演算法－CoPMiner－主要探勘使用模式及包含機率之共相關行為。裝備了三個創新的最佳化策略的CoPMiner演算法能夠有效並有效率的大幅減少探勘時間及搜索空間。再者，為了展示本演算法的實務及研究價值，我們將CoPMiner應用並探勘真實資料以顯現其電器之共相關行為模式。

• 學位論文

運用蒙地卡羅樹狀搜尋於多目標彈性零工式工廠排程問題

在生產管理和組合最佳化的領域中，彈性零工式工廠排程(Flexible Job Shop Scheduling Problem, FJSP)是一個非常重要的問題，本論文最佳化FJSP是最小化以下三項目標：總時程、總工作量與最大工作量，並採用非凌越解集合(Pareto Solutions)的方式進行最佳化。 近年來，蒙地卡羅樹狀搜尋(Monte-Carlo Tree Search, MCTS) 非常成功地運用於電腦圍棋及其他許多遊戲，本論文將運用MCTS來解FJSP問題。我們的做法是結合MCTS與變鄰域下降演算法(Variable Neighborhood Descent Algorithm)，並且加入一些變異的方法如Rapid Action Value Estimates Heuristic、換位表(Transposition Table)應用於FJSP。 我們的MCTS方法能夠在116秒找出Kacem等人提出之基準問題(benchmark)的17組解：4x5共四組、10x7共三組、8x8共四組、10x10共四組、15x10共兩組，除了8x8有一組沒有找到外，其他皆是目前找到最好的，此結果是目前最好的，與蔣宗哲教授等人提出的簡易演化式演算法(Simple Evolutionary Algorithm)與模因演算法(Memetic Algorithm)相同，雖然Xiaojuan Wang等人提出的演算法有找到額外的一組8x8的解，但他們並沒有找到一些上述提到的解。 本研究是第一個用MCTS解出Kacem等人提出之基準問題中17組目前的最佳解，此結果不亞於其他演算法如基因演算法，在作業數量較多的Mk基準問題中所找到的解也與目前的最佳解相近。

• 學位論文

隧道監控系統之多攝影機車輛辨識

隧道內交通意外往往會造成巨大災害且難以處理，因此有大量監視攝影機裝設於隧道中，可即時發現事故並監控路況。但通常並沒有足夠的人力來觀看大量的監視器畫面，使得自動化監控系統的需求增加。本論文提出一種多攝影機車輛辨識系統，利用隧道內多攝影機的監視器畫面追蹤行車在隧道內的位置。 於單一監視器畫面中，使用Haar-like特徵偵測找出車輛，並取出OpponentSIFT影像特徵。接著，本論文提出的空間時間連續關係動態規劃(S2DP)演算法，利用隧道內行車順序關係性，辨識前後兩台攝影機中所偵測到的車輛。此外亦提供兩種進階辨識方法，包含即時運算(RT)方法以及非即時加強處理(OR)。即時運算方法減少車輛配對之搜尋範圍，並快速比對兩攝影機內之車輛。而非即時方法針對空間時間連續關係動態規劃演算法中無法有效配對的行車做進一步處理。 實驗結果顯示所提出之多攝影機車輛辨識系統可得到滿意的準確程度，並優於其他相關演算法。

• 學位論文

使用執行期配置與轉譯技術達成可適性異質多核心計算

本篇論文是在OpenCL的架構上，為異質多核心計算系統增添可適性。實作上我們先在執行時期取得系統環境資訊，再決定kernel該配置於何種裝置。若將kernel配置於CPU上，則進一步採用Whole Function Vectorization所提供的轉譯技術，使kernel能轉譯成SIMD指令，來提升kernel在CPU上執行的效能。此外，我們也利用過去歷史資料來協助預測裝置的附載量，讓該系統更智慧地配置。我們選擇AMD APP SDK所提供的範例程式來驗證增加可適性能改善OpenCL應用程式的效能。實驗結果指出，增加可適性於OpenCL系統可平均省下65%的時間。

• 學位論文

分析Android儲存裝置存取之資料流動追蹤技術

關於Android惡意程式分析的研究，包含了追蹤記憶體、儲存裝置、網路使用等行為。但是目前為止，Android上分析技術的範圍只侷限在記憶體，並沒有完整的追蹤儲存裝置的部分，像是內部空間的NAND flash以及外部空間的SD Card。本篇論文將提出一個以位元組為單位，更細緻地追蹤Android儲存裝置上的檔案。除此之外，我們還實作出YAFFS2的檔案系統解析器，將硬碟上offset與檔案物件做關聯性，可以方便我們在底層去追蹤檔案。我們的系統還會追蹤某特定程式所接收的封包，並且在寫檔及送封包時，指出資料的來源。在實驗的部份，本系統可初步的成功分析到記憶體與儲存裝置之間、記憶體與網路之間的動態資料流動追蹤，提供一個完整的程式行為分析紀錄。

• 學位論文

用於 RESTful Web 服務的使用者效用導向服務代理伺服器框架與機制

我們提出一個 RESTful Web 服務的服務代理框架，於使用者週邊的裝置，如家用電視機上盒 (set-up box)、個人電腦 (PC) 上安裝遍佈式 Web 服務代理伺服器，用於提供本地的 RESTful Web 服務。此種將 Web 服務由雲端負載轉移到本地端執行的方式的可以增強使用者的品質 (QoE) 與他們的移動應用程式的體驗，同時，減少他們的互聯網服務提供者和移動運營商的負荷。本文利用了包括： (1) 基於 HATEOAS 的 Web 服務代理 API 機制、服務代碼封裝及服務描述檔案。(2) 嵌入在 HTTP 標頭中的基於效用導向的體驗品質政策規範。在上述方法的幫助下，遍佈式的服務代理伺服器可以在中繼 Web 服務響應時，取得 Web 服務的執行代碼與運作行為描述，不需要人為的介入部署；且在中繼 Web 服務響應時，動態的決定是否執行本地計算負載轉移。在我們的測試中顯示其能有效的減少行動雲端應用程式的延遲時間和其資料流量服務。

• 學位論文

動態通訊錄 : 行動電話撥打方的智慧型導引

The rapid growth of smartphone uses in today’s modern life encourages the development of useful application that provides a batch of useful information to it's users. The main aim of this development is to make smartphone smarter. Phone call prediction is one of applications that serve as an important feature to achieve smarter smartphone. To the best of our knowledge, there were two most recent works on the development of telephone call [11, 12]. Even though those studies have shown the promising achievements over the basic congenital telephone system, we are still confident to explore many basic features that seem that received little attention in their research. In this paper, we investigate more conservative features that can subscribe as same accuracy result or even better. More specifically, given the user historical call activities, we explore four major features: frequency, duration, recency, and direction. The frequency feature refers the number of interaction calls between the user and callee. The period of time that the user and callee spent in each of their communication call defines as duration feature. While, recency feature is the weight of each connection call between user and callee according to the recentness of that call. Lastly, the feature of direction describes the importance of call initiator between user and callee by giving pre-defined weight. According to these features, we develop three probability ranking models: Probability General-Frequency (PGF), Probability General-Duration (PGD), and Probability Recency (PR). Moreover, we train these models in two real Call Detail Record (CDR) datasets, Reality Mining and Chunghua Telecom dataset to gain depiction result. Finally, we compare these models with the existing works and demonstrate that our conventional models can reach same and even better accuracy prediction.

• 學位論文

探勘智慧型手機中應用程式使用行為之研究

隨著智慧型手機的普及，愈來愈多的行為應用程式(mobile applications)被開發及設計。使用者可以由網路上下載這些Apps來處理各種需求，例如：相機、地圖、瀏覽器、音樂播放器，…等。並且，由於手機的行動性，這些下載、執行及移除的行為可以發生在任何的時間及任何的地點。因為，智慧型手機的使用記錄便成為一個複雜的時間空間資料。在本論文中，主要將探討四個主題：(1)以個人化特徵挑選進行Apps使用預測、(2)以時間性履歷進行Apps使用預測、(3)使用者Apps動態喜好模型、(4)探勘以多維度序列為基礎之使用者Apps使用樣式。 在第一個主題中，我們將收集智慧型手機上的各種感測器，包含硬體感測器，例如：時間、加速度、地理位置、等…；軟體感測器，例如：Apps的使用順序。這些感測裝置的讀數可以有效的利用來預測使用者的Apps使用情況。然而，智慧型手機上的感測裝置非常多，收集這些讀數不只會造成儲存空間上的浪費，也會花費額外的能源來進行感測。因此，我們在這個主題中，會以個人化的觀點進行特徵挑選，只有有利於預測該使用者的Apps使用的感測裝置會進行感測。如此便用大量的降低儲存訓練資料所需的空間及感測時消耗的能量。 在第二個主題中，我們只參考時間的因素來進行Apps使用預測。我們利用傅立葉轉換來得到Apps的使用週期，接著根據這些找出來的週期為每一個App進立他的時間性履歷。此時，由於時間資訊已經被 傅立葉轉換所消除，我們必需將具有相同週期但發生在不同時間的行為區隔開。在這裡，我們利用階層式分群法來將類似的行為分為一群，並且視其為一種使用行為。最後，我們提出一個分數計算的系統，可以計算出每一個App在目前時間可能被執行的機會。但由於這個機率的運算需要對App的使用機率密度進行積分，而積分的計算對於手機來說是一項耗費能源的動作。因此，我們提出一個以柴比雪夫不等式為基礎的分數計算方式，可以不需要進行積分，便能計算出App可能被使用的機率。 在第三個主題中，我們發現使用者的喜好是會隨著時間而改變。但大部份的使用者不會對他們所下載的Apps進行評分，而不可能在他們每次改變喜好時，不停的重新評分。在這個主題中，我們以上一個時間點的喜好搭配上目前時間點的使用次數來計算目前時間點的喜好。然而，使用次數並無法完整的反應出使用者的喜好。例如：對於某些使用者來說，通訊Apps，像是Line、Whatsapp的使用次數必定比生產力工具來得多。於是，在這個主題中，我們以線性迴歸來代表使用者喜好變化的趨勢，而該使用者喜好的變化，便能以迴歸線的斜率來表示。 在第四個主題中，我們設計了一個特殊的序列樣式，稱為多維度序列樣式。由於Apps可能歸屬於各種不同的類別，因為，我們可以將Apps的使用記錄看成是一個多維度(類別)的序列。而最常出現的多維度序列樣式，便可以用來代表這個使用者的使用行為。在這裡，我們提出一個傳遞式的探勘方式，只需要在第一個維度進行序列樣式探，接著再透過傳遞的方式來組合其他維度相對應的樣式，便能組合出一個多維度的序列樣式。除此之外，我們還提出一個增加效率的資料結構，可以只找出最短的樣式，再利用此資料結構來延長樣式的長度。

• 學位論文

個人特徵發現之手機應用程式預測

隨著越來越多的手機應用軟件的開發，它們正密切地融入人們的日常生活中。在本論文中，我們發展了一個基於當前設備狀態以預測智能手機上最有可能被使用的應用軟件的框架。這樣的應用程序使用的預測框架對於加速應用程式發動，智能手機的用戶體驗，和電源管理都是不可或缺的條件.透過真實的應用程序使用日誌數據的分析，我們發現兩種特徵數值：從內置的感測器所測得讀數，稱為顯性特徵（EF），以及從應用程序使用關係轉換的數值，稱為隱性特徵。IF特徵數值是從建構應用程序使用轉變的應用程序使用圖（簡稱ＡＵＧ）的模型而推衍。鑒於ＡＵＧ的圖形，我們能夠發現應用程序之間的關係。由於用戶可能有不同的在智能手機的使用行為，我們進一步提出一個個人化的特徵選擇演算法。從訓練數據裡，我們探索最低描述長度（MDL），並選擇需要較少位元數來形容訓練數據資料的特徵。個人特徵選擇演算法，可以成功地減少日誌的大小和預測所花費的時間。最後，我們採用KNN分類模型來預測應用程序的使用。需要注意的是當我們使用k近鄰分類器時，我們只需要保留通過個人化特徵選擇演算法的特徵，這不僅可以降低預測的時間又能避免多維度所帶來的缺點。最後，我們做了在真實行動應用程式的數據集的一個完整綜合的實驗研究。得到的結果表示，我們提出的框架是有效的並顯示其在應用程式使用上的預測的能力。

• 學位論文

利用志願型運算解決電腦遊戲問題

電腦遊戲是人工智慧(Artificial Intelligence)中一項非常重要的研究領域，其中有些問題需要非常大量的運算才能解出，而志願型運算(Volunteer Computing)非常適合用來解決這些問題。由於電腦遊戲的特性，大部份問題需要即時地產生及取消工作，這在傳統的志願型運算上會非常沒有效率，因為傳統的志運型運算為非連線模式，無法即時更改工作。本論文提出工作層級運算模式(Job-level Computing Model)，並以此模式為基礎發展一套新的且具有一般化之工作層級志願型運算系統，此系統使用的是連線模式，以避免傳統志願型運算解決電腦遊戲效率不佳的問題。本論文利用傳統型志運型運算與工作層級志願型運算分別解決兩個電腦遊戲問題：數獨最小提示數問題(Minimum Sudoku Problem)與六子棋開局問題(Connect6 Opening Problem)。 在解決數獨最小提示數問題中，本論文亦改善了2006年的數獨Checker程式，加快了約128倍效率，使用此改善程式可將原本需要約30萬年單核時間的數獨最小提示數問題減少成約2417年可解。而在解決六子棋開局問題中，成功地將證明數搜尋演算法應用於工作層級志運型運算系統中，並提出了延遲兄弟節點產生法及假設證明數相同之方法來展開搜尋樹節點，成功地解出許多六子棋盤面的勝敗，其中包含多個開局，例如米老鼠開局，此開局在過去是很受歡迎的開局之一。根據實驗數據顯示，在16核的環境下其速率可提升8.58倍。