Классика баз данных - статьи

       

Методы гистограмм и кластеризация


Абстрагируясь от деталей проблемы аппроксимации на основе гистограмм, можно заметить ее поразительное сходство с традиционной проблемой кластеризации []: соединенное распределение данных разделяется на бакеты, содержащие схожие элементы. Сходство определяется на основе некоторой функции расстояния, в которой учитываются значения атрибутов данных и значение частоты, если он каким-то образом изменяется (например, не равняется единице для всех элементов данных). По существу, бакеты являются кластерами в традиционном смысле, и в каждом из них хранится очень краткая аппроксимация элементов, попавших в данный бакет. Несмотря на это сходство, методы, разработанные для решения этих двух проблем, вообще говоря, очень сильно различаются, причем причины многих из этих различий не задокументированы должным образом. Почему методы гистограмм, разработанные для оценки селективности, нельзя использовать для кластеризации и наоборот? С другой стороны, почему бы не рассматривать частоту в оценках селективности как еще одно измерение распределения данных и не считать эту проблему относящейся в области традиционной кластеризации? Как повлияло бы использование хранимых аппроксимаций, разработанных для одной проблемы, на другую проблему? И вообще, при наличии разнообразных методов, существующих для двух проблем, важно понимание достоинств и недостатков каждого из них, диапазона его применимости, а также относительные характеристики методов при их взаимном сравнении. Необходимо произвести

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



Содержание  Назад  Вперед