M. Kamel. Data Mining using Conceptual Clustering. Ссылка (текст на английском языке): http://watnow.uwaterloo.ca/pub/hammouda/sd622-paper.pdfРезюме - задача поиска данных главным образом направлена на извлечение знаний из больших наборов данных. Методы кластеризации обычно используются, чтобы найти регулярные структуры в данных. Концептуальная кластеризация – один из методов, которые формируют понятия из данных инкрементально, подразделяя группы на подклассы итеративно; таким образом строя иерархию концептов. Эта работа представляет использование концептуальной кластеризации в интеллектуальном анализе большого набора документов, чтобы найти значащие группировки среди них. Инкрементальная концептуальная техника кластеризации, основанная на вероятностной функции реализована и протестирована на наборе данных на единство результирующей структуры кластеров. Интеллектуальный анализ данных (ИАД) - область, занимающаяся нетривиальным извлечением скрытой и потенциально полезной информации от больших наборов данных. Учитывая тот факт, что количество доступных данных в последнее время значительно возросло благодаря доступному дешёвому хранению информации и другим факторам, возник актуальный вопрос извлечения знаний из этих данных. Часто можно найти какую-то регулярность в больших количествах данных, которые могут быть раскрыты только используя хороший алгоритм извлечения знаний. Когда не известно никакой информации о классификации данных, алгоритм кластеризации обычно используется, чтобы группировать данные в группы таким образом, чтобы подобие в пределах каждой группы являлось большим, чем подобие объектов из разных групп. Этот механизм известен как обучение из наблюдений, в противоположность задаче классификации, которую рассматривают как обучение из примеров. В этой работе мы применяем одну из методологий машинного обучения, известную как "концептуальная кластеризация", чтобы продемонстрировать задачу поиска данных в большом наборе документов. Одна из ранних работ по концептуальной кластеризации была выполнена Mechalski и Stepp, которые предложили концептуальный алгоритм кластеризации, известный как CLUSTER/2. Выбор в пользу концептуальной кластеризации является результатом интересной особенности, что концептуальная кластеризация главным образом используется для данных с номинальным значением. Существует концептуальная кластеризация, которая может работать с числовыми данными, в данной работе мы работаем с данными с номинальным значением, так как набор данных, с которым мы имеем дело, номинальный и имеет символьные значения. Однако, набор данных, с которым мы имеем дело, содержит большое количество признаков, и их значения являются неустановленными номинальными значениями. Предварительная обработка данных тогда является очень важным шагом, чтобы сделать данные пригодными для дальнейшей обработки. Концептуальная кластеризация строит структуру данных инкрементально, пробуя разделить группу наблюдений на подклассы. Результат - иерархическая структура, известная как иерархия концептов. Каждый узел в иерархии включает все узлы, которые находятся ниже с полным набором данных в корне дерева иерархии. Система, известная как COBWEB была введена Fisher (1987), которая выполняет концептуальную кластеризацию как описано выше, используя вероятностную технику для того, чтобы определить, на сколько хорошо определенное наблюдение соответствует одной из групп, построенных до сих пор; откуда следует обозначение 'возрастающий'. UNIMEM [5] - подобная система, которая выполняет инкрементальную концептуальную кластеризацию, но она использует веса значений атрибутов для реорганизации иерархии концептов. Biswas и другие предложил улучшенный алгоритм концептуальной кластеризации, известный как ITERATE, который уменьшает эффект случайного упорядочения наблюдений, и итеративно перераспределяет наблюдения по кластерам, чтобы улучшить сходство внутри группы. Для того чтобы продемонстрировать задачу ИАД, техника инкрементальной кластеризации реализована и протестирована на наборе данных. Набор данных содержит документы относительно предложений работы, собранных на бирже труда. Набор данных был предобработан, чтобы извлечь ключевые атрибуты и значения. Однако, необходимо было провести дальнейшую предобработку, чтобы очистить набор данных и произвести больше поддающихся толкованию результатов. Секция 5 описывает набор данных и типы предварительной обработки, которая была проведена, чтобы сделать их более пригодными для использования. Ключевое различие между описанной здесь системой и другими системами концептуальной кластеризации - её способность иметь дело с любыми значениями атрибутов и эффективно решать проблему кластеризации. Как мера для оценки работы техники кластеризации, мы принимаем вероятностную меру, которую называем единство, чтобы измерить подобие внутригрупповой структуры кластера. Единство оценивает, на сколько близкими являются наблюдения в определенном кластера. Мы также демонстрируем эффект выбора различных комбинаций атрибутов для кластеризации, основанной на единстве. И наконец эффект организации наблюдений, с целью минимизации искажения кластеризации также изучен. Остальная часть данной статьи организована следующим образом. Секция 2 описывает представление данных. Секция 3 представляет критериальную функцию и её уклон, который управляет алгоритмом кластеризации. Секция 4 представляет алгоритм инкрементальной кластеризации. Секция 5 представляет выполнение и результаты. Наконец, секция 6 дает краткое резюме с заключениями. В схемах кластеризации объекты данных обычно представляются как векторы пар атрибут - значение. Атрибуты представляют определенные признаки объектов, которые, как известно, являются полезными при решении задачи кластеризации. Признаки, которые не уместны в формирующихся структурах данных, могут привести к неточным результатам. Признаки могут быть числовыми и нечисловыми, таким образом формируя представление данных смешанного способа. Концептуальная кластеризация - один из алгоритмов, которые могут работать с данными смешанного способа. Тем не менее, концептуальная кластеризация прежде всего сосредоточилось на признаках, описанных номинальными значениями. Лучший способ объединять числовые, порядковые, и номинально-оценённые данные - все ещё нерешённый вопрос. Если принято соглашение об упорядочении атрибутов в данном контексте проблемы, мы можем представить примеры данных как векторы атрибутов, состоящие только из значений свойств, где названия самого признака неявно известны в соответствии с их порядком. Sison и Shimura предложили относительную модель описания кластеризации данных в противоположность обычному представлению пары атрибут - значение. Обычно атрибуты имеют единственное значение, но иногда они могут иметь несколько значений (мультиоценка), как, например, в поставленной задаче кластеризации документов. В этом случае должно быть принято соглашение, чтобы работать с мультиоцененными атрибутами в зависимости от контекста проблемы. В числовых методах кластеризации мера расстояния используется, чтобы найти несходство между объектами. Это расстояние обычно измеряется как Евклидово расстояние или расстояние Mahalanobis. Для признаков, оценённых номинально, тем не менее, может быть использовано расстояние, типа расстояния Manhattan. Расстояние Manhattan - просто количество различий в парах атрибут - значение. Трудность возникает, когда атрибуты мультиоценены, типа приведенного в работе случая. Каждый пример в наборе данных из документов представлен как вектор 17 пар атрибут - значение. Атрибут может иметь нулевое, единственное, или множественное значение. Таким образом, необходимо обратить внимание на работу с мультиоцененными и оцененными нолем признаками (см. секцию 5). В концептуальной кластеризации концепт (понятие) может рассматриваться как узел в иерархическом дереве, представляющем иерархию концептов. Узлы (концепты) в более высоких уровнях дерева являются более общими, чем узлы в более низких уровнях. Каждый узел хранит список объектов, которые покрыты в соответствии с концептом в этом узле. Таким образом, корень дерева представляет все случаи в наборе данных. Узлы более низкого уровня представляют подклассы их родителей, покрывая только случаи, которые соответствуют их определенному концепту. Листья на самом низком уровне состоят из одного случая каждый, и представляют самые определенные концепты. Представление каждого концепта принимает форму вероятностного распределения всех возможных значений атрибута, вычисленных по набору объектов объединённых этим концептов. Например, если мы имеем два свойства объекта: язык и платформу; тогда, если концепт (узел) содержит один объект только с язык=C ++ и платформа=unix, то распределение вероятностей по значениям свойств в этом концепте - C++=1.0 и unix=1.0, соответственно, в то время как любые другие значения атрибутов будут иметь нулевую вероятность. Если мы добавляем другой объект к этому концепту, который имеет язык=C и платформа=unix, то новое распределение вероятностей по значениям свойств для этого концепта будет C++=0.5, C=0.5 и unix=1.0. Рисунок 1 показывает пример такого концепта в дереве иерархии концептов. Следующий алгоритм кластеризации основан и на алгоритмах COBWEB и на ITERATE. В каждом узле дерева мы пробуем разделить список случаев, связанных с этим узлом среди ряда классов, определяемых функцией Полезности Категории (CU), приведенной в уравнении (1). Мы начинаем, выбирая следующий объект, который должен быть рассмотрен и пробуем добавить его к каждому дочернему узлу и каждый раз численно рассчитываем результат разделения. Кроме того, мы пробуем поместить случай в нового ребенка отдельно, и также рассчитываем результат разделения. Выбираем разделение с самым высоким счётом. Если у текущего узла нет детей, создаётся новый ребенок и к нему добавляется рассматриваемый объект. Созданная иерархия концептов - представление классификации понятий и подпонятий. Однако, для достижения цели кластеризации необходимо извлечь из дерева потенциальные кластеры, которые формируют "хорошее" представление основных группировок данных. После создания иерархии концептов, второй шаг заключается в извлечении кластеров-кандидатов из дерева, используя следующий алгоритм. По пути от корня до любого ребенка значение функции CU, как известно, сначала увеличивается, а затем понижается. Этот факт используется, чтобы извлечь кластеры следующим образом. Мы начинаем проходить дерево от корня. В каждом узле мы вычисляем функцию CU для него и каждого из его детей. Если CU родителя является большим, чем CU каждого ребенка, мы выбираем родителя в качестве кластера-кандидата, и мы больше не рассматриваем узлы, расположенные под этим родителем. Если некоторые из детей имеют CU, больше чем у родителя, те рекурсивно обрабатываются по той же схеме как их родитель. Другие дети, у которых CU ниже, чем у родителя, становятся кластерами-кандидатами в коечном разбиении. |