Нечеткая кластеризация

Нечеткая кластеризация (также называемая мягкой кластеризацией или мягкими k -средними ) — это форма кластеризации, в которой каждая точка данных может принадлежать более чем одному кластеру.

Кластеризация или кластерный анализ включает в себя распределение точек данных по кластерам таким образом, чтобы элементы в одном кластере были максимально похожими, а элементы, принадлежащие разным кластерам, были максимально разными. Кластеры идентифицируются с помощью мер сходства. Эти меры сходства включают расстояние, связность и интенсивность. Различные меры сходства могут быть выбраны на основе данных или приложения. ^[1]

Сравнение с жесткой кластеризацией [ править ]

При нечеткой кластеризации (также известной как жесткая кластеризация) данные делятся на отдельные кластеры, где каждая точка данных может принадлежать только одному кластеру. При нечеткой кластеризации точки данных потенциально могут принадлежать нескольким кластерам. Например, яблоко может быть красным или зеленым (жесткая кластеризация), но яблоко также может быть красным И зеленым (нечеткая кластеризация). Здесь яблоко может быть в определенной степени красным, а также в определенной степени зеленым. Вместо того, чтобы яблоко принадлежало зеленому [зеленый = 1], а не красному [красный = 0], яблоко может принадлежать зеленому [зеленый = 0,5] и красному [красный = 0,5]. Эти значения нормированы между 0 и 1; однако они не представляют вероятности, поэтому не обязательно, чтобы сумма этих двух значений составляла 1.

Членство [ править ]

Каждой точке данных (тегам) присваиваются уровни членства. Эти оценки членства указывают степень принадлежности точек данных каждому кластеру. Таким образом, точки на краю кластера с более низкими оценками принадлежности могут находиться в кластере в меньшей степени, чем точки в центре кластера.

- средних Нечеткая кластеризация C

Одним из наиболее широко используемых алгоритмов нечеткой кластеризации является алгоритм нечеткой кластеризации C-средних (FCM).

История [ править ]

Кластеризация нечетких c-средних (FCM) была разработана Дж. К. Данном в 1973 году. ^[2] и улучшен JC Bezdek в 1981 году. ^[3]

Общее описание [ править ]

Алгоритм нечетких c -средних очень похож на алгоритм k -средних :

Выберите количество кластеров .
Назначьте коэффициенты случайным образом каждой точке данных для нахождения в кластерах.
Повторяйте до тех пор, пока алгоритм не сойдётся (т. е. изменение коэффициентов между двумя итерациями не превысит $\varepsilon$ $\varepsilon$ , заданный порог чувствительности):
- Вычислите центроид для каждого кластера (показано ниже).
- Для каждой точки данных вычислите ее коэффициенты нахождения в кластерах.

Центроид [ править ]

Любая точка x имеет набор коэффициентов, задающих степень нахождения в k -м кластере w _k ( x ). При использовании нечетких c -средних центр тяжести кластера представляет собой среднее значение всех точек, взвешенное по степени их принадлежности к кластеру, или, математически,

$c_{k}={{\sum _{x}{w_{k}(x)}^{m}x} \over {\sum _{x}{w_{k}(x)}^{m}}},$

где m — гиперпараметр, который определяет, насколько нечетким будет кластер. Чем оно выше, тем более размытым будет кластер в конечном итоге.

Алгоритм [ править ]

Алгоритм FCM пытается разделить конечный набор $n$ элементы $X=\{\mathbf {x} _{1},...,\mathbf {x} _{n}\}$ в совокупность c нечетких кластеров по некоторому заданному критерию.

Учитывая конечный набор данных, алгоритм возвращает список $c$ кластерные центры $C=\{\mathbf {c} _{1},...,\mathbf {c} _{c}\}$ и матрица разделов

$W=w_{i,j}\in [0,1],\;i=1,...,n,\;j=1,...,c$ , где каждый элемент, $w_{ij}$ , рассказываетстепень, в которой элемент, $\mathbf {x} _{i}$ , принадлежит кластеру $\mathbf {c} _{j}$ .

FCM стремится минимизировать целевую функцию:

J(W,C)=\sum _{i=1}^{n}\sum _{j=1}^{c}w_{ij}^{m}\left\|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|^{2}

,

где:

w_{ij}={\frac {1}{\sum _{k=1}^{c}\left({\frac {\left\|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|}{\left\|\mathbf {x} _{i}-\mathbf {c} _{k}\right\|}}\right)^{\frac {2}{m-1}}}}

.

с кластеризацией K средних - Сравнение

Кластеризация K-средних также пытается минимизировать целевую функцию, показанную выше, за исключением того, что в K-средних значения членства равны нулю или единице и не могут принимать промежуточные значения, т.е. $w_{ij}\in \{0,1\}$ . В нечетких C-средних степень нечеткости параметризуется выражением $m\in (1,\infty )$ , где большее $m$ приводит к более нечетким кластерам. В пределе $m\rightarrow 1$ , членство, $w_{ij}$ , сходятся к 0 или 1, а цель нечетких C-средних совпадает с целью K-средних. В отсутствие экспериментов или знаний предметной области, $m$ обычно устанавливается равным 2. Алгоритм также минимизирует внутрикластерную дисперсию, но имеет те же проблемы, что и «k»-средние; минимум является локальным минимумом, и результаты зависят от первоначального выбора весов.

Реализация [ править ]

Существует несколько общедоступных реализаций этого алгоритма. ^[4]^[5]

Связанные алгоритмы [ править ]

Нечеткие C-средние (FCM) с автоматически определяемым количеством кластеров могут повысить точность обнаружения. ^[6] Использование смеси гауссиан вместе с алгоритмом максимизации ожидания является более статистически формализованным методом, который включает в себя некоторые из этих идей: частичное членство в классах.

Пример [ править ]

Чтобы лучше понять этот принцип, ниже по оси x приведен классический пример одномерных данных.

Этот набор данных можно традиционно сгруппировать в два кластера. При выборе порога на оси X данные разделяются на два кластера. Полученные кластеры помечены буквами «A» и «B», как показано на следующем изображении. Таким образом, каждая точка, принадлежащая набору данных, будет иметь коэффициент принадлежности 1 или 0. Этот коэффициент принадлежности каждой соответствующей точки данных представлен включением оси Y.

При нечеткой кластеризации каждая точка данных может принадлежать нескольким кластерам. Если уменьшить определение коэффициентов принадлежности со строго 1 или 0, эти значения могут варьироваться от любого значения от 1 до 0. На следующем изображении показан набор данных из предыдущей кластеризации, но теперь применяется нечеткая кластеризация c-средними. Во-первых, может быть сгенерировано новое пороговое значение, определяющее два кластера. Затем новые коэффициенты членства для каждой точки данных генерируются на основе центроидов кластеров, а также расстояния от каждого центроида кластера.

Как можно видеть, средняя точка данных принадлежит кластеру A и кластеру B. Значение 0,3 — это коэффициент принадлежности этой точки данных для кластера A. ^[7]

Приложения [ править ]

Проблемы кластеризации находят применение в науках о поверхности, биологии, медицине, психологии, экономике и многих других дисциплинах. ^[8]

Биоинформатика [ править ]

В области биоинформатики кластеризация используется для ряда приложений. Одно из применений - метод распознавания образов для анализа данных экспрессии генов на основе данных секвенирования РНК или других технологий. ^[9] В этом случае гены со схожими паттернами экспрессии группируются в один кластер, а разные кластеры демонстрируют разные, хорошо разделенные паттерны экспрессии. Использование кластеризации может дать представление о функции и регуляции генов. ^[8] Поскольку нечеткая кластеризация позволяет генам принадлежать более чем к одному кластеру, она позволяет идентифицировать гены, которые условно совместно регулируются или совместно экспрессируются. ^[10] Например, на один ген может действовать более одного транскрипционного фактора , и один ген может кодировать белок, выполняющий более чем одну функцию. Таким образом, нечеткая кластеризация является более подходящей, чем жесткая кластеризация.

Анализ изображения [ править ]

Нечеткие c-средства были очень важным инструментом для обработки изображений при кластеризации объектов на изображении. В 1970-х годах математики ввели пространственный термин в алгоритм FCM, чтобы повысить точность кластеризации в условиях шума. ^[11] Кроме того, алгоритмы FCM использовались для различения различных действий с использованием функций на основе изображений, таких как моменты Ху и моменты Цернике. ^[12] Альтернативно, модель нечеткой логики может быть описана на нечетких множествах , которые определены для трех компонентов цветового пространства HSL HSL и HSV ; Функции принадлежности предназначены для описания цветов, следуя человеческой интуиции в идентификации цвета. ^[13]

Маркетинг [ править ]

В маркетинге клиенты могут быть сгруппированы в нечеткие кластеры на основе их потребностей, выбора бренда, психографических профилей или других разделов, связанных с маркетингом. ^{[ нужна ссылка ]}

Пример обработки изображения [ править ]

Сегментация изображений с использованием алгоритмов кластеризации k-средних уже давно используется для распознавания образов, обнаружения объектов и медицинской визуализации. Однако из-за ограничений реального мира, таких как шум, затенение и различия в камерах, традиционная жесткая кластеризация часто не может надежно выполнять задачи обработки изображений, как указано выше. ^{[ нужна ссылка ]} Нечеткая кластеризация была предложена как более применимый алгоритм для решения этих задач. Данное изображение в оттенках серого подверглось нечеткой кластеризации в Matlab. ^[14] Исходное изображение видно рядом с кластерным изображением. Цвета используются для визуального представления трех отдельных кластеров, используемых для определения принадлежности каждого пикселя. Ниже приведена диаграмма, определяющая нечеткие коэффициенты принадлежности соответствующих им значений интенсивности.

В зависимости от приложения, для которого должны использоваться коэффициенты нечеткой кластеризации, к изображениям RGB могут применяться различные методы предварительной обработки . Преобразование RGB в HCL является обычной практикой. ^[15]

См. также [ править ]

ПЛАМЯ Кластеризация
Кластерный анализ
Алгоритм максимизации ожидания (аналогичный, но более статистически формализованный метод)

Ссылки [ править ]

^ «Нечеткая кластеризация» . ссылка.wolfram.com . Проверено 26 апреля 2016 г.
^ Данн, Джей Си (1 января 1973 г.). «Нечеткий родственник процесса ISODATA и его использование для обнаружения компактных хорошо разделенных кластеров». Журнал кибернетики . 3 (3): 32–57. дои : 10.1080/01969727308546046 . ISSN 0022-0280 .
^ Бездек, Джеймс К. (1981). Распознавание образов с помощью алгоритмов нечеткой целевой функции . ISBN 0-306-40671-3 .
^ Алобайд, Ахмад, нечеткие средства: нечеткие c-средства согласно исследовательской работе Джеймса К. Бездека и др. al , получено 18 января 2023 г.
^ Диас, Мэдсон, fuzzy-c-means: простая реализация алгоритма Fuzzy C-means на Python. , получено 18 января 2023 г.
^ Саид: Э Эль-Хами; Ровайда А Садек; Мохамед Эль-Хореби (октябрь 2015 г.). «Эффективное обнаружение массы мозга с помощью адаптивного нечеткого C-среднего на основе кластеризации и определения порога». Международная конференция IEEE по приложениям обработки сигналов и изображений (ICSIPA) , 2015 г.: 429–433.
^ «Кластеризация — нечеткие C-средства» . home.deib.polimi.it . Проверено 1 мая 2017 г.
^ Jump up to: Перейти обратно: ^а ^б Бен-Дор, Амир; Шамир, Рон; Яхини, Зоар (1 октября 1999 г.). «Кластеризация паттернов экспрессии генов». Журнал вычислительной биологии . 6 (3–4): 281–297. CiteSeerX 10.1.1.34.5341 . дои : 10.1089/106652799318274 . ISSN 1066-5277 . ПМИД 10582567 .
^ Валафар, Фарамарз (1 декабря 2002 г.). «Методы распознавания образов при анализе данных микрочипов». Анналы Нью-Йоркской академии наук . 980 (1): 41–64. Бибкод : 2002NYASA.980...41В . CiteSeerX 10.1.1.199.6445 . дои : 10.1111/j.1749-6632.2002.tb04888.x . ISSN 1749-6632 . ПМИД 12594081 . S2CID 343093 .
^ Валафар Ф. Методы распознавания образов при анализе данных микрочипов. Анналы Нью-Йоркской академии наук. 1 декабря 2002 г.; 980(1): 41-64.
^ Ахмед, Мохамед Н.; Ямани, Самех М.; Мохамед, Невин; Фараг, Али А .; Мориарти, Томас (2002). «Модифицированный алгоритм нечетких C-средних для оценки поля смещения и сегментации данных МРТ» (PDF) . Транзакции IEEE по медицинской визуализации . 21 (3): 193–199. CiteSeerX 10.1.1.331.9742 . дои : 10.1109/42.996338 . ПМИД 11989844 . S2CID 8480349 . Архивировано из оригинала (PDF) 2 октября 2011 г. Проверено 2 октября 2011 г. .
^ Банерджи, Танви (2014). «Распознавание дневной или ночной активности по видео с использованием методов нечеткой кластеризации». Транзакции IEEE в нечетких системах . 22 (3): 483–493. CiteSeerX 10.1.1.652.2819 . дои : 10.1109/TFUZZ.2013.2260756 . S2CID 11606344 .
^ Алиреза, Кашани; Кашани, Амир; Милани, Наргесс; Ахлаги, Пейман; Хезри, Каве (2008). «Надежная классификация цветов с использованием нечетких рассуждений и генетических алгоритмов в футбольных лигах RoboCup». RoboCup 2007: XI чемпионат мира по футболу среди роботов . Конспекты лекций по информатике. Том. 5001. стр. 548–555. дои : 10.1007/978-3-540-68847-1_59 . ISBN 978-3-540-68846-4 . {{cite book}}: |journal= игнорируется ( помогите )
^ «Нечеткая кластеризация — MATLAB и Simulink» . www.mathworks.com . Проверено 3 мая 2017 г.
^ Лекка, Паола (2011). Системные подходы в биоинформатике и вычислительной системной биологии . IGI Global. п. 9. ISBN 9781613504369 .

[1] «Нечеткая кластеризация» . ссылка.wolfram.com . Проверено 26 апреля 2016 г.

[2] Данн, Джей Си (1 января 1973 г.). «Нечеткий родственник процесса ISODATA и его использование для обнаружения компактных хорошо разделенных кластеров». Журнал кибернетики . 3 (3): 32–57. дои : 10.1080/01969727308546046 . ISSN 0022-0280 .

[3] Бездек, Джеймс К. (1981). Распознавание образов с помощью алгоритмов нечеткой целевой функции . ISBN 0-306-40671-3 .

[4] Алобайд, Ахмад, нечеткие средства: нечеткие c-средства согласно исследовательской работе Джеймса К. Бездека и др. al , получено 18 января 2023 г.

[5] Диас, Мэдсон, fuzzy-c-means: простая реализация алгоритма Fuzzy C-means на Python. , получено 18 января 2023 г.

[6] Саид: Э Эль-Хами; Ровайда А Садек; Мохамед Эль-Хореби (октябрь 2015 г.). «Эффективное обнаружение массы мозга с помощью адаптивного нечеткого C-среднего на основе кластеризации и определения порога». Международная конференция IEEE по приложениям обработки сигналов и изображений (ICSIPA) , 2015 г.: 429–433.

[7] «Кластеризация — нечеткие C-средства» . home.deib.polimi.it . Проверено 1 мая 2017 г.

[:0-8] Jump up to: Перейти обратно: ^а ^б Бен-Дор, Амир; Шамир, Рон; Яхини, Зоар (1 октября 1999 г.). «Кластеризация паттернов экспрессии генов». Журнал вычислительной биологии . 6 (3–4): 281–297. CiteSeerX 10.1.1.34.5341 . дои : 10.1089/106652799318274 . ISSN 1066-5277 . ПМИД 10582567 .

[9] Валафар, Фарамарз (1 декабря 2002 г.). «Методы распознавания образов при анализе данных микрочипов». Анналы Нью-Йоркской академии наук . 980 (1): 41–64. Бибкод : 2002NYASA.980...41В . CiteSeerX 10.1.1.199.6445 . дои : 10.1111/j.1749-6632.2002.tb04888.x . ISSN 1749-6632 . ПМИД 12594081 . S2CID 343093 .

[10] Валафар Ф. Методы распознавания образов при анализе данных микрочипов. Анналы Нью-Йоркской академии наук. 1 декабря 2002 г.; 980(1): 41-64.

[fuzzy_c_means-11] Ахмед, Мохамед Н.; Ямани, Самех М.; Мохамед, Невин; Фараг, Али А .; Мориарти, Томас (2002). «Модифицированный алгоритм нечетких C-средних для оценки поля смещения и сегментации данных МРТ» (PDF) . Транзакции IEEE по медицинской визуализации . 21 (3): 193–199. CiteSeerX 10.1.1.331.9742 . дои : 10.1109/42.996338 . ПМИД 11989844 . S2CID 8480349 . Архивировано из оригинала (PDF) 2 октября 2011 г. Проверено 2 октября 2011 г. .

[12] Банерджи, Танви (2014). «Распознавание дневной или ночной активности по видео с использованием методов нечеткой кластеризации». Транзакции IEEE в нечетких системах . 22 (3): 483–493. CiteSeerX 10.1.1.652.2819 . дои : 10.1109/TFUZZ.2013.2260756 . S2CID 11606344 .

[fuzzyset-13] Алиреза, Кашани; Кашани, Амир; Милани, Наргесс; Ахлаги, Пейман; Хезри, Каве (2008). «Надежная классификация цветов с использованием нечетких рассуждений и генетических алгоритмов в футбольных лигах RoboCup». RoboCup 2007: XI чемпионат мира по футболу среди роботов . Конспекты лекций по информатике. Том. 5001. стр. 548–555. дои : 10.1007/978-3-540-68847-1_59 . ISBN 978-3-540-68846-4 . {{cite book}}: |journal= игнорируется ( помогите )

[14] «Нечеткая кластеризация — MATLAB и Simulink» . www.mathworks.com . Проверено 3 мая 2017 г.

[15] Лекка, Паола (2011). Системные подходы в биоинформатике и вычислительной системной биологии . IGI Global. п. 9. ISBN 9781613504369 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]