Национальной академии наук республики казахстан

Вестник Национальной академии наук Республики Казахстан  
 
 
   
10  
правило 
i
R
,  т.е. 
)
,
(
|
)
,
(
|
2
1
2
1
j
j
i
i
i
i
y
y
y
x
x
x





.  Для  простоты  можно  говорить,  что  правило 
выполняется на паре 


2
1
, i
i
. 
Рассмотрим  множество  всех  таких  пар 


2
1
, i
i
,  на  которых  выполнено  одно  из  правил. 
Обозначим  это  множество 
I
,  и  пусть  его  мощность 
n
I

|
|
.  Отметим,  что  анализатор  Link 
Grammar  Parser  допускает  между  двумя  словами  наличие  только  одного  коннектора.  Поэтому 
будет выполняться не более, чем одно правило.  
Далее  пусть 
2
1
, n
n
  –  количество  коннекторов,  получающихся  в  результате  анализа 
предложений 
y
x,
  соответственно.  В  качестве  меры  похожести  двух  предложений  можно  ввести 
)
,
max(
/
)
,
(
2
1
0
n
n
n
y
x


  или 
)
/(
2
)
,
(
2
1
1
n
n
n
y
x



. Предложенный подход обобщает подход, 
используемый  в  базовом  алгоритме.  Более  точно,  базовый  алгоритм  учитывает  только 
инвариантные коннекторы, не принимая во внимание более сложную логику.  
Рассмотрим пример сравнения двух предложений на похожесть:  
 
            +-----Js----+ 
 +-Ss-+-MVp-+   +---Ds--+ 
 |    |     |   |       | 
he went.v to.r the institute.n 
 
            +-----Js----+                 
 +-Ss-+-MVp-+   +---Ds--+---Mp--+---J---+ 
 |    |     |   |       |       |       | 
he went.v to.r the institute.n of Hydrodynamics 
 
Легко видеть, что 
6
,
4
2
1


n
n
. Далее видим, что все четыре коннектора Ss, MVp, Ds, Js из 
первого  предложения  сохраняются  (инвариантны),  поэтому 
4

n
.  В  итоге  получаем 
3
/
2
6
/
4
)
6
,
4
max(
/
4
)
,
(
0



y
x

  и 
5
/
4
10
/
8
)
6
4
/(
4
2
)
,
(
1





y
x

. То есть мы видим, 
что эти меры близости различаются. 
В  заключение  отметим,  что  на  наши  исследования,  рассмотренные  в  данной  главе,  в 
значительной мере повлияли работы Лбова Г.С. [8] и Викентьева А.А. [9], в которых, в частности, 
рассматриваются различные меры близости между логическими формулами. 
6. Заключение 
Для демонстрации эффективности работы системы были произведены тестовые испытания на 
основе  базового  алгоритма.  Были  сформированы  десять  простых  запросов  из  области 
неорганической  химии.  По  каждому  запросу  были  загружены  списки  адресов  с  их  описанием, 
которые  поисковики  обычно  выдают  пользователю.  По  этим  коротким  описаниям  (сниппетам; 
англ.  snippet)  производилась  оценка  ресурса.  Для  сравнения  с  поисковой  системой  (а  именно  с 
системой Нигма.РФ, т.к. она переадресует запросы другим системам) была составлена статистика.  
Система  оставляла  релевантные  ссылки,  отбрасывая  нерелевантные  по  ее  мнению.  В  итоге 
выяснилось,  что  на  проведенных  тестах  в  среднем  из  100  ссылок,  полученных  из  поискового 
сервиса  Нигма.РФ,  система  выделяла  5-15  качественных  релевантных  ссылок,  около  5  ссылок 
система  ошибочно  принимала  за  релевантные  и  остальные  отбрасывала,  как  нерелевантные,  что 
соответствовало  действительности.  Это  показывает,  что  данная  система  смогла  произвести 
фильтрацию на хорошем уровне.  
Далее  было  проведено  сравнение  двух  методов  сопоставления  конструкций  естественного 
языка – базового (используемого в первоначальной версии системы iNetSearch) и нового (с учетом 
перефразирования  предложений),  описанного  в  работах  [9,10].  Запросы,  перефразированные 
варианты которых необходимо было найти, составлялись по различным тематикам. Источниками 
запросов  служили:  коллекция  научных  статей  более  чем  по  20-ти  темам  и  коллекция  текстов 

ISSN 1991-3494                                                              
№ 5. 2014 
 
 
11 
общеобразовательного  плана.  Для  оценки  качества  поиска  использовались  три  различные 
числовые  характеристики.  В  среднем  поисковая  система  стала  одобрять  меньше  нерелевантных 
документов  и  больше  релевантных.  С  другой  стороны  отметим,  что  несмотря  на  предпринятые 
очень  большие  усилия,  метод,  учитывающий  перефразирования,  позволил  улучшить  работу 
системы  iNetSearch,  но  незначительно.  Логические  методы,  описанные  в  данной  статье 
представляют собой дальнейшую серьезную проработку вопроса, но на практике детально они не 
тестировались.  
Несколько  слов  о  границах  применимости  методов.  Очевидно,  что  предложенные  методы 
применимы только к предложениям, которые достаточно корректно могут быть проанализированы 
системой  Link  Grammar  Parser.  То  есть  методы  основаны  на  предположении,  что  на  вход  ему 
подается  диаграмма  связей,  правильно  отражающая  связи  между  понятиями.  Отметим,  что  Link 
Grammar  Parser  не  всегда  строит  для  предложения  адекватную  диаграмму  связей.  Более  того,  в 
большинстве  случаев  он  строит  на  предложении  несколько  диаграмм  связей,  каждая  из  которых 
удовлетворяет  требованиям  к  диаграммам  и  потому  не  может  быть  отброшена.  Чаще  всего  это 
бывает  вызвано  тем,  что  в  предложении  имеет  место  частеречная  омонимия,  или  же  формально 
слова  можно  связать  друг  с  другом  по-разному,  так  что  предложение  получает  разную 
интерпретацию.  
Человек,  пользуясь  знаниями  о  предметной  области,  а  также  опытом,  подсказывающим  ему, 
какие  слова  в  каких  смысловых  связях  могут  или  не  могут  состоять,  чаще  всего  может 
интерпретировать  данную  синтаксическую  конструкцию  однозначно  и  выбрать  для  данного 
предложения  единственную  диаграмму  связей,  предложенную  Link  Grammar  Parser.  Однако  в 
самом анализаторе такие знания не заложены, вследствие чего он может выдать для предложения 
целый  список  диаграмм,  и  нельзя  знать  заранее,  какой  по  счету  будет  идти  «правильная» 
диаграмма (хотя чаще всего она выдается все-таки первой).  
Предложенные  методы  не  могут  отождествлять  перефразированные  предложения  в  том 
случае, если в сравниваемых предложениях содержатся формально разные системы понятий, или 
же  понятия  связаны  друг  с  другом  разными  семантико-синтаксическими  отношениями,  хотя 
предложения  могут  выражать  одну  и  ту  же  мысль.  В  этих  случаях  необходимо  привлечение 
дополнительных знаний о семантике слов, например, использование соответствующих баз знаний. 
 
ЛИТЕРАТУРA 
 
[1]
 
Salton G. Automatic Information Organization and Retrieval, 1968, 514 p. 
[2]
 
Лезин  Г.В.,  Тузов  В.А.  Семантический  анализ  текста  на  русском  языке:  семантико-синтаксическая  модель 
предложения  //  Экономико-математические  исследования:  математические  модели  и  информационные  технологии.  – 
СПб.: Наука, 2003. – Вып. 3. – C. 282–303. 
[3]
 
Батура  Т.В.,  Мурзин  Ф.А.  Машинно-ориентированные  логические  методы  отображения  семантики  текста  на 
естественном языке: моногр. / Институт систем информатики им. А.П. Ершова СО РАН. Новосибирск: Изд. НГТУ, 2008. 
248 с. 
[4]
 
Temperley D., Sleator D., Lafferty J. Link Grammar Documentation [Electronic resource].  – 1998. – Mode of access: 
http://www.link.cs.cmu.edu/link/dict/index.html (accessed 15 November 2012) 
[5]
 
Sleator  D.,  Temperley  D.  Parsing  English  with  a  Link  Grammar.  Pittsburgh:  School  of  Computer  Science  Carnegie 
Mellon University, 1991. – 93 p. 
[6]
 
Murzin  F.,  Perfliev  A.,  Shmanina  T.  Methods  of  syntactic  analysis  and  comparison  of  constructions  of  a  natural 
language oriented to use in search systems // Bull. Nov. Comp. Center, Comp. Science, 2010, Iss. 31, – P. 91-109. 
[7]
 
Перфильев А.А., Мурзин Ф.А., Шманина Т.В. Методы синтаксического анализа и сопоставления конструкций 
естественного  языка,  ориентированные  на  применение  в  информационно-поисковых  системах  //  Вестник  НГУ,  том  9, 
выпуск 4, 2011. – С 50-59. 
[8]
 
Лбов Г.С. Методы обработки разнотипных экспериментальных данных //  моногр. / Институт  математики СО 
АН. – Новосибирск: Изд. Наука, 1981. – 160 с. 
[9]
 
Викентьев А.А., Викентьев Р.А. О метриках для формул от разнотипных переменных и мерах опровержимости 
//  Труды  второй  международной  молодежной  школы-конференции  «Теория  и  численные  методы  решения  обратных  и 
некорректных  задач».  2011.  Часть  1.  –  С.  192-209.  [Электрон.  ресурс].  Режим  доступа:  http://semr.math.nsc.ru/v8/c182-
410.pdf (дата обращения: 18 августа 2014) 
 
REFERENCES 
 
[1]
 
Salton G. Automatic Information Organization and Retrieval, 1968, 514 p. 

Вестник Национальной академии наук Республики Казахстан  
 
 
   
12  
[2]
 
Lezin  G.V.,  Tuzov  V.A.  The  semantic  analysis  of  the  text  in  Russian:  semantico-syntactical  model  of  the  sentence// 
Economic-mathematical  researches:  mathematical  models  and  information  technologies.–  СПб.:  Наука,  2003.  –Is.  3.  – P.  282–
303. (in Russian) 
[3]
 
Batura  T.V.,  Murzin  F.A.  The  machine-oriented  logic  methods  of  representation  of  semantics  of  the  text  in  natural 
language  //  The  monograph  /  A.P.  Ershov  Institute  of  Informatics  Systems  SB  RAS.  –  Novosibirsk:  Publishing  Company  of 
NGTU, ISBN 978-5-7782-1138-4, 2008. – 248p. (in Russian) 
[4]
 
Temperley D., Sleator D., Lafferty J. Link Grammar Documentation [Electronic resource].  – 1998. – Mode of access: 
http://www.link.cs.cmu.edu/link/dict/index.html (accessed 15 November 2012) 
[5]
 
Sleator  D.,  Temperley  D.  Parsing  English  with  a  Link  Grammar.  Pittsburgh:  School  of  Computer  Science  Carnegie 
Mellon University, 1991. – 93 p. 
[6]
 
Murzin  F.,  Perfliev  A.,  Shmanina  T.  Methods  of  syntactic  analysis  and  comparison  of  constructions  of  a  natural 
language oriented to use in search systems // Bull. Nov. Comp. Center, Comp. Science, 2010, Iss. 31, – P. 91-109. 
[7]
 
Murzin  F.,  Perfliev  A.,  Shmanina  T.  Methods  of  syntactic  analysis  and  comparison  of  constructions  of  a  natural 
language oriented to use in search systems // Vestnik of Novosibirsk State Univ. Ser.:Information Technologies.  – Novosibirsk, 
2012. –Vol. 9, Is. 4. – P. 13-28. (in Russian) 
[8]
 
Lbov G.S. Methods of processing of polytypic experimental data // The monograph / Sobolev Institute of Mathematics 
SB RAS . – Novosibirsk: Nauka, 1981. – 160 p. (in Russian) 
[9]
 
Vikentiev A.A., Vikentiev R.A.  On the metrics  for formulas containing polytypic variables and measures of denyty // 
Proc.of  the  Second  International  Youth  School-Сonference  «Theory  and  numerical  methods  of  the  decision  of  inverse  and 
incorrect problems». 2011. Part 1. – P. 192-209. [Electronic resource]. – 1998. – Mode of access: http://semr.math.nsc.ru/v8/c182-
410.pdf (accessed 18 August 2014) (in Russian) 
 
ТАБИҒИ ТІЛДЕГІ СӨЙЛЕМДЕРДІҢ  ЖАҚЫНДЫҚ ДӘРЕЖЕСІН АНЫҚТАУ  
МАШИНАЛЫҚ-БАҒДАРЛАНҒАН ӘДІСІ 
Т.В. Батура
1
, Ф.А. Мурзин
1
, А.А. Перфильев
1
, 
Б.С. Байжанов
2
, М.В. Немченко
2
 
 
Тiрек  сөздер:  ақпаратты-іздестіру  жүйесі,  Link  Grammar  Parser,  синтаксистік  талдау, 
семантика,релеванттық. 
Аннотация: Негізгі қарастырылып отырған мәселе , мәтіннің құрылысына еніп,  барлау сұранысындағы 
мәтіннің  релевантына адекватты бағасын шығару алгоритмдерін құрастыру болып табылады. Берілген баға 
барлау сұранысына негізделген болуы және тек  тірек сөздермен, олардың жақын алысына  ғана шектелмеуі 
өте  маңызды.    Авторлар  Link  Grammar  Parser  программалық  жүйенің  шығу  кезінде  пайда  болатын  сөйлем 
сөздері  арасындағы    семантика-синтаксистік  қатынастарды  қолдануын  ұсынды.  Мақалада    сөйлемдердің 
табиғи тілге жақындық дәрежесі  екі  есептеу  алгоритмімен   суреттелді. Олардың екіншісі математикалық 
логикаға сүйеніп жасалынды.Бұл әдістер  ішінара iNetSearch ақпаратты-іздестіру жүйесінде қолданылды. 
 
Поступила 09.09.2014 г. 

ISSN 1991-3494                                                              
№ 5. 2014 
 
 
13 
BULLETIN OF NATIONAL ACADEMY OF SCIENCES  
OF THE REPUBLIC OF KAZAKHSTAN 
ISSN 1991-3494 
Volume  5,   Number   5(2014),  13 – 17 
 
 
 
UDC 519.683; 519.684 
 
PARALLEL ALGORITHM FOR MULTI-CORE PROCESSORS  
WITH USING K-MEANS METHOD FOR SOLVING 
CLUSTERIZATION PROBLEM 
 
N. Litvinenko 
n.litvinenko@inbox.ru 
Institute of mathematics and mathematical modelling, Committee of Science  
of the Ministry of Education and Science of the Republic of Kazakhstan, Almaty 
 
Key words:  Parallel algorithms, cluster analysis, multithreading, K-means method,multi-core processors. 
Abstract.  Parallel  algorithm  for  multi-core  processors  with  using  K-means  method  for  solving  clusterization 
problem is developed. This algorithm was implemented in source code on C++ in Microsoft Visual Studio 2010 with 
using multithreading. The maximum amount of data: up to 300 000 records with the number of indexes to 25.This 
development may have applications in various areas of science, for example, in genetics, biology,computer science, 
sociology e.t.c. 
 
 
УДК 519.683; 519.684 
 
МЕТОД К-СРЕДНИХ ДЛЯ БОЛЬШИХ ОБЪЕМОВ ДАННЫХ  
ДЛЯ РЕШЕНИЯ ЗАДАЧ КЛАСТЕРНОГО АНАЛИЗА  
С ПРИМЕНЕНИЕМ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ 
 
Н.Г. Литвиненко 
n.litvinenko@inbox.ru 
Институт математики и математического моделирования KН MOН РК, Алматы, Казахстан 
 
Ключевые слова: Параллельные алгоритмы, кластерный анализ, мультипоточность, метод К-средних, 
многоядерные процессоры. 
Аннотация.  Для  объемных  задач  кластеризации  по  методу  К-средних  разрабатывается  параллельный 
алгоритм для многоядерных процессоров. Данный алгоритм реализован в программном коде на языке C++ в 
среде  MicrosoftVisualStudio  2010  с  использованием  средств  мультипоточности.  Максимально  допустимый 
объем данных: до 300 тыс. записей с количеством показателей до 25. 
 
Работа выполнена при поддержке гранта 0741/ГФ МОН РК 
 
Введение.  Задача  кластеризации  является  объемной  многошаговой  вычислительной  задачей 
разбиения  множества  объектов  на  группы  (кластеры).  Существуют  различные  методы 
кластеризации,  которые  чаще  всего  определяются  на  стадии  построения  модели  исследуемого 
процесса.  Метод  К-средних  один  из  наиболее  признанных  методов  среди  разработчиков 
прикладных задач. Данный метод подразумевает, что исследователю априори известно количество 
кластеров.Метод  является  одним  из  самых  простых  в  реализации,  хотя  для  больших  данных 
общедоступных  программных  средств  нет.К-средних,  наверное,  самый  быстрый  из 
распространенных методов кластеризации. Однако метод имеет свои слабые места. Он не всегда является 
устойчивым по отношению к первоначальному выбору К-центров. Обычно проблема решается на стадии 
построения  модели  альтернативным  выбором  первоначальных  К-центров.  Новый  выбор  часто 
определяется  из  конкретных  условий  исследуемого  процесса.Другим  слабым  местом  данного  метода 

Вестник Национальной академии наук Республики Казахстан  
 
 
   
14  
является то, что находится обычно локальное оптимальное решение. Если исследователя не устраивает 
данное  локальное  решение,он  должен  решать  проблему  изменением  начальных  К-центров.  Третьим 
слабым местом является возможность возникновения на очередной итерации пустого кластера. Проблема 
решается на этапе разработки алгоритма различными способами. Например, осуществляется проверка на 
пустоту кластера и если пустой кластер существует, выбирается один из непустых кластеров и делится на 
два кластера, а пустой кластер удаляется. 
Общая  идея  построения кластеров  по  методу  К-средних  следующая.  На  очередной  итерации 
все  объекты  исследуемого  массива  относятся  к  ближайшему  центру  кластера,  построенного  на 
предыдущей  итерации.  Для  вновь  построенных  кластеров  пересчитываются  центры  тяжести. 
Вычисляется  изменение  функционала.  Если  функционал  уменьшается,  переходим  к  новой 
итерации. Когда функционал перестает уменьшаться, процесс заканчивается. 
В  данной  работе  рассматривается  задача  с  большим  количеством  данных  –  до  300тысяч 
записей  и  до  25  показателей.  Данная  задача  хорошо  распараллеливается.  Основная  идея 
распараллеливания  –  каждому  потоку  назначить  свое  подмножество  объектов  и  на  каждой 
итерации каждый поток распределяет свой набор объектов по кластерам. 
Аналогичные разработки. Метод К-средних был предложен практически одновременно в 1950 
году  Гуго  Штейнгаузом  и  Стюартом  Ллойдом.  Дальнейшее  развитие  метод  получил  в  виде  K-
means++,  в  котором  делается  попытка  автоматизировать  выбор  начальных  К-центров.  Широко 
известна нейросетевая реализация K-means. 
Метод  К-средних  реализован  во  многих  универсальных  прикладных  пакетах,  например 
STATISTICA,    SPSS.  Данные  пакеты  хорошо  ориентированы  на  пользователя,  позволяют  решать 
практически  все  встречающиеся  на  практике  задачи,  общедоступны,  недороги,  с  хорошей  и 
доступной  документацией,  с  хорошей  технической  поддержкой.  Имеется  много  технической 
литературы с хорошо и подробно разобранными примерами. Основным недостатком таких пакетов 
является  ограниченность  по  объемам  обрабатываемых  данных.  Как  правило,  все  эти  пакеты 
однопоточные и ресурсы рабочей станции по этой причине задействованы очень слабо. Серьезные 
объемные исследования с помощью данных пакетов проводить нельзя. 
Существуют  и  специализированные  пакеты.  Они,  как  правило,  возникают  при  разработке 
какого-либо  проекта.  Такие  пакеты  обычно  заточены  под  специфику  разрабатываемого  проекта, 
эти  пакеты  сложно  использовать  в  другом  проекте.  Техническая  документация  обычно 
отсутствует,  техническая  литература  отсутствует.  Пакеты  или  недоступны,  или  дороги. 
Техническая поддержка слабая.  
Из современных алгоритмов, реализованных или не реализованных в программном продукте 
можно отметить следующие: 
Алгоритм BIRCH 
BIRCH относится к числу дивизимныхалгоритмовDIANA (DivisiveAnalysis). К плюсам можно 
отнести  двухэтапную  кластеризацию,  возможность  обработки  очень  большого  числа  числовых 
данных,  работу  на  ограниченном  объеме  памяти.  Данный  алгоритм  при  расчетах  способен 
учитывать  неравномерное  распределение  данных  в  пространстве  и  считать  область  с  большей 
плотностью  за  один  кластер.Основные  минусы  алгоритма  –  работа  исключительно  с  числовыми 
данными,  выделение  кластеров  только  сферической  формы,  необходимость  задания  пороговых 
значений. 
Алгоритм CURE 
CURE  относится  к  числу  агломеративных  алгоритмов  AGNES  (Agglomerativenesting). 
Выполняет иерархическую кластеризацию с использованием множества идентифицирующих точек 
для  определения  объекта  в  кластер.  К  плюсам  можно  отнести  выделение  кластеров  сложной 
формы. К минусам – необходимость задания пороговых значений и количества кластеров. 
Алгоритм ROCK 
ROCK  относится  к  числу  агломеративных  алгоритмов  AGNES  (Agglomerativenesting). 
Алгоритм  сочетает  в  себе  все  хорошие  стороны  методов  k-means  и  ближайшего  соседа.  Имеет 
существенный недостаток, связанный с большими вычислительными затратами. 

жүктеу/скачать 6 Mb.

Достарыңызбен бөлісу: