Гистограммы

Гистограмма на атрибуте X конструируется путем разделения распределения данных для X на β (≤ 1) взаимно непересекающихся подмножеств, называемых бакетами (bucket) и аппроксимирующих частоты и значения в каждом бакете в некоторой общей манере. Это определение оставляет несколько степеней свободы при разработке конкретных классов гистограмм, поскольку имеется несколько вариантов выбора для каждого из следующих (большей частью, ортогональных) аспектов гистограмм []:

Правило разделения: Здесь можно выделить следующие характеристики:

Класс разделения: Эта характеристика показывает, имеются ли какие-либо ограничения на бакеты. Огромной важностью обладают сериальный класс разделения, который требует, чтобы бакеты были не перекрывающимися в соответствии с некоторым параметром, и его подкласс - класс разделения со смещением к краям (end-biased), для которого требуется наличие не более одного одноэлементного бакета.
Параметр разделения (Sort Parameter): Это параметр, значение которого для каждого элемента распределения данных порождается из соответствующего значения атрибута и частот. Для всех сериальных гистограмм требуется, чтобы значения параметра разделения в каждом бакете образовывали непрерывный диапазон. Примерами параметров разделения, обсуждаемыми в литературе, являются значение атрибута (V), частота (F) и площадь (A).
Параметр источника (Source Parameter): В этом параметре фиксируется свойство распределения данных, являющееся наиболее важным для проблемы оценки и используемое совместно со следующей характеристикой при определении уникального разделения. Наиболее часто используемыми параметрами источника являются протяженность (S), частота (F) и площадь (A).
Ограничение разделения (Partition Constraint): Это математическое ограничение на параметр источника, которое уникально идентифицирует гистограмму в ее классе разделений. Предлагалось несколько ограничений разделения, например, equi-sum, v-optimal, maxdiff и compressed, которые мы определяем ниже так, как они вводились авторами.

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