1

Тема: Python в наукових дослідженнях

Хотів би започаткувати тут рубрику про застосування програмування на Python для вирішення наукових задач. Disclaimer: для багатьох пітоністів, як і для багатьох людей, пов'язаних таким чи іншим чином з науковою роботою, дані пости можуть бути очевидними. Але можливо для когось це буде цікавим матеріалом.
Передісторія. Я вчуся в аспірантурі на спеціальності "Автоматизація процесів керування". Об'єкт дослідження доволі вузькоспеціалізований, але він не має значення. Предмет дослідження ж - ідентифікація технічних станів промислових об'єктів. Пройшло перші півроку, і зараз я активно працюю в напрямі дата-майнінгу - застосуванням різних методів обробки до наявних даних з метою отримання додаткової, неочевидної на перший погляд інформації. Це виявлення прихованих періодичностей, трендів тощо. В даний момент мене зацікавив розклад часових рядів технологічних параметрів (допустимо, температури вузла, або вібраційної швидкості підшипника) в нетривіальні базиси. Зазвичай розклад відбувається по функціях Фур’є, але є інші базиси, простіші для обробки комп’ютерами: функції Радемахера, Хаара, Крестенсона, Уолша. І дають вони доволі цікаві результати. Однак, невідомо, чи це буде цікаво середньостатистичному читачу цього форуму. Є тема ближча - алгоритми стискання.
Маленька теоретична підготовка
Коли я рився в інтернеті в пошуках інформації про функції Хаара, натрапив на цікаву статтю на одному відомому російському ресурсі. Там функція (або вейвлет) Хаара застосовувалася для стистення зображень. Сама функція виглядає дуже просто:
http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Haar_wavelet.svg/320px-Haar_wavelet.svg.png?uselang=ru
Як же стискалося зображення? Просто, як двері: для чорно-білого фото бралися значення сусідніх пікселів і в один масив записувалася їх півсума, а в другий їх піврізниця. І так для кожної пари пікселів. А потім масив піврізниць просто відсікався. Таким чином, ми отримували масив удвічі меншого розміру з усередненими значеннями для кожної пари пікселів. Повторюся, все дуже просто.
А тепер найцікавіше: а як же втрати? Втрати для кожного конкретного випадку будуть дуже різними. Допустимо у нас є зображення, подібне до шахової дошки - білий піксель-чорний піксель і т.д. Після першого такого стискання у нас вийде повністю сіре зображення. Зміст повністю втратиться, чого нам дуже не хотілося б.
На щастя, реальні фотографії характерні тим, що сусідні пікселі мають дуже близькі значення. І до них цей метод стиснення застосовується доволі ефективно.
Ми зациклилися на зображеннях. В даному випадку чорно-білі зображення - це всього лиш масиви значень відтінку сірого для кожного пікселя. Довгий час працюючи з технологічними параметрами мого об'єкта дослідження, я приблизно вивчив їх характер змін у часі. Специфіка така - з кожного давача значення знімається кожних 5 хвилин. І, так вже сталося, що дані технологічні об’єкти майже не мають змін у параметрах функціонування з коротким періодом - сусідні значення у більшості випадків рівні, або майже рівні. Тому я вирішив просто для себе провести
Стискання масиву часового ряду одного параметра з допомогою вейвлета Хаара
Скільки тексту прийшлося написати, щоби нарешті дістатися до коду=) Підключав я для цього дві бібліотеки - scipy.io (для завантаження даних з файлу .mat, в якому вони зберігалися по замовчуванню) та pylab (для перегляду проміжних резутьтатів).
Функція load (для завантаження даних):

def load():
    data = scipy.io.loadmat('data0.mat')
    mdata=data['data0']
    return mdata

Функція compress (для стискання цих даних):

def compress(mdata):
    a=[]
    b=[]
    isEven=[]
    for e in mdata:
        b.append(e)
    if len(mdata)%2==0:
        isEven.append(True)
    else:
        b.append(mdata[len(mdata)-1])
        isEven.append(False)
    for e in range(int(len(b)/2)):
        a.append((b[e*2]+b[e*2+1])/2)
    return a

В принципі, пояснювати тут нічого. Єдине - масив isEven я думав застосовувати в перспективі, поки що обходиться без нього. Відповідно, приведу тут же функцію decompress:

def decompress(a):
    rdata=[]
    for e in a:
        rdata.append(e)
        rdata.append(e)
    return rdata

Все просто - вона дублює значення зі стиснутого масиву. Що ж у нас вийшло в резутьтаті? Ось вихідні дані:
http://i47.сайт-злодій/big/2013/0622/0f/c28d03192936fe8833e277c7f0b1d10f.png
А ось відновлені:
http://i48.сайт-злодій/big/2013/0622/e4/fcded02c8c909aac99594252680e11e4.png
Ви бачите різницю? Я ні. І це при стисненні в 2 рази! Однак, людське око - штука непевна. Давайте подивимося, що скаже нам про ці дані комп’ютер. Для порівняння вихідних та відновлених даних була написана функція compare:

def compare(mdata,rdata):
    i=0
    mmean=sum(mdata)/len(mdata)
    rmean=sum(rdata)/len(rdata)
    s1=0
    s2=0
    s3=0
    for e in range(len(mdata)):
        s1+=(mdata[e]-mmean)*(mdata[e]-mmean)
        s2+=(rdata[e]-rmean)*(rdata[e]-rmean)
        s3+=(rdata[e]-rmean)*(mdata[e]-mmean)
    r=s3/((s1*s2)**0.5)
    print r
    for e in range(len(mdata)):
        if mdata[e]==rdata[e]:
            i=i+1
    print float(i)/len(mdata)

Функція ця виводить два значення. Спочатку про друге - цілком логічна штука - відношення співпадінь значень у відновлених і вихідних даних до загальної кількості даних. Однак математики користуються іншим критерієм - коефіцієнтом лінійної кореляції (студенти, які вчили теорію ймовірності і матстатистику, мали б бути знайомі з цим поняттям). Його формула дуже проста, вона є у Вікіпедії, не буду переписувати інформацію звідти. Власне змінна r якраз і є цим коефіцієнтом.
Які ж вони результати дають нам при стисненні в два рази?
Коефіцієнт лінійної кореляції: 0.99426435
Кількість значень, що співпали: 0.959474885845
Погодьтеся, не найбільші втрати при такому стисненні. Кореляція в 99,4% - це взагалі прекрасний результат.
Ви можете сказати: окей, чувак, ти взяв такий відрізок з однієї з функцій і воно так красиво працює. Що з іншими? Проведемо ці самі операції стиснення з 5 різними параметрами - серед них є і температура, і тиск, і віброшвидкість. Більше того, додамо результати для стиснення в 4 та 8 раз, провівши стиснення та відновлення 2 та 3 рази відповідно. Що ми отримуємо? Ідентичність значень:
http://i47.сайт-злодій/big/2013/0622/16/ace1da60e1af4399497d057c7530b816.jpg
Коефіцієнт кореляції для цих значень:
http://i46.сайт-злодій/big/2013/0622/48/7aa254097eebc0449ee69c2e9fde5d48.jpg
Можете побачити, як відновлення залежить від характеру даних. Тому, якщо оформляти цей алгоритм "по-дорослому", хорошим рішенням буде його проектування з деякою мірою адаптивності відносно вихідних даних. Тим не менше, відновлена функція після стиснення у 8 разів корелює з вихідними даними на 96-99%.
Я думаю, що проведені операції дають можливість зробити логічний
Висновок:
даний метод стискання до даних такого характеру можна ефективно застосовувати, більше того, він може бути елементом більш вдосконаленого алгоритму стискання, що прекрасно працюватиме з подібними даними, сусідні значення яких дуже подібні.
P.S. Власне я продовжив розвивати тему удосконалення цього алгоритму, і в мене дещо вийшло. Якщо вам буде цікаво, із задоволенням поділюся=)

2

Re: Python в наукових дослідженнях

Бачу декілька подяк, але відгуків чи запитань не видно. Тому запитаю - варто продовжувати? Пропоную сюди ж скидувати ваші програмні реалізації речей, близьких до наукової області - алгоритмів, методів, вирішення прикладних задач. Від себе можу порадити книжку "Python for Data Analysis" - докладний опис інструментів роботи з даними. У більшості випадків для задач, наприклад, моєї сфери діяльності, це непоганний замінник такому монстру, як Matlab.

3

Re: Python в наукових дослідженнях

slabinoha написав:

Бачу декілька подяк, але відгуків чи запитань не видно. Тому запитаю - варто продовжувати?

так

4

Re: Python в наукових дослідженнях

так, цікаво, але для мене трохи складнувато. Спробую пізніше більш детально глянути та розібратись що до чого :)

5

Re: Python в наукових дослідженнях

Replace написав:

так, цікаво, але для мене трохи складнувато. Спробую пізніше більш детально глянути та розібратись що до чого :)

Так розпитуйтеся, я з із задоволенням все поясню :)

6

Re: Python в наукових дослідженнях

Декомпресія дуже проста, дані просто дублюються. Можна спробувати для відновлення початкових даних використовувати кожного разу не одне значення масиву a[], а кілька сусідніх. Хоча для даних, де сусідні значення досить близькі, алгоритм даватиме нормальні результати.
Те, що коефіцієнт кореляції близький до 1, ще може нічого не означати. Потрібна якась інша перевірка. Наприклад, застосувати цей алгоритм до зображення і подивитися на результат. Особливо гарним показником буде трикратне застосування.

Подякували: slabinoha1

7

Re: Python в наукових дослідженнях

Можна спробувати для відновлення початкових даних використовувати кожного разу не одне значення масиву a[], а кілька сусідніх.


Власне, це один зі способів вдосконалення цього алгоритму. Таку "декомпресію" я додав тільки для наочного порівняння даних з вихідного і стисненого масиву. Я поступив ще іншим способом, напишу про це, ймовірно, завтра :)

Хоча для даних, де сусідні значення досить близькі, алгоритм даватиме нормальні результати.

Мова і йшла про застосування алгоритму до таких даних. Це можна назвати частковим випадком, якщо брати сигнали загалом, однак у даного об'єкта досліджень дані мають ось таку характерну рису.

Потрібна якась інша перевірка. Наприклад, застосувати цей алгоритм до зображення і подивитися на результат.

Цим уже займалися на згаданому мною російському сайті (якщо хочете, прорекламую, ось ця стаття http://habrahabr.ru/post/168517/ з купою математики). Для прикладу просто приведу картинку з восьмикратним стисненням з цієї ж статті
http://habrastorage.org/storage2/021/12e/919/02112e9190211983d73dd09ac6135aa3.png
тут, щоправда, піврізниці не відкидалися (вся темна область - це якраз піврізниці - зображення, стиснуте у 8 разів - у верхньому лівому куті.

8

Re: Python в наукових дослідженнях

дуже цікаво, продовжуй дальше

9

Re: Python в наукових дослідженнях

Як я розумію, у вас формат даних після стискання той самий, що й до стискання. Якщо це не обов’язково, то для таких даних набагато краще підійде запис пар елементів: значення і кількість його повторів у початковому потоці даних.

10

Re: Python в наукових дослідженнях

Torbins написав:

Як я розумію, у вас формат даних після стискання той самий, що й до стискання. Якщо це не обов’язково, то для таких даних набагато краще підійде запис пар елементів: значення і кількість його повторів у початковому потоці даних.

Якщо я вас правильно зрозумів, то так, це буде хорошим способом стискання на таких даних. Однак тут я розглядав саме стискання з допомогою вейвлету Хаара. Як варіант комбінації таких рішень, можна подібним чином кодувати послідовності нулів у масиві піврізниць, і не відкидати його. Тоді можна добитися стиснення без втрат, однак коефіцієнт стискання буде непостійним і коливатися в межах від 50%+2 значення (якщо всі числа масиву рівні) до 0 (якщо жодні два сусідні числа не рівні).

11

Re: Python в наукових дослідженнях

Прихований текст

хостинг картинок бажано замінити: "діти на форумі". :)

12

Re: Python в наукових дослідженнях

Як і обіцяв, дописую те, як продумав
Вдосконалення алгоритму стиснення з використанням базису Хаара
Тут прозвучало декілька пропозицій щодо такого вдосконалення, зокрема

Можна спробувати для відновлення початкових даних використовувати кожного разу не одне значення масиву a[], а кілька сусідніх

та

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

Обидві пропозиції є хорошим доповненням до алгоритму і, можливо, автори захочуть реалізувати їх (дуже самонадіяно, та все ж :) ), тому додам до цього поста свій файл з даними.
Щодо мого методу вдосконалення, то в попередньому пості я наводив графік. Як бачимо, окремі ряди рівних даних чередуються з доволі помітними перепадами. Тому досить простим рішенням буде записувати місце такого перепаду і дані з нього.
Але для початку треба вирішити, який перепад вважати значним, а який можна не враховувати. Це важливо тільки на даному етапі. Візьмемо для прикладу довільну величину. В мене під рукою була функція, що визначає середньоквадратичне відхилення:

def sigmacalc(mdata):
    mean=float(sum(mdata))/len(mdata)
    summ=0
    for e in mdata:
        summ+=(e-mean)*(e-mean)
    sigma=(float(summ)/len(mdata))**(0.5)
    return sigma   

Давайте допустимо, що всі перепади, більші від даної величини, ми будемо документувати. Ось функція стиснення:

def acompress(mdata):
    a=[]
    b=[]
    c=[]
    d=[]
    isEven=[]
    sigma=sigmacalc(mdata)
    for e in mdata:
        b.append(e)
    if len(mdata)%2==0:
        isEven.append(True)
    else:
        b.append(mdata[len(mdata)-1])
        isEven.append(False)
    for e in range(int(len(b)/2)):
        if abs(b[e*2]-b[e*2+1])>sigma:
            k=(b[e*2]-b[e*2+1])/2
            c.append(k)
            d.append(e)
        b.append((b[e*2]+b[e*2+1])/2)
    return a,c,d

У масив c заноситься піврізниця пари значень,у масив d заноситься позиція першого значення з пари.
Відновлення відбувається так само, як в попередньому алгоритмі, крім одного нюансу - при додаванні елементів на позицію програма перевіряє масив d на рахунок поточної позиції, якщо така позиція є в масиві, то дані повністю відновлюються із півсуми і піврізниці. Код функції відновлення:

def adecompress(a,b,c):
    rdata=[]
    for e in range(len(a)):
        if e in c:
            for i in range(len(c)):
                if c[i]==e:
                    rdata.append(a[e]+b[i])
                    rdata.append(a[e]-b[i])
        else:
            rdata.append(a[e])
            rdata.append(a[e])

На моїх даних перепад перевищив задане значення в 12 випадках. Тобто на приблизно 3200 значень стиснулися до 1624. Застосуємо попередню функцію compare(). Отримані результати:
0.99907766
0.96404109589
Нагадаю, для попереднього способу стиснення значення були рівні:
Коефіцієнт лінійної кореляції: 0.99426435
Кількість значень, що співпали: 0.959474885845
Як бачимо, точність збільшилася ще на піввідсотка, а кореляція значень 0.999 - це взагалі класний показник.
Але це не головне.
Змінюючи порогове значення, яким у нас в даному випадку виступав результат функції sigmacalc() в більшу чи меншу сторону, ми зможемо робити доволі круту річ - добиватися потрібного ступеня стиснення, потрібного ступеня відновлення, або оптимального відношення між ними, яке потрібне користувачу. Якщо точніше - якщо ми задамо вищий поріг, то у нас буде менше значень в допоміжному масиві, стиснення, відповідно буде кращим. Якщо ми знизимо поріг - то значень буде більше, стиснення буде меншим, але зате ми зможемо досягнути потрібної точності відновлення.
Ось такі прості рішення дозволяють розібратися у стисненні даних і самим щось придумати :)

Подякували: Replace, Очі.завидющі, leofun013

13

Re: Python в наукових дослідженнях

Безголовий, забув додати дані для роботи.

Post's attachments

data0.mat 27.56 kb, 737 downloads since 2013-06-23 

14 Востаннє редагувалося Torbins (23.06.2013 18:49:22)

Re: Python в наукових дослідженнях

slabinoha
Спробував стиснути ваші дані моїм методом, тобто без втрати інформації:
http://replace.org.ua/misc.php?action=pun_attachment&item=186
Жаль, що у ваших даних такі чіткі сходинки, інакше тут іще можна було б розгулятися.
Хоча з іншого боку тепер можна продовжити обробку уже стиснутих даних, і стиснути їх іще більше.

Post's attachments

MathLab.png 17.05 kb, 330 downloads since 2013-06-23 

Подякували: slabinoha, leofun012

15

Re: Python в наукових дослідженнях

Torbins, можна поцікавитися, як ви записували дані? Просто послідовність пар (значення, кількість повторів)?

16

Re: Python в наукових дослідженнях

Так. Правда під кількість повторів я виділив однобайтову змінну, тому у мене максимальна кількість повторів становила 255. Тобто в цілому на одну пару витрачалося 9 байт.

Подякували: slabinoha1

17

Re: Python в наукових дослідженнях

То вже якась реінкарнація PCX формату :)