TIE algorithm: a layer over clustering-based taxonomy generation for handling evolving data

Rabia IRFAN; Sharifullah KHAN; Kashif RAJPOOT; Ali Mustafa QAMAR

doi:10.1631/FITEE.1700517

Your Location：

Home >

Browse articles >

TIE algorithm: a layer over clustering-based taxonomy generation for handling evolving data

Regular Papers | Updated：2022-05-19

- TIE algorithm: a layer over clustering-based taxonomy generation for handling evolving data
- TIE算法：一种用于处理演化数据的聚类分层分类法生成技术上层算法
- Frontiers of Information Technology & Electronic Engineering Vol. 19, Issue 6, Pages: 763-782(2018)
- Affiliations：
  
  School of Electrical Engineering and Computer Science, National University of Sciences and Technology, Islamabad 44000, Pakistan
  School of Computer Science, University of Birmingham, Birmingham B15 2TT, UK
  Department of Computer Science, College of Computer, Qassim University, Al Mulaida, Buraydah 52344, Saudi Arabia
- Author bio：
  
  Rabia IRFAN, E-mail: 12phdrirfan@seecs.edu.pk
- Funds：
- DOI：10.1631/FITEE.1700517
  CLC： TP312
- Received：04 August 2017，
  
  Revised：2018-;6-;8，
  
  Published：2018-06
- Accepted：
Scan QR Code
Rabia IRFAN, Sharifullah KHAN, Kashif RAJPOOT, et al. TIE algorithm: a layer over clustering-based taxonomy generation for handling evolving data[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(6): 763-782.
DOI：

Rabia IRFAN, Sharifullah KHAN, Kashif RAJPOOT, et al. TIE algorithm: a layer over clustering-based taxonomy generation for handling evolving data[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(6): 763-782. DOI： 10.1631/FITEE.1700517.

摘要

分类法可实现对大量数据的有效组织和访问。分类法是表示数据概念的一种方法，其需要通过不断演进来反映数据变化。现有分类法自动生成技术无法处理数据演化，因此，所生成的分类法不能真实反映数据。为反映数据演变，可从头对分类法进行再生，或根据数据变化随时对分类法进行增量演进。其中，前者的时间和资源成本较高。提出一种新颖的分类增量进化（TIE）算法，用于处理随时间演变的数据。TIE是一种现有聚类分层分类法生成技术的上层算法，它允许现有分类法增量地演进。在计算机领域的研究论文中对该算法进行了评估。结果表明，与从头再生分类法相比，随数据演化的分类法生成算法耗时非常短，且在单位时间下性能更佳。

Abstract

Taxonomy is generated to effectively organize and access large volume of data. A taxonomy is a way of representing concepts that exist in data. It needs to continuously evolve to reflect changes in data. Existing automatic taxonomy generation techniques do not handle the evolution of data; therefore

the generated taxonomies do not truly represent the data. The evolution of data can be handled by either regenerating taxonomy from scratch

or allowing taxonomy to incrementally evolve whenever changes occur in the data. The former approach is not economical in terms of time and resources. A taxonomy incremental evolution (TIE) algorithm

as proposed

is a novel attempt to handle the data that evolve in time. It serves as a layer over an existing clustering-based taxonomy generation technique and allows an existing taxonomy to incrementally evolve. The algorithm was evaluated in research articles selected from the computing domain. It was found that the taxonomy using the algorithm that evolved with data needed considerably shorter time

and had better quality per unit time as compared to the taxonomy regenerated from scratch.

关键词

Keywords

references

R Baeza-Yates , , , B Ribeiro-Neto . . Modern Information Retrieval: the Concepts and Technology Behind (2 nd Ed.). . . Pearson Education Limited, New York, USA , , 2011 . . .

R Blumberg , , , S Atre . . The problem with unstructured data . . DM Rev , , 2003 . . 13 ( ( 2 ): ): 42 - - 46 . . . .

SL Camia . . A Comparison of Taxonomy Generation Techniques Using Bibliometric Methods: Applied to Research Strategy Formulation . . MS Thesis, Massachusetts Institute of Technology, Cambridge, MA, USA , , 2010 . . .

D Carmel , , , H Roitman , , , N Zwerdling . . Enhancing cluster labeling using Wikipedia . . Proc 32 nd Int ACM SIGIR Conf on Research and Development in Information Retrieval , , 2009 . . p.139 - - 146 . . DOI: 10.1145/1571941.1571967 http://doi.org/10.1145/1571941.1571967 . .

SH Cha . . Comprehensive survey on distance/similarity measures between probability density functions . . Int J Math Models Methods Appl Sci , , 2007 . . 1 ( ( 4 ): ): 300 - - 307 . . . .

P Cimiano , , , A Hotho , , , S Staab . . Learning concept hierarchies from text corpora using formal concept analysis . . J Artif Intell Res , , 2005 . . 24 ( ( 1 ): ): 305 - - 339 . . . .

G Dawelbait , , , T Mezher , , , WL Woon , , , 等 . . Taxonomy based trend discovery of renewable energy technologies in desalination and power generation . . Proc Technology Management for Global Economic Growth , , 2010 . . p.1 - - 8 . . . .

S Deerwester , , , ST Dumais , , , GW Furnas , , , 等 . . Indexing by latent semantic analysis . . J Am Soc Inform Sci Technol , , 1990 . . 41 ( ( 6 ): ): 391 - - 407 . . DOI: 10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9 http://doi.org/10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9 . .

EA Dietz , , , D Vandic , , , F Frasincar . . TaxoLearn: a semantic approach to domain taxonomy learning . . Proc IEEE/ WIC/ACM Int Conf on Web Intelligence and Intelligent Agent Technology , , 2012 . . p.58 - - 65 . . DOI: 10.1109/WI-IAT.2012.129 http://doi.org/10.1109/WI-IAT.2012.129 . .

Enhanced Taxonomy Generation . . USA Patent , , 20 100 274 733 . . .

T Fountain , , , M Lapata . . Taxonomy induction using hierarchical random graphs . . Proc Conf of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies , , 2012 . . p.466 - - 476 . . . .

E Glover , , , DM Pennock , , , S Lawrence , , , 等 . . Inferring hierarchical descriptions . . Proc 11 th Int Conf on Information and Knowledge Management , , 2002 . . p.507 - - 514 . . DOI: 10.1145/584792.584876 http://doi.org/10.1145/584792.584876 . .

H Hedden . . The Accidental Taxonomist . . Information Today Inc., Medford, New Jersey, USA , , 2010 . . p.18 - - 28 . . . .

R Irfan , , , S Khan . . TIE: an algorithm for incrementally evolving taxonomy for text data . . Proc 15 th IEEE Int Conf on Machine Learning and Applications , , 2016 . . p.687 - - 692 . . DOI: 10.1109/ICMLA.2016.0121 http://doi.org/10.1109/ICMLA.2016.0121 . .

AK Jain , , , MN Murty , , , PJ Flynn . . Data clustering: a review . . ACM Comput Surv , , 1999 . . 31 ( ( 3 ): ): 264 - - 323 . . DOI: 10.1145/331499.331504 http://doi.org/10.1145/331499.331504 . .

V Kashyap , , , C Ramakrishnan , , , C Thomas , , , 等 . . TaxaMiner: an experimentation framework for automated taxonomy bootstrapping . . Int J Web Grid Serv , , 2005 . . 1 ( ( 2 ): ): 240 - - 266 . . DOI: 10.1504/IJWGS.2005.008322 http://doi.org/10.1504/IJWGS.2005.008322 . .

W Koff , , , P Gustafson . . Data Revolution . . Technical Report, Computer Sciences Corporation Leading Edge Forum , , 2011 . . .

AA Kumar , , , S Chandrasekhar . . Text data pre-processing and dimensionality reduction techniques for document clustering . . Int J Eng Res Technol , , 2012 . . 1 ( ( 5 ): ): 1 - - 6 . . . .

E Lefever . . LT3: a multi-modular approach to automatic taxonomy construction . . Proc 9 th Int Workshop on Semantic Evaluation , , 2015 . . p.944 - - 948 . . . .

T Li , , , SS Anand . . Exploiting domain knowledge by automated taxonomy generation in recommender systems . . Proc 10 th Int Conf on E-commerce and Web Technologies , , 2009 . . p.120 - - 131 . . . .

CD Manning , , , P Raghavan , , , H Schütze . . Introduction to Information Retrieval . . Cambridge University Press, New York, NY, USA , , 2008 . . .

RM Marcacini , , , SO Rezende . . Incremental construction of topic hierarchies using hierarchical term clustering . . Proc 22 nd Int Conf on Software Engineering and Knowledge Engineering , , 2010 . . p.553 - - 558 . . . .

O Medelyan , , , S Manion , , , J Broekstra , , , 等 . . Constructing a focused taxonomy from a document collection . . Proc 10 th Int Conf on the Semantic Web: Semantics and Big Data , , 2013 . . p.367 - - 381 . . DOI: 10.1007/978-3-642-38288-8_25 http://doi.org/10.1007/978-3-642-38288-8_25 . .

K Meijer , , , F Frasincar , , , F Hogenboom . . A semantic approach for extracting domain taxonomies from text . . Dec Support Syst , , 2014 . . 62 78 - - 93 . . DOI: 10.1016/j.dss.2014.03.006 http://doi.org/10.1016/j.dss.2014.03.006 . .

A Muller , , , J Dorre , , , P Gerstl , , , 等 . . The TaxGen framework: automating the generation of a taxonomy for a large document collection . . Proc 32 nd Annual Hawaii Int Conf on Systems Sciences, Article 2034 , , 1999 . . .

PM Nadkarni , , , L Ohno-Machado , , , WW Chapman . . Natural language processing: an introduction . . J Am Med Inform Assoc , , 2011 . . 18 ( ( 5 ): ): 544 - - 551 . . DOI: 10.1136/amiajnl-2011-000464 http://doi.org/10.1136/amiajnl-2011-000464 . .

M Neshati , , , A Alijamaat , , , H Abolhassani , , , 等 . . Taxonomy learning using compound similarity measure . . Proc IEEE/WIC/ACM Int Conf on Web Intelligence , , 2007 . . p.487 - - 490 . . DOI: 10.1109/WI.2007.135 http://doi.org/10.1109/WI.2007.135 . .

MS Paukkeri , , , AP García-Plaza , , , V Fresno , , , 等 . . Learning a taxonomy from a set of text documents . . Appl Soft Comput , , 2012 . . 12 ( ( 3 ): ): 1138 - - 1148 . . DOI: 10.1016/j.asoc.2011.11.009 http://doi.org/10.1016/j.asoc.2011.11.009 . .

XG Qi , , , DW Yin , , , ZZ Xue , , , 等 . . Choosing your own adventure: automatic taxonomy generation to permit many paths . . Proc 19 th ACM Int Conf on Information and Knowledge Management , , 2010 . . p.1853 - - 1856 . . DOI: 10.1145/1871437.1871746 http://doi.org/10.1145/1871437.1871746 . .

D Sánchez , , , A Moreno . . Automatic generation of taxonomies from the WWW . . Proc 5 th Int Conf on Practical Aspects of Knowledge Management , , 2004 . . p.208 - - 219 . . DOI: 10.1007/978-3-540-30545-3_20 http://doi.org/10.1007/978-3-540-30545-3_20 . .

F Sclano , , , P Velardi . . TermExtractor: a web application to learn the common terminology of interest groups and research communities . . Proc 3 rd Int Conf on Interoperability for Enterprise Software and Applications , , 2007 . . p.85 - - 94 . . . .

WS Spangler , , , JT Kreulen , , , JF Newswanger . . Machines in the conversation: detecting themes and trends in informal communication streams . . IBM Syst J , , 2006 . . 45 ( ( 4 ): ): 785 - - 799 . . DOI: 10.1147/sj.454.0785 http://doi.org/10.1147/sj.454.0785 . .

M Steinbach , , , G Karypis , , , V Kumar . . A comparison of document clustering techniques . . World Text Mining Conf , , 2000 . . p.1 - - 2 . . . .

R Sujatha , , , Rao BR Krishna . . Taxonomy construction techniques—issues and challenges . . Ind J Comput Sci Eng , , 2011 . . 2 ( ( 5 ): ): 661 - - 671 . . . .

V Thada , , , DV Jaglan . . Comparison of jaccard, dice, cosine similarity coefficient to find best fitness value for Web retrieved documents using genetic algorithm . . Int J Innov Eng Technol , , 2013 . . 2 ( ( 4 ): ): 202 - - 205 . . . .

P Treeratpituk , , , J Callan . . Automatically labeling hierarchical clusters . . Proc Int Conf on Digital Government Research , , 2006 . . p.167 - - 176 . . DOI: 10.1145/1146598.1146650 http://doi.org/10.1145/1146598.1146650 . .

V Turner , , , J Gantz , , , D Reinsel . . The Digital Universe of Opportunities: Rich Data and the Increasing Value of the Internet of Things . . IDC White Paper , , 2014 . . p.1 - - 5 . . DOI: 10.7790/ajtde.v2n3.47 http://doi.org/10.7790/ajtde.v2n3.47 . .

P Velardi , , , S Faralli , , , R Navigli . . OntoLearn reloaded: a graph-based algorithm for taxonomy induction . . Comput Ling , , 2013 . . 39 ( ( 3 ): ): 665 - - 707 . . DOI: 10.1162/COLI_a_00146 http://doi.org/10.1162/COLI_a_00146 . .

SS Weng , , , CK Liu . . Using text classification and multiple concepts to answer e-mails . . Expert Syst Appl , , 2004 . . 26 ( ( 4 ): ): 529 - - 543 . . DOI: 10.1016/j.eswa.2003.10.011 http://doi.org/10.1016/j.eswa.2003.10.011 . .

HC Yang , , , CH Lee , , , HW Hsiao . . Incorporating self- organizing map with text mining techniques for text hierarchy generation . . Appl Soft Comput , , 2015 . . 34 251 - - 259 . . DOI: 10.1016/j.asoc.2015.05.005 http://doi.org/10.1016/j.asoc.2015.05.005 . .

JJ Yao , , , B Cui , , , G Cong , , , 等 . . Evolutionary taxonomy construction from dynamic tag space . . World Wide Web , , 2012 . . 15 ( ( 5-6 ): ): 581 - - 602 . . DOI: 10.1007/s11280-011-0150-4 http://doi.org/10.1007/s11280-011-0150-4 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Domain adaptation in reinforcement learning: a comprehensive and systematic study

Towards sustainable adversarial training with successive perturbation generation

Advances and challenges in artificial intelligence text generation

A disk failure prediction model for multiple issues

Data-driven soft sensors in blast furnace ironmaking: a survey

Related Author

Amirfarhad FARHADI

Mitra MIRZAREZAEE

Arash SHARIFI

Mohammad TESHNEHLAB

Wei LIN

Lichuan LIAO

Bing LI

Peng YANG

Related Institution

Department of Control Engineering, K.N. Toosi University of Technology

Department of Computer Engineering, Science and Research Branch, Islamic Azad University

Fujian Provincial Key Laboratory of Big Data Mining and Applications, Fujian University of Technology

College of Economics and Management, Xi’an University of Technology

College of Computer Science and Mathematics, Fujian University of Technology

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰