Изучение и имитационное моделирование модифицированного агломеративного метода кластеризации
|
Введение 3
Постановка задачи 5
Глава 1. Агломеративные методы кластерного анализа 7
1.1. Кластерный анализ 7
1.2. Описание агломеративной кластеризации 9
1.3. Основные агломеративные методы кластеризации 10
Глава 2. Момент остановки агломеративного процесса кластеризации и очистка от шумов 14
2.1. Марковский момент остановки агломеративного процесса кластеризации 14
2.2. Чистка данных от шумов 23
2.3. Численные эксперименты 24
Глава 3. Дополнительное исследование невзвешенного центроидного метода 27
3.1. Модифицированное расстояние между кластерами 27
3.2. Двухэтапная кластеризация 34
Заключение 37
Список литературы 40
Приложение 41
Постановка задачи 5
Глава 1. Агломеративные методы кластерного анализа 7
1.1. Кластерный анализ 7
1.2. Описание агломеративной кластеризации 9
1.3. Основные агломеративные методы кластеризации 10
Глава 2. Момент остановки агломеративного процесса кластеризации и очистка от шумов 14
2.1. Марковский момент остановки агломеративного процесса кластеризации 14
2.2. Чистка данных от шумов 23
2.3. Численные эксперименты 24
Глава 3. Дополнительное исследование невзвешенного центроидного метода 27
3.1. Модифицированное расстояние между кластерами 27
3.2. Двухэтапная кластеризация 34
Заключение 37
Список литературы 40
Приложение 41
Иерархическая кластеризация — это методы кластерного анализа, производящие последовательное разделение объектов и выстраивающие иерархию разбиений. Эти методы можно разделить на две группы:
1. Агломеративные методы представляют каждый объект в виде отдельного кластера и последовательно объединяют их, пока все точки не окажутся в одном кластере.
2. Дивизивные методы, наоборот, сначала представляют все объекты в виде одного кластера, а затем разбивают его на более мелкие, и так пока каждый из объектов не окажется в отдельном кластере.
В общем случае, при использовании иерархических методов кластеризации, заранее не известно предпочтительное число кластеров. Результаты работы этих методов могут быть представлены различными способами, как правило используются дендрограммы — деревья, представляющие иерархию разбиений. Именно дендрограммы используются для определения момента остановки процесса и определения количества кластеров [1]. Однако такой подход является эвристическим. Для значительного класса задач подобное решение проблемы числа кластеров нельзя признать удовлетворительным. К одной из таких задач можно отнести проблему автоматической типологизации лейкоцитов при цитометрическом исследовании крови.
Лейкоциты (или белые кровяные тельца) — это клетки иммунной системы, их функция — защита внутренней среды организма от инородных патогенов [2]. Проточная цитометрия — это современная технология быстрого измерения характеристик клеток. Её развитие расширило возможности анализа иммунной системы, диагностики иммунодефицитных состояний, аутоиммунных заболеваний и т. д. [3]. Однако выделение групп клеток по выбранным параметрам происходит в "ручном" режиме при помощи программных средств для графического создания регионов, или гейтов (от англ. gate — ворота). Этот процесс называется гейтированием [3; 4]. С учетом высокой детализации клеточных популяций, такой метод является неэффективным и, кроме того, ненадёжным [5; 6], что привело к необходимости разработки автоматических способов для реализации этого процесса.
За последнее время проведено большое число исследований, описывающих специализированные методы кластеризации для типологизации различных субпопуляций лейкоцитов [7; 8]. Однако остаются нерешёнными проблемы, связанные с большим количеством "шумов" в данных, размерами кластеров и их плотностью. Были проведены исследования, показывающие недостатки некоторых популярных методов кластеризации применительно к этой задаче [9].
В выпускной квалификационной работе рассматривается модифицированный агломеративный метод кластеризации. Его изменение предназначено для решения этих проблем; так же проведены численные эксперименты с иерархическими методами кластеризации применительно к задаче выделения основных групп лейкоцитов.
Постановка задачи
Проточный цитофлуориметр — это прибор, позволяющий измерять оптические свойства одиночных биологических клеток в дисперсных средах; принцип его действия основан на измерении светорассеяния и специфического свечения частиц при их прохождении сквозь лазерный луч [3]. Детектор прямого светорассеяния (FSC, от англ. forward scatter) располагается по ходу лазерного луча и собирает излучение, рассеянное в пределах малых углов. Детектор бокового светорассеяния (SSC, от англ. side scatter) располагается под углом 90° относительно направления лазерного луча и собирает излучение, рассеянное в пределах больших углов. Значения FSC- сигнала позволяют судить о размере клетки, а величина SSC-сигнала — о сложности её внутреннего строения [3; 4].
По морфологическим признакам лейкоциты можно разделить на три основные группы: лимфоциты, моноциты и гранулоциты.
Лимфоциты и моноциты имеют простое несегментированное ядро и небольшую зернистость цитоплазмы, моноциты крупнее лимфоцитов. Гранулоциты (нейтрофилы, эозинофилы, базофилы) имеют более сложное строение, они содержат крупные сегментированные ядра, имеют специфическую зернистость цитоплазмы и т. д. [10]. Гранулоциты крупнее лимфоцитов и моноцитов. Типичное распределение лимфоцитов, моноцитов и гранулоцитов в осях FSC и SSC представлено на рис. 1. Важно отметить еще одну группу клеток, расположенную на этом рисунке внизу слева — дебрис (мелкие осколки клеток). Иногда эта группа может не встречаться в распределении лейкоцитов в осях FSC и SSC. Кроме того могут существовать аномальные распределения лейкоцитов, когда в этих осях можно выделить другие кластеры.
Задача состоит в исследовании и модифицировании агломеративного метода кластеризации, наиболее подходящего к решению практической задачи автоматической типологизации лейкоцитов по размеру клеток и сложности их строения (то есть по параметрам FSC и SSC) с учётом возможности встречи данных с аномальными распределениями.
Рис. 1: Распределение лейкоцитов в осях FSC и SSC
Для численных экспериментов и реализации алгоритма использовался программный код, написанный на языке программирования Python 3.7, с подключением библиотек NumPy, SciPy, Numba и с использованием оболочки PyCharm, разработанной компанией JetBrains на основе IntelliJ IDEA, и Colaboratory — бесплатной среды для Jupiter Notebook от компании Google. Код, реализующий функции, описывающие основные модификации, которые представлены в данной работе, можно найти в приложении.
1. Агломеративные методы представляют каждый объект в виде отдельного кластера и последовательно объединяют их, пока все точки не окажутся в одном кластере.
2. Дивизивные методы, наоборот, сначала представляют все объекты в виде одного кластера, а затем разбивают его на более мелкие, и так пока каждый из объектов не окажется в отдельном кластере.
В общем случае, при использовании иерархических методов кластеризации, заранее не известно предпочтительное число кластеров. Результаты работы этих методов могут быть представлены различными способами, как правило используются дендрограммы — деревья, представляющие иерархию разбиений. Именно дендрограммы используются для определения момента остановки процесса и определения количества кластеров [1]. Однако такой подход является эвристическим. Для значительного класса задач подобное решение проблемы числа кластеров нельзя признать удовлетворительным. К одной из таких задач можно отнести проблему автоматической типологизации лейкоцитов при цитометрическом исследовании крови.
Лейкоциты (или белые кровяные тельца) — это клетки иммунной системы, их функция — защита внутренней среды организма от инородных патогенов [2]. Проточная цитометрия — это современная технология быстрого измерения характеристик клеток. Её развитие расширило возможности анализа иммунной системы, диагностики иммунодефицитных состояний, аутоиммунных заболеваний и т. д. [3]. Однако выделение групп клеток по выбранным параметрам происходит в "ручном" режиме при помощи программных средств для графического создания регионов, или гейтов (от англ. gate — ворота). Этот процесс называется гейтированием [3; 4]. С учетом высокой детализации клеточных популяций, такой метод является неэффективным и, кроме того, ненадёжным [5; 6], что привело к необходимости разработки автоматических способов для реализации этого процесса.
За последнее время проведено большое число исследований, описывающих специализированные методы кластеризации для типологизации различных субпопуляций лейкоцитов [7; 8]. Однако остаются нерешёнными проблемы, связанные с большим количеством "шумов" в данных, размерами кластеров и их плотностью. Были проведены исследования, показывающие недостатки некоторых популярных методов кластеризации применительно к этой задаче [9].
В выпускной квалификационной работе рассматривается модифицированный агломеративный метод кластеризации. Его изменение предназначено для решения этих проблем; так же проведены численные эксперименты с иерархическими методами кластеризации применительно к задаче выделения основных групп лейкоцитов.
Постановка задачи
Проточный цитофлуориметр — это прибор, позволяющий измерять оптические свойства одиночных биологических клеток в дисперсных средах; принцип его действия основан на измерении светорассеяния и специфического свечения частиц при их прохождении сквозь лазерный луч [3]. Детектор прямого светорассеяния (FSC, от англ. forward scatter) располагается по ходу лазерного луча и собирает излучение, рассеянное в пределах малых углов. Детектор бокового светорассеяния (SSC, от англ. side scatter) располагается под углом 90° относительно направления лазерного луча и собирает излучение, рассеянное в пределах больших углов. Значения FSC- сигнала позволяют судить о размере клетки, а величина SSC-сигнала — о сложности её внутреннего строения [3; 4].
По морфологическим признакам лейкоциты можно разделить на три основные группы: лимфоциты, моноциты и гранулоциты.
Лимфоциты и моноциты имеют простое несегментированное ядро и небольшую зернистость цитоплазмы, моноциты крупнее лимфоцитов. Гранулоциты (нейтрофилы, эозинофилы, базофилы) имеют более сложное строение, они содержат крупные сегментированные ядра, имеют специфическую зернистость цитоплазмы и т. д. [10]. Гранулоциты крупнее лимфоцитов и моноцитов. Типичное распределение лимфоцитов, моноцитов и гранулоцитов в осях FSC и SSC представлено на рис. 1. Важно отметить еще одну группу клеток, расположенную на этом рисунке внизу слева — дебрис (мелкие осколки клеток). Иногда эта группа может не встречаться в распределении лейкоцитов в осях FSC и SSC. Кроме того могут существовать аномальные распределения лейкоцитов, когда в этих осях можно выделить другие кластеры.
Задача состоит в исследовании и модифицировании агломеративного метода кластеризации, наиболее подходящего к решению практической задачи автоматической типологизации лейкоцитов по размеру клеток и сложности их строения (то есть по параметрам FSC и SSC) с учётом возможности встречи данных с аномальными распределениями.
Рис. 1: Распределение лейкоцитов в осях FSC и SSC
Для численных экспериментов и реализации алгоритма использовался программный код, написанный на языке программирования Python 3.7, с подключением библиотек NumPy, SciPy, Numba и с использованием оболочки PyCharm, разработанной компанией JetBrains на основе IntelliJ IDEA, и Colaboratory — бесплатной среды для Jupiter Notebook от компании Google. Код, реализующий функции, описывающие основные модификации, которые представлены в данной работе, можно найти в приложении.
Подводя итоги, можем сделать следующие выводы.
Модифицированный центроидный метод может быть применён к задаче типологизации лейкоцитов по размеру клеток и сложности их строения, однако стоит отметить две проблемы.
Во-первых, этот метод имеет множество параметров, которые приходится выбирать эвристически: коэффициент тренда, влияющий на чувствительность аппроксимационно-оценочного критерия марковского момента остановки; радиус и предельное число точек окрестностей для поиска условно изолированных точек; коэффициент притяжения для определения "расстояния" между кластерами. Тем не менее в процессе численных экспериментов для некоторых из них были замечены некие закономерности, поэтому ожидается автоматизировать выбор части этих параметров.
Во-вторых, метод может неудовлетворительно работать с данными цитометрического исследования лейкоцитов у тех пациентов, которые имеют серьёзные патологии кроветворения. Однако цель работы заключается не в полной замене специалиста, а в предоставлении последнему удобного инструмента для анализа этих данных с целью сведения к минимуму субъективного фактора. Поэтому логичным будет предоставить анализ таких "аномальных" данных опытному специалисту.
Помимо невзвешенного центроидного метода интерес в рамках данной задачи представляет также метод одиночной связи. С предложенными в главе 2 модификациями он показал неплохие результаты при проведении численных экспериментов в рамках рассматриваемой задачи. Имеет смысл провести его отдельное подробное исследование.
Стоит отметить, что задача типологизации лейкоцитов по размеру клеток и сложности их строения всего лишь частный случай большой задачи типологизации лейкоцитов при цитометрическом исследовании крови [3; 4]. Поэтому в дальнейшем будет проведена работа по изучению модифицированного центроидного метода в рамках задачи кластеризации по другим параметрам, которые используются в проточной цитофлуорометрии при исследовании белых кровяных телец.
Модифицированный центроидный метод может быть применён к задаче типологизации лейкоцитов по размеру клеток и сложности их строения, однако стоит отметить две проблемы.
Во-первых, этот метод имеет множество параметров, которые приходится выбирать эвристически: коэффициент тренда, влияющий на чувствительность аппроксимационно-оценочного критерия марковского момента остановки; радиус и предельное число точек окрестностей для поиска условно изолированных точек; коэффициент притяжения для определения "расстояния" между кластерами. Тем не менее в процессе численных экспериментов для некоторых из них были замечены некие закономерности, поэтому ожидается автоматизировать выбор части этих параметров.
Во-вторых, метод может неудовлетворительно работать с данными цитометрического исследования лейкоцитов у тех пациентов, которые имеют серьёзные патологии кроветворения. Однако цель работы заключается не в полной замене специалиста, а в предоставлении последнему удобного инструмента для анализа этих данных с целью сведения к минимуму субъективного фактора. Поэтому логичным будет предоставить анализ таких "аномальных" данных опытному специалисту.
Помимо невзвешенного центроидного метода интерес в рамках данной задачи представляет также метод одиночной связи. С предложенными в главе 2 модификациями он показал неплохие результаты при проведении численных экспериментов в рамках рассматриваемой задачи. Имеет смысл провести его отдельное подробное исследование.
Стоит отметить, что задача типологизации лейкоцитов по размеру клеток и сложности их строения всего лишь частный случай большой задачи типологизации лейкоцитов при цитометрическом исследовании крови [3; 4]. Поэтому в дальнейшем будет проведена работа по изучению модифицированного центроидного метода в рамках задачи кластеризации по другим параметрам, которые используются в проточной цитофлуорометрии при исследовании белых кровяных телец.
