Диссертация (1150572), страница 9
Текст из файла (страница 9)
В. Шелейховским [34], который решал задачупрогнозирования устойчивого расселения жителей города по районам — транспортную задачу с линейными ограничениями. Этот метод получил названиеметода балансировки (метода Шелейховского). Он заключается в последовательном преобразовании строк и столбцов матрицы смежности умножением иделением на подходящие множители так, чтобы построенное решение удовлетворяло заданным ограничениям. Позже Л. М. Брэгман обобщил [16] методШелейховского на класс задач, ограничения которых не являются линейными,а также доказал [15] сходимость этого метода.
И. В. Романовский показал [30],что построенный стационарный поток максимизирует взвешенную энтропию.3.2Построение стационарного потока на графеРассмотрим изображение как решетку пикселей x(i, j). Каждой точке ре-шетки сопоставляется значение интенсивности пикселя 0 < I(i, j) < 256. Рассмотрим окрестность ближайших соседей пикселя, состоящую из 4 пикселей.По изображению строим ориентированный граф, каждая вершина которого со-55ответствует пикселю решетки. Всем вершинам приписываем вес, соответствующий значению интенсивности пикселя. Вершины графа соединены двумя разнонаправленными дугами, если соответствующие этим вершинам пиксели —соседние. Всем выходящим из вершины дугам приписываем значение интенсивности узла, деленное на число соседей.
Значения в вершинах и дугах графанормируем таким образом, чтобы сумма мер вершин была равна 1. Обозначимполученный поток на графе pij . По построению мера каждой вершины равнасумме мер выходящих дуг. Нас интересует такое распределение uij значений надугах, при котором построенная цепь u будет стационарной, что означает, чтодля каждой вершины графа сумма весов по всем входящим в нее дугам равнасумме весов по всем выходящим.Взвешенная энтропия v определяется в терминах начального распределения весов какv=−Xijpijuij lnuij.(3.1)Рассматривают экстремальную задачу поиска максимума функции Xpijf (u) = −uij ln(3.2)uijijпри условияхXiuik −Xjukj = 0,Xuij = 1.(3.3)ijНачальный поток pij рассматривают как приближенное решение этой задачи (несмотря на то, что он не удовлетворяет ограничениям).
Точное решениеэтой задачи даст нам построенный на графе стационарный поток. Значениевзвешенной энтропии определяется начальным состоянием и полученным стационарным.3.2.1Описание базового алгоритмаАлгоритм построения стационарного потока на графе основан на методебалансировки Шелейховского–Брэгмана. Как было показано в [15], сходимость56метода не зависит от порядка перебора столбцов и строк матрицы смежности.В работах [4, 28] Н. Б.
Ампиловой и Е .И. Петренко для организации переборавершин было предложено использовать приоритетную очередь, приоритетом вкоторой является дисбаланс вершины q(n) = |µout (n) − µin (n)|, где µout (n) —сумма мер исходящих из вершины дуг, а µin (n) — сумма мер входящих. Накаждом шаге для вершины n с максимальным приоритетом вычисляется коэффициентsγ=µout (n).µin (n)(3.4)Меры всех дуг, исходящих из n, делятся на γ, меры всех дуг, входящих в n,умножаются на γ. После этого производится нормировка потока и пересчетзначений в вершинах.
Критерием остановки алгоритма является то, что дисбаланс всех вершин становится меньше некоторого заданного ε. При условии ε= 0 мы получили бы стационарный поток, но вычисления ведутся с некоторойточностью ε > 0, поэтому в результате получится некоторое ε-приближенноерешение.Указанный алгоритм был использован для вычисления взвешенной энтропии изображений растворов серебра различной концентрации [4].
Было показано, что использование значения взвешенной энтропии в качестве классификационного признака достаточно эффективно. Однако авторы отмечают, что времяработы метода на изображениях большого размера (или высокого разрешения)велико.3.3Модификация алгоритма построениястационарного потока на графеОсновная идея модификации алгоритма состоит в том, чтобы разделитьисходные данные на некоторое число подмножеств, вычисления для которыхможно производить независимо друг от друга. Изображение для этого рассмат-57ривается не как единая решетка пикселей, а как набор из таких решеток. Простейший случай разбиения множества на четыре решетки — поделить решеткуна две равные части по каждому из измерений.
Обратим внимание, что пиксели, находящиеся на границе двух решеток (в дальнейшем будем называть ихграничными точками), входят в обе из них.На каждой из таких решеток строится свой собственный граф, на которомвсе дальнейшие вычисления производятся независимо от вычислений на другихграфах.
Полученные ε-стационарные распределения на графах объединяются водно общее: в качестве значения дугам, входящим и выходящим из граничныхточек и принадлежащим нескольким частям, присвается вес, равный сумме весов соответственно входящих и исходящих ребер каждой из частей. Принципобъединения проиллюстрирован рисунком 3.1.Рисунок 3.1. – Принцип объединения граничных точек.Утверждение 3.1. В результате вычислений по модифицированному алгоритму при объединении ε-стационарных распределений на частях на всемграфе получается не более чем 4ε-стационарное распределение.Доказательство.
Действительно, для неграничных точек каждого из объединяемых множеств неравенство q(n) < ε выполнено (это критерий остановкиалгоритма балансировки на соответствующем подмножестве). Дуги, входящие58в и выходящие из граничных точек, не могут принадлежать более чем четыремчастям одновременно, поэтому выполнено следующее соотношениеq(n) <=4Xqi (n) < 4ε.(3.5)1Таким образом, распределение осталось ε-стационарным во всех точках, кромеграничных. В граничных точках распределение 4ε-стационарно. 3.4Оценка вычислительной сложностиСформулируем оценки вычислительной слоности алгоритма в виде следю-щего утверждения.Утверждение 3.2.
При разбиении изображения на K частей сложностьвычислений для модифицированного алгоритма меньше, чем сложность вычислений для базового в K раз.Доказательство. Оценим временную сложность базового алгоритма. Дляпостроения приоритетной очереди необходимо вычислить для каждой вершины ее дисбаланс, после чего отсортировать вершины в порядке уменьшенияприоритета, число требуемых операций O(M N ln(M N )). На каждом шаге алгоритма для вершины, стоящей в голове списка, подсчитывается коэффициентγ, после чего у некоторого числа дуг (и соответственно вершин) в графе изменяется вес.
Пересчет новых дисбалансов вершин и сортировка очереди требуетO(M N ln(M N )) операций.Модифицированный алгоритм представляет собой K запусков базовых алгоритмов на графах размераMNK .Соответственно временная сложность вычис-лений на каждом шаге составляет O( MKN ln( MKN )). Каждый шаг модифицированного алгоритма требует меньше операций, чем шаг базового вln(M N )M N ln(M N )=K> K раз.MNMNln(MN)−lnKln()KK(3.6)59Число шагов алгоритма, которое потребуется для построения ε-стационарного распределения с нужной точностью, не зависит напрямую от M и N ,а зависит от характера изначального распределения. При этом можно ожидать, что число шагов, требуемых для построения K ε-стационарных распределений на подграфах не превосходит числа шагов, требуемых для построения ε-стационарного распределения на полном графе.
Это означает, что общаявременная сложность вычислений по модифицированному алгоритму меньшевременной сложности вычислений по базовому в K раз. Можно заметить, что при использовании предлагаемой модификации алгоритма, все вычисления кроме вычислений, связанных с разбиением графа наподграфы и заключительного объединения результатов, — независимы, а потому могут проводиться параллельно на многоядерном вычислителе. Это дастеще бо́льшие возможности по уменьшению времени вычислений.3.5Численный экспериментПри выборе алгоритма, который будет использован в конкретном случаеклассификации, основными факторами являются точность классификации искорость работы алгоритма.
Для оценки этих характеристик классифицирующего алгоритма его запускают на предварительно разделенных на классы понеобходимым признакам изображениях и получают численную характеристику каждого из них. Алгоритм считают эффективно классифицирующим в томслучае, если полученные численные характеристики кластеризуемы на числовой прямой и разные кластеры соответствуют разным классам изображений.Может быть вычислен некий показатель, который можно назвать процентомточности (accuracy) алгоритма.
В качестве этого показателя, как правило [55],используется отношение числа верно отнесенных в соответствии с численнойхарактеристикой к тому или иному кластеру точек к их общему количеству.60Кроме того, запуск различных алгоритмов на одном и том же наборе исходных изображений позволяет получить усредненные данные о скорости работыразных алгоритмов.Для проверки утверждения был проведен численный эксперимент по вычислению взвешенной энтропии для изображений патологий тканей печени.Изображения имеют размер 2584 пикселя в ширину, 1936 пикселей в высоту.Эти изображения предварительно были разделены на два класса в соответствиис изображенными на них заболеваниями печени. Первый класс составляли изображения тканей печени с жировой дистрофией, второй класс — изображениятканей печени с выраженным полнокровием.
Первый класс изображений состоял из 11 представителей, второй класс — из 14. Типичные представителикаждого из классов показаны на рисунке 3.2.а) Жировая дистрофияб) Выраженное полнокровиеРисунок 3.2. – Представители изображений препаратов печени.Для каждого из изображений взвешенная энтропия была вычислена двумяспособами — по базовому и модифицированному алгоритмам. Для модифицированного алгоритма были рассмотрены его версии с K = 4 и K = 16. Послевычисления взвешенной энтропии для каждого эксперимента полученные числа были кластеризованы на числовой прямой на два кластера. В качестве кластеризующего алгоритма использовалась тривиальная вариация k-means [98],61в качестве исходных центров кластеров брался максимум и минимум значенийточек на числовой прямой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
