DISCRIMINANT ANALYSIS OF THE TECHNICAL SHORT TEXTS
Authors:
1.
Baikal State University
(Doctor of Physics and Mathematics; Professor of the Department of Mathematical Methods and Digital Technologies)
2.
Baikal State University
(Postgraduate Student of the Department of Mathematical Methods and Digital Technologies)
3.
Irkutsk State University
(Candidate of Chemical Sciences; Assistant Professor of the Department Analytical Chemistry)
Type:
Article
Pages:
from 53
to 60
Status:
Published
Received:
05.04.2018
Accepted:
25.04.2018
Published:
25.04.2018
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.93
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.93
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
classification of short texts, defining the weight of terms, singular decomposition, discriminant analysis, Fisher elementary functions, k-nearest neighbor method
Abstract (English):
Today much attention is paid to processing textual information in order to form thematic groups and to systematize documents. This is stipulated by growing popularity of the Internet as a means of communication and requires to categorize short technical texts, which, in turn, is characterized by complexity of traditional approaches - preprocessing and digitization of documents and identification of "classifying" features. Specificity of the study at each stage is determined by the characteristics of the texts - small size, similar vocabulary, a large number of highly specialized symbols and signs, synonymity of terms.There has been suggested the procedure of preparing texts for analysis, reducing the dimensions of "term-document" matrix using singular decomposition method which allows to solve the problem of small-rank approximation of the original matrix. There are classification methods used such as k-nearest neighbors method and discriminant analysis based on Fisher elementary functions (texts on assignment of instruments was taken as an example). The Fisher classification procedure uses discriminant variables and the approach of maximizing the differences between classes to obtain the classification function. An object belongs to the class for which the value of classifying function is the greatest. There has been given assessment of the results obtained and the inadequate accuracy of classification when applying TF-IDF measure under experimental conditions. To improve the quality of classification, a combined method has been proposed to select words at the first step using TF-IDF measure. The dictionary of terms and phrases is to be used at the second stage for classifying texts. According to the obtained data, it has been offered to carry out classification by discriminant analysis and k-closest neighbors method. The proposed combined method is planned to be refined and upgraded in the future.
Today much attention is paid to processing textual information in order to form thematic groups and to systematize documents. This is stipulated by growing popularity of the Internet as a means of communication and requires to categorize short technical texts, which, in turn, is characterized by complexity of traditional approaches - preprocessing and digitization of documents and identification of "classifying" features. Specificity of the study at each stage is determined by the characteristics of the texts - small size, similar vocabulary, a large number of highly specialized symbols and signs, synonymity of terms.There has been suggested the procedure of preparing texts for analysis, reducing the dimensions of "term-document" matrix using singular decomposition method which allows to solve the problem of small-rank approximation of the original matrix. There are classification methods used such as k-nearest neighbors method and discriminant analysis based on Fisher elementary functions (texts on assignment of instruments was taken as an example). The Fisher classification procedure uses discriminant variables and the approach of maximizing the differences between classes to obtain the classification function. An object belongs to the class for which the value of classifying function is the greatest. There has been given assessment of the results obtained and the inadequate accuracy of classification when applying TF-IDF measure under experimental conditions. To improve the quality of classification, a combined method has been proposed to select words at the first step using TF-IDF measure. The dictionary of terms and phrases is to be used at the second stage for classifying texts. According to the obtained data, it has been offered to carry out classification by discriminant analysis and k-closest neighbors method. The proposed combined method is planned to be refined and upgraded in the future.
Keywords:
classification of short texts, defining the weight of terms, singular decomposition, discriminant analysis, Fisher elementary functions, k-nearest neighbor method
classification of short texts, defining the weight of terms, singular decomposition, discriminant analysis, Fisher elementary functions, k-nearest neighbor method
Введение В связи с развитием Интернета и применением его в качестве средства коммуникации или электронной коммерции появились специфические лингвистические объекты, представленные в виде коротких текстов (КТ) - новостные ленты, блоги, сообщения в социальных сетях, обзоры продукции и реклама [1]. Очень часто технические КТ встречаются в проектном деле. Все эти информационные объекты различаются по тематике, типу, смысловой и эмоциональной окраске, стилю и другим критериям. Большое количество разнообразных интернет-ресурсов, содержащих КТ, обусловливает необходимость их обработки и анализа, например, для создания тематических подборок, рубрикации документов, составления рейтингов, подбора контекстной рекламы и фильтрации спама [2]. Особый интерес для исследователей представляют КТ технической направленности [2, 3], которые содержатся в тематических форумах, тезисах научных работ, аннотациях, реферативно-библиографических изданиях, каталогах, рубрикаторах, базах данных (БД) оборудования и пр. Технические КТ, как и научно-техническая информация в целом [4], характеризуются рядом специфических особенностей: - информационная насыщенность текста и связанное с ней применение специальных терминов, символов и знаков, а также формул, таблиц, рисунков, чертежей, схем, графиков и пр.; - лаконичность и краткость изложения материала, использование сокращений слов и словосочетаний, замена часто повторяющихся слов аббревиатурами; - последовательная манера изложения, официально-деловой стиль. При систематизации технических КТ применение основных характеристик сходства - частоты терминов в документе, частоты документов, содержащих термин, - может быть недостаточно эффективным [1-3, 5]. Наибольшие трудности возникают при использовании инверсной частоты документов для слов-вхождений, меры TF - IDF (Term Frequency-Inverse Document Frequency): где - частота термина tj в документе di (Term Frequency); - частота документов с термином tj (Document Frequency); N - число документов. Сложность применения инверсной частоты обусловлена низкими значениями частоты термина в коротком документе, чаще всего . Небольшой размер текстов характеризуется смысловой насыщенностью, в связи с чем затруднено определение «базовых признаков» документов для определения сходства с учетом тематики текста, жанра, целевой аудитории. В данном случае возможно использование некоторых стилистических особенностей, например, сокращения слов, акценты на словах, а также применение признаков в виде знаков обозначения валют, процентов, математических формул и т. п. Короткие тексты, особенно тексты узкой направленности (narrow-domain short text), содержат часто повторяющиеся «штампы», распространенные речевые обороты, специфическую терминологию - «В статье представлены …», «Статья посвящена …», «Имеется много …», «Измеряемая величина» и пр. Как правило, 10-20 % слов из полного списка встречаются в каждом документе [3], т. е. совокупности КТ имеют сильные пересечения в используемом множестве слов. Разница между документами заключается не в выборе терминов, а в их пропорции. Это приводит к нестабильным и неточным результатам классификации текстов. Характер источников КТ (различных видов веб-приложений) определяет изменчивость, динамичность и разнообразие самих документов. Это обстоятельство усложняет формирование больших обучающих выборок и, следовательно, препятствует созданию точных моделей категоризации. Целью данной статьи является определение меток классов КТ узкой направленности, представляющих собой описание назначения датчиков давления. Для достижения поставленной цели необходимо решение следующих задач: - подобрать методы предварительной обработки текстов (стемминг, удаление стоп-слов и пр.); - провести классификацию документов; - проанализировать влияние методов преобразования данных о частоте встречаемости слов на результат категоризации. Для проведения классификации КТ была использована информация из БД оборудования (табл. 1). Таблица 1 База данных оборудования* Датчик давления Измеряемое давление Назначение датчиков давления ДДА Избыточное Датчики давления в амортизаторе ДДА предназначены для измерения избыточного давления; являются составной частью системы контроля параметров шасси СДАИ.406231.026 (система СКПШ) и эксплуатируются в ее составе. ДАЕ 002 Абсолютное Датчики давления ДАЕ 002 предназначены для измерения абсолютного давления и преобразования его в цифровой последовательный код. ДДВ 020 Избыточное Датчики давления ДАЕ 020 предназначены для измерения избыточного давления. Bm 1201 Избыточное Датчики давления частотные Bm 1201 предназначены для измерения избыточного давления и преобразования его в частоту. Bm 1202 Избыточное Датчики давления частотные Bm 1202 предназначены для измерения избыточного давления и преобразования его в частоту. Окончание табл. 1 Датчик давления Измеряемое давление Назначение датчиков давления PTE5000, P1Е, P1A Избыточное Датчики давления PTE5000, P1Е, P1A предназначены для измерения и непрерывного преобразования избыточного давления жидкостей и газов в нормированный выходной сигнал постоянного тока или напряжения. ДЛ 001 Избыточное Датчики давления ДЛ 001 предназначены для измерения избыточного давления, формирования и передачи параметров измеряемого давления в виде цифрового сигнала по интерфейсу RS-485. ДПС 025 Быстропеременное Датчики давления ДПС 025 предназначены для измерения быстропеременных давлений с амплитудой от 0,12 до 5,6 МПа при статическом давлении от 22,4 до 125 МПа в жидких и газообразных средах. Bm 222M Абсолютное Датчики абсолютного давления Bm 222M предназначены для измерения абсолютного давления газообразных сред. * Фрагмент. Минимальная длина текстов для анализа составляет 76 символов, максимальная - около 600 (табл. 1). Предобработка текстов Характер исследуемых КТ обусловливает определение значимых признаков для проведения классификации. Проблема наличия большого количества речевых «штампов» и слов общеупотребительной лексики решалась введением порога частот встречаемости слов [5, 6], т. е. из анализа удалялись самые редкие и наиболеее часто встречающиеся слова. Были определены значения порога частот встречаемости: минимальное - термин встречается менее чем в 1 % документов выборки, максимальное - термин встречается более чем в 65 % документов, - что адекватно отражает частотные характеристики наиболее значимых терминов конкретных текстов. Для анализа документов использовались лексемы, написанные буквами русского алфавита, соответственно, многочисленные цифровые обозначения приборов, латинские аббревиатуры, знаки препинания, символы, обозначения единиц измерения удалялись. В контексте решаемой задачи учитывалась специфическая синонимия терминов, например, «дифференциальное давление» - «разность давлений». Кроме того, из данных для анализа удалялись «стоп-слова», т. е. слова, не имеющие смысловой нагрузки для технических текстов (предлоги, союзы и пр.). В результате были получены тексты, на основе которых составлялась матрица частот вхождений слов «термин - документ». Для уменьшения размерности матрицы применялось сингулярное разложение (Singular Value Decomposition (SVD)) [7]: где C - исходная матрица «термин - документ» размерностью m × n; U - m × m-матрица, столбцы которой являются собственными ортогональными векторами матрицы CCT; VT - n × n-матрица, столбцы которой являются собственными ортогональными векторами матрицы CTC; W - диагональная m × n-матрица с диагональю из невозрастающих чисел σ1, …, σr, равных , т. е. , где λr - собственные значения матриц CCT и CTC; r - ранг матрицы С; CT - транспонированная матрица C. Для нахождения матрицы Cp, являющейся малоранговой аппроксимацией матрицы C [7, 8], по матрице W строилась матрица Wp с заменой нулями (r - p) наименьших значений. По полученным матрицам (U, VT, Wp) вычислялась матрица Cp = U Wp VT. Дискриминантный анализ Наличие большого количества входных переменных после «оцифровки» текстов дает возможность применения дискриминантного анализа, который связан с получением одной или нескольких функций, позволяющих отнести некоторый объект к одной из групп (классов). В классическом дискриминантном анализе [9, 10] классификация проводится с помощью линейной комбинации дискриминантных переменных (X1, X2, …, Xp). Линейная комбинация подбирается таким образом, чтобы максимизировать различия между классами и минимизировать дисперсию внутри классов. Для нахождения функции классификации применяется подход, основанный на определении функции плотности нормально распределенных классов где - вектор дискриминантных переменных [11, 12]. Предполагается, что объект относится к тому классу, для которого fk(X) имеет наибольшее значение. Формально эту процедуру можно описать следующим образом. Для p-мерного нормального распределения с вектором средних и ковариационной матрицей где - определитель ковариационной матрицы; - обратная матрица. После преобразования - удаления констант, логарифмирования [12] - получаем выражение Заменив векторы средних и ковариационную матрицу их оценками получим: Введем обозначения и где и - коэффициенты k-й классифицирующей функции i-го объекта (элементарные функции Фишера): Коэффициенты bki и bk0 определяются выражениями где n - общее число объектов всех классов; g - число классов; wij - элемент матрицы, обратной к внутригрупповой матрице сумм попарных произведений W. Классификация КТ выполнялась на основе матрицы частот слов «термин - документ» Cp с предварительным преобразованием данных: 1) без преобразования (бинарные значения: «1» - слово встречается в документе, «0» - не встречается); 2) с логарифмическим преобразованием; значения TF - IDF (определение веса термина с учетом его частоты во всех документах). Классы текстовых документов определялись как характеристики вида измеряемого давления описанных датчиков: 1-й класс - избыточное давление; 2-й класс - абсолютное давление; 3-й класс - динамическое давление; 4-й класс - без указания вида давления; 5-й класс - абсолютное, избыточное, дифференциальное давление. Результаты вычисления параметров функций классификации без преобразования исходных данных приведены в табл. 2. Таблица 2 Коэффициенты функций классификации текстов о назначении приборов Класс Переменная Класс «1» Класс «2» Класс «3» Класс «4» Класс «5» X1 166,8334 201,2125 34,576 56,7252 508,775 X2 -57,4644 -69,5657 -40,629 -14,5528 -159,745 X3 10,1298 -35,6508 44,397 12,0078 -42,786 Окончание табл. 2 Класс Переменная Класс «1» Класс «2» Класс «3» Класс «4» Класс «5» X4 3,5302 77,3975 -240,029 -20,7028 121,439 X5 -35,8392 -7,4478 -72,443 -12,5255 -31,731 X6 -15,2625 11,2764 -64,525 -6,2505 2,770 X7 -20,9876 -74,6343 11,447 -2,5727 -139,218 X8 -24,3535 -11,2977 -30,575 -0,0766 -43,848 X9 -42,0514 3,8375 -32,974 -11,6697 -53,158 X10 18,4265 42,2728 -24,321 -3,6249 70,392 Constant -6,6420 -11,2501 -18,513 -4,2123 -38,562 По полученным функциям можно вычислить классы для новых наблюдений. Например, для класса «1» функция классификации (табл. 2) будет иметь вид Максимальное вычисленное значение функции определяет принадлежность нового наблюдения к тому или иному классу. Точность классификации текстов с различными методами преобразования исходных данных показана в табл. 3. Таблица 3 Точность классификации текстов методом дискриминантного анализа и k-ближайших соседей Показатель Метод Абсолютные значения частот вхождения слов Бинарные значения Логарифмические преобразования Значения TF - IDF Дискриминантный анализ, % 90,0 85,0 95,0 40,0 Метод k-ближайших соседей, % 90,9 90,9 81,8 54,5 В результате анализа было установлено, что КТ о назначении приборов могут быть классифицированы с использованием классифицирующих функций Фишера. Удовлетворительные результаты (точность классификации 85 % и выше) получены с применением абсолютных значений частот слов, а также с бинарным логарифмическим преобразованием. Использование меры TF - IDF в условиях проведенного эксперимента дает недостаточную точность классификации (40 %). Метод k-ближайших соседей Для проведения классификации были подобраны методы, которые учитывают «размытость» границ классов, наличие большого количества нехарактерных, выпадающих точек [7, 13]. Так, в методе k-ближайших соседей (KNN) границы классов определяются локально, все пространство разбивается на сегменты смежных классов. В варианте с одним ближайшим соседом текст относится к определенному классу в зависимости от информации о его ближайшем соседе. При k > 1, в соответствии с гипотезой о пространственной компактности и классах, исследуемому документу будет присвоен тот же класс, что и документам обучающей выборки локальной области. Для классификации методом k-ближайших соседей использовались те же данные, с такими же зависимыми и независимыми переменными, что и в дискриминантном анализе. Количество ближайших соседей - 1, метрика расстояния - расстояние Евклида. Из результатов проведенных исследований (табл. 3) следует, что преобразование исходных частот слов имеет большое значение при классификации текстов о назначении приборов. Самая низкая точность классификации была получена при использовании оценки важности термина TF - IDF. Заключение Категоризация коротких текстов с применением технологий, основанных на использовании частотных характеристик терминов в текстах, требует учета специфичности анализируемых объектов. При определении признакового пространства текстов особое внимание уделяется наличию распространенных речевых оборотов, профессиональных синонимических терминов, цифровых символов, обозначений, представленных в виде сочетаний букв русского и латинского алфавитов. Влияние многочисленных речевых повторов уменьшалось введением порога встречаемости терминов. Специфическая синонимия терминов учитывалась при составлении словаря синонимов. Проблема наличия большого количества латинских обозначений решалась применением символов только русского алфавита. Выбор методов классификации определялся многомерностью входных переменных (по матрицам частот «термин - документ») и наличием категориальной выходной переменной - метки класса. При этом принималась во внимание размытость границ классов и присутствие нетипичных, выпадающих точек. В результате проведенного исследования получены неудовлетворительные результаты с применением преобразования данных TF - IDF. При расчете TF - IDF, в классическом варианте, веса терминов имеют высокие значения, если термин часто встречается в небольшом количестве текстов, и низкие значения, если термин редко встречается в тексте или встречается во многих текстах. В анализируемых текстах каждое слово, как правило, встречается один раз. При значение в большей степени зависит от частоты документов, содержащих термин . Для уменьшения эффекта «независимости» частоты термина в документе и улучшения результатов классификации необходимо применить комбинированный метод. На первом этапе произвести селекцию слов при помощи меры TF - IDF, на втором этапе применить словарь терминов и словосочетаний для классификации текстов. Далее, по полученным данным, провести классификацию методом дискриминантного анализа и k-ближайших соседей. В будущем планируется уточнение и доработка предлагаемого комбинированного метода.
1. Cagnina L., Errecalde M., Ingaramo D., Rosso P. A discrete particle swarm optimizer for clustering short text corpora // Proc. of the 3rd International Conference on Bioinspired Optimization Methods and their Applications (BIOMA08). Ljubljana, Slovenia, 2008. P. 93-10.
2. Ramírez-de-la-Rosa G., Montes-y-Gómez M., Solorio T., Villaseñor-Pineda L. A document is known by the company it keeps: neighborhood consensus for short text categorization // Lang Resources and Evaluation. 2012. Vol. 47. P. 127-149.
3. Pinto D., Rosso P., Jiménez H. A Self-Enriching Methodology for Clustering Narrow Domain Short Texts // Computer Journal. 2011. Vol. 54. No. 7. P. 1148-1165.
4. Kozhina M. N., Duskaeva L. R., Salimovskiy V. A. Stilistika russkogo yazyka. M.: FLINTA: Nauka, 2008. 464 s.
5. Barsegyan A. A., Kupriyanov M. S., Stepanenko V. V. Tehnologii analiza dannyh: Data Mining, Visual Mining, Text Mining, OLAP. SPb.: BHV-Peterburg, 2007. 384 s.
6. Borovskiy A. V., Rakovskaya E. E., Bisikalo A. L. Klasterizaciya informacii baz dannyh oborudovaniya // Izv. Baykal. gos. un-ta. 2016. T. 26. № 5. S. 805-810.
7. Manning K. D., Raghavan P., Shyutce H. Vvedenie v informacionnyy poisk. M.; SPb.; Kiev: Vil'yams, 2011. 520 s.
8. Verzhbickiy V. M. Vychislitel'naya lineynaya algebra: ucheb. posob. M.: Vyssh. shk., 2009. 351 s.
9. Kim Dzh.-O., M'yuller Ch. U., Klekka U. R. i dr. Faktornyy, diskriminantnyy i klasternyy analiz. M.: Finansy i statistika, 1989. 215 s.
10. Ayvazyan S. A., Buhshtaber V. M., Enyukov I. S. i dr. Prikladnaya statistika. Klassifikaciya i snizhenie razmernosti. M.: Finansy i statistika, 1989. 606 s.
11. Rao S. R. Lineynye statisticheskie metody i ih primeneniya. M.: Nauka, 1968. 548 s.
12. Bol'shakov A. A., Karimov R. N. Metody obrabotki mnogomernyh dannyh i vremennyh ryadov: ucheb. posob. M.: Goryachaya liniya-Telekom, 2007. 522 s.
13. Borovikov V. P. STATISTICA. Iskusstvo analiza dannyh na komp'yutere. SPb.: Piter, 2003. 686 s.
