臺灣博碩士論文加值系統

將文集中內容相似的文章群集在一塊是議題與內容分析常用的方法，不過世界上的語言有千百種，在文獻分類上並非所有語言都可以使用過去英文分類所常使用的斷字切詞(Tokenization)、去除停用詞(Delete stop word)、字詞原型化(Word Stemming)、字詞權重計算的方式進行分類，因此本研究提出透過區域敏感雜湊(Locality Sensitive Hashing, LSH)進行分類，LSH過去被用於網路內文的相似性比對，其不受限於任何語言，因此本研究選用LSH作為文獻分類之分類演算法。LSH主要透過擷取Shingling的方式作為文獻的特徵，而Shingling擷取之長度k由文獻佐證與實測顯示，對於研究論文或期刊這類較龐大的文獻，使用k=9的擷取長度準確率會較為準確，擷取Shingling後利用Minhash將Shingling集合縮減成較小之簽名(signature)矩陣，再利用LSH將特徵透過雜湊的方式進行分類。
本研究為證明LSH可對文獻進行分類且確保其準確率，因此將過去常用於英文文獻分類的空間向量模型(Vector Space Model, VSM)做為比較基準，並結合K-NN與K-means將兩分類流程建立在同一個分類的基準上進行比較。結合K-NN的流程中使用不同的文獻篇數產出各篇數不同的訓練模型，再對待分類文獻進行分類，最後透過混淆矩陣對兩分類流程所產出之結果，檢視模型之性能。結合K-means的流程中透過集群與內文一致性檢定的方式，評估分群結果。本研究從IEEE網站上搜尋6主題之文獻(Cloud Computing、Information Analysis、Enterprise Resource Planning、Image Processing、Music及Criminal Justice)，並透過LSH與VSM兩流程對此6個主題的文獻進行訓練分類，而結果顯示當每個類別提供50篇以上的文獻進行模型訓練時，其待分類文獻的準確率皆接近90%，證明LSH可應用於文獻分類之研究。

Most of the contemporary text clustering or classification methods are based on texting mining technique that characterize documents using features derived from the frequency of term’s occurrence and the distribution of these terms in the document corpus. In these methods, a document is represented by a vector of terms’ frequency and their inverse document frequency (TF-IDF). The similarity between documents is measured by the cosine of their vector representation. However, the TF/IDF based methods were devised to process English language. Other languages may have a very different form that may render the term-based method inapplicable. We propose a language neutral classification/clustering method that utilizes the Locality Sensitive Hashing (LSH) that does not rely on lexical terms in a document. We compare the accuracy between the classical Vector Space Model (VSM) and LSH method and found their performance on par. Our proposed method is indeed a language neutral text classification/clustering scheme that is suitable for very large document corpus.

致謝 I
中文摘要 II
英文摘要 III
目次 IV
表目次 VII
圖目次 IX
第一章、緒論 1
第一節、研究背景與動機 1
第二節、研究目的 2
第三節、論文架構 3
第二章、文獻探討 5
第一節、 文字探勘 5
2.1.1 特徵選取 5
第二節、 分類演算法 10
2.2.1 LSH 10
2.2.2 LSH相關研究 15
2.2.3 最近鄰法(K-th nearest neighbor, K-NN) 17
2.2.4 K-means分群法 18
第三節、 混淆矩陣 18
第四節、 集群評估方式 20
2.4.1 Jaccard Index 20
2.4.2 Kappa & Gwet’s AC1 21
2.4.3 Rand Index 22
2.4.4集群評估方式小結 23
第五節、 內文一致性 24
2.5.1 Jensen-Shannon Divergence (JSD) 24
第三章、研究方法 26
第一節、 研究架構 27
第二節、 資料蒐集 29
3.2.1 文獻字詞萃取 29
3.2.2 擷取Shingling 30
第三節、 資料處理 30
3.3.1 VSM資料處理 30
3.3.2 LSH資料處理 33
第四節、 資料評估 35
3.4.1 混淆矩陣 35
3.4.2 集群與內文一致性評估 36
第四章、 研究實作與結果 38
第一節、研究實作 38
4.1.1 文獻蒐集 38
4.1.2 k-Shingling之k值檢測 38
4.1.3 VSM與LSH結合K-NN之模型建置 39
4.1.4 VSM與LSH結合K-NN之分類結果 42
4.1.5 VSM與LSH結合K-means之分群結果 43
第二節、研究結果 43
4.2.1 VSM與LSH結合K-NN分類後混淆矩陣 43
4.2.2 準確率比較 45
4.2.3 集群與內文一致性評估 48
第五章、結論與建議 49
第一節、研究貢獻 49
第二節、研究限制 50
第三節、未來研究議題 51
參考文獻 52
附錄一、Cloud Computing文獻集之文獻列表 56
附錄二、Information Analysis文獻集之文獻列表 60
附錄三、Enterprise Resource Planning文獻集之文獻列表 64
附錄四、Image Processing文獻集之文獻列表 68
附錄五、Music文獻集之文獻列表 72
附錄六、Criminal Justice文獻集之文獻列表 76
附錄七、各類別抽選50篇做為模型進行分類結果 80
附錄八、各類別抽選50篇做為模型之混淆矩陣 85
附錄九、各類別抽選50篇做為模型的Precision、Recall和F-measure 87
附錄十、VSM與LSH結合K-means之分群結果 88
附錄十一、各模型分類結果與混淆矩陣結果 90
簡歷 91
著作權聲明 92

英文參考文獻
Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician, 46(3), 175-185.
Aslam, J. A., & Pavlu, V. (2007). Query hardness estimation using Jensen-Shannon divergence among multiple scoring functions. Paper presented at the European Conference on Information Retrieval.
Baoli, L., Qin, L., & Shiwen, Y. (2004). An adaptive k-nearest neighbor text categorization strategy. ACM Transactions on Asian Language Information Processing (TALIP), 3(4), 215-226.
Blekanov, И., & Korelin, V. (2015). Hierarchical clustering of large text datasets using Locality-Sensitive Hashing. Proceedings of the International Workshop on Applications in Information Technology (IWAIT-2015).
Boyack, K. W., & Klavans, R. (2010). Co-citation analysis, bibliographic coupling, and direct citation: Which citation approach represents the research front most accurately? Journal of the American Society for Information Science and Technology, 61(12), 2389-2404.
Broder, A. Z. (1997, June). On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997. Proceedings (pp. 21-29). IEEE.
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (1998, May). Min-wise independent permutations. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (pp. 327-336). ACM.
Buhler, J. (2001). Efficient large-scale sequence comparison by locality-sensitive hashing. Bioinformatics, 17(5), 419-428.
Carletta, J. (1996). Assessing agreement on classification tasks: the kappa statistic. Computational linguistics, 22(2), 249-254.
Cha, S.-H. (2007). Comprehensive survey on distance/similarity measures between probability density functions. City, 1(2), 1.
Chen, H., Chung, Y. M., C., Marshall, R., & Yang, C. C. (1998). An intelligent personal spider (agent) for dynamic Internet/Intranet searching. Decision Support Systems, 23(1), 41-58.
Chowdhury, G. (2010). Introduction to modern information retrieval: Facet publishing.
Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1), 21-27.
Dutta, D., Guha, R., Jurs, P. C., & Chen, T. (2006). Scalable partitioning and exploration of chemical spaces using geometric hashing. Journal of chemical information and modeling, 46(1), 321-333.
Feldman, R., Fresko, M., Kinar, Y., Lindell, Y., Liphstat, O., Rajman, Y., Schler & Zamir, O. (1998, September). Text mining at the term level. In European Symposium on Principles of Data Mining and Knowledge Discovery (pp. 65-73). Springer Berlin Heidelberg.
Gwet, K. (2002). Inter-rater reliability: dependency on trait prevalence and marginal homogeneity. Statistical Methods for Inter-Rater Reliability Assessment Series, 2, 1-9.
Han, E. H. S., Karypis, G., & Kumar, V. (2001, April). Text categorization using weight adjusted k-nearest neighbor classification. In Pacific-asia conference on knowledge discovery and data mining (pp. 53-65). Springer Berlin Heidelberg.
Haveliwala, T., Gionis, A., & Indyk, P. (2000). Scalable Techniques for Clustering the Web (Extended Abstract). In: Third International Workshop on the Web and Databases (WebDB 2000), May 18-19, 2000, Dallas, Texas,.
Hopfield, J. J. (1982). Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8), 2554-2558.
Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of classification, 2(1), 193-218.
Hull, D. A. (1996). Stemming algorithms: A case study for detailed evaluation. JASIS, 47(1), 70-84.
Indyk, P., & Motwani, R. (1998, May). Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (pp. 604-613). ACM.
Jaccard, P. (1901). Distribution de la Flore Alpine: dans le Bassin des dranses et dans quelques régions voisines: Rouge. Sciences Naturelles, 1901, 241-272.
Leskovec, J., Rajaraman, A., & Ullman, J. D. (2014). Mining of massive datasets: Cambridge University Press.
Levandowsky, M., & Winter, D. (1971). Distance between sets. Nature, 234(5323), 34-35.
MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Paper presented at the Proceedings of the fifth Berkeley symposium on mathematical statistics and probability.
Oprişa, C., Checicheş, M., & Năndrean, A. (2014). Locality-sensitive hashing optimizations for fast malware clustering. Paper presented at the Intelligent Computer Communication and Processing (ICCP), 2014 IEEE International Conference on.
Park, D. C., El-Sharkawi, M., Marks, R., Atlas, L., & Damborg, M. (1991). Electric load forecasting using an artificial neural network. Power Systems, IEEE Transactions on, 6(2), 442-449.
Powers, D. (2007). Evaluation: From Precision, Recall and F Factor to ROC, Informedness, Markedness & Correaltion. Sch. Informatics Eng. Flinders.
Ravichandran, D., Pantel, P., & Hovy, E. (2005, June). Randomized algorithms and nlp: using locality sensitive hash function for high speed noun clustering. InProceedings of the 43rd Annual Meeting on Association for Computational Linguistics (pp. 622-629). Association for Computational Linguistics.
Salton, G., & McGill, M. J. (1986). Introduction to modern information Retrieval. New York, NY, USA: McGraw-Hill, Inc.
Salton, G., Wong, A., & Yang, C.-S. (1975). A vector space model for automatic indexing. Communications of the ACM, 18(11), 613-620.
Santos, J. M., & Embrechts, M. (2009). On the use of the adjusted rand index as a metric for evaluating supervised classification. Paper presented at the International Conference on Artificial Neural Networks.
Slaney, M., & Casey, M. (2008). Locality-sensitive hashing for finding nearest neighbors [lecture notes]. IEEE Signal Processing Magazine, 25(2), 128-131.
Sparck Jones, K. (1972). A statistical interpretation of term specificity and its application in retrieval. Journal of documentation, 28(1), 11-21.
Stehman, S. V. (1997). Selecting and interpreting measures of thematic classification accuracy. Remote sensing of Environment, 62(1), 77-89.
Sullivan, D. (2001). Document warehousing and text mining: techniques for improving business operations, marketing, and sales. John Wiley & Sons, Inc..
Wu, G., Boydell, O., & Cunningham, P. (2014). High-throughput, Web-scale data stream slustering. In Proceedings of the 4th Web Search Click Data workshop (WSCD 2014).
Yang, Y., & Pedersen, J. O. (1997, July). A comparative study on feature selection in text categorization. In ICML (Vol. 97, pp. 412-420).
Zhang, J., Song, R., Yu, W.-X., Xia, S.-P., & Hu, W.-D. (2005). Construction of hierarchical classifiers based on the confusion matrix and fisher's principle. Ruan Jian Xue Bao(Journal of Software), 16(9), 1560-1567.
中文參考文獻
江珅薇(2007)，相關學術論文集合關鍵詞擷取-學術領域自動命名，國立臺北大學資訊管理研究所。
曾有德(2008)，以 Web 2.0 概念建構自動化文件分群與內容相似性比對之研究， 國立高雄第一科技大學資訊管理研究所。
黃馨儀(2015)，智識建構方法論之改進研究，國立臺北大學資訊管理研究所。
鄭宇傑(2015)，以核運算方法與LDA主題模型產生文字標籤之比較研究，國立臺北大學資訊管理研究所。
謝祥榆(2016)，應用區域敏感雜湊進行中文文獻分類之研究，國立臺北大學資訊管理研究所。