Data la sequenza-esempio:
0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 10, 11, 12, 15


si "vede" a occhio che è fatta di due gruppi di valori (da 0 a 4, da 10 a 15) fra loro disomogenei. Che algoritmo statistico si può usare per separarli matematicamente? Perchè python "non ha occhio"...

io esaminerei la sequenza come delta fra successivi elementi, calcolerei media e deviazione standard dei delta, aggiungendo un elemento alla volta e individuerei il punto di separazione là dove c'è un delta che esce dai limiti media più o meno 2*deviazione standard.

Ha senso?
Poi ti spiego a cosa serve. C'entrano i testi.... ho un ambizioso progetto di interpretazione approfondita dell'OCR del testo di una pagina.

(27-11-2011 12:36)alex Ha scritto:  Data la sequenza-esempio:
0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 10, 11, 12, 15


si "vede" a occhio che è fatta di due gruppi di valori (da 0 a 4, da 10 a 15) fra loro disomogenei. Che algoritmo statistico si può usare per separarli matematicamente? Perchè python "non ha occhio"...

io esaminerei la sequenza come delta fra successivi elementi, calcolerei media e deviazione standard dei delta, aggiungendo un elemento alla volta e individuerei il punto di separazione là dove c'è un delta che esce dai limiti media più o meno 2*deviazione standard.

Ha senso?
Poi ti spiego a cosa serve. C'entrano i testi.... ho un ambizioso progetto di interpretazione approfondita dell'OCR del testo di una pagina.

Il sistema che tu proponi è del tutto analogo all'ESD, ( acronimo di extreme studentized deviate).
L'ESD però si può usare SOLO quando la distribuzione è normale o pressochè normale ed ogni eventuale valore "anomalo" viene trattato come outlier.
In questo caso, come è evidente, la distribuzione non è normale e non ha nessun senso calcolare la media.
La media è una misura della tendenza centrale.
Bisogna ricorrere a test non parametrici, cioè che non implicano la distribuzione normale e il passaggio dalla media per successive elaborazioni.

La successione di numeri che tu proponi può essere analizzata, solo in confronto con una analoga.
Supponi per esempio di avere monitorato un certo fenomeno prima e dopo un certo trattamento.
Allora puoi confrontare la seriazione del prima con quella del dopo, con numerosi test ( test dei segni, test di Wilcoxon, test di Mann Whitney, test di Kolmogorov-Smirnov, di Kendall e via dicendo).
Però è sempre un confronto tra DUE serie di dati.
Per una sola serie di dati puoi sempre ricercare un polinomio che lo spieghi ma non avrebbe alcun valore predittivo.

Se mi dai qualche elemento in piu' vedo se mi viene in mente qualcos'altro.

Io penso che la soluzione stia nelle tecniche per discriminare distribuzioni bimodali o polimodali - ossia: "miscele" di elementi diversi, ciascuno con la sua distribuzione normale.

Andiamo nel concreto.

L'OCR produce, oltre che il testo, le coordinate degli elementi del testo nello spazio pagina. Io sto lavorando sulle righe. L'OCR mi fornisce le coordinate x1,y1,x2,y2, sulla pagina, del rettangolo che contiene ciascuna riga.

Ingenuamente supponevo che chi fossero delle "uguaglianze", ossia che se delle righe sono allineate a sinistra, allora il loro valore x1 fosse uguale. Nemmeno per sogno. Varia, da riga a riga; ma varia "poco". A me serve chiarire questo "poco", isolare le righe allineate a sinistra, e distinguerle chiaramente, ad esempio, da quelle che sono indentate, in cui x1 varia "di più". Basandomi sulle coordinate, ed esaminando la loro variabilità, voglio distinguere chiaramente due gruppi di righe, quelle allineate a sinistra e quelle indentate. Lo stesso dovrò fare per le coordinare x2, allineamento a destra, più variabile ancora; e lo stesso per l'altezza delle interlinee, per riconoscere gli "stacchi".

Ora, potrei procedere in modo arbitrario ("uno spostamento a dx oltre il 5% della pagina è un'indentatura"), dopo un po' di misure, ma mi secca; mi piacerebbe capire l'algoritmo mentale (e tradurlo in algoritmo matematico) che a occhio, e senza fallo, riconosce un "allineamento a sinistra" in qualsiasi pagina, e con altrettanta sicurezza riconosce dalle altre le righe indentate, come riconosce quelle centrate, le spaziature fra righe che identificano le parti del testo, ecc; ad esempio, le poesie sono "sequenze di righe in genere allineate a sinistra, ma con margine destro non allineato, variabile casualmente, e più brevi di una riga di prosa".

Poi le cose si faranno complicate, perchè mica è detto che la pagina sia stata scannerizzata diritta.... dovrò anche tener conto di uno scarto sistematico, dovuto al fatto che la pagina è scannerizzata "storta" (ossia, tener conto anche dell'asse y). Ma questo dovrebbe essere risolvibile focalizzando l'attenzione sulla variazione di coordinate x fra una riga e le righe adiacenti, piuttosto che sul suo valore "assoluto".

Ovviamente, a occhio, non c'è alcuna difficoltà a percepire un allineamento a sinistra anche se l'immagine della pagina è un po', o anche molto, "storta".... il che è molto frustrante.

Se hai bisogno di numeri di esempio, posso produrtene migliaia. :-)

Ma non è meglio seguite un sistema empirico?
Determini la coordinata x minima (quella della riga che comincia più a sinistra)
determini il valore massimo di larghezza di un carattere (che so della lettera m per esempio)
Consideri indentate le righe che hanno un valore iniziale di x uguale o maggiore di 4 m
Tanto per seguire la regola del KISS.

E come faccio, a determinare automaticamente la larghezza di un carattere? Al momento sto lavorando su un algoritmo del tutto automatico; io non voglio ancora che un "umano" guardi nemmeno la pagina.

Ci sono solo rettangoli di coordinate date, e basta.

Daniele, guarda questa sequenza, individua "da sola" il salto sul numero 10:


0 0.0
1 0.5 2.0
1 0.66 1.94
1 0.75 1.86
1 0.8 1.8
2 1.0 3.15
2 1.14 3.27
2 1.25 3.32
2 1.33 3.33
3 1.5 4.61
3 1.63 4.76
3 1.75 4.84
4 1.92 6.14
10 2.5 14.64
11 3.06 17.17
12 3.62 19.37
15 4.29 23.93

per ogni elemento, ho calcolato la media e la deviazione standard di tutti gli elementi uguali o minori; il secondo numero è la media, il terzo è il valore + 2 volte la deviazione standard. Nella sequenza, il valore 10 è il primo che supera il valore + 2 dev. st. del valore precedente. Mi pare incoraggiante.

A questo punto ho individuato una serie di valori "omogenei" (fino a 4); li elimino, e ripeto il procedimento alla ricerca di altri "salti".

Dato [0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 10, 11, 12, 15], l'obiettivo è di ottenere [[0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4], [10, 11, 12, 15]].

---

Primo vagito (copioincollo dalla console python la riga di comando e il risultato)


>>> lista=[2,5,10,5,10,9,3,4,11,11,12,2,3,2];splitta(lista)
[[2, 2, 2, 3, 3, 4, 5, 5], [9, 10, 10, 11, 11, 12]]

---

Ma anche:

splitta([42.76, 45.57, 27.65, 23.37, 40.15, 22.63, 47.83, 24.6, 23.57, 41.33, 46.74, 25.66, 23.44, 47.03, 44.85, 29.7, 44.22, 22.91, 25.03, 25.18, 26.83, 46.77, 43.54, 43.16, 25.23, 41.39, 29.05, 45.42, 41.8, 26.77, 40.9, 48.3, 42.72, 20.24, 48.19, 49.95, 46.72, 45.7, 24.22, 42.6, 29.69, 24.12, 24.96, 41.4, 25.42, 42.95, 46.16, 48.04, 28.15, 29.65])
[[20.24, 22.63, 22.91, 23.37, 23.44, 23.57, 24.12, 24.22, 24.6, 24.96, 25.03, 25.18, 25.23, 25.42, 25.66, 26.77, 26.83, 27.65, 28.15, 29.05, 29.65, 29.69, 29.7], [40.15, 40.9, 41.33, 41.39, 41.4, 41.8, 42.6, 42.72, 42.76, 42.95, 43.16, 43.54, 44.22, 44.85, 45.42, 45.57, 45.7, 46.16, 46.72, 46.74, 46.77, 47.03, 47.83, 48.04, 48.19, 48.3, 49.95]]
Sembra che funzi.

si certo addensa è giusto che funzioni
E come faccio, a determinare automaticamente la larghezza di un carattere?

Non si può. O meglio, non si può, a meno che tu non abbia un output OCR mappato a livello di carattere; ma è rarissimo. In genere, la mappatura è a livello di parola, o di riga. A qualcuno interessano "i misteri del testo mappato"? Se la cosa vi incuriosisce e masticate xml, andate in uno dei tanti libri di Internet Archive, e scaricatevi un file "djvu.xml". Lì potete studiarvi una ottima mappatura "gerarchica" multilivello: pagina, colonna, regione, paragrafo, linea e parola.

Ecco un link diretto per i più pigri: http://ia700507.us.archive.org/16/items/...e_djvu.xml

Io preferisco al xml un'altra rappresentazione (simil-LISP), molto più compatta; i dati, comunque, solo quelli.

Citazione:E come faccio, a determinare automaticamente la larghezza di un carattere?

avevo risposto ma chissà come non non l' ha salvato.
Ci sono 2 modi:
Per caratteri "noti" fai l' OCR dell' alfabeto, un carattere su ogni riga.
Per caratteri ignoti semplicemente dividi la lunghezza della riga per il numero di caratteri riconosciuti... e ottieni la dimensione media del carattere.

Alex, la faccio molto semplice (sbagliando probabilmente), ma data la sequenza ordinata di valori che hai proposto non ti basta definire un valore di 'tolleranza' t per l'allineamento e verificare che il valore n sia compreso nell'intervallo aperto n <= (n-1) + t ?

t potrebbe essere definito arbitrariamente da te o matematicamente tenendo conto della deviazione standard, che poi è abbastanza simile a quanto hai effettivamente fatto.

Già; basterebbe calcolare la varianza delle linee allineate a sinistra, vero?

E quali sono, le righe allineate a sinistra?

A parte gli scherzi, quello che mi serviva era un algoritmo astratto: "dato un gruppo n, ogni elemento del quale caratterizzato dai valori x1,x2,x3...., suddividerlo in gruppi statisticamente omogenei in base a una misura qualsiasi".

L'algoritmo è complesso ma chi se ne importa, visto che il comando è semplicissimo? Infatti, se il gruppo si chiama l, e ciascun elemento è una lista di valori 0,1,2,3...n, per "splttare" l in due gruppi rispetto al valore n basta che scriva (senza fare nessuna misura preliminare nè sapere alcunchè della serie di valori e di cosa questi valori rappresentano):

>>> splitta(l,n)

il che è semplice; e mi basta e mi avanza.

Più bello,più semplice, più utile.

>>> serie=[25,30,50,5,20,100,2,3,4,22,0,0,2,23,105,21,54,55]

>>> grouper(splitter(serie,20))
[[0, 10, 7], [20, 35, 6], [50, 60, 3], [100, 110, 2]]

>>> grouper(splitter(serie,10))
[[0, 10, 7], [20, 40, 6], [50, 60, 3], [100, 110, 2]]

Il valore restituito si legge:
nell'intervallo 0-10 ci stanno 7 dati
nell'intervallo 20-40 ce ne stanno 6
nell'intervallo 50-60 ce ne stanno 3
nell'intervallo 100-110 ce ne stanno due

Niente statistica, niente math, solo un truccaccio empirico. Come indovinate, uno script "splitta" e passa il valore a un secondo script che "raggruppa".

E visto che questo è un forum strano, ecco il codice: