Обнаружение ошибок и заполнение пробелов

Записаться

А теперь поговорим еще об одном классе задач, связанных с обнаружением ошибок в таблицах данных и с заполнением пробелов в этих таблицах. Начнем с обнаружения ошибок. Представим себе, что у нас вот такая таблица: имеется M объектов, N признаков и какие-то значения стоят на пересечении столбцов и строк. Таблица полная, пробелов нет, но вместе с тем нет уверенности, что все данные там правильные, что там нет больших ошибок, например ошибка возникает из-за сбоя аппаратуры или при перезаписи данных из полевого протокола в компьютер, запятую не в том месте поставили, много разных причин к этому имеется. Эта задача, постановка ее выглядит так, как мы уже однажды видели такого рода задачи. Представим себе, что у нас имеется много разных способов проверки правильности этой таблицы, например можно, проверяя каждую клеточку, сравнить поставленное в эту клеточку со средним значением всего столбца, всех клеточек столбца. Или опираться на линейные регрессии со всеми столбцами. Тот столбец, в котором есть клеточка, называем целевым. Построим линейной регрессии регрессионное уравнение его со всеми остальными столбцами и, пользуясь этой зависимостью предскажем, что там должно быть, и сравним с тем, что там на самом деле записано.

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

Для этой цели в свое время для двумерных таблиц объект-свойства был разработан алгоритм Z и его модификации, целое семейство алгоритмов Z. Основные предположения, которые использует алгоритм Z, следующие: избыточность. Мы считаем, что реальные таблицы содержат избыточность, которая выражается в том, что есть похожие друг на друга строки, объекты похожие, иногда близнецы, иногда даже клоны. Дальше, в реальных таблицах могут встретиться признаки, которые связаны между собою простой зависимостью и, например дают высокий коэффициент корреляции, этим тоже можно пользоваться - это первый постулат. Затем локальная компактность - это существенное отличие алгоритма Z от всех других, которые раньше были для решения такого рода задач, они раньше опирались на данные всей таблицы, но на самом деле таблицы бывают такого рода, что есть определенные участки, где часть признаков связаны между собою для части объектов, а не для всех остальных, то есть вот такой b-кластер можно выделить таких объектов. Так надо ориентироваться именно на те данные, которые попадают такой b-кластер и с помощью этих компетентных данных предсказывать пропущенный объект, а не учитывать при этом совершенно посторонние свидетельства других признаков, никак не связанных или других объектов, ни на что не похожих. Локальная компактность, значит, мы исповедовали в этом алгоритме. И из всех видов зависимости применяем самые простые — линейные. Во-первых, по той причине, что это все просто и быстро, а во-вторых, в основном, потому что выборка обычно маленькая и обосновать применение какого-нибудь полинома высокой степени - это большая натяжка, поэтому мы решили ограничиться линейными зависимостями.

Как предсказание делается? Делается а основании такой простой расхожей гипотезы: объекты, похожие по n свойствам, похожи и по (n+1)-му свойству. Кажется, это банально, можно привести сто примеров, когда это неправда, это неправильно, но можно привести миллион примеров, когда это правильно, так что мы все-таки полагаемся на эту гипотезу, потому что другой равносильной и полезной для этой задачи мы не обнаружили. Но если так то, например похожими эти объекты, строчки этой таблицы, ai и as объекты могут быть похожи следующим: признаки этих объектов связаны друг с другом закономерностью, например, их отношение у всех признаков одинаковое, то есть отношение bi1 к bs1, оно такое же, как bi2 к bs2 и так далее. На основании этого, пользуясь таким простым соотношением, мы берем неизвестный объект, рассматриваем клеточку пустую, строим вот такие отношения в конце и получаем вот такое выражение простое. Каждая такая пара, сравнение с каждой характеристикой дает свой вариант заполнения пропущенной клеточки, а какой из них выбрать - по-разному можно. Можно, например, по среднему значению из всех этих вариантов, и вставлять сюда - это используется похожесть по объектам. По столбцам то же самое, если есть объекты и мы рассматриваем два столбца, то есть два признака, и смотрим их зависимость, то мы можем вообще построить такой график, вот данные по первому признаку, вот по второму признаку, в котором содержится пробел, для всех известных объектов. И аппроксимировать, например, в счастливым случае простом, аппроксимировать простой линией, такую вот регрессию построить, и тогда, зная значение этой характеристики, можно, используя этот закон, предсказать значение неизвестной характеристики.

Постулат локальной компетентности, локальности, он выражается в том, что мы берем не всю таблицу, а только часть ее, которую мы называем компетентной подтаблицей или компетентной подматрицей. Как она строится? Она строится с помощью фактически алгоритма AdDel, о котором уже говорилось. Но сначала формируется все-таки некий зародыш путем просто жадного варианта, мы берем целевой столбец и сравниваем с ним все остальные столбцы, и выбираем несколько штук, например 3 столбца, наиболее похожих на этот первый столбец. Потом то же самое делаем со строчками, берем строчку, в которой пробел, интересующий нас, и выбираем тоже три строчки, наиболее похожие на эту строку. Их пересечение образует маленькую матрицу четыре на четыре - целевая строка и столбец, и еще три компетентных строки и три компетентных столбца. Это ядро такой матрицы, и дальше мы занимаемся наращиванием размерности этой матрицы таким путем: работаем со столбцами. Взяли целевой столбец и начинаем сравнивать остальные, мы уже один раз сравнивали, можно взять те меры, которые были уже получены. Выбираем некую плоскость, которая похожа на него больше всего из тех, которые еще пока не включены, и смотрим: добавление этой плоскости к этой подматрице улучшает характеристики этой подматрицы или нет? Улучшать она будет, если действительно добавление позволяет повысить компактность этой матрицы. И запоминаем, какой столбец является главным претендентом на добавку. Обратите внимание, что мы сравниваем теперь расстояние между столбцами или сходство между столбцами не по всем объектам таблицы, а только по тем объектам, которые включены в эту подматрицу, прострация малой размерности.

Затем ту же самую процедуру делаем со строками. Сравниваем те строчки в пространстве тех признаков, которые уже включены в матрицу, то есть в этом подпространстве выбираем самого похожего объекта, и потом сравниваем между собой, кого из них присоединить, столбец или строку. Присоединяется тот элемент, который дает лучшие характеристики этой матрицы, например компактность матрицы. После этого то же самое повторяем еще раз и еще раз, n1 раз, это отражает этап Addition, добавления, жадный алгоритм добавления. После этого мы останавливаемся и начинаем критически осматривать то, что у нас получилось - может быть некоторые элементы, то есть некоторые строчки, некоторые столбцы, которые были включены на основании сходства по всей таблице, теперь в этом подпространстве они не сильно похоже и не очень они помогают, не очень помогут заполнить эту клеточку правильно. Такой слабый элемент мы выбрасываем, сокращаем чуть-чуть таблицу, а потом снова жадно начинаем добавлять еще, то есть та же самая процедура: добавление, добавление, остановка, сброс накопившегося мусора и снова добавление. На каждом шаге оценивается компактность этой подматрицы.

Мы тут говорим «компетентность» и «компактность», поточнее, что это такое? Компетентность, на основании которой мы говорим, если это компетентный элемент, то мы его добавляем в матрицу, если нет, то нет. Как мы проверяем? Предположим, очередной претендент попасть в эту под матрицу — объект A. Мы берем и находим два расстояния, первое расстояние от него до трех ближайших соседей из имеющейся подматрицы, или вообще в общем случае k ближайших соседей, допустим, три. Второе расстояние - это расстояние до k ближайших соседей из тех, которые не включены пока в матрицу, ближайшие, но еще не попали туда. Получили расстояние r1 и r2, и дальше хорошо знакомая нам функция конкурентного сходства. Расстояние это минус это, деленное на их сумму, говорит о том, что если эта величина больше нуля, то это значит, что A больше похож на это множество, чем на это и, значит, имеется основание его сюда присоединить. А если отрицательная величина, то, значит, не надо его присоединять, его добавление будет разрушать эту структуру и ничего полезного не принесет. А остановка при этом такая: набираешь, набираем, набираем, пока, наконец, как по строчкам, так и по столбцам претенденты не выдерживают этой проверки. Все, нечего добавлять ни к строкам, ни к столбцам, и получается некая подматрица, на основании которой мы делаем дальше вычисление значения пропущенного элемента.

Про компетентность я сказал. Компетентность этой подматрицы, она вычисляется у нас тут просто как среднее значение компетентности столбцов и строк. Они вычисляются по отдельности, значит компетенция столбца - это среднее значение сходства с целевым столбцом всех остальных столбцов, входящих компетентную подматрицу в конкуренции с теми столбцами, которые не вошли в эту подматрицу. То же самое и для строк. Выбираются те строки, сходство которых с целевой строкой больше нуля в конкуренции со строчками, не вошедшими в эту подматрицу.

Это что касалось редактирования, когда мы можем убедиться, правильно ли мы предсказывали то, что там было, и на этом основании выбирать метод предсказания. Осложняется дело, когда действительно заполняются пробелы. Мы заполнили этим методом или другим, но точную оценку, какая же ошибка заполнения, мы получить напрямую не можем, поэтому делаем некоторые косвенные оценки. Эта оценка ожидаемой ошибки - новая проблема, которая возникает в этом. Мы используем такие косвенные оценки, как компактность компетентной подматрицы, о которой только что говорилось. Нужно еще и сделать так — предсказывать, заполнять известные элементы целевой строки и целевого столбца, на их пересечении пустая клеточка, а вот этот крест - все элементы известны. Мы тем же самым методом, которым мы редактировали, начинаем редактировать эти известные элементы, вычисляем среднее значение ошибки и переносим этот вывод и на элемент, который мы заполняем. Можно посмотреть на дисперсию этих ошибок, можно абсолютную величину посмотреть, и тем самым есть возможность заказчику сказать, что мы предлагаем это пробел заполнить таким-то значением, но, судя по соседним, в этом месте ошибка заполнения может достигать, допустим, плюс-минус пять процентов. Устраивает вас это или нет? Вот такие значит ситуации бывают.

На самом деле часто встречаются таблицы, в которых этих пробелов много, не один пробел в таблице, а много. Был у нас такой случай, геологи нам предъявили некий материал, в котором были характеристики различных участков, которые они исследовали в экспедициях, участков было много, характеристик было много, но измерений было очень мало таких, которые были бы на всех участках, и поэтому там было 82 процента пустых клеточек, и только 18 процентов были заполнены. Была мольба, помогите хоть что-нибудь. Кое-что, очень мало удавалось где-то зацепиться и найти такие объекты, то есть такие участки, где более-менее одинаковые характеристики измерялись, что-то по поводу их можно было говорить, а остальное нет, эти все варианты ответов мы и предъявляли.

Теперь ZET-прогнозирование с использованием этих же алгоритмов. В свое время мы разработали алгоритм прогнозирования. На чем основан? На некоторых предположениях о постоянстве чего-нибудь, например, что имеются какие-то циклы, которые повторяются, и тогда давайте мы выберем из прошлой истории эти циклы и совместим их и тогда что-то получится общее. Или характеристики меняются монотонно, в идеале — линейно, совсем просто тогда. Конкретно эта реализация выглядела так: представим себе, что у нас имеются данные за все двенадцать месяцев этого года по какой-то характеристике. Нам интересно было бы посмотреть, а что нас ждет январе, феврале и марте следующего года. Тогда мы берём эти данные, сдвигаем влево на 3 месяца, на 1 квартал, и теперь тут 1-4, 2-5, вот такое совмещение. До сих пор все известно, а вот это пустые клеточки. Мы можем и дальше пойти, еще там сдвинуть, и тогда будет вот такая таблица, полностью заполненная, а вот это все пустые клеточки. По очереди вот на этом основании мы можем предсказать значение вот этих клеточек, у нас возникает желание посмотреть, что будет дальше, тогда вот в этой строчке мы предсказываем то, что здесь было знаком вопроса, ну и так далее. Понятно это было и без экспериментов, что ошибка предсказании ухудшается, растёт, такой раструб, довольно быстро растет, поэтому далеко таким путем не пройдешь, но на ближние шаги все-таки удается поймать такие закономерности.

Много мы задач решали, в частности, по прогнозированию. В свое время мы сотрудничали с Госпланом Российской Федерации, и там ставились перед нами задачи - предсказать урожайность зерновых культур, допустим, по данным до середины лета, когда еще уборка не началась, а где-то еще только-только взошли эти самые культуры, вот по этим данным предсказать, что можно ждать на этом участке, какой урожай. Такую задачу решали, но наиболее успешной у нас была задача, связаная с надоями молока. Имелись у нас данные о надоях, средних надоях одной коровы за период с 1946 года и до 80 какого-то года, такой длинный ряд. Сам по себе этот ряд представлял интерес, он был не монотонный, он рос, рос, потом падал, потом снова начинает расти, потом падает. Мы обнаружили даже такую закономерность, что точки минимума соответствовали смене правительства. Приходит новый правитель, вздрагивает экономика, доярки начинают аккуратно ухаживать за коровами, вовремя их поить, кормить, начинает повышаться производительность, и все это идет, пока снова чего-то там не начинает скрипеть. Мы смотрим, что через некоторое время снова меняется система управления или лидер. Что касается прогнозирования, то нам до октября месяца помесячные надои Госплан выдавал, и требовалось заполнить, во-первых, на ноябрь и декабрь, и на следующий год. Вот такое прогнозирование, мы это делали и, надо сказать, закономерности там были довольно гладкими, поэтому предсказание оказывалось достаточно правильным. Очень нравилось это нашему заказчику, что именно так это получается. Предсказывали, например, падеж овец, ну в общем, скота в Якутии, которая содержит зимой на снегу просто, и эти бедные животные там ковыряют снег и добывает мерзлую траву. Мы прогнозировали, что в этом году будет большой падеж, судя по периодическому изменение климата, что оно и подтвердилось потом. Много таких задач с помощью алгоритма ZET решалось.

У нас не было возможности сравнить решение этих же задач с другими методами, их не существовало просто, мы не знали, а вот что такое косвенная оценка - все-таки преимущество этого подхода мы получили, когда сделали алгоритм для прогнозирования, FRiS-PRO, и это было на такой задаче: в 2009 году организаторы очередная конференция по Data mining в Германии предложили посоревноваться в решении некоторой задачи Data mining. Задача выглядела так: вот имеется около 5000 книжных магазинов европейских, может быть только германских, я не знаю, в которых продавалось около 2000 разных книг, так что вот матрица исходная за прошлый год. В прошлом году в этих магазинах было продано столько-то книг такого-то автора. Она тоже содержала очень много пробелов, некоторых магазинах какой-то автор совсем не появлялся, некоторые бестселлеры показывали там высокие результаты, некоторые маленькие, и что требовалось? Вот вам обучающая выборка на половину магазинов примерно, их там было порядка 2000 с чем-то, это обучающая выборка, а вот вторая часть, тоже 2000 с чем-то - это контрольная, в которой надо было предсказать, угадать, сколько книг восьми авторов из этих двух тысяч было продано в этих магазинах. Итого получилось пустых клеточек около 20000, нужно было заполнить 20000 клеточек. Мы применили алгоритм ZET, но даже на такой, несколько сокращенной версии мы использовали сходство только между строчками. Применили там разные эвристические хитрости ускорения обработки этих данных, и в результате получили заполнение некое, которое послали туда, в оргкомитет, и оргкомитет во время конференции опубликовал результаты. Участвовало в этом соревновании более 600 команд из 42 стран. До финиша дошло 230 команд, не все выдержали эту задачу, просто отказались, но из этих 230 было выбрано 49 команд, которые показали лучшие результаты. Наш результат оказался в этом списке и занимал там четвертое место, и мы уступили победителям очень мало. Показатель там такой - считался модуль разности между предсказанным количеством в эту клеточку и фактическим, и суммировались эти расхождения. У победителя было 0,89 единиц ошибок на клеточку, меньше одной книжки на клеточку ошибка, а у нас 0,95. Скажем, для сравнения, у сорок девятого, отобраного в этот список, было сто с лишним ошибок на каждую клеточку. Разнообразие было очень большим, но удалось угадать достаточно хорошо. В этом мы убедились, что ZET кое-что стоит.

Еще применение ZET, если упомянуть или подвести черту - это восстановление скрытых или утерянных данных, обнаружение ошибок или умышленных искажений, Fraud detection — это как раз область широкого применения для этих целей, обнаружение сбоев в технологическом процессе или в системе измерений. Идет поток данных, и вдруг что-то там зашкалило, вышло из закономерности, это обнаруживает алгоритм и сообщает, обратите на это внимание. Прогнозирование динамических объектов, это примерно то же самое.

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

Формирование компетентного подкуба. Здесь философия та же - формируется сначала зародыш небольшой, допустим, присоединяем к целевым плоскостям три самых похожих плоскости, в которых измеряются характеристики, объекты, время, получается кубик 4 на 4 на 4, и дальше присоединяем жадным алгоритмом следующие плоскости по каждой из этих координат, сравниваем претендентов по каждой координате получившихся, кто из них лучше, добавляем, кубик меняется, после чего снова ищем самых похожих уже в этом формате, в этой размерности и так далее, кубик растет, количество плоскостей тоже растет. Останавливаемся, проверяем, все ли включенные плоскости оправдывает свое назначение, обнаруживаем, что кто-то там слабо влияет или совсем не влияет, или даже мешает уже, особенно из тех, которые мы сначала включили, ориентируясь на общее пространство. Слабаков мы исключаем, добавляем новые, новые и так далее, та же самая схема, только по трем координатам одновременно.

Критерий остановки, тот, что я описывал. Очередная присоединяемая плоскость, оценивается ее расстояние до k соседей из тех, которые внутри уже компетентного подкуба, R2 - это до k соседей, пока еще не входящих в КП, остановка - если сходство выше нуля. Второй вариант остановки, если монотонное что-то такое бывает, и нет отрицательного, то остановка, если количество плоскостей по каждой координате в этом подкубе достигает некоторого порога. По нашему опыту этот порог обычно где-то в районе 6-7, 6-7 соседей себя оправдывает, а дальше редко бывают случаи, когда еще кто-то им оказывается полезным.

Это что касается куба, теперь ожидаемая ошибка. При заполнении каждого пробела делается редактирование известных клеточек компетентных плоскостей, точнее клеточек в этом кресте, который там показан был, редактирование этих элементов, и получается среднее значения ошибки, которые мы говорим - это ожидаемая ошибка заполнения данной клеточки. Применение: вот тут задача один, она касалась анализа данных, берется группа из 10 спортсменов, измеряется 10 характеристик во время тренировок: до тренировки, после тренировок - 10 характеристик, это в 10 моментов времени, то есть получится куб 10 на 10 на 10. Пробелов нет, но интересно было, во-первых, посмотреть, есть ли какие-то выбросы, все ли там гладко меняется, или кто-то ведет себя очень непредсказуемо, его характеристики, вернее, нельзя ожидать, предсказуемы или нет, сбои обнаруживать или выбросы. Для этого применялось редактирование каждой из этих клеточек и смотрели, какая там будет ошибка. Получилось, что средняя ошибка при перекрёстной проверке всех ячеек порядка 14 процентов. Хорошо это или плохо - трудно сказать, наш заказчик говорит, получается инженерная ошибка, принято у инженеров 15 процентов ошибка, человек часто не замечает в некоторых вещах, значит, на грани приемлемости это было. Это может говорить о том, что может быть выборка мала, всего 10 на 10, может быть при более длительном наблюдении удалось бы это улучшить.

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

Вторая задача - тут данных побольше, задача связана с нефтяными скважинами. Объектов, скважин 13, характеристик 11, но дней 122, на таком большом периоде тут показаны таблицы длинные этих данных, и тут надо было то же самое, предсказывать дебит скважин на основании других, остальных характеристик. Надо сказать, что по этим характеристикам дебит предсказывается достаточно хорошо, общая ошибка редактирования оказалось 2,24 процента, что вполне устраивает наших заказчиков. Тут графически показано одновременно две кривых: фактический дебет и предсказанный дебит, то есть в некоторых местах там есть небольшой дребезг, а в целом предсказание достаточно хорошее. Распределения ошибок выглядит гистограмма вот так. По координатам по разным видам плоскостей на объектах, на времени и на характеристиках ошибки в основном мало, те, что встречались, они малого значения, больших выбросов нет, очень редко встречаются большие ошибки. Такое первое применение трёхмерного куба мы тоже уже проделали, но мы еще учитываем, что нужно продолжать совершенствовать этот алгоритм и дальше.

Закончить я хотел бы перечнем проблем, которыми мы сейчас занимаемся, те, которые, по-видимому, можно в обозримом будущем решить, но пока не решены. Вот обучение без переобучения, у нас даже есть один вариант алгоритма, который эту задачу решает, но он нам не нравится, не нравится своим неизяществом. Там такая большая путаница получается и некрасивый критерий неформальный. Мы сейчас над этим усиленно работаем. Прогнозирование на кубах данных. Я показывал, как это делается, прогнозирование одномерной последовательности, то же самое делается на таблицах, идея та же самое для кубов, просто это еще не реализовано и не опробовано. Универсальная программа SDX. У нас есть уже программа, алгоритм описан нами, а вот с экспериментами, с программами пока еще это на стадии рассмотрения. Программа, которая у нас есть, она, как кажется успешно решает задачи SD, DX - само собой, но если задан алфавит распознаваемых объектов, то дальше одновременный выбор признаков и решающих правил - это делается, конечно, алгоритм FRiS-GRAD тому пример Нам удалось объединить в одну программу задачи, когда заданы все значения целевой характеристики кроме одной - задача распознавания классическая, а также задача, когда задана часть значений целевых характеристик задано, остальные клетки пустые. При разной степени заполненности этого столбца та же самая программа успешно такую задачу решает. Что касается крайнего случая, когда ни одного элемента в целевом столпе нам не известно, эта задача кластеризации, вот тут сочетание кластеризации с выбором признаков оказалось очень крепким орешком — да, выдает программа варианты, и много вариантов, что касается того — полезны ли варианты, или не полезны, тут эксперт должен смотреть на это и, глядишь, что-нибудь случайно таким путем полезное и интересное и будет выбрано - вот над этим мы сейчас дальше работаем. Таблицы и кубы с разнотипными свойствами - эта проблема частично решена, теоретически нам понятно, как это делается, но таких хороших рабочих программ, чтобы мы смело брались за любую задачу с разного типа характеристиками у нас пока нет, мы над этим сейчас тоже усиленно работаем.

И самая главная проблема, в которой мы сейчас работаем, и чем мы сейчас озадачены, озабочены - это адаптация к большим данным, Big data. Надо сказать, что мы вспомнили интересный факт, что лет сорок назад мы решали задачу Big data. Это было так: у нас был алгоритм, он и сейчас есть, алгоритм FOREL, это самый первый алгоритм кластеризации в нашей литературе, который делал следующее - он разбивал множество объектов на некоторые подмножества сферической формы, шариками, раскатывал в шарике классы, сферические образования. Потом нам встретила задача, в которой столько данных было, что они не вмещались в оперативную память машины в то время, в то время машина наша, M20, вмещала в себя 4096 чисел, это был порог, все, что выше, это были Big data. Мы тогда не знали этого слова. Что же делать? Все это на ленте там где-то на большой было, тогда мы с ленты по очереди закачивали в машину небольшие куски, тысячи по четыре объекта, для каждого куска программа FOREL работала, и мы задавали такой радиус шарика, чтобы раскатывалось на большое число небольших шариков и дальше запоминалось: координаты центра шарика и количество объектов в этом шарике. Это уже вторичное описание объектов. После того, как прошла вся выборка, у нас получился объем данных, который умещается в памяти, мы дальше делали дальнейшую агломерацию, уже используя именно эти шарики. Вот такой из приемов уже применялся, я думаю, он и сейчас вполне для каких-то задач может быть применен. А в общем проблема то, что наши алгоритмы, особенно ZET, алгоритмы громоздкие для машины, и применять их к большим кубам данных на самом деле непростое дело. И даже не для кубов, даже для плоских таблиц большого объема все наши алгоритмы не очень-то оптимизировались, все не очень-то настраивались на то, чтобы быстро эти задачи решать. Сейчас мы коллекционируем все эвристики, какие нам встречаются, и которые направлены на уменьшение машинного времени. Вот этим мы сейчас занимаемся. Спасибо за внимание.