Тип публикации: статья из журнала
Год издания: 2020
Идентификатор DOI: 10.25743/ICT.2020.25.3.011
Ключевые слова: кластеризация документов, концептуальное индексирование, таксономия, онтология, смешанное целочисленное программирование, NP-трудная задача, document clustering, Conceptual Indexing, taxonomy, ontology, mixed integer programming, NP-hard problem
Аннотация: Рассматривается проблема кластеризации - автоматического разбиения коллекции документов на группы, близкие по тематике. Предложен новый подход к концептуальному индексированию документов путем перехода от набора ключевых терминов к взвешенному множеству концептов некоторой иерархической модели знаний. Получаемая в результате применПоказать полностьюения данного метода семантическая матрица связей документов с концептами онтологии может быть использована в качестве матрицы данных для решения задачи кластерного анализа. Оригинальный подход к кластеризации сводится к формализации в виде NP-трудной задачи смешанного программирования, декомпозиции и поэтапному решению, снижающему ее трудоемкость Purpose. The purpose of this work is to develop a method for document clustering based on conceptual indexing with the help of knowledge taxonomy. Methodology. Solving the problem of document clustering involves two fundamental stages. The first stage is preprocessing of a text document and representing it as a data table suitable for subsequent application of data analysis methods. The second stage is actually the optimization of clustering algorithm, which allows achieving optimal partitioning of the document collection in order to achieve, on the one hand, compactness of clusters, on the other hand, distinctness of clusters. We suggest a new approach to conceptual indexing of documents by transformation of a set of key terms to a weighted set of concepts for a certain hierarchical knowledge model of the application domain. The semantic matrix of document relationships with taxonomy concepts obtained as a result of the approach can be used as a data matrix for solving the clustering problem. For this purpose, we propose an original approach that uses the formalization of an NP-hard mixed programming problem, decomposition, and step-by-step solution that reduces its complexity. Results. As an example of applying the proposed approach, we consider the problem of clustering of 120 documents using 20 features that are terminal concepts of taxonomy. The result of direct clustering across 10 clusters did not guarantee closeness to the optimum, which caused the need for decomposition. The decomposition was carried out according to a two-stage hierarchical scheme: the first stage is the allocation of 2 clusters, the second stage is a sequential 5-clustering of each of the subsets formed at the first stage. The final result of clustering with two-step decomposition was about 20 percent better than the original one. Findings. The results of calculations confirmed the prospects of an optimization approach for clustering documents using a semantic matrix of relationships and revealed computational problems. In particular, the necessity of developing special computing tools and improving the formal statements themselves for reducing the overall complexity of calculations was revealed
Журнал: Вычислительные технологии
Выпуск журнала: Т. 25, № 3
Номера страниц: 99-110
ISSN журнала: 15607534
Место издания: Новосибирск
Издатель: Федеральный исследовательский центр информационных и вычислительных технологий