進階搜尋


 
系統識別號 U0026-0812200914315107
論文名稱(中文) 以序列比對演算法實現人類行為模式探勘與辨識
論文名稱(英文) Human Activity Pattern Mining and Recognition by Sequence Alignment Algorithm
校院名稱 成功大學
系所名稱(中) 資訊工程學系碩博士班
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 96
學期 2
出版年 97
研究生(中文) 李思賢
研究生(英文) Sz-Shian Li
學號 p7695420
學位類別 碩士
語文別 英文
論文頁數 60頁
口試委員 口試委員-李冠榮
口試委員-李允中
指導教授-郭耀煌
口試委員-李強
口試委員-謝孫源
中文關鍵字 行為辨識  無線射頻識別系統 (RFID  序列比對演算法 
英文關鍵字 Sequence Alignment  RFID  Activity Recognition 
學科別分類
中文摘要 在此篇論文中,我們利用序列比對演算法,提出了一個創新的機制去實現人類行為辨識。人類的行為是由一連串的行為模式所組成,而一個行為模式包含了一段時間內的行為特徵,像是使用者碰觸到的物體、時間,與地點的資訊。這些行為特徵透露了人類行為的狀態與不同行為之間的差異,我們可以藉由這些特徵來辨識各種行為。我們根據下列步驟來實現人類行為辨識,首先,利用RFID設備來收集訓練資料,訓練資料是由一連串的行為特徵資訊組合而成的行為序列。接著,再從這些訓練資料中的特徵找出行為的模式,由於人類行為具有多樣性與差異性,所以這些行為序列並不是那麼地一致,而序列比對演算法 (sequence alignment algorithm) 善於比對受到雜訊干擾的序列,因此我們修改序列比對演算法來發掘出行為模式。最後,同樣利用序列比對演算法來比對行為模式與真實生活中的行為序列,並且辨識出序列中的行為。
我們的方法具有下列的優點:從此方法找出來的行為模式並不是固定長度的序列,而是依據行為的特徵自動找出行為序列中重要的區段,如此一來可以避免人為地介入與主觀的定義,使得行為辨識的系統更符合真實情況。藉由統計行為模式在特定行為中出現的機率,可以提昇行為辨識的準確性。此外,在辨識行為的程序中,因為我們採用了動態規劃 (dynamic programming) 的方法,所以能夠立即地將對偵測到的資訊與行為模式互相比對,得到行為辨識的結果,而且這種方法解決了如何對序列分段的問題。最後,實驗結果顯示我們的系統在真實環境中的辨識結果準確率高於81%。
英文摘要 In this paper, we propose a novel mechanism which uses the sequence alignment algorithm to realize the human activity recognition. Human activity is composed of a se-ries of human activity patterns and an activity pattern includes some activity features in a period of time. Each activity feature contains such information as an object touched by the user, the current time, and the location. These activity features reveal the state of hu-man activity and the differences between different activities. Based on these features, we execute following steps. First, collect the training samples composed of the sequential activity features using RFID sensing technique. Second, mine the activity patterns from these activity features by employing the sequence alignment algorithm. We apply such algorithm in this paper because human activity has great diversity and the sequence alignment algorithm is good at comparing interfered sequences. Hence, we modify this algorithm to discover the activity patterns. Last, by applying the sequence alignment al-gorithm, compare the mined activity patterns with the real activity sequences and thus, recognize the human activity.
Our purposed mechanism comprises several advantages. The activities pattern ob-tained from this method is not fixed length. It is created automatically according to the activity features without any human intervention or subjective judgment. Therefore, it is adaptive for the variety of real human activities. The algorithm for mining activity pat-terns is able to improve the activity recognition by calculating probability of activity pat-terns. In addition, we adopt the dynamic programming in the process of recognizing ac-tivities, so the result of recognition can be obtained immediately by comparing the pat-terns and real activity sequence. Also, the problem of segmenting observed sequence is resolved. The experiment results show that the accuracy of human activity recognition in reality is higher than 81%.
論文目次 Chapter 1 Introduction 1
1.1 Human Activity Recognition in Context-aware Computing 1
1.2 Motivation 2
1.3 Challenges of Recognizing Human Activities 3
1.3.1 Sensing Techniques 4
1.3.2 Methods of Modeling Activity 6
Chapter 2 Problem Formulation and Sequence Matching Algorithms 10
2.1 Problem Formulation 10
2.2 Sequence Matching Algorithms 11
2.2.1 Fixed-length words 11
2.2.2 Dictionary-based compression 12
2.2.3 Sequence Alignment 13
Chapter 3 Activity Recognition System & Activity Model 20
3.1 Sensing Information 23
3.2 Preprocess 25
3.3 Pattern Mining 26
3.4 Pattern Matching 27
Chapter 4 Modified Sequence Alignment Algorithm for Activity Recognition 29
4.1 Activity Pattern Mining 29
4.1.1 Initialization 30
4.1.2 Filling Matrixes 32
4.1.3 Searching Patterns 35
4.1.4 Saving and Counting Patterns 37
4.2 Activity Pattern Matching 39
4.2.1 Location Filter 40
4.2.2 Similarities of Patterns 40
4.2.3 Related Degree of Activity 42
Chapter 5 Experiments 45
5.1 Experimental Environment 45
5.2 Experiment Results 47
Chapter 6 Conclusions and Future Work 54
6.1 Conclusions 54
6.2 Future Work 55
References 57
參考文獻 [BAH00] P. Bahl and V. N. Padmanabhan, “RADAR: An In-Building RF-based User Location and Tracking System,” in Proc. of 19th Annual Joint Conf. of the IEEE Computer and Communications Societies, vol. 2, pp. 775-784, 2000.
[BER02] B. Bergeron, Bioinformatics Computing, Prentice Hall, 2002.
[CLE97] J. G. Cleary and W. J. Teahan, “Unbounded Length Contexts for PPM,” The Computer Journal, Vol. 40, pp.67-75, 1997.
[DAS02] S. K. Das, D. J. Cook, A.Bhattacharya, E. O. Heierman III, and T. Y. Lin, “The role of prediction algorithms in the MavHome smart home architecture,” IEEE Wireless Communications, vol.9, no.6, pp. 77-84, 2002.
[GIB01] C. Gibas, and P. Jambeck, Developing Bioinformatics Computer Skills, O'Reilly Media, Inc, 2001.
[HIG01] J. Hightower and G. Borriello, “Location Sensing Techniques,” IEEE Com-puter, vol. 34, no. 8, pp. 57-66, 2001.
[KRA05] N. Krahnstoever , J. Rittscher, P. Tu, K. Chean, and T. Tomlinson, “Activity Recognition using Visual Tracking and RFID,” in Proc. of the 7th IEEE Workshops on Application of Computer Vision, vol. 1, pp. 494-500, 2005.
[LIN06] C. Y. Lin and J. Y. Hsu, “IPARS: Intelligent portable activity recognition sys-tem via everyday objects, human movements, and activity duration,” in Proc. of Int. AAAI Workshop on Modeling Others from Observations, pp. 44–52, 2006.
[MAN04] S. S. Manapure, H. Darabi, V. Patel, and P. Banerjee, “A comparative study of radio frequency-based indoor location sensing systems,” in Proc. of IEEE Int. Conf. on Networking, Sensing and Control, vol. 2, pp. 1265-1270, 2004.
[MAN08] S. Mantaci, A. Restivo, and M. Sciortino, “Distance measures for biological sequences: Some recent approaches,” Int. Journal of Approximate Reasoning, vol. 47, no. 1, pp. 109-124, 2008.
[MOU04] D. W. Mount, Bioinformatics: Sequence and Genome Analysis, Cold Spring Harbor Laboratory Press, 2004.
[NI03] L. M. Ni, Y. Liu, Y. C. Lau and A. P. Patil, “LANDMARC: indoor location sensing using active RFID, ” in Proc. of the 1st IEEE Int. Conf. on Pervasive Computing and Communications, pp. 407-415, 2003.
[PAT05] D. J. Patterson, D. Fox, H. Kautz, and M. Philipose, “Fine-Grained Activity Recognition by Aggregating Abstract Object Usage,” in Proc. of the 9th IEEE Int. Symposium on Wearable Computers, pp.44-51, 2005.
[PER04] M. Perkowitz, M. Philipose, K. Fishkin, and D.J. Patterson, “Mining models of human activities from the web,” In Proc. of the 13th Int. Conf. on World Wide Web, New York, pp. 573-582, 2004.
[PHI04] M. Philipose, K. P. Fishkin, M. Perkowitz, D. J. Patterson, D. Fox, and H. Kautz and D. Hähnel, “Inferring Activities from Interactions with Objects,” IEEE Pervasive Computing, vol.3, no.4, pp. 50-57, 2004.
[PHI05] M. Philipose, J. R. Smith, B. Jiang, A. Mamishev, S. Roy, and K. S. Rajan, “Battery-free wireless identification and sensing,” IEEE Pervasive Compu-ting, vol. 4, pp. 37-45, 2005.
[QUI04] A. Quigley, B. Ward, C. Ottrey, D. Cutting and R. Kummerfeld, “BlueStar, a privacy centric location aware system,” in Proc. of Position Location and Na-vigation Symposium, pp. 684-689, 2004.
[ROY03] A. Roy, S. K. Das Bhaumik, A. Bhattacharya, K. Basu, D. J. Cook and S.K. Das, “Location aware resource management in smart homes,” in Proc. of Pervasive Computing and Communications (PerCom), pp.481-488, 2003.
[ROY06] N. Roy, A. Roy, and S. K. Das, “Context-Aware Resource Management in Multi-Inhabitant Smart Homes: A Nash H-Learning based Approach,” in Proc. of Pervasive Computing and Communications (PerCom), pp.148-158, 2006.
[SCH94] B. Schilit, N. Adams, and R. Want, “Context-aware computing applications,” in Proc. of Int. IEEE Workshop on Mobile Computing Systems and Applica-tions (WMCSA'94), pp. 85-90, 1994.
[SMA02] A. Smailagic, D. P. Siewiorek, J. Anhalt, D. Kogan, and Y. Wang, “Location sensing and privacy in a context-aware computing environment,” IEEE Wireless Communications, vol. 9, pp. 10-17, 2002.
[SMI05] J. R. Smith, K. P. Fishkin, B. Jiang, A. Mamishev, M. Philipose, A. D. Rea, S. Roy, and K. Sundara-Rajan, “RFID-based techniques for human-activity de-tection,” Commun. ACM, vol. 48, pp. 39-44, 2005.
[WAN07] S. Wang, W. Pentney, A. M. Popescu, T. Choudhury, and M. Philipose, “Common Sense Based Joint Training of Human Activity Recognizers,” In Proc. of Int. Joint Conf. on Artificial Intelligence (IJCAI), 2007.
[WAR06] J. A. Ward, P. Lukowicz, G. Troster, and T. E. Starner, “Activity Recognition of Assembly Tasks Using Body-Worn Microphones and Accelerometers,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 28, pp. 1553-1567, 2006.
[WYA05] D. Wyatt, M. Philipose, and T. Choudhury, “Unsupervised Activity Recogni-tion Using Automatically Mined Common Sense,” in Proc. of Int. Conf. on AAAI, 2005, pp. 21-27.
[YAN08] J. Yang, B. N. Schilit, and D. W. McDonald, “Activity Recognition for the Digital Home,” IEEE Computer, vol. 41, pp. 102-104, 2008.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2010-08-22起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2010-08-22起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw