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

Вестник Национальной академии наук Республики Казахстан  
 
 
   
16  
Каждый поток вычисляет функционал кластера 
 по формуле 
 
Далее работа идет в однопоточном режиме. 
Рассчитывается общий функционал  по формуле 
 
Если  
 
Переходим к пункту 6. Иначе заканчиваем работу. 
Среда  разработки.  Для  разработки  данного  программного  обеспечения  использовался 
системный блок, оснащенный: 
Материнская  плата - Gigabyte Technology Co., Ltd., Z77MX-D3H, Chipset Intel;  
CPU - Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz;  
GPU - NVIDIA GeForce GTX 660 сархитектуройKepler  (CC  3.0);  
Оперативная память - 16384 Mb; Жесткий диск - 2 Тб. 
Операционная система - MicrosoftWindows 7, Ultimate, 32 bit. 
Использовалась следующая среда разработки: 
Язык программирования - С++. 
Программная среда- Microsoft Visual Studio 2010. 
Выводы. В данной работе рассматривается кластеризация объектов по методу К-средних для 
больших  объемов  данных.  Существующие  прикладные  пакеты  по  статистике,  к  сожалению,  не 
позволяют решать задачи с большими объемами данных. Разработанные параллельные алгоритмы 
и  их  программная  реализация  сориентированы  именно  на  объемные  задачи.  Метод  К-средних 
является  достаточно  востребованным  в  различных  прикладных  проектах  и  реализация  данного 
метода  для  задач  с  большими  объемами  данных  может  быть  востребована  при  разработке 
различных проектов в биологии, генетике, социологии. 
 
ЛИТЕРАТУРА 
 
[1]
 
Уильямс Э. Параллельное программирование на С++ в действии. Москва, ДМК Пресс, 2012г 
[2]
 
Гергель  В.П.  Высокопроизводительные  вычисления  для  многоядерных  многопроцессорных  систем,  Нижний 
Новгород, Изд-во НГУ, 2010 
[3]
 
Богачев К.Ю., Основы параллельного программирования, Москва, Бином, 2003 
[4]
 
ЭхтерШ, Робертс Д. Многоядерное программирование. «Питер», 2010 
[5]
 
Вятченин Д. А. Нечёткие методы автоматической классификации. — Минск: Технопринт, 2004. — 219 с. 
 
REFERENCES 
 
[1]
 
Uiljams Je. Parallel'noeprogrammirovanienaС++ v dejstvii. Moskva, DMK Press, 2012  
[2]
 
Gergel  V.P.  Vysokoproizvoditel'nyevychislenijadljamnogojadernyhmnogoprocessornyhsistem,  NizhnijNovgorod, 
Izdatelstvo NGU, 2010 
[3]
 
BogachevK.Ju., Osnovyparallelnogoprogrammirovanija, Moskva, Binom, 2003  
[4]
 
JehterSh, Roberts D. Mnogojadernoeprogrammirovanie. «Piter», 2010  
[5]
 
Vjatchenin D. A. Nechjotkiemetodyavtomaticheskojklassifikacii. — Minsk: Tehnoprint, 2004. — 219 s. 
 
ПАРАЛЛЕЛЬДІ  АЛГОРИТМ ОРТАЛЫҚ ПРОЦЕССОРДЫҢ КӨП АҒЫНДЫЛЫҚ  ӘДІСТЕРІН 
КОМПЛЕКСТІ ҚОЛДАНЫС 
Н.Г. Литвиненко 
институт математики и математического моделирования НАН РК, Алматы, Казахстан 
 
Тірек  сөздер:  Параллельді  алгоритм,  графикалық  процессор,  кластерлік  талдау,  көп  ағындылық,  ең 
жақын көрші тәсілі. 
Аннотация:  Берілген мақалада көлемі 2 млн. жазбасы және 25-ке дейін көрсеткішері бар есептердің, ең 
жақын көрші (ЕЖК) кластеризация тәсілі арқылы,  шығару жолдары сүреттеледі. Мағлұматтардың көлемдері 
үлкен  болуына    байланысты,  есептерді  шығару  үшін  есептеуіш  графикалық  процессорлар  қолданылады. 
Параллельді    алгоритм  орталық  процессордың  көп  ағындылық   әдістерін  комплексті  қолданыс  астында 
пайдалана    отырып  және  берілгендерді  графикалық  процессор  арқылы  параллельді  өңдеу  мүмкіндіктері 
Microsoft Visual Studio 2010  ортасында, С++ тілінде жүзеге асырылды. Айтылмыш зерттеме ғылымның түрлі 
тармақтарында, мысалы биологияда, генетикада, социология және т.б. қолданыс табуы мүмкін. 
 
Поступила 09.09.2014 г. 
 

ISSN 1991-3494                                                              
№ 5. 2014 
 
 
17 
 
BULLETIN OF NATIONAL ACADEMY OF SCIENCES  
OF THE REPUBLIC OF KAZAKHSTAN 
ISSN 1991-3494 
Volume  5,   Number   5(2014),  17 – 20 
 
 
 
UDC 519.683; 519.684 
 
CLUSTERING OF LARGE AMOUNTS OF DATA BY THE 
COMPLETE LINKAGE METHOD IN MULTITHREADING MODE
 
V. Pospelova 
 
Institute of Mathematics and Mathematical Modelling, Almaty, Kazakhstan 
 
Key words: clustering of big data, complete-linkage method, multithreading. 
Abstract. In this paper version of the parallel algorithm and its implementation for solving the cluster analysis 
problems  by  the  method  of  complete  linkage  (MCL)  in  the  environment  of  multi-core  processors  are  considered. 
This  algorithm  is  implemented  in  software  code  written  in  C  #  in  Microsoft  Visual  Studio  2010  with  the  use  of 
multithreading.  Algorithm  and  its  implementation  are  designed  for  volume  tasks.  Estimated  volume:  up  to  300 
thousand records with the number of fields to 25. 
 
 
УДК 519.683; 519.684 
 
КЛАСТЕРИЗАЦИЯ БОЛЬШИХ ОБЪЕМОВ ДАННЫХ ПО МЕТОДУ 
ПОЛНОЙ СВЯЗИ В МУЛЬТИПОТОЧНОМ РЕЖИМЕ 
 
В. Поспелова 
Институт математики и математического моделирования, Алматы, Республика Казахстан 
 
Ключевые слова: кластеризация больших объемов данных, метод полной связи, мультипоточность. 
Аннотация.  В  текущей  работе  рассматривается  вариант  параллельного  алгоритма  и  его  программная 
реализация  для  решения  задач  кластерного  анализа  по  методу  полной  связи  (дальше  МПС)  в  среде 
многоядерных  процессоров.  Данный  алгоритм  реализован  в  программном  коде  на  языке  C#  в  среде 
MicrosoftVisualStudio  2010  с  использованием  средств  мультипоточности.    Алгоритм  и  его  реализация 
рассчитаны на объемные задачи. Предполагаемый объем данных: до 300 тыс. записей с количеством полей 
до 25. 
 
Работа выполнена при поддержке гранта 0741/ГФ МОН РК 
 
Кластеризация  данных  является  частной  задачей  интеллектуального  анализа  данных 
(DataMining),  главной  задачей  которой  является  объединение  объектов  в  небольшие  группы  по 
схожим признакам. Подобные объединения должны быть проведены с учетом схожести и отличий 
объектов,  степень  схожести  которых  определяется  расстоянием.  Главное  отличие  кластеризации 
данных от классификации заключается в том, что в кластеризации группы объектов определяются 
ее результатом, в то время как в класификации группы, к которым необходимо отнести объекты, 
заранее  определены.  Данное  различие  объясняет  интерес  ученых  к  использованию  алгоритмов 
кластеризации  для  исследования  в  прикладных  областях  науки,  так  как  позволяет  проводить 
распределение без обучающей информации (количество групп и сами группы заранее неизвестны).  
Современный  программный  рынок  уже  сегодня  предлагает  разнообразные  универсальные 
(STATISTICA,  SAS,  Minilab,  SPSSStatistics)  и  специализированные  (STADIA,  STATIT,  KNIME) 
пакеты для статистического анализа, частично решающие и задачи кластерного анализа. Однако ни 
те, ни другие не могут быть использованы для решения задач с большими объемами данных, часто 
возникающих  в  таких  прикладных  отраслях  науки,  как  генетика  и  социология.  Решение  задач 

Вестник Национальной академии наук Республики Казахстан  
 
 
   
18  
кластеризации  большого  объема  данных  позволяет  не  просто  разбить  объекты  на  группы 
(кластеры),  но  и  в  итоге выявить  связывающие  объекты  законы.  В  среднем  рынок  программного 
обеспечения  предлагает  обработку  порядка  14000-16000  записей  на  компьютере  средней 
мощности, однако этого явно недостаточно, так как перспективным является обработка от 100000 
до  1  млн  записей  без  особых  временных  затрат  (количество  характеристик  около  25).  Конечно 
стоит  учитывать,  что  популярный  алгоритм  k-средних  дает  возможность  продуктивной 
кластеризации  большего  объема  данных,  и  на  сегодня  он  успешно  реализован  в  большинстве 
статистических пакето и показывает хорошие результаты (например,STATISTICA). Однако нельзя 
сказать  что  данный  алгоритм  является  универсальным  и  подойдет  для  любой  задачи.  Поэтотому 
возникает  необходимость  разработки  алгоритмов  по  другим  методам  кластеризации  с  их 
дальнейшей реализацией в программном коде.  
В настоящее время над решением объемных задач кластерного анализа работают российские и 
зарубежные разработчики. Однако нам неизвестно на какой стадии находятся данные разработки, 
так  как  все  они  имеют  закрытый  характер  и,  скорее  всего,  будут  недоступны  для  массового 
использования.По  этим  причинам  целесообразной  и  весьма  перспективной  является  разработка 
прикладного пакета программ, ориентированного, во-первых, на большие объемы обрабатываемых 
данных, а, во-вторых, на решение конкретных прикладных задач. 
Эффективное решение задач кластерного анализа по методу МПСпредставляет определенный 
интерес для многих прикладных отраслей науки. Однако при работе с большими объемами данных 
возникает проблема с выбором инструментария, реализующих данный метод, для решения задач. 
Стандартных  программных  пакетов  для  работы  с  большими  объемами  задач  практически  нет.  В 
данной  работе  сделана  попытка  заполнить  этот  пробел,  так  как  интерес  рынка  к  данной  теме 
возрастает.  
Данная задача является комплексной, и для ее успешного решения необходимо: 
Найти  способы  уменьшения  количества  итераций,  необходимых  для  нахождения  соседних 
кластеров. 
Разработать эффективные параллельные алгоритмы. 
Как  можно  более  эффективно  использовать  технические  возможности  многоядерных 
процессоров.  
Постановка  задачи.Требуется  разработать  алгоритм  объединения  объектов  в  кластеры  и 
реализовать  его  в  программном  коде  по  методу  МПС.  Предполагаемый  объем  данных  может 
достигать 300 тысяч записей, количество характеристик может достигать 25.  
За расстояние между объектами a и b возьмём обычное Евклидово расстояние: 
 
Расстояние между кластерами P и Rпо методу МПС определяется формулой: 
 
При решении задач кластеризации необходимо задать ряд дополнительных условий, которые 
позволят контролировать поцесс кластеризации. Например: 
Ограничение  на  минимальное  количество  построенных  кластеров.  Построение  кластеров 
прекращается, как только количество кластеров становится меньше заданного числа N1. 
Ограничение  на  максимальное  расстояние  между  кластерами.  Работа  по  построению 
кластеров  прекращается,  если  расстояние  между  двумя  ближайшими  кластерами  становится 
больше заданного числа N2. 
Ограничение  на  максимальное  количество  объектов  кластера.  Выбранный  кластер  не 
подлежит объединению с другими, если количество объектов в нем больше заданного числа N3. 
Ограничение на максимальный размер кластера. Кластер не подлежит объединению с другими 
кластерами, если его диаметр превышает значение заданного числа N4. 
Так как решаемая задача представляет собой задачу с большим объемом данных, абсолютно 
логическим  является  отступление  от  стандартных  иерархических  методах  кластеризации,  где  на 
каждой  итерации  происходит  объединение  только  одной  пары  кластеров,  расстояние  между 

ISSN 1991-3494                                                              
№ 5. 2014 
 
 
19 
которыми  наименьшее.  Причина  подобного  отказа  ввиду  больших  временных  затрат  на 
вычисления при работе с большими объемами данных. В предлагаемом алгоритме рассматривается 
способ,  когда  на  очередной  итерации  происходит  объединение  не  одной  пары  кластеров,  а 
нескольких.Кластеризацию  данных  поставленной  задачи  будем  проводить  по  методу  МПС.  В 
данном  методе  расстояние  между  кластерами  будет  определяться  расстоянием  между  их  самими 
отдалёнными  членами.  На  первом  шаге  каждый  объект  принимается  за  отдельный  кластер. 
Анализируя результаты проведенных вычислений, объединяться в кластер у нас будут те объекты, 
расстояние между которыми наименьшее. После того как будет проведено некоторое количество 
таких  объединений,  будут  происходить  вычисления  расстояний  не  только  между  выбранным 
объектом  и  объектом,  но  и  между  выбранным  объектом  и  каждым  объектом  кластера.  Согласно 
полученным  расстояниям,  объединяться  будут  кластеры,  у  которых  расстояние  между 
максимально  уделенными  представителями  будет  наименьшим.  Включение  объекта  в  кластер 
будет  происходить  по  подобной  схеме  –  объект  будет  включен  в  состав  кластера,  расстояние  с 
максимально удаленным представителем которого у него будет наименьшим.  
Для  успешной  реализации  алгоритма  в  параллельном  режиме  нам  необходимо  обозначить 
следующие  параметры: 
–  количество  записей, 
–  количество  ядер  процессора, 
– 
количество потоков, 
– количество полей в записи. 
Описываемый  алгоритм  будет  работать  в  параллельном  режиме  с  большим  количеством 
данных.  Однако  не  будем  исключать  из  рассмотрения  варианты,  когда  необходимо  обработать 
малый  набор  данных  –  в  таком  случае  разумнее  использовать  однопоточный  режим.  Запишем 
следующее условие: 
Условие  определения  режима  работы  центрального  процессора:  если 
, 
процессор  работает  в  однопоточном  режиме,  если  же 
–  в  мультипоточном 
режиме.  
Следующим подготовительным к вычислениям шагу является определение числа потоков для 
центрального процессора по формуле: 
 
где  выбор  утроенного  значения  количества  ядер 
обосновывается  практическими 
результатами. Так как на момент начала 2013 года наибольшее распространение имели физические 
процессоры с 4 ядрами, положим 
. Получим  
 
После того, как все вспомогательные характеристики будут вычислены, имеющиеся данные и 
условия  расчета  передаются  в  оперативную  память.    Следующим  шагом  является  разделение 
данных на количество потоков (в нашем случае 12), и формирование задания для каждого потока. 
Потоки готовятся к работе. 
Дальнейшие итерации происходят по алгоритму классификации метода МПС:каждым потоком 
производится  вычисление  расстояний  между  всеми  возможными  парами  объектов,  включая 
объекты  кластеров,  после  чего  каждым  потоком  отбирается  около  100  пар,  расстояние  между 
которыми оказалось минимальным. Данные пары передаются на обработку в следующий цикл.  
Условно обозначим описанный цикл внутренним, а следующий – внешним. Задачей внешнего 
цикла является объединение всех направленных ему пар от всех потоков и нахождение среди них 
100 пар с наименьшим расстоянием, а так же объединение выбранных пар в кластеры. Так же цикл 
принимает  решение,  остановить  работу  или  повторить  итерацию.  Данное  решение  принимается, 
исходя из условий, представленных в параграфе «Постановка задачи», например, если количество 
построеных  кластеров  становится  меньше  заданного  числа  N1  (Ограничение  на  минимальное 
количество  построенных  кластеров).  В  случае,    если  формирование  кластеров  незакончено, 
откорректированные данные снова разделяются между потоками и направляются на обработку во 
внешний цикл. 
Заключение.Актуальным  для  любой  задачи  является  применения  алгоритма,  наиболее 
эффективно  справляющегося  с  ее  решением.  Напомним,  что  каждый  из  существующих  методов 

Вестник Национальной академии наук Республики Казахстан  
 
 
   
20  
кластеризации  имеет  свои  достоинства  и  недостатки  и  хорошо  справляется  с  решением  только 
узкого  круга  задач.  Поэтому  исследование  имеющихся  и    разработка  новых  алгоритмов  для 
решения  задач  кластерного  анализа  и  их  реализация  в  программном  коде  на  сегодня  является 
одним из перспективных направлений.  
 
ЛИТЕРАТУРА 
 
[1]
 
Jain A., Murty M., Flynn P. Data Clustering: A Review. // ACM Computing Surveys. 1999. Vol. 31, no. 3. 
[2]
 
Дюран Б., Оделл П. Кластерный анализ. Пер. с англ. Е.3.Демиденко под ред. и с предисл. А.Я.Боярского. - М.: 
Статистика, 1977. -128 с.: ил. 
[3]
 
Фленов М.Е. Библия С# (2-е издание, 2011), Санкт-Петербург: «БХВ-Петербург», 2011 
[4]
 
Шилдт Г. С# 4.0 полное руководство, Санкт-Петербург: «Печатный двор», 2011 
 
REFERENCES 
 
[1]
 
Jain A., Murty M., Flynn P. Data Clustering: A Review. // ACM Computing Surveys. 1999. Vol. 31, no. 3. 
[2]
 
Durand B., Odell P. Cluster analysis. - M.: Statistics, 1977. – p. 128. 
[3]
 
Flenov M.E. C # Bible (2nd edition, 2011), St. Petersburg: "BHV-Petersburg", 2011 
[4]
 
Shildt G. C # 4.0 complete guide St. Petersburg: "Printing House", 2011. 
 
В. Поспелова 
 
ГРАФИКАЛЫҚ  ПРОЦЕССТЕРДІ  ҚОЛДАНА  ОТЫРЫП,  ТОЛЫҚ  БАЙЛАНЫС  ӘДІСІ 
БОЙЫНШАКӨЛЕМДІ  МАҒЛҰМАТТАРЫ  БАР  КЛАСТЕРИЗАЦИЯ  ЕСЕПТЕРІН  ШЫҒАРУҒА 
КЕРЕКТІ ПАРАЛЛЕЛЬДІ АЛГОРИТМДЕРДІҢ ҚОЛДАНЫСЫ. 
 
Тiрек сөздер: үлкен көлемді мағлұматтарды кластеризациялау, толық байланыс әдіс, көп ағындылық. 
Аннотация. Берілген жұмыста көп ядролы процессор аймағындағы толық байланыс әдіс(ТБӘ) арқылы  
кластерлік  талдау  есептері  үшін,  параллельді    алгоритм  және  оның  жүзеге  асырылуы  қарастырылады. 
Берілген  алгоритм  көп  ағындылық  әдісін  колдана  отырып    Microsoft  Visual  Studio  2010    ортасында,  С++ 
тілінде  жүзеге  асырылды.  Алгоритм  және  оның  орындалуы  көлемді  есептерге  арналған.  Болжамалы 
айтылмыш көлемі: 300 мың жазба, 25  жиек көрсеткішер саны. 
Поступила 09.09.2014 г. 
 

ISSN 1991-3494                                                              
№ 5. 2014 
 
 
21 
BULLETIN OF NATIONAL ACADEMY OF SCIENCES  
OF THE REPUBLIC OF KAZAKHSTAN 
ISSN 1991-3494 
Volume  5,   Number   5(2014),  21 – 27 
 
 
УДК 517.957.6 
 
ANALYTICAL SOLUTION OF HEAT EQUATION  

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

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