Ausreßertest (Grubbs-Test) in Postgresql

Hallo,

seit Tagen versuche ich einen Grubbstest zum Auffinden von Ausreißer als eine SQL-Abfrage oder Datenbankfunktion zu implementieren. Leider hat es bis jetzt nicht geklappt, deswegen bitte um HILFE.

Gegeben ist eine Tabelle namens Data mit folgender Struktur:
create table data (id integer, value numeric, set_id integer).
[LEFT]Jeder Datensatz der tabelle repräsentiert eine Messung, set_id zeigt welche Werte zu welcher Stichprobe gehören, z. B.

id value set_id
1 0.5 1
2 0.7 1
3 1.0 2

usw.

Man soll eine SQL-Abfrage/Funktion etwickeln, die Grubbs-Test durchfüht und die Ausreißer markiert, so dass das Ergebniss etwa so ist:

id value set_id aussreisser
1 0.5 1 ja
2 0.7 1 nein
3 1.0 2 nein

Habe schon mit vieles probiert, komme aber nicht dahinter.
Wäre dankbar für jede Hilfe.


[/LEFT]

Uhm. Das ist ja eine statistische Funktion. Für solche Aufgaben gibt es spezielle Programme, z.B. R. Kennst Du Dich damit aus, also mit R?

Falls ja, hier die gute Nachricht: Du kannst PostgreSQL um die Sprache pl/R erweitern, das ist faktisch das Statistik-Paket R mit PostgreSQL als Datenhalde.

R gibt es als Open Source definitiv für Linux und wohl auch für Kleinweich.

R findest Du hier: The R Project for Statistical Computing
pl/R hier: PL/R - R Procedural Language for PostgreSQL

Alternativ: selber eine Funktion schreiben.

Andreas

Hallo Andreas,

mit dem Pl/R kenne ich mich nicht aus. Mir geht es aber darum die Funktion zu schreiben, die eine Tupelmenge übergeben bekommt und sie rekursiv abarbeitet, wobei in jedem Durchlauf eine Zeile zurückgegeben wird. Die Menge der verbleibenden Zeilen bildet das Ergebnis.
Falls du dich mit WITH RECURSIVE queries auskennst, muss etwa Folgendes getun werden:

WITH RECURSIVE t AS (
select * from data
except
SELECT grubbs_test(t) //gibt eine zeile zurück
)SELECT * FROM t;Aber WITH RECURSIVE gibt es in Postgre nur mit UNION und weiß nicht
wie ich das sonst machen soll.

Gruß

Alger

Hmm, sicher, dass ein UNION immer notwendig ist?

Hrm. Ich keine Ahnung von Mathe :wink:

Wenn ich Ausreißertest nach Grubbs – Wikipedia richtig interpretiere, solltest Du Deine Daten in eine Tabelle packen. Dann eine Funktion schreiben, die diese Tabelle EXCEPT eine (erst mal leere) Tabelle nimmt und davon die Ausreißer ermittelt und diese in dieser (ursprünglich leeren) Tabelle speichert. In einer Schleife rufst das halt solange auf, bis die ursprüngliche Tabelle EXCEPT der neuen Tabelle leer ist oder die EXCEPT-Tabelle nicht mehr größer wird.


Andreas

Scheinbar. Nur das ALL ist optional. PostgreSQL: Documentation: Manuals: PostgreSQL 8.4: WITH Queries Oder hast Du ein Beispiel ohne UNION?

Andreas

WITH RECURSIVE ausreisser(id int, messwert messtyp, ... ) AS (

    -- 1. "recursion" -> 1. test
    -- LIMIT 1 - weil ja immer ein Ausreisser-Wert aussortiert wird .. 
    SELECT messwert, .. 
    FROM messungen m
    WHERE grubb(m.messwert, ... )
    ORDER BY m.messnr
    LIMIT 1
    
    UNION ALL

    -- die recursion .. 
    SELECT messwert, .. 
    FROM messungen m
    WHERE grubb(m.messwert, ... ) -- die gleiche bedingung wie oben
      AND m.id NOT IN (SELECT a.id FROM ausreisser a) -- die, welche wir schon haben nicht testen
    ORDER BY m.messnr
)

select * from ausreisser

die funktion grubb liefert einen boolean, der true ist wenn der satz ein ausreißer ist, sonst false

die musst du natuerlich noch implementieren

Scheinbar nicht.

WITH RECURSIVE t(n) AS (
VALUES (3)
)
SELECT SUM(n) FROM t;

Nicht dass die Anfrage sehr viel Sinn macht, aber sie funktioniert ohne UNION.

ich bin zwar etwas eingerostet

aber du kannst das auch so in etwa machen:

with kennzahlen (set_id, Xn, Sn) as (
  
  select 
     set_id,
     abs(x - avg(x) OVER (PARTITION BY set_id)) Xn, 
     variance(x) OVER (PARTITION BY set_id) as Sn 
  from messungen
)

select  max(Xn) OVER (PARTITION BY set_id) / Sn as G from kennzahlen

die tabelle waere

create table messungen (
   x double precision,
   set_id int)

der akretschmer ist aber hier im forum der windowing-function-virtuose

nachtrag:
weil eigentlich gehts ja darum jede zeile zu erhalten - zu jeder dieser zeilen das aggregat namens grubb zu berechnen - um dieses auszugeben / weiter zu verarbeiten …
fuer solche faelle sind die windowing-functions gedacht … man muss auch nicht immer alles auf einmal machen - aus dem beispiel oben (sofern inhaltlich korrekt) wuerd ich mir ein view bauen … das kannst dann gegen deinen “ausreisser” wert checken

Nun, nach dieser geistigen Steilvorlage ist mir auch eine Abfrage mit EXCEPT geglückt:

test=*# WITH RECURSIVE t(n) AS ( VALUES (3) except values (3) ) SELECT SUM(n) FROM t;
 sum
-----

(1 row)

Ich geh mich dann mal verstecken …


Andreas

Interessant.
Die PG Dokumentation scheint da nicht ganz vollständig zu sein:

Aus: PostgreSQL: Documentation: 8.4: SELECT

Ich denke mal, das Handbuch ist an der Stelle schon okay, denn das, was ads und ich da verbrochen haben, ist alles Mögliche, vor allem ist es Unfug, aber keine rekursive Abfrage.

Andreas

Hallo an alle, zuerst möchte ich mich bei allen bedanken die am Thema teilgenommen haben. Der Vorschlag mit WITH RECURSIVE+EXCEPT habe ich ausprobiert, der geht aber nur mit konstanten Werten und ist auch nicht rekursiv.

Der Vorschlag von symbiont hat mich ein wenig weitergebracht und habe folgende Abfrage zusammengestellt:

SELECT set_id, id, value, min, max, mean, std, case when abs(max - mean) > abs(min - mean) then abs(max - mean)/std else abs(min - mean)/std end as pg
FROM
(
SELECT set_id, id, value, min(value) OVER w as min, max(value) OVER w as max, avg(value) OVER w as mean, coalesce(stddev_samp(value) OVER w, 0) as std FROM data WINDOW w AS (PARTITION BY set_id ORDER BY value ASC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) ORDER BY value ASC
) as d

Unter der Annahme dass der Ausreißer immer der größte, next größte usw. Wert der Menge ist, funktioniert das. Ich kriege es aber nicht hin, falls die Ausreißer abwechselnd min und/oder max sind. Einfacher gesagt, ich muss in WINDOW nach maximalen Abstand zum Mittelwert sortieren und ich weiß nicht wie das geht, weil dann eine aggregat. Fkt. in ORDER BY auftauchen würde. Falls einer gut mit WINDOW Klausel auskennt, könnte er mir eventuell helfen.

Danke

Alger

Sollte doch einfach so gehen:

test=# create table data (id serial, data float);
NOTICE:  CREATE TABLE will create implicit sequence "data_id_seq" for serial column "data.id"
CREATE TABLE
test=*# insert into data (data) select random() from generate_series(1,10);
INSERT 0 10
test=*# select id, data, avg, avg-data, abs(avg-data) as abstand from data, (select avg(data) from data) foo order by abstand desc;
 id |        data        |        avg        |      ?column?       |      abstand
----+--------------------+-------------------+---------------------+--------------------
  1 | 0.0543986530974507 | 0.606656908197328 |   0.552258255099878 |  0.552258255099878
  7 |  0.190013178158551 | 0.606656908197328 |   0.416643730038777 |  0.416643730038777
  5 |  0.992218289524317 | 0.606656908197328 |  -0.385561381326988 |  0.385561381326988
  8 |  0.930751285050064 | 0.606656908197328 |  -0.324094376852736 |  0.324094376852736
  6 |  0.818015911150724 | 0.606656908197328 |  -0.211359002953395 |  0.211359002953395
  4 |  0.774203835986555 | 0.606656908197328 |  -0.167546927789226 |  0.167546927789226
 10 |  0.443240758031607 | 0.606656908197328 |   0.163416150165722 |  0.163416150165722
  3 |  0.451245051342994 | 0.606656908197328 |   0.155411856854334 |  0.155411856854334
  9 |  0.706385356374085 | 0.606656908197328 | -0.0997284481767565 | 0.0997284481767565
  2 |  0.706096763256937 | 0.606656908197328 | -0.0994398550596088 | 0.0994398550596088
(10 rows)

Oder?

In der letzten Spalte hast Du, von oben nach unten sortiert, nun Deine ‘Ausreißer’.

Andreas

Gut,
angenommen der Datensatz mit id=1 isr ein Ausreißer, den ich aus der Menge entferne. Jetzt soll ich den Test rekursiv für die verbleibende wiederholen. d.h. avg, …, abstand neu rechnen… Ausreißer bestimmen …usw. bis es am Ende keine Ausreißer in der Restmenge gibt. Und gerade diese rekursivität schaffe ich nicht in einer SQL-Abfrage unterzubringen.

also ich sagte ja schon - man muss nicht alles auf einmal machen

ich wuerde 2 table expressions nehmen:


[color="SeaGreen"]-- mit der 1. berechnest du fuer alle diesen grubbs wert G[/color]
WITH grubbs(id, set_id, grubbs) AS (
   .... hier das select mit den windowing-functions, welches dir für ALLE den wert grubbs berechnet 
   ... was ??? wahrscheinlich ??? nicht geht -> SELECT <grubbs> FROM <set_id> WHERE id NOT IN ausreisser
),
[color="#2e8b57"]-- hier nun die 2. recursive, welche eine tabelle darstellt die NUR ausreisser enthaelt - im prinzip added die rekursion jeden ausreisser aus grubbs hinzu - UNION ALL[/color]
ausreisser(id) AS (
   SELECT id FROM grubbs
   UNION ALL
   SELECT id FROM grubbs ... 
   WHERE id NOT IN ausreisser 
)
[color="#2e8b57"]-- und nun kannst du die "Tabelle" ausreisser dazu verwenden irgendwelche Datensätze woanders zu markieren [/color]
SELECT i.*, a.id IS NOT NULL AS "das_ist_ein_ausreisser"
FROM irgendwas i
LEFT JOIN ausreissser a ON a.id = i.id

ah ich glaub das funzt net, weil du auch grubbs nach dem aussortieren nur ueber die verbleibende menge berechnen darfst?

da waere natuerlich cool, wenn die table-expressions sich gegenseitig referenzieren koennen … ich glaube aber genau das geht nicht!

Für eine Rekursion brauchst Du eine Abbruchbedingung, andernfalls hättest Du bei Deinem Plan oben als Resultat eine komplett leere Tabelle.

So, ich hab mal was gebastelt.

test=# create table daten (id serial primary key, d float);NOTICE:  CREATE TABLE will create implicit sequence "daten_id_seq" for serial column "daten.id"
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "daten_pkey" for table "daten"  
CREATE TABLE                                                                                   
Zeit: 5,412 ms                                                                                 
test=*# insert into daten (d) select random() from generate_Series(1,100);INSERT 0 100                                                              
Zeit: 1,266 ms                                                            
                                                         

test=*# create or replace function del_ausreiser(float) returns bool as $$begin loop delete from daten where id in (select id from (select *, abs(d-avg) as abstand from daten, (select avg(d) from daten) foo order by abstand desc limit 1) bar where abstand > $1); if not found then return true; end if; end loop; end; $$ language plpgsql;
CREATE FUNCTION
Zeit: 0,678 ms
test=*# select * from del_ausreiser(0.3);
 del_ausreiser
---------------
 t
(1 Zeile)

Zeit: 6,166 ms
test=*# select count(*) from daten;
 count
-------
    71
(1 Zeile)

Zeit: 0,288 ms

Ich lösche also immer einen, solange dieser mehr als 0.3 vom Durchschnitt abweicht. Ob dies der exakte Rechenweg ist bezweifle ich aber. Jedenfalls - es bleiben 71 von 100 Datensätze übrig.

test=*# select 'Minimum', min(d) from daten group by 1 union select 'Maximum', max(d) from daten group by 1;
 ?column? |        min
----------+--------------------
 Maximum  |  0.977650795597583
 Minimum  | 0.0283374600112438
(2 Zeilen)

Zeit: 0,488 ms
test=*# select * from del_ausreiser(0.3);
 del_ausreiser
---------------
 t
(1 Zeile)

Zeit: 6,225 ms
test=*# select 'Minimum', min(d) from daten group by 1 union select 'Maximum', max(d) from daten group by 1;
 ?column? |        min
----------+-------------------
 Maximum  | 0.853486565407366
 Minimum  | 0.286866198293865
(2 Zeilen)

Andreas

ich befürchte fast, das problem laesst sich so nicht wirklich loesen

das problem am problem ist naemlich, dass man hier elemente entfernen muss - und dann mit der restmenge in der rekursion weiterarbeiten

die recursiven queries in pg erlauben aber

  1. nur das hinzuefuegen von elementen … daher dachte ich zunaechst man koennte ja ausreisser “hinzufuegen” … dazu benoetigt man aber
  2. eine subquery auf ausreisser um den naechsten ausreisser zu ermitteln … das geht aber leider auch (noch??) nicht:

FEHLER: rekursiver Verweis auf Anfrage »ausreisser« darf nicht in einer Unteranfrage erscheinen
LINE 12: where not exists (select a.id from ausreisser a where a.se…

hier mein (auch falscher und nicht funktionierender) ansatz

with recursive ausreisser (id, set_id, Xn, Sn) as (
 
  select w.id, w.set_id, w.x as Xn, w.x as Sn 
  from werte w where false
  
  union all 
  
  select w.id, w.set_id, 
	 abs(w.x - avg(w.x) OVER (PARTITION BY w.set_id)) Xn, 
	 variance(x) OVER (PARTITION BY w.set_id) as Sn 
  from werte w
  where not exists (select a.id from ausreisser a where a.set_id = w.set_id)
)

select  * from ausreisser

die aufgabe ist aber wirklich eine schoene :wink:

für das verfahren muss eine menge verringert (restmenge) und eine andere vergroessert (ausreisser) werden und in jedem schritt muss man noch ein max() ermitteln …
das braucht viele dinge die pg in dem zusammenhang glaube ich nicht einfach so kann

Also ich bin zu dem Schluss gekommen, dass sich das Problem (leider) nicht bzw. nicht wirklich schoen mit einer einfachen Abfrage lösen läßt.
Daher hier ein neuer Vorschlag:

Eine stable funktion - weil die für jedes set (gleiche parameter-werte id_set und Gn) nur einmal ausgefuehrt wird - lassen wir den grubbs iterieren:

CREATE TABLE grubbs.werte (
  id serial not null primary key,
  set_id int  not null,
  x double precision not null
) WITH (OIDS=FALSE);

insert into grubbs.werte VALUES 
(DEFAULT, 1, 0.5), 
(DEFAULT, 1, 0.7), 
(DEFAULT, 2, 1.0); 

CREATE OR REPLACE FUNCTION grubbs.test(test_set_id integer, g double precision) 
    RETURNS SETOF grubbs.werte AS $$

DECLARE
  ausreisser int[];
  row_grubbs RECORD;
BEGIN
     
    [color=SeaGreen] -- array allociieren
     -- wie allociiert man eigentlich ein array mit laenge 0?[/color]
     ausreisser = ARRAY[0];

     LOOP 
      [color=SeaGreen]-- den top-ausreisser ermitteln[/color]
      SELECT id, set_id, x, Xn / Sn as Gn FROM (
        [color=SeaGreen]-- kennzahlen[/color]
        SELECT id, set_id, x,
           abs(x - avg(x) OVER (PARTITION BY set_id)) Xn, 
           variance(x) OVER (PARTITION BY set_id) as Sn 
        FROM grubbs.werte w
        WHERE w.set_id = test_set_id
          AND NOT (w.id = ANY(ausreisser)) 
        ) AS kennzahlen 
      ORDER BY Xn DESC LIMIT 1[color=SeaGreen] -- max(abs(Xn - X) ... )[/color]
      INTO row_grubbs; 
          
      IF row_grubbs.Gn >= g THEN

        [color=SeaGreen]-- ausreisser aussortieren[/color]
        ausreisser = ausreisser || row_grubbs.id;

        RAISE NOTICE 'aktuelle ausreisser %', ausreisser;

       [color=SeaGreen] -- spalten anzahl anpassen 
        --     darf man leider nicht direkt hinter RETURN NEXT!
        -- ausreisser zurückliefern
[/color]        row_grubbs = ROW(row_grubbs.id, row_grubbs.set_id, row_grubbs.x);
        RETURN NEXT row_grubbs;
      ELSE
        [color=SeaGreen]-- keine weiteren ausreisser[/color]    
        RETURN;
      END IF;
     END LOOP;
  
END;
$$ LANGUAGE plpgsql [color=Red]STABLE[/color];

select w.*, (SELECT w.id IN (SELECT id FROM grubbs.test(w.set_id, 1))) as "AUSREISSER111!!!1"
from grubbs.werte w

liefert dann z.B:

id    set_id    x    AUSREISSER111!!!1
-----------------------------------------
1;    1;    0.5;    t
2;    1;    0.7;    f
3;    2;    1;    f

Man koennte natuerlich auch nur einen Vector von IDs liefern lassen, dann schauen später die abfragen nicht so strange aus

und der parameter G ist auch ueberfluessig - den müsste man ja eigentlich in der fuktion aus dem set berechnen koennen?!