Анализ числовой последовательности.

[Kreol]

День добрый.

Задачка на первый взгляд простенькая, но для меня превратилась в сущую проблему ....
Итак, дана некая числовая последовательность из нулей и единиц. Требуется при помощи n метода проанализировать данную последовательность и выдать прогноз на 1 цифру вперёд.
Собственно вопросы :
1) Какой метод прогнозирования в данном случае лучше всего подходит ?
2) С помощью какой программы можно осуществить прогнозирование по этому методу и получить желаемый результат ?
3) Какой метод и какая программа лучше всего подходят для анализ числовых последовательностей В ОБЩЕМ ?

Примечания :
а) Мною были произведены попытки анализа, используя средства excel. Я находил автокорреляцию, с помощью соответствующей надстройки (http://www.hcxl.ru/af02.html). Однако удовлетворительных результатов я не получил.
б) С математикой, как и с программированием я честно говоря на "Вы" (иначе бы сюда не писал). Поэтому требуется что-то мощное и действенное, но в то же время простое.
в) Я больше склоняюсь к пакету STATISTICA, но как уже упоминалось в программировании я не силён, да и разбираться в самой программе для меня будет трудновато.

P.S
Также мною была создана тема тут (www.sql.ru/forum/actualthread.aspx?bid= ... 2807&pg=-1) , а на этом форуме была похожая тема тут (topic30857.html). Буду благодарен, если заинтересовавшиеся пользователи также прочтут эти ветки, поскольку какой-никакой результат в них получен. Возможно это поможет.

Заранее спасибо.

[Circiter]

2Kreol
Есть такая "сисадминская" шутка, использующаяся некоторыми генетиками, не любящими программировать. Записываете вашу последовательность в текстовый файл. Например, запишем 1110111011101110 в файл data; подразумевается, что следующий "бит" будет скорее всего единицей. Теперь последовательно выполним две команды:

$ echo 1 | cat data - | gzip -9 | wc -c
27
$ echo 0 | cat data - | gzip -9 | wc -c
28

Как видите, исходные данные лучше сжались именно при добавлении к ним единицы -- сжатый результат занимает 27 байт против 28. Значит статистически единица здесь действительно более вероятна. :)

Вообще, для решения вашей задачи, думаю, неплохо подошли бы скрытые марковские модели aka HMM. Как-то до них в упомянутой вами соседней теме дело не дошло, хотя я для себя и сделал кое-какие наброски кода (далекие от завершенности). Может быть потом как-нибудь в той теме поделюсь результатами, а пока лень... Да и наверняка в интернете подобных вещей предостаточно, нужно только хорошенько поискать... :)

[Kreol]

Circiter в сообщении #369560 писал(а):

2Kreol
Есть такая "сисадминская" шутка, использующаяся некоторыми генетиками, не любящими программировать. Записываете вашу последовательность в текстовый файл. Например, запишем 1110111011101110 в файл data; подразумевается, что следующий "бит" будет скорее всего единицей. Теперь последовательно выполним две команды:

$ echo 1 | cat data - | gzip -9 | wc -c
27
$ echo 0 | cat data - | gzip -9 | wc -c
28

Как видите, исходные данные лучше сжались именно при добавлении к ним единицы -- сжатый результат занимает 27 байт против 28. Значит статистически единица здесь действительно более вероятна. :)

Вообще, для решения вашей задачи, думаю, неплохо подошли бы скрытые марковские модели aka HMM. Как-то до них в упомянутой вами соседней теме дело не дошло, хотя я для себя и сделал кое-какие наброски кода (далекие от завершенности). Может быть потом как-нибудь в той теме поделюсь результатами, а пока лень... Да и наверняка в интернете подобных вещей предостаточно, нужно только хорошенько поискать... :)

Спасибо, что откликнулись.

Да, на соседнем форуме мне порекомендовали воспользоваться архиватором, а конкретнее

Цитата:

нужно написать маленькую программку которая поделит вашу последовательность по 8 элементов. С каждого блока по 8 элементов нужно получить байт. С байтов получите файл.
Тоесть если у вас последовательность 8000 символов то должен получится файл размером около 1 кбайт.

Только вот сам я подобную программку написать не смогу. Поэтому возможно вы знаете аналоги в интернете ?

Насчёт моделей. В какой программе их можно опробовать в действии ?

На данный момент я наиболее склонен к нейросетям, потому что они наиболее для меня доступны.
Я установил STATISTICA 8.
Открыл свой файлик, выделил диапазон и зашёл в data meaning > automated neural networks .
Дальше мне предлагают выбрать тип анализа :
Regression
Classification
Time series (regression)
Time series (classification)
Cluster analysis
Какой выбирать то ? К сожалению с дуру выбрал самую новую версию, к которой нет русского руководства.

[Circiter]

2Kreol

Цитата:

Насчёт моделей. В какой программе их можно опробовать в действии ?

Не знаю. Я потихоньку пишу собственный софт, но, как я уже сказал, закончу не скоро (в упомянутой теме были кое-какие близкие примеры предикторов, а именно гадалка Шеннона и демоны Эшби). К тому же, я до сих пор толком не разобрался с мат.частью. :) Так что рекомендую начать, например, с соответствующей статьи в вики, а там уже по ссылкам побегать.

Цитата:

На данный момент я наиболее склонен к нейросетям, потому что они наиболее для меня доступны.

В ещё одной соседней теме давалась прекрасная ссылка на Matthew V.Mahoney, Fast Text Compression with Neural Networks. Непосредственно про саму компрессию там можно и не читать, только про предикцию. А так не знаю, что посоветовать, я в сторону ИНС в контексте предсказаний никогда не смотрел...

[e2e4]

Прекрасная программа с описанием по поднятой топикстартером теме.

[Kreol]

Circiter в сообщении #369626 писал(а):

2Kreol

Цитата:

Насчёт моделей. В какой программе их можно опробовать в действии ?

Не знаю. Я потихоньку пишу собственный софт, но, как я уже сказал, закончу не скоро (в упомянутой теме были кое-какие близкие примеры предикторов, а именно гадалка Шеннона и демоны Эшби). К тому же, я до сих пор толком не разобрался с мат.частью. :) Так что рекомендую начать, например, с соответствующей статьи в вики, а там уже по ссылкам побегать.

Цитата:

На данный момент я наиболее склонен к нейросетям, потому что они наиболее для меня доступны.

В ещё одной соседней теме давалась прекрасная ссылка на Matthew V.Mahoney, Fast Text Compression with Neural Networks. Непосредственно про саму компрессию там можно и не читать, только про предикцию. А так не знаю, что посоветовать, я в сторону ИНС в контексте предсказаний никогда не смотрел...

Теория она и есть теория. Я к тому что меня ей можно напичкать, как плюшевого мишку ватой, но осуществить эту теорию при всём моём желании и знаниям по программированию=0, невозможно.
На данный момент мне бы со СТАТИСТИКОЙ разобраться ИЛИ с гадалкой.

e2e4, прочитайте пожалуйста, что я написал насчёт этой программы.

[e2e4]

Где же я должен это прочитать?

[Circiter]

Ну это он про + и -. Правда, это, кажется, на другом форуме было. :)

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

2Kreol
Сисадминский хак вам не подошел? Я же говорю, некоторые ленивые генетики вот так вот через архиваторы анализируют ДНК-последовательности. :)

[Kreol]

Circiter в сообщении #369731 писал(а):

Ну это он про + и -. Правда, это, кажется, на другом форуме было. :)

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

2Kreol
Сисадминский хак вам не подошел? Я же говорю, некоторые ленивые генетики вот так вот через архиваторы анализируют ДНК-последовательности. :)

Я же вроде писал уже :)

Цитата:

Только вот сам я подобную программку написать не смогу. Поэтому возможно вы знаете аналоги в интернете ?

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

[Circiter]

2Kreol

Цитата:

Я же вроде писал уже :)

Цитата:

Только вот сам я подобную программку написать не смогу. Поэтому возможно вы знаете аналоги в интернете ?

Вы про программку ltwood'а, которая свободно скачивается, или про мою попытку C++ реализации, которая лежит неподалеку на этом форуме, или про shell-хак, для которого вообще ничего писать не нужно? :)

[Kreol]

Circiter в сообщении #369801 писал(а):

2Kreol

Цитата:

Я же вроде писал уже :)

Цитата:

Только вот сам я подобную программку написать не смогу. Поэтому возможно вы знаете аналоги в интернете ?

Вы про программку ltwood'а, которая свободно скачивается, или про мою попытку C++ реализации, которая лежит неподалеку на этом форуме, или про shell-хак, для которого вообще ничего писать не нужно? :)

Это я про "сисадминскую" шутку :)

[Circiter]

2Kreol

Цитата:

Это я про "сисадминскую" шутку :)

Вот я и не понимаю, что вам мешает ею воспользоваться? Куда уж проще? Вбил две команды в консоль и готово. :)

[Kreol]

Circiter в сообщении #369906 писал(а):

2Kreol

Цитата:

Это я про "сисадминскую" шутку :)

Вот я и не понимаю, что вам мешает ею воспользоваться? Куда уж проще? Вбил две команды в консоль и готово. :)

Вы меня наверное меня кирпичами закидаете, если я спрошу, где взять консоль, две команды и как их все связать с моим файликом ?

[Circiter]

О боже... Записываете ваши данные в файлик, но в конце добавляете единичку. Пакуете этот файлик любым подходящим архиватором (хоть gzip, хоть winrar, правда последним я не пробовал). Замеряете размер архива в байтах. Теперь опять лезете в исходный файлик, меняете добавленную единичку на ноль и снова пакуете и замеряте размер. Если в первом случае размер будет меньше, значит следующим битом должна быть единица, иначе -- ноль. :)

[Kreol]

Circiter в сообщении #370551 писал(а):

О боже... Записываете ваши данные в файлик, но в конце добавляете единичку. Пакуете этот файлик любым подходящим архиватором (хоть gzip, хоть winrar, правда последним я не пробовал). Замеряете размер архива в байтах. Теперь опять лезете в исходный файлик, меняете добавленную единичку на ноль и снова пакуете и замеряте размер. Если в первом случае размер будет меньше, значит следующим битом должна быть единица, иначе -- ноль. :)

Мне помог пользователь параллельного форума, за что ему огромное спасибо.

Цитата:

Немного поэкспериментировал на присланных мне данных.

Попробовал посжимать разными способами. Замечательно сжимает раз в 5-6. Но никаких особых зависимостей оно не нашло.

Попробовал статистику получить, в том числе по подряд идущим группам цифр (от 1 до 20 подряд со сдвигами, с разными шагами). Группы, длиной больше 20 изучать тяжеловато, плюс, начиная с 10 они становятся практически равномерно распределенными.

По результатам экспериментирования у меня процент правильных предсказаний около 50-60% на окне в 500 последовательных точек (угадал или не угадал =) ). Если брать всю последовательность, результат получается в районе 50%, так что, к сожалению, мне не удалось найти какую-либо явную зависимость. Если ее внимательно изучить, то получится на самом деле, что данная последовательность состоит из подпоследовательностей (см картинки ниже) ( приблизительно 0-600, 600-1100, 1100-2200, 2200-2880). Если по группам, то результат дает в районе 60% (что не легче)

Пробовал еще моделировать ядрами Винера-Вольтерра. Но опять же они не для бинарных данных. Еще пробовал по системам с памятью на основах этих ядер - результат аналогичен. Алгоритм Берлекэмпа-Мэсси тоже отправился в топку. Всякие вкусные корреляции поехали следом, так как мы получаем значения вроде 0,05+-0,1. К сожалению больше мне ничего не удалось припомнить.

На закусь.

График 1.
http://i51.tinypic.com/15fksuc.png
Визуализация по данным. Как вы понимаете 0 и 1 показывать на графике бесполезно. Поэтому я сделал небольшое отображение и просуммировал, где 0 это -0,5, а 1 это +0,5.
Получилось интересный график суммы. Можно еще попробовать поисследовать его. Разложить например по частотам, сделать какое-нибудь сглаживание, но тогда мы уже будем не нули и единицы предсказывать, а поведение этого графика, что не есть хорошо.

График 2.
http://i56.tinypic.com/17rfyb.png
Визуализация по первым девяти группам цифр. По оси ординат частота той или иной группы деленная на максимальную, по оси абсцисс, числа, соответствующие последовательностям в двоичной системе счисления (например 23 это 10111).

При взгляде на вторую картинку меня не оставляла мысль, что там фрактал или что-то подобное лежит в основе.

Т.е что-то уже можно исключить. Какие ещё варианты ?