"похожесть" матриц, прошу помощи

Сообщение №3492 от tanya 17 мая 2002 г. 16:33
Тема: "похожесть" матриц, прошу помощи

Дано: набор матриц (целочисленные, размерность можно выровнять). Каким способом (с помощью чего) можно показать, что матрица А более похожа на матрицу В, чем матрица С? т.е. найти показатель "несхожести"?


Отклики на это сообщение:

Приветствую!
Это в принципе задачка из области распознавания образов.
Есть фундаментальный труд У.Гренандера "Теория
распознавания образов". Аж в 3-х томах!
Однако я предпочел бы использовать нейросети.
Например - сеть Хопфилда. Или сеть Больцмана (имитатор
"отжига"), или сеть Обратного Распростарнения (BPE - англ.
от Back Propagation Error).
Самое простое - Хопфилд. Для бинарных матриц. Очень
красиво, быстро и наглядно. Ну, если матрицы не состоят
только из нулей и единиц, то можно каждый из элементов
представить как бинарный вектор и поразрадно отобразить в
опять-таки бинарные матрицы. Хлопот, конечно, больше. Но
работать будет достаточно качественно. Впрочем, исследо-
ваниями потом можно будет долго заниматься.
Так что желаю удачи.

С уажением, *БИОМАССА*


> Дано: набор матриц (целочисленные, размерность можно выровнять). Каким способом (с помощью чего) можно показать, что матрица А более похожа на матрицу В, чем матрица С? т.е. найти показатель "несхожести"?

Берешь две матрицы одинакового размера, вычитаешь однцу из другой и складываешь модули всех элементов разности.


Здравствуйте!
А если конкретизировать вопрос? В общем, есть несколько графов, прадставляющих возможные пути достижения цели. Вот эти-то графы и преобразовали в матрицы. И теперь сидим и думаем: к какому-же "графу" нам примкнуть? С которым "графом" у нашего больше общего?
Можно ли получить более развернутый ответ, пожалуйста.


Приветствую!
Как я понимаю, речь идет о матрицах инциденций?
Т.Е., если связь между вершинами есть, то тогда Aij=1,
а если нет, то Aij=0. Так?
Таких матриц у Вас несколько.
Тогда, как я и говорил, примените искусственную нейросеть
Хопфилда. Она должна обучиться на те матрицы, С КОТОРЫМИ
нужно сравнить Вашу. Сеть научится их распознавать и они
составят ее "пространство образов".
Теперь нужно решить, к какому их этих образов ближе
Ваша "контрольная" матрица. Если ее подать на вход уже
обученной сети Хопфилда, то после некоторых итераций она
скатится к тому образу из своей памяти, который ближе
всего к Вашей "контрольной" матрице. Степень "близости"
интегрально можно оценить по величине минимума "энергии"
Хопфилдовской сети при принятии ей (сетью) решения об
идентификации Вашего входного образа. То есть после
окончания итераций. Вы почитайте теорию, очень там все
просто.
Ну вот, собственно и все. Алгоритм построения сети -
простой. Даже, кажется, в стандартных математических
пакетах есть. Так что - желаю удачи.
Если что - пишите на fatso@mail.ru

С уважением, *БИОМАССА* :)


> Дано: набор матриц (целочисленные, размерность можно выровнять). Каким способом (с помощью чего) можно показать, что матрица А более похожа на матрицу В, чем матрица С? т.е. найти показатель "несхожести"?

А вам это для чего? просто от этого зависит то как выбирать
критерий непохожести . В любом случае надо будет вычислить
норму ||A-B|| ||A-C||. А вот какую надо братьиз задачи


> Здравствуйте!
> А если конкретизировать вопрос? В общем, есть несколько графов, прадставляющих возможные пути достижения цели. Вот эти-то графы и преобразовали в матрицы. И теперь сидим и думаем: к какому-же "графу" нам примкнуть? С которым "графом" у нашего больше общего?
> Можно ли получить более развернутый ответ, пожалуйста.

Если я правильно понял Вас речь идет о классической задаче поверки измоморфизма двух графов. Или о более общей задаче - задаче поиска изоморфима графа подргафу. Для первой задачи есть эффективные эвристики, конечно, если графы не слишком регулярные (поиск по www.google.com алгоритм nauty). Если же графы просто "похожи", то имеет смысл рассмотреть спектр матриц и собственные вектора, тогда "похожесть" можно интерперетировать как соответсвие отношений нескольких первых собственных чисел и перестановку
переводящую прямоугольную матрицу нескольких первых собственных вектров в другую.

Если же матрицы графов имеют кратные собственные числа, например, регулярные графы, то есть алгоритм работающий с обратными матрицами и с расщеплением спектра вплоть до 10000 вершин и более. Если на самом деле интересует и надо, то пишите rtf@univer.omsk.su , меня интересуют возможные приложения.



> > Дано: набор матриц (целочисленные, размерность можно выровнять). Каким способом (с помощью чего) можно показать, что матрица А более похожа на матрицу В, чем матрица С? т.е. найти показатель "несхожести"?

> Берешь две матрицы одинакового размера, вычитаешь однцу из другой и складываешь модули всех элементов разности.

Наверно не совсем подходит, и вот почему, например есть заданная матрица, создадим из неё другую матрицу путём умножения каждого элемента на постоянную. "Похожесть" матриц в этом случае полная, а вот сам алгоритм работать не будет.


> "Похожесть" матриц в этом случае полная, а вот сам алгоритм работать не будет.

Это противоречит определению "похожести", неявно введенным мной. Следуя данному определению матрицы будут весьма непохожи.

Весь-то базар на тему метризации пространства матриц.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100