# 論文筆記——基於身體動作結合新興模式探勘方法於人類活動辨識之研究
## 背景知識
### 人類活動辨識 (Human Activity Recognition, HAR)
可以分為簡單活動和複雜活動，簡單活動代表在給定時間內持續執行的活動，複雜活動則是由複數的簡單活動組成。複雜活動可以有兩種模式，分別是並行(concurrent)以及交錯(interleaved)，並行活動是同時發生簡單活動的集合，交錯活動是在簡單活動之間切換的集合。

人類活動辨識流程會表示為活動辨識鏈
### 活動辨識鏈 (Activity Recognition Chain, ARC)
有監督式和非監督式兩種執行鏈，監督式方法會將擷取的特徵和對應label作為輸入以訓練分類器，主要流程如下
* 資料獲取 (data acquisition)
* 輸入都是由多個感測器獲取的串流資料組成
* 資料前處理 (data preprocessing)
* 取得需要的真實訊號
* 資料分段 (data segmentation)
* 資料萃取 (data extraction)
* 取得特徵向量

要取得用於人類活動辨識資料的類型主要有影像與音訊一派，以及感測器活動辨識一派，影音部分的資料收集與處理成本較高且面對著隱私議題，感測器則有低成本及高精確度等優點，且搭上遍布式計算的發展而受到廣泛使用。
==辨識資料：影像與音訊、感測器活動辨識 => 感測器活動辨識==
感測器分為環境感測器與穿戴式感測器。環境感測器，像是簡單二元感測器 (simple binary sensors) 、RFID (Radio-Frequency IDentification) 等，能夠安裝在智慧環境中的不同區域，或是附於某些物體上來監測使用者活動。通常使用者活動會在特定的位置，例如煮飯會在廚房，所以我們可以透過觀察環境結合使用者與物體的互動來辨識活動。
==感測器活動辨識：環境感測器、穿戴式感測器 => 穿戴式感測器==
穿戴式感測器能夠直接附著在人體或身上的服飾或配件上，像是皮帶、眼鏡或是行動裝置等，通常會提供 連續的資訊，這種感測器又可以分為生命跡象感測器 (vital signs sensor) 和慣性感測器 (inertial sensors)。前者常用於醫療服務以提供生命跡象，根據從這些生物感測器收集的資料，可以進一步疾病預測、異常檢測和診斷決策的服務。而後者的常見實物有加速器 (accelerometer) 和陀螺儀 (gyroscopes)。
==穿戴式感測器：生命跡象感測器、慣性感測器 => 慣性感測器==
加速器可以監測動態活動、讀出物體沿著某一軸的加速度值。像是在監測走路、跑步、坐下等動作時所收集到的資料有時間和直角坐標的三軸加速度資訊，這些資料推斷出的情境可以用於長期連續活動的監測以及緊急情況，比如跌倒的辨識。陀螺儀則是將震動體加到感測器中，以測量在一段時間內的角速度變化。大部分研究會將陀螺儀與加速度感測器一起使用，組成一個慣性測量單元(Inertial Measurement Unit, IMU)。

許多研究只使用慣性感測器當作資料源，好處是缺乏其他資訊的情況下也能辨識活動，除此之外減少了其他類型的感測器如環境感測器，這則造成環境中情境資訊缺乏。如何在有限的資訊中辨識活動是此類研究的目標。

### 資料處理
取得的資料可能因為環境、通訊因素使得資料中包含不需要的雜訊，或者需要進一步處理為有用的訊號。資料若有缺失或不平衡，也可以用差補缺失值或是重新取樣來克服。

對於感測器生成連續的串流資料，因為資料量與感測器的取樣頻率相比，所以一旦人類活動的持續時間拉長，便會提高使用連續串流資料進行活動分類的難度。且模型在訓練時難以從連續的資料中檢索出重要和有用的訊息，因此需要將資料分段。

#### 資料前處理
通常會由機器學習演算法 (machine learning algorithm) 或是推理方法 (reasoning approach) 來實現，但是未來智慧家庭環境會越來越複雜，裝置數量多，所收集到的資料會包含更多的雜訊，這些雜訊原因可能來自電池放電、感測器讀取數值失敗以及無線感測器網路中訊息丟失。我們可以透過過濾雜訊以留下真實資訊，再使用一些濾波器萃取出需要的資料。

在UCI dataset中，利用手機中的加速器與陀螺儀以50hz的取樣頻率收集資料之後，因為人類身體運動有 99%都低於 15Hz，使用中值濾波器與三階的巴特沃斯 (Butterworth) 低通濾波器以 20Hz 的截止頻率做資料前處理。另外從任何加速器收集的三軸加速器訊號是由重力與身體動作訊號所組成的，而身體動作被視為只有低頻率的組成，所以用另一個巴特沃斯低通濾波器消除重力的影響，來取得目標真實的加速度。

#### 資料分段
分段的資料會包含相關分類的活動訊息，在辨識流程中會需要將這些資料分段並映射到活動標籤，若輸入特徵沒有區分性會造成分類器不能產生有意義的分類結果。

活動辨識中，將資料分段的動作被稱為活動分段，需要依賴預先定義的活動知識，或是有先經足夠訓練的模型，主要方法有事件分段和滑動視窗。

* 事件分段
將感測器事件的序列分為不重疊的子序列，每個子序列代表單一活動，且內部具有同質性，活動辨識會將每個子序列映射到一個活動標籤。
給定n個感測器事件$S = < e_1,\cdots,e_n>$的序列，事件分段會將序列劃分為x個子序列$P = <S_1,\cdots,S_x>$的集合，$S_i \subseteq S$，($S_i$屬於$S$)，子序列P會是非空且不重疊的，且所有$S_i$的總和會是$S$。綜上所述，事件分段的作用是將連續的串流資料分為離散的活動執行單元，每個片段都可以歸類為一項活動，而每個片段不一定會和活動邊界完全對齊。

* 滑動視窗
將感測器世間的序列案時間排序，並分為可能重疊的子序列。
給定n個感測器事件$S = < e_1,\cdots,e_n>$的序列，事件視窗識別出一組x個的視窗$P = <S_1,\cdots,S_x>$，視窗大小為{$w_1,\cdots,w_n$}，使得每個$S_i$是$S$的有序子序列。視窗集合P是有序、非空以及可能重疊的，且$S_i$的總和會是$S$的父集合，因此$S_i$可以表示為$<e_i,\cdots,e_{i+w_i}>$。
使用滑動視窗的方法是將每個$S_i$的最後一個或最近的一個感測器事件映射到活動標籤，滑動視窗中感測器事件的順序給予活動進行的資訊，因此有利於映射。由於視窗的有序性，讓實時標記串流資料活動的標記成為有效方法。且在訓練階段讓模型學習時有一種簡單方法，又降低了活動辨識的計算複雜度。
在連續串流資料中，活動與背景雜訊和無關的動作混合在一起，而滑動視窗這個活動辨識技術還可用於促進未知活動的發現，活動發現是從連續串流資料中定義特定活動實例的過程。
滑動視窗方法仍然需要做出許多決策，首先需要根據情境資訊的適當性和將要識別的活動類型來確定視窗大小，其次可能需要根據事件與當前情境資訊的相關性在一個視窗內對事件進行加權。

### 辨識方法
取得前處理過的時序性資料後，就是要擷取並選擇有用的特徵來建構辨識模型。基於慣性感測器的活動辨識，常見的資料型態是串流的三軸加速器和陀螺儀的讀值，根據取樣頻率會有連續且多筆的值對應到一個活動標籤。會透過滑動視窗得到人類身體最直接的資訊，再用機器學習模型進行分類。

==有段在講reference [9]到[13]==
每個研究分類結果最好的方法

諸多研究顯示了利用慣性感測器讀值來辨識簡單動作的準確度可以高於90%，至於複雜活動的研究較少，成效也較差，因此本研究將利用簡單活動來辨識複雜活動。另外有一種複雜活動辨識的研究方式，名為模式探勘，目的是從大量資料集中擷取模式與知識，使用到機器學習、統計學、資料庫系統等領域方法。常用於人類活動辨識的方法有頻繁模式探勘(Frequent Pattern mining, FP)以及新興模式探勘 (Emerging Pattern mining, EP)，會在第三章進一步介紹。

==講述為什麼使用頻繁模式和新興模式的方法的reference [14]到[17]==
本研究是透過身體動作的序列來辨識活動，因為想解決不同的活動可能會包含類似動作，其概念與前述研究使用新興模式的概念類似，故選擇結合頻繁模式與新興模式的方法來達到好的分類效果。

### 小結
而本研究會結合頻繁模式與新興模式用於以動作辨識活動的任務，目的是要找出能夠代表各個動作的模式並且利用新興模式來解決組成比較相似的活動，得到哪些活動之間彼此更有區別性的模式，以此來訓練辨識模型以辨識活動，會在下一個章節做更詳細的介紹。

## 研究方法
本研究中主要的方法是結合兩種不同的模式探勘方法來尋找具有辨識度的特徵，本章會討論本研究的方法，圖 3-1 為本研究的架構圖，對應到圖 2-1 的活動識別鏈流程並稍作修改。一開始先將原始資料處理成能夠擷取特徵並且訓練的型態(data processing)，在訓練階段使用模式探勘方法作為本研究篩選特徵的方法，並對訓練資料做特徵提取以訓練分類器(training phase)，再在測試階段同樣做特徵 提取當作新的測試資料來評估分類器(testing phase)。

在 3.1 小節中介紹資料的型態，包括資料的擷取與處理；在 3.2 小節中，我們會先介紹模式探勘的一些基本定義，並且介紹本研究所使用的第一個模式探勘方法：頻繁模式；在 3.3 小節中介紹第二個模式探勘方法：新興模式，並討論兩種不同的評估方法；在 3.4 小節中介紹本研究評估特徵值的方法，以及介紹本研究使用的三個分類器；最後在 3.5 小節做一個小結論。


### 資料處理
本研究的目的是要找出每個活動的模式，需要將包含不同的動作序列資料先處理成對應相同活動類別的數個動作子序列。在給定的動作序列下需要將之區分為有序的完整活動，我們會利用資料集中的動作類別標籤所得到活動邊界，將資料分段成數個動作子序列，以及對應的活動類別當作標籤。本小節介紹基於身體動作的活動辨識資料型態，一個完整的串流活動紀錄會包括時間、事件以及所對應的活動標籤，而本研究將事件視為一個動作。

設$A$表示包含了$m$個動作類別的集合，如公式(1)，$L$表示包含$n$個活動類別標籤的集合，如公式(2)，而一個動作序列$S$包含數個有序動作$a_p$滿足$a_p \in A$。

模式探勘方法中在事件分段階段時，需要將完整的動作序列$S$區分為非空的動作子序列$S_1,\cdots,S_k$，當$0 \leq i,j \leq k$時，滿足$S_i \bigcap S_j = \emptyset$，每個子序列分別對應不同活動標籤。假設資料取樣頻率是2hz，擇一段10秒鐘的動作序列$A$如公式 (3)所示，序列中1,2,3為三個不同的動作編號，分別代表右手移動、右手抓取、右手放下。原始的動作序列可能會包含連續重複的動作，如果我們將其視為單一的完整動作，並且記錄每個完整動作開始與結束的時間，便可以將動作序列$A$簡化為公式 (4)，依序為右手移動、抓取、移動、放下、移動。若將時間拉長到一個活動的時間長度，則可以得到一個動作子序列$A_i$以及對應的活動標籤$L_i$， 而完整的活動序列$S$則會包含$t$個動作子序列，如公式 (5)，每個子序列都會對應一個活動標籤。

將資料分段成不同的活動後，我們將不同活動的動作子序列分類成不同資料集，得到n個包含數筆動作子序列的資料集。最後我們就可以透過模式探勘方法找出相同活動的序列中之模式來做為活動的特徵，在分類階段訓練分類器來辨識活動，接下來的兩個小節會介紹本研究使用的模式探勘方法。

### 頻繁模式探勘
頻繁模式探勘是在給定大型資料集中分析與搜索出最頻繁之相關模式的任務，該概念最初是為了挖掘交易資料集而出現，而本研究視每個項目為動作，每筆交易視為動作子序列，將其應用在動作資料集，找出某一活動中常見的模式當作特徵。而頻繁模式定義為出現在資料集中的模式，其頻率不小於使用者指定或系統自動定義的閾值。本節介紹了頻繁模式探勘的基本概念，用於發現資料集中項目集之間有趣的關聯和相關性。

#### 支持度 (support)
支持度是模式探勘的一個度量方法，它反映了所發現的模式出現的頻繁性。假設$I$是一個包含$m$個項目的項目集，如公式 (6)，$D$是一組資料集，其中包含的每一筆交易$T$是一個非空的項目子集，滿足$T \subseteq I$。令$X$為一組項目，其中滿足$X \subset I$且$X \neq \emptyset$，則$X$在所有交易$T$中出現的總次數則稱之為絕對支持度，記作 $count_D(X)$，而$X$在$D$中的支持度就是$X$在所有交易T中出現的機率總和，如公式 (7)，通常又稱其為相對支持度，記作$sup_D(X)$。

以下面的例子來看，假設有一資料集如表 3-1，其中TID為交易編號，項目清單是每一筆交易所包含的項目集$T$，則可以計算出每組項目在這個資料集中的支持度，如表 3-2，項目I1在交易 T1、T2、T3 中出現，出現的次數是 3 次，可以記為$count_{TID}(I1) = 3$，佔總共交易次數 4 次的比例為75%，就是項目 I1 的支持度，可以記為$sup_{TID}(I1) = \frac {count_{TID}(I1)}{|TID|} = 0.75$。

#### 頻繁模式
意旨在一個資料集內出現次數頻繁的模式，模式可以試項目集、子序列或是子結構。比方說在一個商品交易資料集中頻繁出現「棒球和手套」，那這個項目就是頻繁項目集；先後購買電腦、螢幕、以及滑鼠的購物活動在歷史資料集中頻繁出現，就是一種頻繁序列模式；子結構可以代表不同形式的結構，例如子格、子圖或子樹，它們可以與項目集或子序列組合，如果子結構頻繁發生，則稱為頻繁結構化模式。

以數學化的角度來說，如果一個模式的支持度滿足所設定的最小支持度閾值$min\_sup$，則這個模式就是頻繁模式，如公式 (8)，而這些閾值可以由使用者設置。延續上一個小節的例子，如果最小支持度閾值設為 50%，則頻繁模式有{I1}、{I2}、{I3}，如表 3-3。

頻繁模式探勘在挖掘資料集之間的關聯、相關性和許多其他有趣的關係中至關重要，它也有助於資料分類、聚類和其他資料探勘任務。因此，頻繁模式探勘已成為重要的資料探勘任務和研究的重點主題。

#### k-項目集
有數個項目的集合稱為項目集，例如一組包含牛奶、麵包的項目是一個 2-項目集。如果項目集 I 的相對支持滿足預定 的最小支持閾值，或 I 的絕對支持滿足相應的最小支持計數閾值，則 I 為頻繁項 集，頻繁的 k 項集通常表示為 $L_k$。因此，上一小節中表 3-3 計算出的頻繁模式 是 1-項目集的頻繁模式，而如果要考慮包含 2-項目集的支持度，也就是兩個項目 同時出現在的交易的頻率，就需要找出任兩個項目排列組合的項目集，通常稱其 為 2-項目集的候選者 (candidate)，而這些候選者所組成的集合就稱為 2-項目集 的候選集，如表 3-4，接著對每個候選者掃描資料集中的每個交易來計算支持度， 如表 3-5，與此同時就能得到滿足最小支持度閾值的頻繁的 2-項目集，如表 3-6。

以這種方式下去可以找到資料集 D 中所有頻繁模式，但是如公式(6)所示， 若資料集 D 中的項目集 L 包含 m 個項目，則計算各個 k-項目集的支持度所需要 花費如下式：

總共所需要的次數如公式(9)，若 m 越大，計算量會呈 2 的指數倍數成長。因此 在下一小節，會介紹一個資料探勘領域中經典的演算法 Apriori，來解決這個問 題。

#### Apriori演算法
Apriori 是 R.Agrawal 和 R.Srikant 於 1994 年提出的一種演算法，用於關聯規 則挖掘頻繁項目集，Apriori 採用逐級搜索的迭代方法，使用 k-項目集探索(k+1)-項目集，通過掃描資料集以累加每個項目的數量，然後收集滿足最小支持閾值的那些項目，找到一組頻繁的 1-項目集，記作 L1，接下來，利用 L1 找出頻繁的 2 個項目集，記作 L2，該集合用於找出 L3，依此類推，直到找不到更多的 k 個項目集，而找出每個 Lk 要求對資料集進行一次完整的掃描。

Apriori 有一個重要的特性：對一個非空的頻繁集合，其子集合必定也為頻繁。根據這個特性可以反向推斷出：若有一個集合為非頻繁，則它的所有超集合都為非頻繁。根據公式 (6) (7)，如果有一個項目集 X 不滿足最小支持度閾值，也就是P(X) < 𝑚𝑖𝑛_𝑠𝑢𝑝，則 X 為非頻繁，若將一個項目 B 加到項目集 X 中產生新的項目集X ∪ B在 D 中發生的頻率也無法更高，也就是P(X ∪ B) < 𝑚𝑖𝑛_𝑠𝑢𝑝，因此X ∪ B也為非頻繁。這一個特殊的特性稱為反單調性 (anti-monotone)，其意義是若一個集合無法通過一個測驗，則所有它的超集合也都無法通過這個測驗。接下來會介紹 Apriori 透過組合 (join) 和刪減 (prune) 兩個步驟來利用 Lk-1 來找出 $L_k$。

* 組合
* 為了要找出$L_K$，我們透過$L_{K−1}$本身的組合來產生候選集𝑘-itemsets，這些候選項目的集合記作$C_K$。假設𝐼1與𝐼2是𝐿𝑘−1中的項目集，𝐼𝑖[𝑗]表示𝐼𝑖中的第𝑗個項目，例

###### tags: `論文`