Допустим у меня есть два дискретных ряда R1, R2 допустим это измерения одного и того же процесса разными инструментами. Количество измерений не обязательно равно.

Как определить их похожесть? Понятно, когда "похожесть" 100%, но не понятно, где обратная граница. Ведь "непохожесть" может быть какой угодно большой. И как её измерять...

чаще всего "похожесть" понимается сходно с расстоянием
т.е. фраза получается "эти города близки на 30%" - не очень-то осмысленно

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

для более специфического случая с рядами нужно уточнить по каким параметрам сравниваются ряды, если в процессе сравнения происходит поиск какой-то общей части, можно сравнивать её длину с длинами двух рядов и оттуда получать какие-то проценты

Можно на манер вычисления расстояния между строками (вставка/удаление символов) вычислить "наименьшую" разницу между элементами, т.е. (вставка/удаление/+дельта), где каждой из этих операций можно дать разный вес. Задача по идее квадратична ("динамическое программирование"), если данных не много, то вполне быстро.

Спасибо за ответы 
 

Я тут обмозговал это, получился такой пример:


R1 - N точек на f1(x)
R2 - L точек на f2(x)

"Похожесть" определяется количеством точек, которые однозначно принадлежат или f1, или f2 

Если точек нет - похожесть 0%
Если по имеющимся точкам не определить, к какой функции они относятся - 100%

При этом есть точки примеры из f1 и точки - примеры из f2 по которым можно примерно f1 и f2 восстановить. (просто дело идёт не о функции, а о дискретном ряде, поэтому не говорю, что f1,f2 известны) 



Мне именно измерение "похожести" необходимо, а не само решение задачи.


Скажем так... в процентах не совсем необходимо, но намного удобнее сравнивать множество таких пар рядов между собой, особенно если каждая пара специфична..

что подразумевается?

Любая функция.
Например f1(x) - парабола, a f2(x)- прямая.

тогда не очень понятна эта фраза

насколько я понял, сравниваются два ряда (R1, R2?)
если это так - при чём тут функции?

Из институтского курса высшей математики вспоминается слово "корреляция"...

Именно корреляция и методы борьбы с ним опусаны в куче книг по обработке результатов измерений.

В простейшем случае применяется метод наименьших квадратов. Две величины наносятся на график по двум осям, ищется зависимость (проще всего - линейная) и считается коэффициент корреляции. Метод наименьших квадратов - самый распространенный подход к поиску такой зависимости. В общем виде:
sum[(x(i) - y(i))**2]=min

Ну а если есть желание погуглить - клучевое слово коэффициент корреляции.

Сдаётся мне, корреляция здесь и даром не нужна. 
Ну, допустим, получили значение коэффициента корреляции 0.78. Дальше что? Какие из этого выводы (случаи 0, 1 и близкие к ним не рассматриваем) ? Что с этим делать?


sergejzr, разжевал бы подробнее, какова цель? Ведь по неё можно подогнать любую науку 

Для чего тебе нужна похожесть/непохожесть рядов измерений? Чтобы угадывать, одним инструментом они получены или разными? Где цель, вобщем?

А то для начала я бы, например, поработал с сырыми данными и посмотрел: 

1) а не образуют ли данные хотя бы 2 кластера? 
2) не попадают ли результаты измерений разными инструментами в разные кластеры?

Вот было бы тогда за что цепляться. 

Я что-то не въезжаю... 
В ответ дали КОЛИЧЕСТВЕННУЮ оценку похожести. В полном соответствии с просьбой. 

Akina, у корреляционного анализа малость другое предназначение. 

Если бы Серж пытался найти, скажем, как изменение R1 отражается на значениях R2, тогда велкам. Но он ведь не ищет взаимосвязь R1 и R2, ибо и так дано, что это измерения одного и того же процесса, только разными инструментами. 

Ребята, спасибо за дискуссию. сейчас разобрался вроде, что мне на самом деле надо. 



Для кластеризации необходимо фичерсы как-то выделить, а в том и проблема, что их как-то определить надо..



Попробую открыть "секрет"  

Я тут занимаюсь "security in information outsourcing and retrieval".  

Надеюсь народ имеет представление об "inverted index"
Смысл в том, что коллекция из документов записывается в виде: слово:указатели_на_документы_содержащие_это_слово


Допустим следующие документы:

1) "светило солнце"
2)"солнце - самая близкая звезда и самая большая"

составят следующий индекс (по схеме: слово документ(кол-во)):

светило 1(1)
солнце 1(1),2(1)
самая 2(2)
близкая 2(1)
звезда 2(1)
большая 2(1)

Таким образом имея индекс очень легко найти интересующий документ без того, чтобы перелопачивать всё содержимое коллекции, а количество искомого слова в документе определяет "важность" документа. Но и имеющий индекс, может сказать всё про всё коллекцию. Чего нам и нельзя допускать. Даже если зашифровать слова и отдельные указатели, по их количеству можно догадаться, о каком слове идёт речь.


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

светило,солнце,звезда 1(1), 1(1), 2(1),  2(1)
самая,близкая,большая  2(2), 2(1), 2(1)

Это всё основано на теорвере и акцептировано научным миром (бумажка 109).

Вот только информация о количестве тоже зашифрована, потому что её распределение может рассказать о слове. Проблему эту решали (и решили здесь). Тем, что просто равномерно распределяем вероятностно обоснованные значения в одинаковых пределах для всех слов.

Осалось только проверитъ, насколько функция хорошо защищает слова, то есть может ли нападающий сказать, что например "в хвосте" слово "большая" более вероятно, или нет 

  

зубодробительно

Пока - да. Но ведь и работа пока не закончена. Сейчас причёсываю. Поэтому и пришлось конкретную проблему описать "на пальцах"..

Возьмём два слова, "и" и "нитропропилен", возмьём также 3 документа. 3 из них содежат "и", 2 - "нитропропилен".
информацию записываем в виде индекса, то есть каждая пара слово-документ - элемент в листе. дополнительно имеется инфа (rank), сколько раз в документе слово встречается. итого получаем 3+2=5 элементов записанных в виде: документИД:слово:количество_слова_в_документе

Е1 1:и:10 
Е2 2:и:15 
Е3 3:и:9 
Е4 1:"нитропропилен":2 
Е5 3:"нитропропилен":5

У каждого элемента шифруется первая часть и список сортируется по  rank, так что получается:

Е2:15, Е1:10, Е3:9, Е5:5, Е4:2

Это то, что видит нападающий. Незашифрованная часть нужна для сортировки элементов по "важности" (rank).

Теперь вопрос, как нападающему определить, в каком элементе находится какое слово?
В вышеописанном примере всё просто, нападающий знает, что слово "и" среднестатистически встречается чаще, чем "нитропропилен", а значит rank будет у них больше. Т.е он знает, что Е2 с большей вероятностью является словом "и", чем Е4.

Есть функция, которая трансформирует rank так, чтобы элементы распределились равномерно, при этом порядок одинаковых слов не изменился то есть она даст в идеальном случае:

Е5:5, Е2:4, Е1:3, Е4:2, Е3:1

Вот теперь и вопрос, как измерить, что функция действительно "спрятала" исходные значения. Сможет ли нападающий определить, где какое слово?

Чую просто тестом доказать не получиться, нужен алгоритм перемешивающей функции...

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

Можно замерить dist для каждого rank, где dist - это расстояние (количество позиций) между позицией элемента в перемешанном и не перемешанном рядах, для каждого элемента с выбранным rank. Получаем список rank => [dist1, dist2...], подсчитываем одинаковые расстояния, получаем множество {dist1:n1, dist2:n2...}, рисуем гистограмму. Собственно по частотам n1, n2... смотрим хорошо ли распределились расстояния (равномерно), т.е. доказать, что перемешивающая функция это в принципе не плохой генератор псевдослучайных чисел. Повторяем для каждого rank, накладываем гистограммы друг на друга, смотрим что бы диапазоны distN для каждого rank не "кучковались" (т.е. диапазоны более-менее равны, как и функции дистрибуции). Если получили общую гистограмму как один плотный прямоугольник, то функция перемешивания идеальна.

Количественную оценку можно вывести из разности дистрибуции nN внутри гистограммы (сумма разниц по квадрату от среднего к примеру), где 1 - площадь гистограммы это идеальный прямоугольник, 0 - на гистограмме полный хаос. Помножить на "кучковатость" диапазонов distN между rank'ами, т.е. взять разницу в диапазонах (разницу во множествах, к примеру среднее по элементам, разница в длинне и т.д.), 1 - диапазоны идеентичны (пересечение всех ==  каждому из них), 0 - пересечение диапазонов всех rank это пустое множество. Получим число [0-1], где 1 - перемешивающая функция идеальна (рандомно перемешивает), 0 - перемешивающая функция распределяет dist'ы не равномерно и/или диапазоны dist'ов для всех rank'ов не пересекаются.

Если два ряда вообще не перемешивать, то результат будет 1 - идеально   Что бы этого избежать, можно представить минимальный допустимый размер диапазона dist'ов - expected_dist_domain_size; посчитать средний размер множеств dist'ов каждого rank'а - mean_dist_domain_size; тогда оценку полученную выше перемножить на (mean_dist_domain_size / expected_dist_domain_size), но в таком случае можно получить оценку качества выше 1 (т.е. функция раскидывает элементы шире чем ожидалось).


P.S. перечитал... от меня на ночь торкнуло... но по идее это за более/менее честную оценку принять можно (статистика). Посчитать конечно ресурсоёмко будет... 

Всё же не могу понять архитектуру  Сергей, после предпоследнего твоего поста было всё более-менее понятно, а после последнего у меня вообще крыша съехала. 

Если есть возможность, попробуй пояснить, как это всё работает. Без этого сложно думать о "тонких вещах" (математике). Я полагал, что архитектура системы состоит из 3 частей: владелец индекса (actor 1), поисковая машина (actor 2) и ищущий пользователь (actor 3). Давай для простоты рассмотрим модель: sergejzr (actor 3) хочет найти в NewGoogle (actor 2) информацию из Клуба Винграда. Винград (actor 1) в данном случае поставляет индекс компании NewGoogle и не хочет по той или иной причине, чтобы NewGoogle что-то смог понять по этому индексу. Но хочет, чтобы sergejzr смог что-то найти в Клубе через поисковик NewGoogle. Далее, Винград выдаёт Сергею ключ, при помощи которого он может расшифровать результаты поиска NewGoogle. Более того, так как NewGoogle не знает (и не может знать) самих, собственно, слов индекса, Сергей сначала шифрует запрос и даёт Гуглу не чистый текст ("нитропропилен"), а зашифрованный вариант (грубо говоря, "AB6BBG7890"). ((Хотя, сейчас подумал, тоже непонятно, как это архитектурно устроить...))

В первом варианте (бумажка 109), как я понял, вы мешаете слова (то есть одному хэшу AB6BBG7890 соответствует несколько слов). Качество поиска падает, но при грамотном смешении слов не сильно. ((Кстати, можешь намекнуть, как именно вы мешали слова, если это не закрытая информация? Интересно, так как вы должны были сделать объединение в группы слов из разных тематик, чтобы не потерять ранк -- этакая атникластеризация, хотя, это тоже домыслы)) При этом мне, кажется, понятно, почему информацию о количестве нельзя публиковать (см. ниже рассуждения).

Теперь ты говоришь, что индекс выглядит как Е2:15, Е1:10, Е3:9, Е5:5, Е4:2. А что тогда sergejzr передаёт в качестве запроса Гуглу? Ведь теперь одному слову соответствует сразу 2, 3 и более хэшей?

А вообще, когда я исходил из понятой мной (видимо, неверно) модели, я рассуждал так.

Для начала надо понять, какая атака для нас опасна. То есть что мы не должны рассказать атакующему. Распределение само по себе вряд ли слишком опасно. То есть да, мы будем знать, что E1 -- это более вероятно "и", чем "нитропропилен", но... что далее? Как мы сможем понять содержимое коллекции из этого? Или как ещё мы сможем использовать информацию? Гораздо интереснее модель с ненулевым начальным знанием. Например, мы (NewGoogle) выкладываем в интернет документ, посвящённый определённой тематике (бомбы, терроризм и т. п.) и "вшиваем" в него какой-нибудь новый термин, который упоминаем в тексте ровно 21 раз. После этого смотрим, кто из пользователей обновил индекс: у кого появился новый термин с количеством использования 21. 3-5 таких "тестов" смогут достаточно хорошо понять аудиторию интересующихся "терроризмом". Далее мы можем отлавливать ещё и тех, кто по этому новому термину что-то ищёт (после того как поймём, как это слово шифруется). То есть я исхожу из того, что опасно не само распределение, а его "хвост" с малым количеством использования терминов. Ты исходишь примерно из той же модели атаки? А далее, если мы приходим к выводу, что нам опасен "хвост" -- может быть, его проще... отсечь? То есть дать всем "опасным" словам одинаковый ранк. Мне кажется, твои алгоритмы со склеиванием терминов и т. п. дают не меньшее искажение результатов поиска. Таким образом, у донора индекса в настройках получим такой "бегунок": на одном конце будет "ищем по вашим документам качественно", на другом "ищем безопасно для Вас". И график распределения будет уже не просто exp(-x), а exp(-x), которая с какого-то момента не падает, а устанавливается на определённом значении.

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

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



Да, верно. Секрет кроется в составлении таблицы слово-хэш. "мешание" (merging) присходит по вероятностной модели. То есть частые слова практически не "смешиваются" с другими, а вот редкие наоборот со многими. 

Здесь интересным оказался тот факт, что частые слова ищутся чаще. Поэтому поиск почти не искажается. Да, при поиске редких слов приходит много мусора, но на то они и редкие.



При поиске по хэшу (например sergejzr передал "AB6BBG7890") всегда возвращаются ВСЕ элементы, относящиеся к словам с этим хэшем. Это впринципе и было слабым местом системы. (Хотя эксперименты показали, что для коллекции в 200000 документов результат составил "всего" 24 кБ при размере "Хэш-таблицы" в 30168 строк)


Да, верно абсолютно. Но распределение опасно. Это мы в бумажке опишем. Конечно нельзя будет полностью сепарировать строки, но отдельные документы - вполне. А если у нападающего уже есть подозрения, то они усилятся именно на тот фактор "непохожести", который я пытаюсь промерять В самом худшем случае вероятность увеличится до 1 по сравнению с исходной. Вот этот фактор увеличения actor 1 должен знать. Иначе он не сможет решит, использовать нашу систему, или чего нибудь ещё.



Отличная атака. Но в эту бумажку уже не ляжет. 7 Марта дедлайн. Но на будущее конечно можно просимулировать и посмотреть 


Нет, одинаковый нельзя, усилится вероятность опять же..


Да, по этому принципу построена первая бумажка. Один хэш для всего - максимум секьюрити, индекс по типу слово - документы - минимум траффа.

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

ППС:
Кстати ключа у нас как такого нет, инфа распределяется на три сервера и только если получены ответы со всех трёх, комбинированный ответ и есть расшифровка.


Sardar, да, я тоже сперва думал о равномерности, но равномерность != максимум непохожести. Именно разница в равномерности между разными словами - проблема. Например я могу привести распределение к любому узору. Пока он действителен для всех слов - защита максимальна. А вот если узоры разные...

Добавлено @ 21:10
В аттаче - пример распределения ранка двух разных слов. "Смешивание" произойдёт, если одну картинку на другую наложить. Из графика видно, что некоторые части, заполненые точками одного слове не совпадают с точками другого слова. Они то как раз и станут видны нападающему.

Присоединённый файл ( Кол-во скачиваний: 18 )
 verteilung2.png 34,52 Kb

А бумажка 109 вот. После 25 Марта должна официально появится на ACM.
http://www.l3s.de/~olmedilla/pub/2008/2008-EDBT-Zerber.pdf

Присоединённый файл ( Кол-во скачиваний: 5 )
 Zerber.pdf 481,71 Kb

sergejzr, пусть у нас есть индекс Е5:5, Е2:4, Е1:3, Е4:2, Е3:1 (указанный тобой выше).

Я правильно понимаю, что владелец индекса знает, что Е1, Е2 и Е3 -- это "и", а Е4 и Е5 -- это "нитропропилен"? Ведь таблица хэшей открыта?

А вот номера документов он не знает: они "зашифрованы". То есть номера документов передаются клиенту, он их расшифровывает, обрабатывает и уже сам строит релевантность поиска.

Добавлено через 1 минуту и 27 секунд
За Zerber.pdf спасибо. Попробую посмотреть.

У всех них одинаковый хэш. Это те элементы, которые смешали в одну строку. 


Да, но там не только номера, но и правильное слово к каждому Е зашифровано.