Тема Системы линейных уравнений
Equation Section (Next)Тема 3 Метрические пространства и некоторые способы статистической обработки данных
жүктеу/скачать 3.13 Mb.
|
- Бұл бет үшін навигация:
- Методы иерархической классификации
- 3Введение и определения. Базовая модель.
Equation Section (Next)Тема 3 Метрические пространства и некоторые способы статистической обработки данныхВекторное пространство U называется нормированным, если для каждого принадлежащего ему вектора а существует такое действительное число |a| (норма, абсолютная величина, модуль вектора а), что из a=b следует |a|=|b| и для любых выполнены следующие условия (аксиомы): MERGEFORMAT В евклидовом пространстве в качестве нормы вектора принимается его длина, однако длина вектора является лишь одним из возможных, но не единственным вариантом нормы. Пространство называется метрическим, если задан способ вычисления расстояний (метрика) d(a,b) между любыми двумя векторами a и b. Каждое нормированное пространство является метрическим с метрикой . Наличие метрики дает возможность говорить об удаленности векторов друг от друга. Близким векторам соответствуют малые расстояния, далеким – большие. Понятие расстояния можно использовать для классификации объектов, описываемых многомерными векторами.
Из рисунка видно, что точки располагаются не беспорядочно, а имеют сгущения. Эти сгущения обозначены на рисунке буквами A, B, C, D. Расстояния между отдельными точками внутри сгущения относительно малы, в то время как расстояния между точками из разных сгущений существенно больше. Если координаты вектора суть численное выражение некоторых свойств, описываемого им объекта, то можно утверждать, что объекты, входящие в состав одного сгущение обладают близкими свойствами. Сгущения точек, типа изображенных на рисунке 1, принято называть кластерами, а процесс их выявления из всего множества точек кластерным анализом. Кластерный анализ позволяет разбить все множество объектов на отдельные классы (кластеры), обладающие общностью свойств, то есть он решает задачу классификации объектов. Речь здесь идет не о распределении объектов по известным заранее классам, а о выявлении и формировании самих классов. То есть кластерный анализ устанавливает классификацию, либо не существовавшую ранее, либо, если это желательно, игнорирующую предшествующие работы и пересматривающую данные заново. Естественно, что кластерный анализ активно использует метрику пространства, то есть способ вычисления расстояний между векторами. Сфера применения кластерного анализа очень широка. В качестве объектов кластеризации могут рассматриваться растения, животные, минералы, почвы, покупатели, страны, политические партии, политические деятели и многое другое. Для лучшего понимания дальнейшего материала рассмотрим простой пример. Пусть ставится задача классификации депутатов Парламента по результатам их персональных голосований. Здесь полностью игнорируется партийная или фракционная принадлежность депутата, анализируется лишь его голосовательное поведение. Нелишне заметить, что декларируемая политическая позиция и позиция, занимаемая при голосовании могут сильно отличаться друг от друга.
Матрица, получаемая из таблицы исключением первой строки и первого столбца, называется матрицей исходных данных. Матрица состоит из векторов строк размерности n. Вектор-строка с номером i фиксирует голосовательное поведение депутата с номером i. Величина n обычно имеет порядок нескольких десятков, поэтому использовать визуальные методы выявления кластеров, как это показано на рисунке 1 для двумерных векторов, не представляется возможным. Кластерный анализ может производиться только с привлечением специальных математических методов, активно использующих понятие расстояния, и, безусловно, с использованием компьютера. 3Введение и определения. Базовая модель.Данные, предназначенные для кластерного анализа, как правило, состоят из множества элементов, обычно известных как индивиды или операционные таксономические единицы (ОТЕ), каждый из которых определяется набором признаков (в приведенном выше примере – вектором поданных голосов). Термин "признак" используется в широком смысле как обобщение понятия переменной. Множество индивидов предполагается неоднородным в том смысле, что его полезно рассматривать как состоящее из неизвестного числа подмножеств, которые надо найти. Члены одного подмножества должны быть более сходны друг с другом, чем с членами любого другого подмножества. Термин "сходны" включает ряд различных математических выражений, которые будут даны ниже. Этот подход обычно называют моделью минимальной дисперсии, хотя дисперсия в ее статистическом смысле может и не использоваться как мера сходства. Решение задачи обычно не единственно, и его лучше рассматривать не как структуру, являющуюся объективным свойством данных, а как структуру для исследователя в том смысле, что она предназначена для выяснения исследователем интересующих его свойств данных, слишком громоздких для непосредственного анализа. Полезно различать два крайних типа интересов исследователя. 1. Исследователь хочет выяснить, в какой степени можно считать, что существуют различные подмножества при использовании данной численной модели. Система должна быть возможно меньше искажена, так чтобы если разделения на различные подмножества не существует, то оно и не должно быть найдено. Этот тип анализа относительно устойчив при изменении численной стратегии. 2. Исследователь подозревает, что истинных различных подмножеств не существует, однако для облегчения анализа очень большого числа элементов хочет иметь подмножества, полученные путем искусственного расчленения. Этот процесс, обычно называемый рассечением, очень чувствителен к изменению численной стратегии и поэтому не нравится математикам. Однако исследователи-прикладники применяют его довольно часто. Иногда желательно транспонировать матрицу данных и классифицировать признаки на основе их значений для разных индивидов. Такая классификация называется обратной в противоположность нормальной классификации индивидов.
Наибольшие проблемы возникают при попытке кластеризации с использованием номинальных признаков. Их трудно разумным образом оцифровать (за исключением случая бинарных признаков), а без оцифровки невозможно использовать понятие расстояния. Иногда в подобных случаях используются иные меры сходства и различия, отличные от расстояния. Однако в рамках нашего курса мы ограничимся тем случаем, когда применение понятия расстояния возможно. Типы классификации. Численные классификации включают различные численные процессы, из которых выбирается наиболее подходящий. Последовательность выборов представлена на рис. 2, на котором они пронумерованы. Стратегии, заключенные в прямоугольник, и любые выборы внутри них не рассматриваются в данном пособии. Решения принимаются в следующем порядке. (1) Исключающие/неисключающие. В исключающей классификации один элемент может появиться в одном и только одном подмножестве. В неисключающем варианте один и тот же элемент может, появиться более чем в одном подмножестве. (В классификации пациентов больницы, основанной на болезнях, один и тот же пациент может иметь более одного заболевания.) Неисключающие классификации используются в некоторых видах информационного поиска, особенно в библиотечной работе и медицинской диагностике. Они не носят иерархического характера и не будут далее рассматриваться в этой главе. (2) Иерархические/неиерархические. В неиерархической классификации группы выбираются таким образом, чтобы каждая была возможно более однородной. Отношения между группами не выясняются. В иерархическом случае группы рассматриваются попарно как возможные кандидаты для объединения. Критерием объединения служит возможно меньшее увеличение неоднородности при объединении. Формально это обычно формулируется как утверждение, что неиерархическая классификация оптимизирует внутренние свойства подмножеств, а иерархическая — отношения между индивидами и всей популяцией. Неиерархическая классификация всегда итеративная и нами далее рассматриваться не будет. Почти все иерархические стратегии детерминированы в вычислительном отношении и, как следствие, менее требовательны к машинному времени по сравнению с неиерархическими стратегиями. (3) Агломеративные/дивизивные. Различие между этими классификациями состоит в направлении. В агломеративной классификации индивиды объединяются в подмножества возрастающего объема до тех пор, пока вся популяция не объединится в одно множество. В дивизивной классификации исходная популяция элементов постепенно разделяется (обычно дихотомически) до тех пор, пока не будет получена желаемая степень разделения. (4) Монотетические/политетические. В монотетической классификации деление производится на основании одного признака, имеющего максимальную информативность, тогда как в политетической классификации все признаки учитываются в равной степени. Агломеративные стратегии всегда политетические. Каждый из перечисленных типов может быть разделен в свою очередь на различные стратегии, отличающиеся используемыми численными моделями, выбор которых зависит от обрабатываемых данных. Дополнительные требования. В начале классификации почти во всех приложениях все признаки считаются равноправными. Однако после того, как процесс закончен, обнаруживается, что вклад в полученный результат различных признаков неодинаков. Отсюда вытекает потребность в диагностической системе, которая следила бы за ходом политетической классификации и выдавала бы упорядоченный список вкладов признаков для каждого очередного объединения или деления. Может возникнуть потребность в том, чтобы взаимные отношения между конечными подмножествами были отображены в евклидово пространство низкой размерности. Этот процесс называется ординацией. жүктеу/скачать 3.13 Mb. Достарыңызбен бөлісу:
|