學術產出-Theses
Article View/Open
Publication Export
-
題名 應用記憶體內運算於多維度多顆粒度資料探勘之研究―以醫療服務創新為例
A Research Into In-memory Computing In Multidimensional, Multi-granularity Data Mining ― With Healthcare Services Innovation作者 朱家棋
Chu, Chia Chi貢獻者 姜國輝<br>季延平
Chiang, Kuo Huie<br>Chi, Yan Ping
朱家棋
Chu, Chia Chi關鍵詞 資料探勘
多維度關聯分析
記憶體內運算
創新醫療服務應用
Data Mining
Multidimensional and Multi-granularity Data Mining Association Analysis
In-Memory Computing
Apriori Algorithm日期 2015 上傳時間 1-Apr-2016 10:40:25 (UTC+8) 摘要 全球面臨人口老化與人口不斷成長的壓力下，對於醫療服務的需求不斷提升。醫療服務領域中常以資料探勘「關聯規則」分析，挖掘隱藏在龐大的醫學資料庫中的知識(knowledge)，以支援臨床決策或創新醫療服務。隨著醫療服務與應用推陳出新(如，電子健康紀錄或行動醫療等)，與醫療機構因應政府政策需長期保存大量病患資料，讓醫療領域面臨如何有效的處理巨量資料。然而傳統的關聯規則演算法，其效能上受到相當大的限制。因此，許多研究提出將關聯規則演算法，在分散式環境中，以Hadoop MapReduce框架實現平行化處理巨量資料運算。其相較於單節點 (single-node) 的運算速度確實有大幅提升。但實際上，MapReduce並不適用於需要密集迭帶運算的關聯規則演算法。本研究藉由Spark記憶體內運算框架，在分散式叢集上實現平行化挖掘多維度多顆粒度挖掘關聯規則，實驗結果可以歸納出下列三點。第一點，當資料規模小時，由於平行化將資料流程分為Map與Reduce處理，因此在小規模資料處理上沒有太大的效益。第二點，當資料規模大時，平行化策略模式與單機版有明顯大幅度差異，整體運行時間相差100倍之多；然而當項目個數大於1萬個時，單機版因記憶體不足而無法運行，但平行化策略依舊可以運行。第三點，整體而言Spark雖然在小規模處理上略慢於單機版的速度，但其運行時間仍小於Hadoop的4倍。大規模處理速度上Spark依舊優於Hadoop版本。因此，在處理大規模資料時，就運算效能與擴充彈性而言，Spark都為最佳化解決方案。
Under the population aging and population growth and rising demand for Healthcare. Healthcare is facing a big issue how to effectively deal with huge amounts of data. Cased by new healthcare services or applications (such as electronic health records or health care, etc), and also medical institutions in accordance with government policy for long-term preservation of a large number of patient data.But the traditional algorithms for mining association rules, subject to considerable restrictions on their effectiveness. Therefore, many studies suggest that the association rules algorithm in a distributed computing, such as Hadoop MapReduce framework implements parallel to process huge amounts of data operations. But in fact, MapReduce does not apply to require intensive iterative computation algorithm of association rules.Studied in this Spark in-memory computing framework, implemented on a distributed cluster parallel mining association rules mining multidimensional granularity, the experimental results can be summed up in the following three points. 1th, when data is small, due to the parallel data flow consists of Map and Reduce, so not much in the small-scale processing of benefits. 2nd, when the data size is large, parallel strategy models and stand-alone obviously significant differences overall running time is 100 times as much when the item number is greater than 10,000, however, stand-alone version cannot run due to insufficient memory, but parallel strategies can still run. 3rd, overall Spark though somewhat slower than the single version in small scale processing speed, but the running time is less than 4 times times the Hadoop. Massive processing speed Spark is still superior to the Hadoop version. Therefore, when working with large data, operational efficiency and expansion elasticity, Spark for optimum solutions.參考文獻 [1] Agrawal, Rakesh, and Ramakrishnan Srikant. "Fast algorithms for mining association rules." Proc. 20th int. conf. very large data bases, VLDB. Vol. 1215. 1994.[2] Agrawal, Rakesh, Tomasz Imieliński, and Arun Swami. "Mining association rules between sets of items in large databases." ACM SIGMOD Record. Vol. 22. No. 2. ACM, 1993.[3] Apache Hadoop, https://hadoop.apache.org/,2015[4] Chae, Young Moon, et al. "Data mining approach to policy analysis in a health insurance domain." International journal of medical informatics 62.2 (2001): 103-111.[5] Cheung, David W., et al. "A fast distributed algorithm for mining association rules." Parallel and Distributed Information Systems, 1996., Fourth International Conference on. IEEE, 1996.[6] Chiang, Johannes, and Chia-Chi Wu. "Mining multi-dimensional association rules in multiple database segmentation." Proceedings of International Conference on Information Management. 2005.[7] Chuang, Kun-Ta, Ming-Syan Chen, and Wen-Chieh Yang. "Progressive sampling for association rules based on sampling error estimation." Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 2005. 505-515.[8] Das, Amitabha, Wee-Keong Ng, and Yew-Kwong Woon. "Rapid association rule mining." Proceedings of the tenth international conference on Information and knowledge management. ACM, 2001.[9] Dean, Jeffrey, and Sanjay Ghemawat. "MapReduce: simplified data processing on large clusters." Communications of the ACM 51.1 (2008): 107-113.[10] Do, Tien Dung, Siu Cheung Hui, and Alvis Fong. "Mining frequent itemsets with category-based constraints." Discovery Science. Springer Berlin Heidelberg, 2003.[11] Ghemawat, Sanjay, Howard Gobioff, and Shun-Tak Leung. "The Google file system." ACM SIGOPS operating systems review. Vol. 37. No. 5. ACM, 2003.[12] Han, Jiawei, Jian Pei, and Yiwen Yin. "Mining frequent patterns without candidate generation." ACM SIGMOD Record. Vol. 29. No. 2. ACM, 2000.[13] Khare, Neelu, Neeru Adlakha, and K. R. Pardasani. "An Algorithm for Mining Multidimensional Association Rules using Boolean Matrix." Recent Trends in Information, Telecommunication and Computing (ITC), 2010 International Conference on. IEEE, 2010.[14] Lent, Brian, Arun Swami, and Jennifer Widom. "Clustering association rules." Data Engineering, 1997. Proceedings. 13th International Conference on. IEEE, 1997.[15] Li, Lingjuan, and Min Zhang. "The strategy of mining association rule based on cloud computing." Business Computing and Global Informatization (BCGIN), 2011 International Conference on. IEEE, 2011.[16] Li, Ning, et al. "Parallel implementation of apriori algorithm based on MapReduce." Software Engineering, Artificial Intelligence, Networking and Parallel & Distributed Computing (SNPD), 2012 13th ACIS International Conference on. IEEE, 2012.[17] Lin, Ming-Yen, Pei-Yu Lee, and Sue-Chen Hsueh. "Apriori-based frequent itemset mining algorithms on MapReduce." Proceedings of the 6th international conference on ubiquitous information management and communication. ACM, 2012.[18] Qiu, Hongjian, et al. "YAFIM: A Parallel Frequent Itemset Mining Algorithm with Spark." Parallel & Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International. IEEE, 2014.[19] Schuster, Assaf, and Ran Wolff. "Communication-efficient distributed mining of association rules." Data Mining and Knowledge Discovery 8.2 (2004): 171-196.[20] Srikant, Ramakrishnan, and Rakesh Agrawal. "Mining quantitative association rules in large relational tables." ACM SIGMOD Record. Vol. 25. No. 2. ACM, 1996.[21] Wojciechowski, Marek, and Maciej Zakrzewicz. "Dataset filtering techniques in constraint-based frequent pattern mining." Pattern detection and discovery. Springer Berlin Heidelberg, 2002. 77-91.[22] Yang, Xin Yue, Zhen Liu, and Yan Fu. "MapReduce as a programming model for association rules algorithm on Hadoop." Information Sciences and Interaction Sciences (ICIS), 2010 3rd International Conference on. IEEE, 2010.[23] Zaharia, Matei, et al. "Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing." Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2012.[24] “Frequent Itemset Mining Dataset Repository”, http://fimi.ua.ac.be/data/ 描述 碩士
國立政治大學
資訊管理學系
102356020資料來源 http://thesis.lib.nccu.edu.tw/record/#G1023560202 資料類型 thesis dc.contributor.advisor 姜國輝<br>季延平 zh_TW dc.contributor.advisor Chiang, Kuo Huie<br>Chi, Yan Ping en_US dc.contributor.author (Authors) 朱家棋 zh_TW dc.contributor.author (Authors) Chu, Chia Chi en_US dc.creator (作者) 朱家棋 zh_TW dc.creator (作者) Chu, Chia Chi en_US dc.date (日期) 2015 en_US dc.date.accessioned 1-Apr-2016 10:40:25 (UTC+8) - dc.date.available 1-Apr-2016 10:40:25 (UTC+8) - dc.date.issued (上傳時間) 1-Apr-2016 10:40:25 (UTC+8) - dc.identifier (Other Identifiers) G1023560202 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/83535 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊管理學系 zh_TW dc.description (描述) 102356020 zh_TW dc.description.abstract (摘要) 全球面臨人口老化與人口不斷成長的壓力下，對於醫療服務的需求不斷提升。醫療服務領域中常以資料探勘「關聯規則」分析，挖掘隱藏在龐大的醫學資料庫中的知識(knowledge)，以支援臨床決策或創新醫療服務。隨著醫療服務與應用推陳出新(如，電子健康紀錄或行動醫療等)，與醫療機構因應政府政策需長期保存大量病患資料，讓醫療領域面臨如何有效的處理巨量資料。然而傳統的關聯規則演算法，其效能上受到相當大的限制。因此，許多研究提出將關聯規則演算法，在分散式環境中，以Hadoop MapReduce框架實現平行化處理巨量資料運算。其相較於單節點 (single-node) 的運算速度確實有大幅提升。但實際上，MapReduce並不適用於需要密集迭帶運算的關聯規則演算法。本研究藉由Spark記憶體內運算框架，在分散式叢集上實現平行化挖掘多維度多顆粒度挖掘關聯規則，實驗結果可以歸納出下列三點。第一點，當資料規模小時，由於平行化將資料流程分為Map與Reduce處理，因此在小規模資料處理上沒有太大的效益。第二點，當資料規模大時，平行化策略模式與單機版有明顯大幅度差異，整體運行時間相差100倍之多；然而當項目個數大於1萬個時，單機版因記憶體不足而無法運行，但平行化策略依舊可以運行。第三點，整體而言Spark雖然在小規模處理上略慢於單機版的速度，但其運行時間仍小於Hadoop的4倍。大規模處理速度上Spark依舊優於Hadoop版本。因此，在處理大規模資料時，就運算效能與擴充彈性而言，Spark都為最佳化解決方案。 zh_TW dc.description.abstract (摘要) Under the population aging and population growth and rising demand for Healthcare. Healthcare is facing a big issue how to effectively deal with huge amounts of data. Cased by new healthcare services or applications (such as electronic health records or health care, etc), and also medical institutions in accordance with government policy for long-term preservation of a large number of patient data.But the traditional algorithms for mining association rules, subject to considerable restrictions on their effectiveness. Therefore, many studies suggest that the association rules algorithm in a distributed computing, such as Hadoop MapReduce framework implements parallel to process huge amounts of data operations. But in fact, MapReduce does not apply to require intensive iterative computation algorithm of association rules.Studied in this Spark in-memory computing framework, implemented on a distributed cluster parallel mining association rules mining multidimensional granularity, the experimental results can be summed up in the following three points. 1th, when data is small, due to the parallel data flow consists of Map and Reduce, so not much in the small-scale processing of benefits. 2nd, when the data size is large, parallel strategy models and stand-alone obviously significant differences overall running time is 100 times as much when the item number is greater than 10,000, however, stand-alone version cannot run due to insufficient memory, but parallel strategies can still run. 3rd, overall Spark though somewhat slower than the single version in small scale processing speed, but the running time is less than 4 times times the Hadoop. Massive processing speed Spark is still superior to the Hadoop version. Therefore, when working with large data, operational efficiency and expansion elasticity, Spark for optimum solutions. en_US dc.description.tableofcontents 摘要 i目錄 i圖目錄 iv表目錄 vi第一章、 概論 11、 研究背景 12、 研究動機 23、 研究目的 3第二章、 文獻探討 41、 資料探勘技術應用於醫療服務 42、 關聯規則 52.1 關聯規則定義 52.2 關聯規則演算法 63、 多維度關聯規則 113.1 Quantitative Association Rules 113.2 Association Rule Clustering System 123.3 Boolean Matrix based Approach 124、 Map-Reduce 134.1 Map-Reduce概念與發展 134.2 Apache Hadoop 16( 1 ). Hadoop MapReduce 16( 2 ). Apache Hadoop HDFS 175、 記憶體內運算(In-Memory Computing) 184.1 記憶體內運算概念與發展 184.2 Apache Spark 19第三章、 多維度多顆粒度演算法設計 221、 問題定義 221.1 多維度資料庫(Multi-dimension Database, MD) 221.2 概念化階層架構(Concept Hierarchy, CH) 231.3 多維度型樣(Multi-Dimension Patterns) 241.4 多維度關聯規則(Multi-dimension association rules) 262、 演算法流程 272.1 階段0：產生所有的多維度型樣 292.2 階段1：挖掘多維度多顆粒度關聯規則 302.3 階段2：更新多維度多顆粒度關聯規則 312.4 階段3：產出多維度多顆粒度關聯規則 333、 平行化多維度多顆粒度關聯規則演算法設計 343.1 平行化Apriori演算法 353.2 平行化多維度多顆粒度演算法 36第四章、 實驗結果與討論 371、 實驗數據與環境參數配置 372、 效能度量實驗結果與討論 382.1 速度指標實驗討論 392.2 擴充性指標實驗討論 403、 實際案例分析－ 台灣全民健康研究資料庫 423.1 實驗數據 423.2 實驗流程 433.3 實驗結果 44第五章、 研究結論與建議 461、 結論與貢獻 462、 未來研究建議 46參考文獻 47 zh_TW dc.format.extent 6586582 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G1023560202 en_US dc.subject (關鍵詞) 資料探勘 zh_TW dc.subject (關鍵詞) 多維度關聯分析 zh_TW dc.subject (關鍵詞) 記憶體內運算 zh_TW dc.subject (關鍵詞) 創新醫療服務應用 zh_TW dc.subject (關鍵詞) Data Mining en_US dc.subject (關鍵詞) Multidimensional and Multi-granularity Data Mining Association Analysis en_US dc.subject (關鍵詞) In-Memory Computing en_US dc.subject (關鍵詞) Apriori Algorithm en_US dc.title (題名) 應用記憶體內運算於多維度多顆粒度資料探勘之研究―以醫療服務創新為例 zh_TW dc.title (題名) A Research Into In-memory Computing In Multidimensional, Multi-granularity Data Mining ― With Healthcare Services Innovation en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Agrawal, Rakesh, and Ramakrishnan Srikant. "Fast algorithms for mining association rules." Proc. 20th int. conf. very large data bases, VLDB. Vol. 1215. 1994.[2] Agrawal, Rakesh, Tomasz Imieliński, and Arun Swami. "Mining association rules between sets of items in large databases." ACM SIGMOD Record. Vol. 22. No. 2. ACM, 1993.[3] Apache Hadoop, https://hadoop.apache.org/,2015[4] Chae, Young Moon, et al. "Data mining approach to policy analysis in a health insurance domain." International journal of medical informatics 62.2 (2001): 103-111.[5] Cheung, David W., et al. "A fast distributed algorithm for mining association rules." Parallel and Distributed Information Systems, 1996., Fourth International Conference on. IEEE, 1996.[6] Chiang, Johannes, and Chia-Chi Wu. "Mining multi-dimensional association rules in multiple database segmentation." Proceedings of International Conference on Information Management. 2005.[7] Chuang, Kun-Ta, Ming-Syan Chen, and Wen-Chieh Yang. "Progressive sampling for association rules based on sampling error estimation." Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 2005. 505-515.[8] Das, Amitabha, Wee-Keong Ng, and Yew-Kwong Woon. "Rapid association rule mining." Proceedings of the tenth international conference on Information and knowledge management. ACM, 2001.[9] Dean, Jeffrey, and Sanjay Ghemawat. "MapReduce: simplified data processing on large clusters." Communications of the ACM 51.1 (2008): 107-113.[10] Do, Tien Dung, Siu Cheung Hui, and Alvis Fong. "Mining frequent itemsets with category-based constraints." Discovery Science. Springer Berlin Heidelberg, 2003.[11] Ghemawat, Sanjay, Howard Gobioff, and Shun-Tak Leung. "The Google file system." ACM SIGOPS operating systems review. Vol. 37. No. 5. ACM, 2003.[12] Han, Jiawei, Jian Pei, and Yiwen Yin. "Mining frequent patterns without candidate generation." ACM SIGMOD Record. Vol. 29. No. 2. ACM, 2000.[13] Khare, Neelu, Neeru Adlakha, and K. R. Pardasani. "An Algorithm for Mining Multidimensional Association Rules using Boolean Matrix." Recent Trends in Information, Telecommunication and Computing (ITC), 2010 International Conference on. IEEE, 2010.[14] Lent, Brian, Arun Swami, and Jennifer Widom. "Clustering association rules." Data Engineering, 1997. Proceedings. 13th International Conference on. IEEE, 1997.[15] Li, Lingjuan, and Min Zhang. "The strategy of mining association rule based on cloud computing." Business Computing and Global Informatization (BCGIN), 2011 International Conference on. IEEE, 2011.[16] Li, Ning, et al. "Parallel implementation of apriori algorithm based on MapReduce." Software Engineering, Artificial Intelligence, Networking and Parallel & Distributed Computing (SNPD), 2012 13th ACIS International Conference on. IEEE, 2012.[17] Lin, Ming-Yen, Pei-Yu Lee, and Sue-Chen Hsueh. "Apriori-based frequent itemset mining algorithms on MapReduce." Proceedings of the 6th international conference on ubiquitous information management and communication. ACM, 2012.[18] Qiu, Hongjian, et al. "YAFIM: A Parallel Frequent Itemset Mining Algorithm with Spark." Parallel & Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International. IEEE, 2014.[19] Schuster, Assaf, and Ran Wolff. "Communication-efficient distributed mining of association rules." Data Mining and Knowledge Discovery 8.2 (2004): 171-196.[20] Srikant, Ramakrishnan, and Rakesh Agrawal. "Mining quantitative association rules in large relational tables." ACM SIGMOD Record. Vol. 25. No. 2. ACM, 1996.[21] Wojciechowski, Marek, and Maciej Zakrzewicz. "Dataset filtering techniques in constraint-based frequent pattern mining." Pattern detection and discovery. Springer Berlin Heidelberg, 2002. 77-91.[22] Yang, Xin Yue, Zhen Liu, and Yan Fu. "MapReduce as a programming model for association rules algorithm on Hadoop." Information Sciences and Interaction Sciences (ICIS), 2010 3rd International Conference on. IEEE, 2010.[23] Zaharia, Matei, et al. "Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing." Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2012.[24] “Frequent Itemset Mining Dataset Repository”, http://fimi.ua.ac.be/data/ zh_TW
