Porządkowanie skorup i statystyka

Data ostatniej modyfikacji:
2019-12-18
Autor: 
Andrzej Dąbrowski
emerytowany pracownik IM UWr
Poziom edukacyjny: 
gimnazjum
szkoła średnia z maturą
szkoła profilowana zawodowa
szkoła wyższa
Dział matematyki: 
statystyka

W 1899 roku podczas wykopalisk w Diospolis Parva nad brzegiem Nilu, wieczorami można było spotkać mężczyznę w sile wieku zajmującego się dziecinną zabawą w przestawianie pasków papieru. Człowiekiem tym był znakomity archeolog brytyjski Flinders Petri. Przestawianie pasków papieru było łamigłówką, której rozwiązanie daje możliwość datowania znalezisk archeologicznych.

W owym czasie nie były znane bezwzględne metody datowania, takie jak metoda datowania radiowęglowego, odkryta około roku 1940. Datowanie względne opierało się na porównywaniu warstw wykopalisk – im głębiej – tym wcześniej. Czasami można było ocenić wiek niektórych warstw  na podstawie dodatkowych źródeł i wtedy układanka stawała się bardziej precyzyjna.

Niestety, w wykopaliskach w Diospolis Parva napotkano na stanowiska z ceramiką w grobach o nieznanym datowaniu. Tu nie można już było zastosować porządku wyznaczonego przez kolejne warstwy. Petrie wpadł na pomysł, aby spróbować odtworzyć właściwą chronologię grobów (takie działanie nosi nazwę seriacji) wychodząc z założenia, że podobne motywy na ceramice występują w sąsiednich czasowo grobach oraz, że w okresach przejściowych mogą występować jednocześnie kilka motywów z bliskich chronologicznie pochówków.

Przypuśćmy, że w czterech grobach A,B,C,D występują konfiguracje motywów  ♦ ▲ ●. Petrie zapisywał takie konfiguracje na 4 paskach papieru w ten sposób, że w każdej kolumnie występowały te same motywy:

A

B

C

D

Należy te paski tak przestawić aby uzyskać konfigurację, gdzie takie same motywy są w sąsiedztwie. W tym przypadku nie jest to trudne. Układ CABD daje pożądane uporządkowanie wskazujące, że najstarszym pochówkiem jest D, potem B, następnie A i najmłodszy pochówek C. Tabela tak uporządkowana nosi nazwę macierzy Petriego.

 

C

A

B

D

Zawsze możliwe jest bliźniacze uporządkowanie DBAC odpowiadające odwrotnemu uporządkowaniu czasu. Uwzględniając tą symetrię, wszystkich uporządkowań wierszy w tym przypadku jest 4!/2=12. Często porządkuje się też kolumny, co pozwala skojarzyć motywy z chronologią. Można przypuszczać, że najwcześniej występującym chronologicznie motywem są trójkąty, potem koła a później romby.

C

A

B

D

 

Przy n pochówkach jest  n!/2 uporządkowań. Na przykład, przy n=10 pochówkach jest to 1 814 400 możliwych uporządkowań i trudno bez jakiegoś algorytmu znaleźć właściwą seriację. Profesor Petrie mógł próbować ustalić seriację jedynie gdy miał do czynienia z małą liczbą pochówków. Sprawa jest tym bardziej trudna, że czasami nie istnieje permutacja wierszy prowadząca do macierzy Petriego, jak w tym przykładzie

A

B

C

W takim przypadku poszukuje się takiej permutacji wierszy macierzy, która prowadzi do macierzy bardzo zbliżonej do postaci Petriego.

Niestety, przez kolejnych 70 lat nie poczyniono żadnego postępu.  Sprawa posunęła się naprzód gdy zajęli się nią matematycy i statystycy. W roku 1969 wybitny brytyjski matematyk, twórca archeologii matematycznej, David Kendall, udowodnił twierdzenia, które ułatwiały znalezienie permutacji wierszy przekształcających macierz do postaci Petriego o ile to jest możliwe.  Metody te nie wskazywały jednak sposobu wyznaczenia tej permutacji, jedynie upraszczały ich poszukiwanie metodą prób i błędów. Nie dawały też w ogóle wskazówki jak skonstruować permutację tworząca macierz najbardziej zbliżoną do postaci Petriego.

Okazało się, że można tu wykorzystać metody stosowane w statystycznej metodzie zwanej analizą korespondencji. Zapiszmy macierz opisującą motywy występujące w pochówkach
 

A

B

C

D

przy pomocy macierzy incydencji:

 
A101
B001
C100
D011

1 na przecięciu wiersza i kolumny oznacza wystąpienie w danym wierszu symbolu, opisanego w tej  kolumnie, 0 – oznacza niewystępowanie tego symbolu. Macierz Petriego  ma w każdej kolumnie jedynki występujące w kolejnych wierszach.

Kluczowym pomysłem analizy korespondencji jest spójna punktacja wierszy i kolumn dla macierzy incydencji. Pojęcie to można przedstawić na przykładzie dla powyższej macierzy incydencji.

Przypuśćmy, że wiersze  A,B,C,D wyceniono jako -1;0,1;0,7 i 2

   
A101 -1,0
B001 0,1
C100 0,7
D011 2,0

Wycena wierszy wyznacza wycenę kolumn. Na przykład, wycena pierwszej kolumny, przypadająca na jeden obiekt wynosi: (-1,0+0,71)/2= -0,15, drugiej kolumny 2,0/1=2,00, trzeciej (-1,0+0,1+2,0)/3=0,37

   
A101 -1,0
B001 0,1
C100 0,7
D011 2,0
 -0,152,000,37  

Wycena kolumn wyznacza wtórną wycenę wierszy: dla pierwszego wiersza (-0,15+0,37)/2=0,11, dla drugiego 0,37 dla trzeciego -0,15 dla czwartego (2,00+0,37)/2=1,18

    
A101 -1,0 0,11
B001 0,1 0,37
C100 0,7 -0,15
D011 2,0 1,18
 -0,152,000,37    

Z kolei wtórna ocena wierszy wyznacza wtórną wycenę kolumn:

    
A101 -1,0 0,11
B001 0,1 0,37
C100 0,7 -0,15
D011 2,0 1,18
 -0,152,000,37    
 -0,021,180,55    

Ocena wierszy (kolumn) jest stabilna jeśli oceny wtórne i pierwotne dla wierszy i kolumn są proporcjonalne z tym samym współczynnikiem proporcjonalności. Tutaj tak nie jest, gdyż 0,11/-1,0= -0,11 , 0,37/0,1=3,7 .

Zawsze istnieje stabilna wycena trywialna, dająca każdemu wierszowi i kolumnie wycenę 1. Współczynnik proporcjonalności wyceny trywialnej wynosi 1.

Okazuje się, że dla macierzy o w wierszach i k kolumnach jest min(w,k)-1 nietrywialnych wycen stabilnych o dodatnim  współczynniku proporcjonalności. I co najważniejsze:

Nietrywialna wycena stabilna o największym współczynniku proporcjonalności wyznacza permutację wierszy i kolumn prowadzącą do macierzy, najbliższej macierzy Petriego. Kolejność wierszy/ kolumn  odpowiada porządkowi wycen wierszy/kolumn.

Wycena pierwotna i wtórna w naszym przykładzie  (rozpoczęto od wyceny pierwotnej dla kolumn), odpowiadająca największemu współczynnikowi proporcjonalności 2/3

    
A101 -1 -2/3
B001 1 2/3
C100 -3 -2
D011 2 4/3
 -331    
 -222/3    

Porządkując wyceny od najmniejszej do największej (osobno dla wierszy i kolumn) otrzymamy macierz Petriego:

    
C100 -3 -2
A110 -1 -2/3
B010 1 2/3
D011 2 4/3
 -313    
 -22/32    

Uzyskanie stabilnych wycen dla macierzy incydencji nie jest proste. Wymaga zaawansowanych metod algebry i praktycznie bez użycia komputera jest niemożliwe.

Tabela przedstawia autentyczny zapis wzorów na ceramice, znalezionej na 6 stanowiskach, wraz z najlepszą wyceną. Spróbuj utworzyć macierz Petriego i odkryj chronologię stanowisk i motywów na ceramice. Jaki jest współczynnik proporcjonalności dla tej wyceny?

  puchar cz. brzeg butla płaskie rączka punkty spirale  
s1 0 1 1 0 1 0 0 2,79
s2 0 0 0 1 0 1 0 -3,36
s3 0 0 0 0 0 1 0 -3,50
s4 0 0 0 1 1 1 1 -2,18
s5 1 1 0 0 0 0 0 6,29
s6 0 0 0 0 1 0 1 -1,00
     6,29 4,54 2,79 -2,77 -0,13 -3,01 -1,59  

 

Powrót na górę strony