hakank.blogg: Machine learning/data mining Archives

februari 21, 2010

Ny engelskspråkig blogg: Arrays in Flux

Häromdagen startade jag min andra engelskspråkiga blogg: Arrays in Flux (ungefär "Vektorer i rörelse").

Det första inlägget Arrays in Flux: My third blog, and second English beskriver inriktningen och förklarar namnet mer.

Det andra inlägget, som precis publicerades, Symbolic regression (using genetic programming) with JGAP beskriver det jag hållt på med de senaste veckorna. Det är en utveckling av det som skrevs om i Eureqa: equ.ation discovery med genetisk programmering.

Posted by hakank at 06:46 EM Posted to Blogging | Machine learning/data mining

januari 24, 2010

Eureqa: equation discovery med genetisk programmering

(For English readers: This blog post is available as a Google Translation from this Swedish text: Eureqa: equations discovery with genetic programming.)

För mer än 6 år sedan bloggade jag om equation discovery (att hitta ekvationer/samband givet en datamängd) och hittade några roliga system som jag då kollade in rätt mycket.

Nu är det dags igen: Eureqa är ett modernt equations discovery-system baserat på genetisk programming (närmare bestämt symbolisk regression) och det har ett fint GUI etc.

Eureqa blev världskänt i början av december förra året genom att Wired skrev en artikel om systemet och forskningen/forskarna bakom: Download Your Own Robot Scientist. Faktum är att jag laddade ner systemet och testade det lite men jag höll på på med andra saker.

De senaste dagarna har jag suttit med några enkla problem (dvs datafiler) för att lära känna Eureqa mer. Mer avancerade saker såsom dynamiska modeller (differentialekvationer) och komplexa ekonomiska system (såsom börskurser) tar jag tag i senare.

Jag tänker inte gå in på vad genetisk programmering är mer än att säga att det använder inspiration från biologin för att leta rätt på en lösning. Se vidare genetic programming (Wikipedia) för mer info och länkar.

Huvudprincipen för den variant av genetisk programmering som Eureqa använder är att man har
- en datamängd
- ett visst antal matematiska funktioner ("byggklossar")
- en relation mellan variabler som man vill studera

Eureqa hittar då givet variablerna och funktioner ett antal samband (lösningar, modeller). Med en "felfunktion" (error function) kommer diskrepansen mellan data och den skapade modellen att minska till ett så litet värde som möjligt, förhoppningsvis 0.

Här följer några kommentarer och ett och annat tips. Först beskrivs Eureqa, sedan lite mer om modelleringen med några exempel. Efter det länkar till några av de datafiler som används, och sist mer länkar om Eureqa.

Mycket kortfattat: Jag tycker Eureqa är ett riktigt trevlig och skoj system, tyvärr rätt mycket CPU-slukande för att min dator ska må riktigt bra. Men skoj.

Min vana trogen skapades även en My Eureqa page för länkar, filer och annat etc.

Installation

Programmet finns att ladda ner här.

Tyvärr finns endast en Windows-version men det ska komma klienter för åtminstone Linux. Jag har inga större svårigheter att köra Eureqa under Wine förutom att det alltså tar väldigt mycket kräm när det bearbetar data.

Det installerades på min burk med följande kommando:

wine msiexec /i eureqa_full_0.7.7.msi

och kör det sedan med

wine "<installation path in Wine>/Eureqa.exe"

Mer om systemet

Eureqa har ett mycket trevligt GUI med olika tabbar för data, plottning/smoothing av data, modellering, start/stop och lösning. Dessa tabbar presenteras här kortfattat.

* "Enter Data"
Man kan skriva in data som i ett enkelt spreadsheet à la Open Office Calc eller Excel (vad jag vet stöds inte formler etc). Det sätt jag använder är dock att skapa en text fil (ASCII) som består av följande:
- header med information om fälten. T.ex.
% | x y z |
där "%" är kommentar och de två "|" är avgränsare för variabelnamnen. Tänk på att det bör vara relativt korta namn annars kan det bli svårläst med mer komplexa uttryck.
- sedan data med mellanslag som separator.

För att hämta in en datafil används "File", "Import data...". Om det är fel i filen kommer mer eller mindre lättförståeliga felmeddelanden. Jag har inte testat så mycket att manuellt lägga in data via kalkylprogram men det ska gå.

* "Preview Data" (och smoothing)
I detta fönster man man se de olika värdena plottade i en x/y-graf. Man kan även göra en smoothing (vad jag förstår är det loess man använder), t.ex. om det är mycket brus för någon variabel.

* "Pick Modeling Task"
Här gör man själva modellen, dvs skapar förutsättningen för uttrycket. Se även nedan under "Modellering, några exempel".

- Search for a formula: Här skriver man formen för uttrycket, t.ex.
x1 = f(x2,x3).

- Using building blocks: Här väljs de funktioner ("byggklossar" som man vill att Eureqa ska testa. Normal vill man alltid ha "+","-","*","/", men sedan beror det lite på vad det är för typ av data. Intressant nog är "sin" och "cos" alltid med, vilket väl speglar utvecklarnas preferens för fysiska system. Eftersom de flesta av mina datamändger inte är fysiska system brukar jag börja med att ta bort sin och cos och i stället välja t.ex. square root, exponential och logarithm, eller helt enkelt endast börja med de fyra räknesätten.

Det finns ett flertal andra byggstenar, t.ex. minimum, maximum, Logistic, Gaussian, Gamma, Step och Sign, man inverser och hyperboliska varianter av trigonometriska funktionerna. På forumet antyds att det kommer flera i nästa version, t.ex. de booleanska AND, OR, XOR, samt att man ska kunna definiera egna varianter.

Det finns även andra saker på denna sida, t.ex. att välja Fitness metric och viktningen av datapunkterna.

Det går också att använda flera datorer till en körning. I "Use the following servers" väljer man eventuellt andra datorer som kör en Eureqa server. Detta har jag inte testat.

"Seed previous solution(s)": Här kan man skriva uttryck (formler) som en vink ("bias" till Eureqa att dessa är viktiga formler. Detta har jag inte kollat in så mycket.

* "Start/stop"
Här startar, stoppar och pausar man en körning. Förutom dessa knappar finns en mängd annan information om hur körningen går.

* "Solution Results"
Det är här man ser lösningen både som ett uttryck och även en graf hur bra lösningen är jämfört med de givna datapunkterna. Det är fascinerande att se den växa fram och lära sig.

Datamängden delas upp (automatiskt av Eureqa) innan körningen i två delar: träningsdata (train data) och valideringsdata (validation data). Sedan körs modellen på träningsdatan och valideras på valideringsdatan. Dessa två delar presenteras med olika färger här så man ser hur bra eller dåligt den valda modellen (uttrycket) passar. Mycket trevligt.

Olika statistiska metriker visas för respektive träning- och valideringdata:
- Fitness
- R-squared
- Correlation Coeff
- Mean Squared Error
- Mean Absolute Error
- Minimum Error
- Maximum Error

De flesta av dessa kan man använda som fitness metric i modelleringstabben.

I listan över lösningar ser man en handful lösningar som anses som mest intressanta, med den mest lovande överst. Denna lista växer dynamiskt hela tiden efter hand Eureqa hittar nya modeller. Om man klickar på en av modellerna visar både statistik och plottningen för den valda modellen. Dubbelklickar man på en formel kopieras den för att sedan klistras in i något finns program (t.ex. om man vill blogga om det).

Modellering, några exempel

Här en kort beskrivning om modelleringen. Till skillnad från traditionell "curve-fitting" så skriver man inte några matematiska uttyck som ska parametriseras, utan endast vilka variabler som ska vara med i uttrycket. För dessa variabler väljs om de överhuvudtaget ska vara med samt eventuell parameter. Eureqa hittar även olika konstanter, både "globala" och inom uttryck.

Exempel med sinus
En av de första sakerna jag testade var att skapa en datafil med två kolumner (x och y) skapad på följande sätt (med Perl):

perl -le 'for (-100..100) { print $_/100, " ", sin(2*$_/100)+3}'

som skapar data för sambandet y = sin(2*x) + 3. De sparades i datafilen sin_formula.txt.

Eureqa hittar lösningen efter cirka 10-15 sekunder. Notera att x motsvaras av "x0" och y av f(x0) (eller x1):

  f(x0) = 3 + sin(2 * x0)

Detta var alltså 201 datapunkter, men man behöver inte alls så mycket data för att Eureqa ska hitta en lösning.

En variant där man endast tar 20 slumpmässiga punkter är sin_formula_rand20.txt som är skapad genom att ta 20 punkter mellan 0 och 2*Pi:

perl -le 'for (1..20) { my $x = rand(2*3.14159); print "$x ", sin(2*$x)+3}'

Eureqa hittar 3+sin(2*x0) på cirka 30 sekunder. Det gick (denna gången i alla fall) lite långsammare eftersom det är färre punkter. Man ska dock komma ihåg att färre punkter gör att det är snabbare att kontrollera hur bra lösningen är.

Den viktigaste delen i modelleringen, förutom att hitta tillförlitlig data, är att hitta rätt byggstenar, dvs de matematiska funktioner som ska användas. Det bör göras med viss försiktighet och eftertanke: Om man väljer för många kan det ta väldigt lång tid och man kan får konstiga resultat. Väljer man för få så hittas inte en enkel lösning. Detta är en konst.

Fibonacci-serien
En annan skoj sak som man kan testa är tidsserier eller data som kan ses som tidsserier. T.ex. kan Eureqa hitta en formel för Fibonacci-serien? De 25 första talen i Fibonacciserien är: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946.

För att göra detta till en lämplig representation - och som vanligt är representationen av problemet väldigt viktigt - är att man tar (tids)serien och lägger den i sekvens över flera variabler.

Låt oss anta att vi inte vet så mycket om denna serie, men anar att det finns en rekursivitet i serien, dvs att senare värden beror på de tidigare, normalt de omedelbart föregående (andra tidsserier, till exempel de ekonomiska kan ha andra beoenden såsom säsonger och veckodagsberoenden).

Här tas serien om fyra. Den första raden är 1,1,2,3, och sedan förskjuts serien för varje rad. Hela serien finns alltså i första kolumnen.
% | t1 t2 t3 t4 | 1 1 2 3 1 2 3 5 2 3 5 8 3 5 8 13 5 8 13 21 8 13 21 34 13 21 34 55 21 34 55 89 34 55 89 144 55 89 144 233 89 144 233 377 144 233 377 610 233 377 610 987 377 610 987 1597 610 987 1597 2584 987 1597 2584 4181 1597 2584 4181 6765 2584 4181 6765 10946 4181 6765 10946 17711 6765 10946 17711 28657 10946 17711 28657 46368

Nu kan vi modellera problemet i Eureqa på följande sätt:
- Formel: t4 = f(t1,t2,t3) - Byggklossar: "+","-","*","/"



Det tar mellan 5 och 10 sekunder för Eureqa att hitta sambandet:

  t4 = t3 + t2

Correlation Coefficient är 1.00000, R-squared är 1 och alla error är exakt 0 så det ser helt korrekt ut. 

Detta är skoj!

Man kan här notera att egentligen behövde vi ju bara de tre första variablerna t1, t2 och t3 men jag valde att ta med den extra kolumnen t4 för att inte fuska för mycket. En annan sak att notera att det är viktigt att titta på Correlation Coefficient och R-squared samt Error för att se hur bra lösningen är. 

Nu kan man göra lite mer roliga saker. Given en lite större datamängd (fib_38.txt) med 38 värden kan vi kolla om Eureqa hittar några andra samband, t.ex. mellan endast två variabler t1 och t2, dvs mellan ett värde och endast de närmast föregående. Här lägger jag till funktionerna "exp", "sqrt" och "log". 

Här är några samband som hittades i flera olika körningar. Samtliga dessa har en fitness error på 0.000 (det som i lösningstabben kallas "Error") och correlation coefficient på 1.0



f(t1) = 1.61803*t1

f(t1) = 1.61803*t1 - 0.472137/t1

f(t1) = 1.61803*t1 - 1.67999/exp(t1)

f(t1) = 1.61803*t1 - 1.67999/exp(t1)

f(t1) = 0.809017*t1 + 0.809017*sqrt(t1)*sqrt(t1) - 0.470881/t1

f(t1) = 1.61803*t1 + 0.221196/(t1*t1 - 1.61571*t1 - 1.70552)

f(t1) = 1.61803*t1 + -3.39888*log(t1)/exp(t1*t1 - 1.69947)

f(t1) = (1.61803*t1*t1 - 0.459213)/t1

f(t1) = 1.61803*t1 - 0.440428/(t1 - 0.440428/(1.61803*t1))

f(t1) = 1.61803*t1 - 0.3884/(t1 - 0.354305)



Notera att Eureqa har identifierat konstanten 1.61803 i flera av ovanstående lösningar vilket är väldigt nära phi, dvs "gyllene snittet" (golden ratio) = (1+sqrt(5))/2 ~ 1.6180339...). phi är precis förhållandet mellan två intilliggande Fibonaccital, så det är ju inte konstigt att Eureqa hittade detta samband. Se Fibonacci number på Wikipedia och Encyclopedia of Integer Sequences:A000045 för mycket mer info om detta.

Man kan säkert hitta andra matematiska konstanter om man letar vidare. Plouffe's Inverter är en guldgruva för sådant. T.ex. här är en sökning på konstanten 1.61803. Tyvärr är det väldigt många träffar eftersom det är så liten precision på talet.

Formeln f(t1) = 1.61803*t1 är alltså en approximering av nästa tal i Fibonacci-serien, dvs F[n+1] = phi*F[n] (avrundat till heltal).

Ett mera avancerat exempel är om Eureqa månne  kan hitta den slutna formeln för Fibonaccital, dvs



  F(n) = (phi^n - (1-phi)^n)/sqrt(5)



För detta krävs en ytterligare parameter i datafilen, nämligen n, dvs index för raden. Så här ser filen ut nu (fib_50.txt"), utökat till 50 rader. Den första kolumnen är alltså index.



% | ix t1 t2 t3 t4 |

1 1 1 2 3

2 1 2 3 5

3 2 3 5 8

4 3 5 8 13

...

48 4807526976 7778742049 12586269025 20365011074

49 7778742049 12586269025 20365011074 32951280099

50 12586269025 20365011074 32951280099 53316291173



Jag vet inte riktigt hur stora tal som Eureqa kan använda, men det saknas i alla fall stöd för arbiträr precison.

När jag skapat filen testades först med samtliga variabler:



  t4 = f(ix,t1,t2,t3)



Då kommer lite mer avancerade förslag än tidigare körning, samtliga med Error 0 och correlation coeff på 1.0000 (dock inte med Maximum error 0), några av dem innehåller n, dvs index.



f(ix, t1, t2, t3) = sqrt(1.61803*t2*t3) + (t2*sqrt(t3) - t2*t2)/(sqrt(t3) - t2)



OK, nu till problemet om den slutna formeln

Formel: t1 = f(ix)

Funktioner: +,-,*,/, sqrt

Det vi vill ha är alltså något som liknar:



(phi^n - (1-phi)^n)/sqrt(5)



eller snarare den numeriska motsvarigheten



f(ix) = (1.61803^ix - (1-1.61803)^n)/2.2361

      = (1.61803^ix - (-0.61803)^n)/2.2361

      = 0.4472071911*1.61803^ix - 0.4472071911*(-0.61803)^ix



(Den tredje varianten hittades via ett matematikverktyg.)

Intressant nog började Eureqa med lösningar där endast ix upphöjt till stora tal (t.ex. 18) samt addition, multiplikation med konstanter. Efter ett tag började experimenten med sqrt, men den körningen hittade inte skoj på många minuter så jag stoppade den.

För att komma runt detta testade jag "hints", dvs "Seed previous solution(s)" på "Pick Modeling Task"-tabben, genom att skriva 1.61803^ix samt sqrt(5). Då kom följande lösningar efter liten stund. De har alla korrelationskoefficient på 1, Error på 0 men stora Maximum Error.



f(ix) = ix + 4*ix*ix*ix + 0.0256922*ix*1.58422^ix

f(ix) = 0.445386*ix + 0.445386*1.61817^ix

f(ix) = 0.0893707 + 0.399785*sqrt(1.61804^ix) + 0.447094*sqrt(1.61804^ix)*sqrt(1.61804^ix)

f(ix) = 2*ix + 0.447097*1.61804^ix

f(ix) = 0.611078*sqrt(1.62499^ix) + 0.447094*1.61804^ix - 127.933



Jag undrar dock hur "naturligt" det är för Eureqa att testa formler på formatet "konstant^variabel", så detta anser jag vara lite fusk. Däremot, om det skulle gärna mer seriösa experiment är denna typ av hintar vettiga. Då anger man vissa samband som grund, ett "alfabet" att bygga vidare på. Jag tror att mer stöd för detta kommer i senare versioner.

Efter detta - ska vi säga misslyckande - skippade jag hintarna och lade på funktionerna "exp", "sin", "cos" och då hittades detta samband och flera liknande, som jag faktiskt inte vet hur det ska tydas. Vad är 0.481188 för något tal i detta sammanhang?



f(ix) = 0.447755*exp(0.481188*ix) - 0.481188*ix*ix*ix



Om man däremot lägger till funktioner "power" (och tar bort alla hintar) så kommer lösningar på formen konstant^ix väldigt snabbt (dvs inom en minut eller så), t.ex.



f(ix) = 32.1653 + 0.446572*1.61809^ix



Där vi möjligen kan ana phi i konstanten 1.61809.

En kommentar om "power": När man väljer den i funktionslistan kommer meddelandet Tip: integer powers are implemented automatically with the multiply operation. This more general power operator may not be needed for modeling the dataset.. Här har vi tydligen ett fall där "power" behövs.

Andra lösningar i olika körningar:



f(ix) = 1.61808^(ix - 1.67492)

f(ix) = 0.0893756 + 0.399799*1.27202^ix + 0.447099*1.27202^ix*1.27202^ix

f(ix) = 1.61804^(ix - 1.67287) + 1.61804^(0.478442*ix - 0.800371)

f(ix) = 1.26564^(2*ix - 1.26564) + 2*ix - 1.26564

f(ix) = ix + 0.447144*1.61804^ix



(Jag har inte analyserat vidare eventuella matematiska samband...)

Notera att även om det är 0 i Error och 1 i korrelationskoeffient så kan det vara stora fel när man pumpar i konkreta värden. 

En intressant lösning är följande där man möjligen kan skymta de viktiga beståndsdelarna i den slutna formeln:

  - sqrt(5) ~ 2.2361

  - 0.4472071911*1.61803 (från tredje varianten av den sökta formeln)



f(ix) = 2.23642*ix + 0.447144*1.61804^ix



Mer komplexa varianter:



f(ix) = 0.447144*1.61804^ix + 2.61804*ix*ix - (ix*ix)^(ix - 48.6408) - 48.6408*ix



Efter detta avslutade jag testet p.g.a. tidsfaktorer. 

Slutsats: Vi hittade alltså inte formeln under dessa experiment, men vissa av sambanden kanske kan vara intressanta att studera vidare. Och så lärde vi oss det där med "power". En annan sak detta visar är att man kan vara tvungen att starta om flera gånger för att få mer aptitliga lösningar.

Derivata

Som nämnts några gånger tidigare så har jag inte labbat så mycket med dynamiska modeller, ävenom Eureqa skapats för detta ändamål. En av anledningarna är att jag inte har så bra data tillgänglig, en annan är att de mer intressanta körningarna kan ta lång tid, i vissa fall många timmar; "över natten" är ett uttryck som används några gånger i skrifterna. 

Som videon (se Eureqas hemsida för länk) visar finns det möjlighet att använda derivata på följande format:



D(x1,t) = f(x1,x2,t)



och även i högerledet



 D(x1,t) = f(x1,x2,D(x2,t))



Andra derivatan skrivs på följande sätt:



D(x1,t,2) = f(x1,x2,t)



Man ska dock tänka på att med derivata så krävs en preprocessing som kan ta mycket lång tid. 

Andra modelleingsexempel  beskrivs nedan.

Datafiler
Här är några av de datafiler som jag testat. För det mest är det enklare saker, och inte någon dynamisk data. De läses in med "File", "Import data...". Datafilerna finns även att tillgå på My Eureqa page. 

 gelman.csv: Linjär regressionsexempel. 

Data från Andrew Gelman's bloggpost Equation search, part 1, Equation search, part 2. Problemet beskrivs även lite mer i A linear regression example, and a question.

Skriv följande i Pick Modelling Task: 

y = f(x1,x2)

och lägg till "sqrt" som funktion.

En lösning är mycket riktigt



f(x1,x2) = sqrt(x1^2+x2^2) 



Med en korrelationskoefficient på 1.0 (och det är alltså bra).

 planets.txt: Keplers tredje lag

Detta exempel baseras på DTREG, ett annat symboliskt regressions-verktyg. Här hittas Keplers tredje lag baserat på den data som Kepler hade. Keplers tredje lag är: 



   Period^2 = Distance^3



Formel: Period = f(Distance)

Funktioner: Skippa sin och cos, lägg till square root, exp och logarithm.

Eureqa hittar rätt snabbt samband såsom:  



    Period = sqrt(Distance)*Distance 



och det går snabbt.

 odd_parity.txt

En test på "paritet", men det funkar inte eftersom Eureqa än så länge saknar booleanska operatorer såsom OR, AND och XOR. Det ska komma "snart".

 sin_formula.txt

Se ovan.

 sin_formula2.txt

Se ovan.

 sqrt_formula.txt

Skapad så här:



perl -le 'for (-100..100) { print $_/100, " ", sqrt(abs(2*$_/100))+3}'



Glöm inte att lägga till sqrt, abs och lite andra funktioner.

 iris.txt: Iris data

Iris är ett standardproblem (-datamängd) inom machine learning och traditionell multivariat statistisk analys. Se Iris flower data set (Wikipedia) för mer information. Kortfattat handlar det om att klassifiera tre olika blomtyper (Iris setosa, Iris virginica and Iris versicolor) med avseende på fyra attribut: (Sepal Length, Sepal Width, Petal Length, Petal Width). 50 mätningar gjordes för respektive blomtyp.

Jag tänkte att det skulle vara skoj att testa det med Eureqa också. Tyvärr klarar inte Eureqa att hantera kategorier (dvs strängrepresentation) så jag döpte om dem till "1", "2", samt "3" vilket troligen förvirrar Eureqa. En standardlösning för visssa typer av analysverktyg/-metoder som inte klarar kategorier är att i stället använda tre binära variabler som representation för de tre kategorierna. Men jag vet inte hur man får in sådant i Eureqa.

Jag började med att representera attributen som sepallength, sepalwidth, petallength, petalwidth men det blev så trångt i lösningsfönstret att jag ändrade till kortnamnen sl, sw, pl, pw.

Problemet skrivs på följande sätt



class = f(sl, sw, pl, pw)



Första körningen, med standarduppsättningen "+","-","*","/" samt "sin" och "cos" gick inte alls bra. Men när - som experiment - jag lade till funktionerna "minimum", "maximum" och "sqrt" så hittas följande rätt snart



   class = f(sl,sw,pl,pw) = max(1,pw + 2.20/sw)



med en error på 0.179, fitness på -0.18, correlation coeff på 0.96, mean squared error 0.04. Traditionella metoder inom data mining/machine learning såsom beslutsträd brukar ligga ungefär där med 5-10 felklassificerade instanser.

Efter lite mer tuggande kommer några bättre lösningar.

error 0.129:



f(sl, sw, pl, pw) = 0.975279 + min(0.624122*pw*pw, 2.02407)



error 0.124: 

f(sl, sw, pl, pw) = 0.926007 + min(max(0.63846*pw*pw, 0.0735181), 2.07556)

Jag är inte nöjd med detta eftersom min och max inte är så naturliga i sammanhanget och jag har inte analyserat vidare ramifikationerna av detta. Men det är ett roligt experiment. Man skulle kunna gå vidare och kontrollera vad som händer om man representerar de tre kategorierna med talen 100, 200, 300 istället, eller lägger till andra funktioner såsom sign etc.

Som jämförelse kan nämnas att andra metoder (t.ex. via machine learningverktyget Weka) ger följande resultat, båda med ett antal felklassifikationer.

J48 (beslutsträd):



petalwidth <= 0.6: Iris-setosa (50.0)

petalwidth > 0.6

|   petalwidth <= 1.7

|   |   petallength <= 4.9: Iris-versicolor (48.0/1.0)

|   |   petallength > 4.9

|   |   |   petalwidth <= 1.5: Iris-virginica (3.0)

|   |   |   petalwidth > 1.5: Iris-versicolor (3.0/1.0)

|   petalwidth > 1.7: Iris-virginica (46.0/1.0)





JRIP (regelbaserad method):



(petallength <= 1.9) => class=Iris-setosa (50.0/0.0)

(petalwidth >= 1.7) => class=Iris-virginica (48.0/2.0)

(petallength >= 5) => class=Iris-virginica (5.0/1.0)

 => class=Iris-versicolor (47.0/0.0)



Se även min My Weka page för mer saker om Weka.

 Sunspots.txt: Sunspots

Solfläcksdata är ett annat standardproblem inom statistik och tidserieanalys. Tyvärr är jag lite osäker på vad denna data kommer ifrån, men det ska mätning av solfläckar på årsbasis. Så ta följande med en viss nypa salt och se det som ett generellt experiment.

Detta är alltså en tidsserie med 11 "förskjutna" variabler.

Formel t11 = f(t1,t2,t3,t4,t5,t6,t7,t8,t9,t10)

Funktioner: +,-,*,/, sin, cos

Notera att jag lät sin och cos vara med men de användes inte under den cirka halvtimmen jag körde (förutom några tidigare lösningar som förkastades snabbt).

Efter ett par minuter var följande med i listan över aktuella lösningar (avrundat till 2 decimaler):



Error: Solution

0.215: 0.65*t10 + 0.66* (t10 / (0.32+0.08*t8)

0.237: 7.20+1.34*t10 - 0.58*t9

0.261: 1.39*10-0.54*t9

0.302: 1.91*t10-t9

0.307: t10-0.19*t9

0.342: 0.84*t10

0.400: t10



Ingen av lösningarna är speciellt bra. Vi ser dock att t10 - inte förvånande - alltid är med, ibland t9 och vid ett tillfälle (det bästa) med t8 vilket visar att det finns någon form av beroende av tidigare värden.

 sin_formula_rand20.txt

Skapad med följande:



perl -le 'for (1..20) { my $x = rand(2*3.14159); print "$x ", sin($x)+exp($x)+3}' 



Hittar följande snabbt:



   3 + exp(x0) + sin(x0)



Testar genom att skippa sin(), men låter cos() vara kvar. Det tar en stund, sedan hittar den följande



  3.00 + exp(x0) + cos(1.57-x0)



 boyles_law.txt: Boyles gaslag

Se mer på Wikipedia Boyle's law.

Detta är en klassiker i sammanhanget (dvs equation/scientific discovery), från boken Langley et.all Scientific discovery (ISBN: 9780262620529, länk till Bokus), sidan 82. Boken beskriver hur systemet BACON angriper problemet. BACON är ett system med liknande intentioner som Eureqa men använder en annan teknik. Boken är för övrigt mycket intressant.

Eureqa hittar relativt snabbt samtliga samband (vid var sin körning):



  PV = P*V 

  V = PV/P

  P = PV/V



Corelation coeff är 1 och mean error i princip 0.

Intressant nog kommer under körningen VP=f(V,P) även andra samband efter en stund:



f(V, P) = (V*P*cos(-1*P - 1.36791) - V*P*P)/(cos(-1*P - 1.36791) - P)



 fib_25.txt: Fibonacci

Se ovan.

 fib_35.txt

Se ovan.

 catalan.txt: Catalan-talen. 

Har inte hittat något skoj hittills, men ska nog leta vidare...

 not_squares.txt

Tal som inte är kvadrater. Hittade inget skoj.

 primes.txt: Primtal

Detta är också en tidsserie-variant med 10 variabler för att se om något skoj samband hittas. Även här får man leta vidare.

 primes_with_index.txt: Primtal med index (dvs ordningstalet för primtalet)

Se ovan om primes.txt

 p4_gap.txt: Polynom

Detta är ett av exempelproblem från JGAP (ett generellt genetisk programmingssystem i Java) där problemet är att hitta polynomet x^4 + x^3 + x^2 - x.

Detta tog cirka 30 sekunder att hitta denna funktion i Eureqa. Notera att jag tog bort "sin" och "cos". 

Som jämförelse kan nämnas att JGAP-versionen tog cirka 12 minuter (vid första och enda körningen), men det är inte en rättvis jämförelse eftersom Eureqa är optimerat för denna typ av körningar. Uppdatering: . Jag noterade att anledningen till att det tog så lång tid i JGAP var att det inte fanns några operatorer för  Add (+) eller Subtract (-) vilket ju gör problemet mycket svårare. När dessa lades till (samt Sine och Exp togs bort) tog det  cirka 10 sekunderi JGAP. JGAP är helt klart ett intressant system för genetisk programmering.

 p4_1.txt: Polynom

Jag skrev ett litet program som skapar slumpdata för polynom på formen x^n+n^(n-1)+...n^2+x^1+x. Sådan problem kallar jag för p(n) nedan.

Detta är alltså p(4). Det tog Eureqa cirka 20 sekunder att hitta



 p(4) =  x^4 + x^3 + x^2 + x



baserat på 30 punkter x,y inom intervallet -5.0..5.0.

 p10_1.txt Polynom P(10)

Däremot var det lite problem med p(10) över intervallet -2.5..2.5 och 100 punkter. Jag startade om ett antal gånger efter att ha väntat - ovetenskapligt nog - "några minuter .

Rätt tidigt hittades x^10+x^8+x^7 men sedan tog det stopp 

och Eureqa började labba med x^12, t.ex. (x^12-x^2)/(x^2-x).

En trolig förklaring till detta är att Eureqa straffar flera termer till förmån för färre.

Jag startade om och ändrade Fitness Metric till "Maximum Error" (på tabben "Pick Modeling Task"). Efter cirka 6 minuter hittades 



0.73*x+x^2+x^3+x^4+x^5+x^6+x^7+x^9+x^9+x^10



med ett Maximum error på 1.76. Correlations coefficienten är 1.0000 vilket ju är bra. 

Lösningen

(x^12-x^2)/(x^2-x) 

har ett mindre felvärde för den datamängd jag testade, det var ju bara 100 punkter, så en del kan förklaras utifrån slump. 

Jag tröttnade efter typ 20 minuter.

 p6_1.txt: p(6)

 p7_1.txt: p(7)

 circle_1_fixed.txt: Cirkel

Detta är ett av exemplen till Eureqa, som finns att laddas ner här. Tyvärr är de i ett konstigt format så jag var tvungen att snygga till dem lite, härav namnet "_fixed.txt".

Formel: x3 = f(x1,x2)

Hittar lösningen 4*sin(x1) på 20 sekunder.

Formal: x2 = f(x1,x3)

Hittar lösningen 4*sin(x1) på 20 sekunder.

Testar nu derivata:

Formel:   D(x3,x1) = f(x1,x2)

Lösningen verkar vara



  dx3/dx1 = x2



Testar formeln D(x3,x2) = f(x1,x2)

Lösningen är 0 som Eureqa hittar omedelbart.

Formeln D(x2, x1) = f(x1, x3)

ger lösningen  x3.



Mer om Eureqa
Här är en samling länkar om Eureqa.
 Download page
 User Guide  (PDF)
  Discussion Group (google group)
  FAQ
  Video: "Introduction to Eurequa" finns via Eureqa-sidan, och även på Youtube: Introduction to Eureqa (1/2) samt Introduction to Eureqa (1/2)
 Hod Lipon och Michael Schmidt är utvecklarna av Eureqa. Deras Science-artikel Distilling Free-Form Natural Laws from Experimental Data, supplemental materials (PDF). Mer finns på Sciences sajt Distilling Free-Form Natural Laws from Experimental Data, Supporting Online Material, med bl.a. den data som används invar_datasets.zip. Som nämndes ovan är datafilerna konstiga (i alla fall i min miljö) och måste fixas till. 


Mer om symbolisk regression som är den metod Eureqa använder: Symbolic regression (Wikipedia)

* Andra artiklar om Eureqa:

 Wired: Download Your Own Robot Scientist

 Guardian: 'Eureka machine' puts scientists in the shade by working out laws of nature

 Physorg.com: Eureqa, the robot scientist (w/ Video)

 Andrew Gelman (bloggar på "Statistical Modeling, Causal Inference, and Social Science"): Equation search, part 1, Equation search, part 2. 








Posted by hakank at 09:16 FM
Posted to Dynamiska system
 | Machine learning/data mining
 | Pyssel
 | Statistik/data-analys






april 28, 2009


Karl Wettin intervjuas om Lucene and Mahout

Karl Wettin har blivit långintervjuad i Interview with Karl Wettin on Lucene and Mahout.

Grant Ingersoll  talks to Karl Wettin, an Apache Lucene and Mahout Committer and independent Lucene Solr consultant. Karl talks about lexically complex European languages, using terms with shingles to simplify queries rather than complex span queries, and improving spellchecking with reinforcement learning, and looking at Mahout NLP.



Kul, Kalle!

Via Clas på Frisim som faktiskt lyckades avkoda att "Wolkan Schellestum" är mitt namn.  (Jag har inte lyckats lyssna på ljudversionen; där är det kanske tydligare.)

Det skrevs för övrigt om Kalle anno 2003 i Silvertejp.






Posted by hakank at 09:07 EM
Posted to Machine learning/data mining






augusti 19, 2007


Recension av Keith Devlin, Gary Lorden: The Numbers Behind Numb3rs: Solving Crime with Mathematics

TV-serien Numb3rs handlar om bröderna Don, FBI-agent, och den yngre brodern Charlie som är en matematikprofessor. Charlie är den egentlige "hjälten" i serien där hans matematiska begåvning (genialitet!) gör att Don kan lösa sina fall. Speciellt skoj är att matematiken i TV-serien är central och man har gjort sig möda om att göra den så korrekt som möjligt. Inte speciellt förvånande (för mina reguljära läsare) är serien en stor favorit.

Serien ska strax börja på fjärde säsongen och då passar det utmärkt att en bok om (kring) serien kommer ut. Det är matematikerna Keith Devlin och Gary Lorden som skrivit The Numbers Behind Numb3rs: Solving Crime with Mathematics (ISBN: 9780452288577) som gör en populärvetenskaplig exposé över matematiken som används i serien.

De två författarna är väl lämpade att skriva boken:

Keith Devlin, professor i matematik och är nog mest känd som Math Guy och skriver i den (populär)matematiska kolumnen Devlin's Angle (Archives). Devlin har även skrivit flera böcker (där 1988 års utgåva av Mathematics - the New Golden Age var en stor inspirationskälla för mitt matematikintresse).

Gary Lorden kände jag däremot inte till innan serien Numb3rs. Han är professor i matematik och "chief mathematics consultant" till TV-serien. Den senare rollen beskrivs t.ex. i CaltechNews-artikeln Crime and Computation.

Boken är "oteknisk" skriven och det krävs inga speciella matematiska förkunskaper (förutom sådana som normal skolgång bör ha gett). Det finns få formler/ekvationer och de som finns förklaras nästan alltid ingående.

När jag först läste om boken trodde jag att alla kapitel skulle behandla Numb3rs-relaterade saker och endast sådana. Man har istället valt en mer utökad variant och det saknas Numb3rs-koppling i några kapitel, t.ex. kapitel 5, "Image Enhancement and Reconstruction" som handlar om bildbearbetning i samband med efterverkningarna av lynchningen av Rodney King. Det görs också intressanta genomgångar av matematiken i och kring rättegångarna (som inte alls är med i TV-serien), t.ex. bevisvärdet av DNA-test och fingeravtryck samt kring urvalet av jurys. Denna utökning fungerar bra, även om det möjligen kan vara lite förledande i marknadsföringen.

En av de stora fördelarna med populärvetenskapliga böcker är att man blir inspirerad att läsa vidare i det ämne som behandlas. Tyvärr försvåras sådan vidareläsning genom att det i många kapitel inte finns några litteraturreferenser eller vidareläsningstips (det finns dock flera kapitel som har mycket referenser). Möjligen har författarna ansett att läsarna själv söker efter obekanta termer via sökmotorer eller Wikipedia. Fel approach enligt min mening.

Trots bristerna tycker jag om boken och rekommenderar den till de som också gillar TV-serien. Och rekommenderar TV-serien för den som inte sett den.

Bokens kapitel

Här är en listning av kapiteln och några kommentarer kring dem.
1. Finding the Hot Zone - Criminal Geographic Profiling


"Geografisk profiling" är det centrala temat i pilotavsnittet (Pilot). Tekniken innebär att man skapar en "hot zone" var en brottsling bor. Avsnittet bygger på ett faktiskt fall (något dramatiserat).

2. Fighting Crime with Statistics 101


Ett introducerande avsnitt om statistik och sannolikheter.

3. Data Mining - Finding Meaningful Patterns in Masses of Information


En sammanställning av några av de metoder som finns inom data mining (något som jag skrivit om en del).

Följande metoder beskrivs med flera exempel:


 * link analysis

 * (artificiella) neurala nätverk, inklusive Kohonens Self Organising Maps (SOM)

 * machine learning

 * (geometrisk) klustring

 * software agents ("intelligenta" mobila program)

Jag blev dock lite förvånad att se "software agents" med i listan över data mining-tekniker. Men OK.

4. When does the Writing First Appear on the Wall? - Changepoint Detection


Detta kapitel om "change point detection" var det som gav mig mest ny information. Tekniken går ut på att försöka röna ut när det sker en signifikant förändring i en serie av data (tidsserie).

Not: Det är vanligare med mellanslag mellan "change" och "point" än utan.

5. Image Enhancement and Reconstruction


Se ovan.

6. Predicting the Future - Bayesian Inference


Bayesiansk analys med enkla exempel, t.ex. det berömda taxibilsexemplet som även nämns i Devlins artikel Tversky's Legacy Revisited och Weighing the evidence.

7. DNA Profiling


Förklarar matematiken bakom DNA-tester. 

På Devlins preprintsida finns bl.a. Scientific Heat About Cold Hits som handlar sannolikheter vid "cold hits" i DNA-analyser. Normala DNA-tester är då man studerar hur väl ett DNA-prov från en brottsplats matchar DNA från misstänkt person. Vid cold hits har man inte en misstänkt utan gör en data snooping i DNA-databasen och försöker hitta någon som matchar detta DNA. Sannolikhetsmässigt är detta inte samma sak (speciellt inte om man tar vilken "närmaste match" som helst".

Se även Devlins artiklar  DNA math and the end of innocence, Statisticians not wanted samt Damned lies.

8. Secrets - Making and Breaking Codes


Krypto. Naturligtvis beskrivs RSA-algoritmen översiktligt.

Se t.ex. Devlins Cracking the Code.

9. How Reliable is the Evidence? - Doubts about Fingerprints


Kritisk genomgång om hur fingeravtryck används och hur svag bevisgrund sådana har i amerikanska domstolar.

10. Connecting the Dots - The Math of Networks


Sociala nätverk och komplexa nätverk. Mycket kring terrorismbekämpning.

Cf Social Network Analysis och Complex Networks - En liten introduktion.

11. The Prisoner's Dilemma, Risk Analysis, and Counterterrorism


Spelteori och risker.

12. Mathematics in the Courtroom


Avsnitten i TV-serien avslutas när boken blivit infångad (följt av några minuter fin familjedramatik). Efterspelet med rättegångarna finns däremot aldrig med. Boken beskriver genomgående däremot denna del rätt mycket, specifikt i detta kapitel.

Den i skrivande stund senaste Devlin's Angle-kolumnen  The Professor, the Prosecutor, and the Blonde With the Ponytail är en mycket förkortad version av detta kapitel 12.

13. Crime in the Casino - Using Math to Beat the System


Kasino och korträknare i Black Jack (21). 

 Appendix: Mathematical Synopses of the Episodes in the First Three Seasons of NUMB3RS


Trevligt med en listning av matematiken inom avsnitten. Se nedan för länkar till sajter som har liknande listningar.





Se även

Devlins artikel om TV-serien NUMB3RS gets the math right.

Jag har köpt de två första säsongerna från Discshop. Tyvärr saknas här de kommentatorspår som finns i region 1-varianterna.

Recensionen New Book Explains How Math Can Help Solve Crimes finns även som pratversion inklusive författarnas (autentiskt återgivna förutsätter jag) röster.

Sajten Redhawke NUM3RS med länkar till matematiska begrepp

Dr. Andrew Nestler's Analysis of NUMB3RS

Min favoritblogg i Numb3rsiana: num3rs blog

Succén med TV-serien har även knoppat ett samarbete mellan CBS, Texas Intstrument och National Council of Teachers of Mathematics i form av sajten We All Use Math Every Day där lärare kan hämta material som kopplas till de olika avsnitten. Aktiviteter för respektive säsong (sorterad i bloggordning):

 Season 1

 Season 2

 Season 3






Posted by hakank at 11:21 FM
Posted to Böcker
 | Machine learning/data mining
 | Matematik
 | Social Network Analysis/Complex Networks






mars 11, 2007


Några saker om Weka (databrytning, data mining och machine learning)

Not: Delar i nedanstående förutsätter att man känner till data mining/machine learning-verktyget Weka (Wiki). Tyvärr är det en ganska begränsad skara bland mina läsare.

Tystnaden den senaste tiden har till visst del berott på läsning av andra upplagan av boken Data Mining

Practical Machine Learning Tools and Techniques (ISBN: 0120884070, ISBN13: 9780120884070) som förutom en mycket trevlig och pedagogisk läsning om data mining/machine learning generellt även beskriver just Weka. Till läsande av sådana böcker kommer naturligtvis lekande och testande av saker. 



CVS-versionen

Även om det kommer nya versioner av den publika versionen är CVS-versionen att rekommendera eftersom där kommer nya saker hela tiden, framförallt buggfixar. Via mailinglistan förmedlas (de flesta) av ändringarna.

Numera hämtar jag den senaste versionen dagligen med nedanstående program shell-program (Linux). Apache Ant krävs för att kompilera Java-koden. Lösenordet för cvs login är  en vagnretur (Enter-tangenten, alltså)



#!/bin/sh

export CVSROOT=:pserver:cvs_anon@cvs.scms.waikato.ac.nz/usr/local/global-cvs/ml_cvs

cvs login

cvs -q co weka 

cvs -q co tests

cd weka

# kompilerar koden

/usr/bin/ant 

# skapar java doc

/usr/bin/ant docs > /dev/null



Se även CVS-sidan på Wikin.

Närmare bestämt görs detta som ett cron-jobb. Ett Expect-script skapades med programmet autoexpect så att det går helt utan manuell inblandning.

Just det: i crontab måste man se till så att programmen körs i rätt katalog och har de miljövariabler som krävs, såsom CLASSPATH. Min crontab-entry ser ut så ungefär så här (det ska vara en rad) där weka_co.exp är Expect-programmet:



6,12 * * *   . /home/hakank/.zshrc && cd /home/hakank/weka_cvs && /home/hakank/weka_cvs/weka_co.exp





Filter

I Weka Explorer (GUI-versionen) och via kommandoraden kan man använda filter för att filtrera datamängderna på olika sätt. Som jag använder Weka nu är det nästan uteslutande via GUI-versionen.

Här är några användbara filter för initialanalys av datan:

  unsupervised.attribute.InterquartileRange: Skapar två nya attribut (Outlier, ExtremeValue) som indikerar om en instans är en outlier respektive extremvärde.

unsupervised.attribute.RemoveUseless: Tar bort attribut som är useless, såsom värden som varierar för mycket (t.ex. unika id) eller för lite (konstanter).



Ett filter som jag nyligen skapade är ExpandFreqField som givet ett frekvensfält duplicerar instanser så att det finns så många som frekvensfältet anger. T.ex. följande synnerligen fiktiva datafil (i ARFF-format) har ett sådant frekvensattribut  freq (det sista fältet).  



@relation Freq

@attribute a {p,q,r}

@attribute x numeric

@attribute y numeric

@attribute freq numeric

@data

p,1,2,1

q,2,3,2

r,3,4,4



dvs första instansen (dataraden som börjar med "p") ska förekomma 1 gång, andra instansen 2 gånger samt tredje instansen 4 gånger. Filtret skapar en ny datamängd som ser ut så här om man kör från kommandoraden: java weka.filters.unsupervised.instance.ExpandFreqField -i ExpandFreqFieldTest.arff

 eller väljer filtret via Weka Explorer.



@relation Freq-weka.filters.unsupervised.instance.ExpandFreqField-Flast

@attribute a {p,q,r}

@attribute x numeric

@attribute y numeric

@attribute freq numeric

@data

p,1,2,1

q,2,3,2

q,2,3,2

r,3,4,4

r,3,4,4

r,3,4,4

r,3,4,4



Installation av filtret kräver att man har Java-koden till Weka-installerat (det har man om man laddar ner CVS-versionen enligt ovan):

Kopiera Java-programmet till katalogen weka/filters/unsupervised/instance
        
 Kompilera filen
        
 Lägg till följande rad i properties-filen weka/gui/GenericObjectEditor.props  tillsammans med andra filters.unsupervised.instance-filter:
weka.filters.unsupervised.instance.ExpandFreqField,\
(glöm inte det avslutande "\")
       
Starta om Weka Explorer. Där finns nu filtret inlagt.


Kommentar: Normalt skriver jag Perl-program för sådana filter-saker men sådant går inte alls att integrera i Weka Explorer på samma sätt som ett riktigt Weka-filte.



MultiFilter

Eftersom jag använder Weka Explorer för "explorativ data mining" är det många saker som måste göras om varje gång, t.ex. RemoveUseless eller outliner-kontroll enligt InterquartileRange (se ovan). MultiFilter finns ett bra sätt att kombinera flera olika filter. Så här gör man:

* Öppna filtret MultiFilter

* Lägg till de filter som ska användas. Se till så att de läggs i rätt ordning

* Spara filtret med ett lämpligt namn

* Vid senare tillfälle kan man öppna MultiFiltret och köra det rakt av

 

Några exempel



 RemoveUseless + InterquartileRange


För beskrivning av dessa filter se ovan. Instruktion med ett tips:- 

  

      Öppna MultiFilter

     
 Add:a  filtret RemoveUseless

     
 Add:a filtret AllFilter (se kommentar nedan)

     
 Add:a InterquartileRange 


            Sätt eventuellt SetExtremeValuesAsOutlier till True.

     
 Spara detta MultiFilter med Save och ett bra namn.

  


 Ta bort instanser av outliers och extremvärden, t.ex. efter att ha kört ovanstående filter

 

   Öppna MultiFilter och lägg till följande. 

   
  RemoveWithValues


      attributeIndex: last


      nominalIndices: last

  
  attribute.Remove


    attributeIndex: last

  
   AllFilter

  
 unsupervised.instance.RemoveWithValues


      attributeIndex: last


      nominalIndices: last

  
  attribute.Remove


    attributeIndex: last

  
 Spara med ett lämpligt namn.

  




Det andra filtret tar alltså först bort instanser som är ExtremeValues (det sista attributet), sedan raderas detta attribut. Ett AllFilter justerar attributpositionerna, varefter samma sak görs med Outlier-attributet (som då är det sista attributet).

I båda dessa MultiFilter har filtret AllFilter lagts till som ett "strömfilter" eftersom föregående filter tar bort ett attribut. Sådana attributförändringar förvirrar uppenbarligen nästkommande filter om det arbetar med attributpositioner (såsom first, last, 2,4).  



Några nya favoritklassificerare

Tidigare har trädklassificeraren J48 (tillsammans med baselinemetoden OneR och NaiveBayes) varit förstaklassificerare eftersom den är snabb och ger ett översiktlig bild av datans struktur. Numera är det REPTree som har denna status eftersom den är  ännu snabbare (dock inte lika stabil som J48), 

Några andra nya som är värda att testa:

* SimpleCart - som är en "enkel" implementation av CART (en av de första trädklassificerarna)

* JRip och - inte så ny i Weka men efter genomläsningen av boken återficks ett intresse för regelbaserade klassificerare. Man hittar i dessa regelbaserade små data-klimpar (nuggets) som kan vara intressanta.

För övrigt kan rekommenderas ett studium av BayesNet med algoritmen ICSSearch som ger riktigt trevliga dependensträd (som man i vissa fall möjligen kan tolka som orsaksgrafer), t.ex. om man sätter maxCardinality till > 2.  Man bör inte glömma att högerklicka på entryn i Result list och välja "Visualize graph" för då missar man den fina dependensgrafen. Tyvärr kostar metoden mycket kräm (dvs internminne + tid).  Mer om BayesNet-implementationen i Weka kan man läsa i Remco R Bouckaert Bayesian Network Classifiers in Weka (PDF, även gammal HTML-version).



R:s RWeka för att konvertera datafiler

Om man som jag är på jakt efter trevliga datamängder att leka med kan man fördel utnyttja den rikliga mängd av data som finns i R med hjälp av paketet RWeka där funktionen write.arff (och read.arff) kan användas. Notera att vissa konverteringar inte fungerar eftersom write.arff förutsätter en datastruktur som inte alltid uppfylles. 

Om man vill (och det vill man nog) konvertera alla data från ett R-paket kan man använda följande. ARFF-filerna läggs i den katalog där man startade R.



write.arff.data.package <- function(pack) {

   require(RWeka);

   for (x in data(package = pack)$results[,3]) {

          print(x);

          data(list=as.character(x),package=pack)

          try(write.arff(get(x),paste(x,".arff",sep="")))

   }

}



Exempel: konvertera data som finns i paketet dprep:



write.arff.data.package("dprep")





Känner man sig riktigt modig och har tid (det gör man ibland och har man ibland)  kan man köra detta för att konvertera data i samtliga paket



for (pack in .packages(all = TRUE)) {

  print(pack);

  write.arff.data.package(pack)

}



Notera återigen att allting blir inte konverterat korrekt. Ett kännetecken på att det inte gick bra är att filerna innehåller strängen structure(list. Dessa filer är alltså inte användbara i Weka.



Datafiler

Apropå datafiler.

Har man inte laddat ned ARFF-datafilerna som finns nedladdningsbara bör man göra det. Där finns framförallt standarddatamängderna från UCI Machine Learning Repository och Statlib. 

Just det: Man borde ARFF-iera DASL - The Data and Story Library . [... time passes ... ] Fixat:  Arff-versioner av DASL.



YALE (och Weka Knowledge Flow)

YALE Yet Another Learning Environment är ett - egentligen - trevligt GUI för att data mining / machine learning. Det inkluderar mycket av Wekas algoritmer och har använder processflöde snarare än det manuella framochtillbakande som används i Weka Explorer. YALE har framförallt bättre möjligheter än Weka att visualisera data, t.ex. sådant som SOM (Kohonen), Andrews-kurvor och plotter-matriser. Man styr experiment antingen via GUI eller att skriva XML-filer. En mycket stor fördel är att det finns en bra online-tutorial som förklarar komponenterna och hur de ska integreras (med många exempel). Det är bra.

Personligen är jag inte så väldigt förtjust i detta processflödande, vilket mest beror på mitt sätt att arbeta med Weka just nu, nämligen att leka med algoritmer, metoder och datamängder. Just sådant är meckigare i YALE.  Ett exempel: I Weka Explorer antas att klassattributet är det sista  och vill man ändra det är det enkelt att göra i Preprocess.  I YALE måste man däremot alltid manuellt skriva in attributnamnet (såvida man inte sparat ett experiment med ett sådant ifyllt).  En annan sak är att det finns ohyggligt många komponenter med olika roller och krav, och i alla fall i början är det förvirrande hur de hänger ihop och hur man ska tolka olika felmeddelande att man inte har rätt komponent. Det finns dock en flera hundra sidors dokumentation som beskriver alla komponenter.

Trots ovanstående kittsligheter är YALE definitivt något att hålla ögonen på och att åtminstone använda som komponent till Weka.

Weka KnowledgeFlow har också ett flödestänkande och jag har samma relation till det som till YALE, nämligen att hellre använda Weka Explorer.



Se även

My Weka Page




Posted by hakank at 10:51 FM
Posted to Machine learning/data mining






februari 16, 2007


Ansikten: länkar 20070216

Det blev visst mest om ansikten idag.

New York Times: Faces, Faces Everywhere



Why do we see faces everywhere we look: in the Moon, in Rorschach inkblots, in the interference patterns on the surface of oil spills? Why are some Lay’s chips the spitting image of Fidel Castro, and why was a cinnamon bun with a striking likeness to Mother Teresa kept for years under glass in a coffee shop in Nashville, where it was nicknamed the Nun Bun?

...

Dr. Sinha of M.I.T. says that whether the hair-trigger response to faces is innate or learned, it represents a critical evolutionary adaptation, one that dwarfs side effects like seeing Beelzebub in a crumpled tissue.



Pawan Sinha

Mind Hacks: Faces, faces everywhere

The Face Clouds

Cognitive Daily: Why we see faces when they're not really there (with poll!)



Wikipedia: Apophenia: Apophenia is the experience of seeing patterns or connections in random or meaningless data. 

Wikipedia: Pareidolia: Pareidolia [...] describes a psychological phenomenon involving a vague and random stimulus (often an image or sound) being mistakenly perceived as recognizable.



Mind Hacks: Beauty and the average girl, Average girls are hot

Seed Magazine: Beauty is in the processing time of the beholder: Prototypical faces are pleasing because they're easy for the brain to process.

Piotr  Winkielman, Prototypes are attractive because they are easy on the mind (PDF)

Face Research

Figurer i moln



Här passar det utmärkt att länka till det trevliga Malmöföretaget Polar Rosesom specialicerat sig på ansiktsigenkänning. 



The web is increasingly becoming visually oriented, progressing from text to photos and other rich media. Close to 10 million new photos are uploaded on a daily basis, a number which is doubling every eight to ten months.

Photos tell many stories, but unlike text, the context of a photo is hard to search for unless explicitly "translated" by a human being. The photo web of today is like the text web before Altavista, Inktomi, and Google.

Polar Rose makes photos searchable by analyzing their content and recognizing the people in them.



Polar Rose blog.






Posted by hakank at 06:25 EM
Posted to Diverse vetenskap
 | Machine learning/data mining

| Comments (2)





februari 11, 2007


Några länkar om dataanalys, data mining etc 20070211

Statistical Modeling, Causal Inference, and Social Science

The fallacy of the one-sided bet (for example, risk, God, torture, and lottery tickets)

Animated Social Network Visualization



Data Mining Research

Data mining application: terrorism, som även tipsar om en ny bok Data Mining and Predictive Analysis: Intelligence Gathering and Crime Analysis (ISBN: 075067796) skriven av Colleen McCue .

 

Geeking with Greg

 Excellent data mining lecture notes tipsade för länge sedan om kursen CS345, Autumn 2006: Data Mining. Där finns en mängd presentationer av metoder.



Cognitive Daily

Is 17 the "most random" number?

Randomness wrap-up



Nyupptäckta bloggar i ämnet

Data Mining Research tipsade även om en ny blogg Crime Analysis and Data Mining:  A meeting place for those interesting in analyzing or solving crimes using Predictive Analytics!, se presentationen.

Data Mining in MATLAB






Posted by hakank at 10:37 FM
Posted to Machine learning/data mining
 | Statistik/data-analys







juni 21, 2006


Pascal Virtual Playground: machine learning videoföreläsningar

(Mer videos fast denna gång något mer akademiskt än Lite nördmusikmotvideos.)

PASCAL Virtual Playground innehåller ett stort antal videoföreläsningar kring machine learning statistisk modellering och liknande ämnen.  För att se föreläsningarna synkroniserade med presentationerna krävs Internet Explorer, men det finns även möjligheter att se de allra flesta videoföreläsningarna i andra webläsare via "Preview video" (då utan synkroniserade presentationer) .

T.ex. Machine Learning Summer School 2005 - Canberra.

PASCAL står för Pattern Analysis, Statistical Modelling and Computational Learning och är ett nätverk för att samla forskare inom forskningsområdet. Från dess hemsida



The objective is to build a Europe-wide Distributed Institute which will pioneer principled methods of pattern analysis, statistical modelling and computational learning as core enabling technologies for multimodal interfaces that are capable of natural and seamless interaction with and among individual human users.



Se även

PASCAL EPrints



(Via Machine Learning Thoughts.)



Andra bloggar om: videos, machine learning, statistik.






Posted by hakank at 07:49 FM
Posted to Machine learning/data mining
 | Video podcasts







maj 11, 2006


Uppdatering på Weka-sidan

[Detta har jag visst glömt att berätta.]

På min Weka-sida gjordes några uppdateringar för ett tag sedan. Det fria-att-nedladda programmet Weka är alltså det program jag mest använder för data mining/machine learning.

* Den Weka-version som används är nu 3.5.2 (den som just nu är den aktuella officiella utvecklingsversion). 

* Appletarna och dess stödprogram är uppdaterade till denna Weka-version. Främst var det klassnamnen till klassificerarna som har ändrats till de mer moderna. Några andra småjusteringar gjordes också.  Programmen är nu kompilerade med Java 1.5.

* Några nyare klassificeringsmetoder har lagts till, bl.a. en ny favorit: REPTree som är en snabbt beslutträdsmetod och där man enkelt kan ändra djupet på trädet (för att undvika overfittning eller detaljer). Men som alltid bör man jämföra flera olika klassificerare och inte nöja sig med en enda. Och följande tips gäller fortfarande: Börja med regelklassificeraren OneR (One-rule) som en jämförande baseline hur bra andra klassificerare är. (NaiveBayes är också bra att använda som baseline.)

* På allmän - eller i alla fall en hel del mailförfrågningar - finns nu också källkoden till programmen tillgängliga, både till applets och stödprogrammen. Notera att dessa program skrevs kring 2002/2003 mest som proof-of-concept att Weka kunde appletifieras. Snyggare Java-kod finns säkert...

* Två mycket enkla program med associationsregler för analys av shoppingkorgar (med Apriori-algoritmen)  har lagts till: 

Simple Association Rule Applet 1 (småsaker från en pappershandel?)

Simple Association Rule Applet 2 (filmer).



Se även

Här är de referenserna som också blev ditlagda vid siduppdateringen:

The Weka Wiki

Weka mailinglist

Weka API documentation

Information hur man hämtar den allra senaste CVS-versionen (som har en hel del smått och gott som inte finns i de officiella versionerna. Uppdateras nästan dagligen.).

Samt naturligtvis boken Data Mining: Practical Machine Learning Tools and Techniques  (Second Edition) som beskriver generellt om data mining/machine learning och med konkreta exempel i Weka. Finns på Bokus och rekommenderas varmt.

Annat skrivet här om Weka finns via en känd sökmotor: weka site:hakank.org.



Andra bloggar om: weka, data mining, machine learning




Posted by hakank at 09:22 EM
Posted to Machine learning/data mining

| Comments (3)





maj 08, 2005


Sällskapsspel, strategier och spelteori

BBC News-artikeln  Scissors, paper, stone - a strategic game beskrivs inledningsvis en lite märklig historia där två auktionsfirmor tävlade om en kunds kontrakt genom att spela sten-sax-och-påse.

You probably thought scissors, paper, stone was a game of chance not strategy. But you'd be wrong. Christie's auction house won a £10.5m contract by playing the game tactically - so is there more to such games than meets the eye?

En intressant sak här är vilka experter som (vinnaren) Christie hade frågat. Har ett storföretag verkligen inte har någon annan expert att fråga (eller så är det en frisering för att söta till en historia).

...but Christie's asked the experts, Flora and Alice, 11-year-old daughters of the company's director of Impressionist and modern art, and aficionados of the game.


They explained their strategy:

1. Stone is the one that "feels" the strongest

2. Therefore a novice will expect their opponent to go for stone, and will go for paper to beat stone

3. Therefore go for scissors first

Sure enough, the novices at Sotheby's went for paper, and Christie's scissors got them an enormously lucrative cut. 



Derren Brown har i sina shower visat stor förmåga att förutse/påverka sina motståndare i detta spel och använder troligen en något mer avancerad variant än ovanstående. Varför frågade de inte honom?



Sedan nämns översiktligt studier om strategier för olika spel (där man felstavat några namn). Här är några nedslag till referenser:

* Rock, Paper, Scissors (Sten, sax och påse)

Se wikipediaartikeln Rock, Paper, Scissors.

Några introduktioner kring spelteori som nämner spelet:

A Brief Introduction to Game Theory

Games, Dilemmas, and Traps



* Monopoly 

(den engelskspråkiga varianten av Monopol).  

Troligen är det Neil Thompson (inte Thomson) man avser i artikeln, i alla fall har en sådan skrivit Monopoly Statistics and Strategy som innehåller strategier och statistik för spelet.

Två andra sajter:

Durango Bill's Monopoly Probabilities.

Truman Collings har skrivit om sannolikheterna för det amerikanska Monopoly: Probabilities in the Game of Monopoly (som också innehåller ett C-program för simuleringen).

(Colling har gjort andra roliga saker, t.ex. både en solver och en generator för alphametics-problem, dvs problem såsom SEND + MORE + MONEY, där man ska ersätta bokstäverna med siffror så att additionen blir korrekt.)



* Connect Four

Han som skrev sin doktorsavhandling om Connect Four heter Victor Allis (inte Allen): A Knowledge-based Approach of Connect-Four The Game is Solved: White Wins (CiteSeer).

Fler referenser om spelet finns hos MathWorld Connect-Four.



* Samlingssajter

Slutligen två sajter som har helt olika inriktningar:

Combinatorial Game Theory är en länksamling för matematisk forskning om bl.a. sällskapsspel.



En annan intressant sajt och som jag ofta besökte för några år sedan  är Machine Learning in Games. index of games har en listning över de olika spelen. Sajten har dock inte uppdaterats sedan 2002.






Posted by hakank at 08:45 FM
Posted to Machine learning/data mining
 | Spelteori och ekonomi
 | Statistik/data-analys






april 14, 2005


Amazons "Statistically Improbable Phrases"  (SIPs)

I två separata maildiskussioner (med Peter Lindberg och Simon Winter) har Amazon.com:s "Statistically Imprabable Phrases" (SIPs i folkmun) diskuterats. Den enda svenska text jag har hittat om detta är Erik Starcks notis Amazon testar Statistically Improbable Phrases (med en kommentar av Simon).

Det känns som det är dags att göra en liten sammanfattning (och ett gemensamt ställe att kommunicera findings).

Sedan några veckor har flera böcker presenterats med vad Amazon.com kallar för "Statistically Improbable Phrases". Det är sådana fraser som används ofta i en viss bok men sällan i andra böcker. Så här förklarar de själva:

Amazon.com's Statistically Improbable Phrases, or "SIPs", show you the interesting, distinctive, or unlikely phrases that occur in the text of books in Search Inside the Book. Our computers scan the text of all books in the Search Inside program. If they find a phrase that occurs a large number of times in a particular book relative to how many times it occurs across all Search Inside books, that phrase is a SIP in that book. 

För t.ex. Malcolm Gladwells The Tipping Point finns SIPparna: social epidemics, transactive memory, mouth epidemics, teenage smoking. Man kan notera att frasen "tipping point" inte finns med, vilket beror på att det används i och för sig ofta i Gladwells bok, men finns även ofta i andra böcker.

Tanken med sådana SIP:ar verkar vara att visa på utmärkande drag i boken, men jag är tveksam till hur nyttiga de egentligen är för detta ändamål. Anledningen till tveksamheten är att det verkar vara svårt att göra en bedömning av bokens innehåll med hjälp av endast dessa fraser. Det känns rätt mycket som en titta-vad-vi-kan-göra-funktion (som i och för sig är cool). I och för sig är jag benägen att ändra mig när jag ser detta.

Däremot ger möjligheten att SIP-surfa, dvs att klicka till andra böcker med samma fraser, ännu ett trevligt sätt att upptäcka nya böcker. Vi har nog bara sett början på detta...



Principen bakom SIPs är inte ny. T.ex. får man väl anse att det är en variant (konceptuellt i alla fall) av hapax legomenon, dvs helt unika ord i en text. Se även denna längre artikel. 

Mer generellt änvänds (troligen) en variant av Term Frequency / Inverse Document Frequency (TFIDF), som det finns en hel del skrivet om. Det stora med Amazons implementation är naturligtvis att det är publikt surfbart och att metoden används på en stor mängd texter (böcker). 



Inspirerad av allt detta började vi (Peter, Simon och jag i  separata) att fundera på hur man bäst gör egna varianter för våra respektive blogganteckningar, där en bok skulle motsvaras av en blogganteckning. 

Peter tipsade om ett litet Pythonprogram (dess notis), men som endast arbetade med "fraser" på ett enda ord, vilket inte är så skoj.

Själv kikade jag i helgen på ett Perl-paket som Simon fått nys om: Ngram Statistics Package (NSP), på CPAN heter det Text::NSP. Efter en del föreståendeskapande lekar med detta började de mer seriösa arbetet, men det kräves mycket tråkigt filtreringsarbete och annat så projektet lades på hyllan, i alla fall för tillfället. 

Jag är nu, efter de trevlande inledande försöken, till viss del tveksam hur mycket detta projekt egentligen ger (förutom leken, utmaningen och äran) eftersom en blogganteckning innehåller så pass lite text att det kan vara svårt att det blir intressant. I och för sig påverkas jag inte mycket av nyttan av ett projekt. :-) 

Troligen kommer man fram till att det finns en stor mängd ord som endast förekommer i en enda blogganteckning (dvs blogg-hapax legomenon), såsom namn eller begrepp, och så finns det en stor mängd fraser som har en frekvens som motsvarar det vanliga språkbruket. Frågan som är intresserant att undersöka är om det finns tillräckligt många ord som befinner sig mellan dessa två frekvenstyper och därmed betecknar något "statistiskt osannolikt" (och förhoppningsvis överraskande) om en blogganteckning.

En utökning av detta vore att arbeta med samtliga texter för en blogg och jämföra frasfrekvenserna med andra bloggar, vilket nog skulle ge bättre utdelning.



Andra finesser som Amazon infört den senaste tiden är presentation över vanligast förekommande ord (concordance), olika typer av textstatistik och complexity. Exempel på sådant finns t.ex. här (Peters exempel).



Ytterligare:

Google-sökning på "Statistically Improbable Phrases"

Det finns en Perl-modul som beräknar olika textindex för engelska texter. Lingua::EN::Fathom.



Uppdateringar

Blind "Jonas Söderström" Höna har även skrivit om detta: 

Amazon letar fram "osannolika fraser" i böcker samt Mer på amazon: de hundra vanligaste orden

En annan sak. Böckerna beställes naturligtvis via Bokus:

* Malcolm Gladwell: The Tipping Point

* Lynne Truss: Eats, Shoots & Leaves - The Zero Tolerance Approach to Punctuation




Posted by hakank at 08:55 EM
Posted to Böcker
 | Machine learning/data mining
 | Språk







november 23, 2004


Wired: Software Detects the True Artist 

Wired News: Software Detects the True Artist

Scholars have had their suspicions that the painting of Madonna and child credited to the Italian Renaissance master Pietro Perugino wasn't really done by him alone. But they could never be sure.


Now, a new set of software tools, developed by a Dartmouth College team, seems to confirm the art historians' doubts, showing evidence of at least four different painters working on the canvas. The programs' makers hope this will be the first in a long line of art authentication mysteries they can help put to rest, with code that can sort out real from fake. 

"There are properties in an artist's pen and brush strokes that aren't visible to the human eye, but that are there nonetheless. And we can find them, through mathematical, statistical analysis," said Dartmouth computer science professor Hany Farid, who developed the algorithms, along with math professor Daniel Rockmore and graduate student Siwei Lyu.





Några länkar:

Hany Farid

Dan Rockmore

Siwei Lyu

Art Forensics

Siwei Lyu, Dan Rockmore and Hany Farid: A Digital Technique for Art Authentication

Abstract:

We describe a computational technique for authenticating works of art, specifically, paintings and drawings, from high resolution digital scans of the original works. This approach builds a statistical model of an artist from the scans of a set of authenticated works, against which new works are then compared. The statistical model consists of first- and higher-order wavelet statistics. We show preliminary results from our analysis of thirteen drawings that have at various times been attributed to Pieter Bruegel the Elder, which confirm expert authentications. We also apply these techniques to the problem of determining the number of artists that may have contributed to a painting attributed to Perugino and again achieve an analysis agreeing with expert opinion.





För övrigt skulle jag gärna vilja se filmen The Math Life



Uppdatering

Philip Ball skriver också om detta i Nature: Computers confront the art experts




Posted by hakank at 08:15 EM
Posted to Machine learning/data mining







november 02, 2004


InfoVis: Collaborative Filtering 

InfoVis.net Collaborative Filtering:

Collaborative filtering is increasingly present as an integral part of commercial web sites. "Memory based" algorithms are the most simple to implement, yet the most effective when recommending products and predicting preferences..





Se även följande samlingssidor:

Collaborative Filtering

Lyle Ungar: Recommender Systems

Principia Cybernetica Web: Collaborative Filtering

samt Farliga rekommenderare.




Posted by hakank at 10:35 EM
Posted to Machine learning/data mining
 | Rekommendationssystem







augusti 24, 2004


Demokratiska akademiska tidskrifter

En metod att skapa mer demokratiska journaler presenteras i Journal of New Democratic Methods: An Introduction skriven av John David Funge. (Jag tror att det är rätt person Uppdatering. Det är samma person: samma emailadress.)

Abstract:

This paper describes a new breed of academic journals that use statistical machine learning techniques to make them more democratic. In particular, not only can anyone submit an article, but anyone can also become a reviewer. Machine learning is used to decide which reviewers accurately represent the views of the journal's readers and thus deserve to have their opinions carry more weight. The paper concentrates on describing a specific experimental prototype of a democratic journal called the Journal of New Democratic Methods (JNDM). The paper also mentions the wider implications that machine learning and the techniques used in the JNDM may have for representative democracy in general.



Från Conclusion



One of the biggest challenge to the success of the JNDM is obtaining participation from qualified people. This is a classic  chicken and egg  problem and hopefully the paper you are now reading will help to interest people. The more widely it can read the better. 


Even if people begin signing up to the JNDM and submitting articles it will still be a challenge to encourage people to review and rate articles. It may be necessary to institute incentives to encourage people to actively participate. For example, users should probably not be allowed to read another submission until they have submitted their review for the last one. Similarly readers could be rationed to only being able to read a fixed number of articles without submitting any ratings. The danger is that a small number of enthusiasts end up doing all the reviewing with little or no feedback from the larger readership.

Se även

www.democraticjournals.org som kräver konto och inloggning (har alltså inte testat detta). Man säger så här på välkomstsidan:

Welcome to the Journal of New Democratic Methods (JNDM). The JNDM is currently only available as part of a beta release and limited test. We don't have details on when the JNDM will be made more widely available, as that depends in part on the results of the test.

Från paprets litteraturlista:

Collaborative Filtering

www.kernel-machines.org

Chris Manning and Hinrich Schütze. Foundations of Statistical Natural Language Processing (kompanjonsajt till en mycket trevlig bok).




Posted by hakank at 07:39 EM
Posted to Machine learning/data mining







mars 22, 2004


Bibliomining - data mining for libraries

Detta låter onekligen spännande. Är detta månne något för de svenska biblioteken, eller de kanske redan använder tekniken?

Bibliomining - Data mining for libraries. Termen bibliomining förklaras på följande sätt:



The basic definition is "data mining for libraries."


For years, bibliometrics has been used to track patterns in authorship, citation, etc. Today, there are many more tools available for discovering similar patterns in complex datasets from data mining and statistics. In addition, tools from management science such as Online Analytical Processing (OLAP) can be used to explore the data for patterns.

Therefore, a more complex definition is:

Bibliomining is the combination of data mining, bibliometrics, statistics, and reporting tools used to extract patterns of behavior-based artifacts from library systems.



FAQ:n förklarar - uppenbarligen på förekommen anledning - att det inte är frågan om att hitta individuella låntagare (etc) utan generella mönster.

The goal is _not_ to get to the individual patron level. Instead, the goal is to look for patterns of behavior of either large groups of patrons, staff, or both to help the library managers make better management decisions.


It may be that it's useful to look at the broad demographic groups that a patron is in (like age range), but it would be unethical (and in many cases, impossible or illegal) to look at the individual patron level without the permission of the patron.






Posted by hakank at 11:53 FM
Posted to Machine learning/data mining







januari 23, 2004


Evolving a Stigmergic Self-Organized Data-Mining

Vitorino Ramos, Ajith Abraham: 

Evolving a Stigmergic Self-Organized Data-Mining (PDF).

Abstract:



Self-organizing complex systems typically are comprised of a large number of frequently similar components or events. Through their process, a pattern at the global-level of a system emerges solely from numerous interactions among the lower-level components of the system. Moreover, the rules specifying interactions among the system’s components are executed using only local information, without reference to the global pattern, which, as in many real-world problems is not easily accessible or possible to be found. Stigmergy, a kind of indirect communication and learning by the environment found in social insects is a well know example of self-organization, providing not only vital clues in order to understand how the components can interact to produce a complex pattern, as can pinpoint simple biological non-linear rules and methods to achieve improved artificial intelligent adaptive categorization systems, critical for Data-Mining. On the present work it is our intention to show that a new type of Data-Mining can be designed based on Stigmergic paradigms, taking profit of several natural features of this phenomenon. By hybridizing bio-inspired Swarm Intelligence with Evolutionary Computation we seek for an entire distributed, adaptive, collective and cooperative self-organized Data-Mining. As a real-world / real-time test bed for our proposal, World-Wide-Web Mining will be used. Having that purpose in mind, Web usage Data was collected from the Monash University’s Web site (Australia), with over 7 million hits every week. Results are compared to other recent systems, showing that the system presented is by far promising.


KEYWORDS: Self-organization, Stigmergy, Data-Mining, Linear Genetic Programming, Distributed and Collaborative Filtering.



Läs även Självorganisation och data mining/data analys, samt stigmergy för några av författarnas tidigare arbeten samt länkar om stigmergi.




Posted by hakank at 08:17 FM
Posted to Agentbaserad modellering
 | Machine learning/data mining







januari 13, 2004


Senaste SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining) Explorations

SIGKDD (ACM Special Interest Group on Knowledge Discovery and Data Mining) kommer några gånger per år ut med skriften Explorations. Det senaste (Vol 5, Issue 2) är ett temanummer om Microarray Data Mining. 

Det finns även andra intressanta papers (samtliga PDF-filer), t.ex.

Tom Fawcett: 

In vivo" Spam Filtering:  A Challenge Problem for KDD

Abstract: 

Spam, also known as Unsolicited Commercial Email (UCE), is the bane of email communication. Many data mining researchers have addressed the problem of detecting spam, generally by treating it as a static text classi cation problem. True in vivo spam  ltering has characteristics that make it a rich and challenging domain for data mining. Indeed, real-world datasets with these characteristics are typically di cult to acquire and to share. This paper demonstrates some of these characteristics and argues that researchers should pursue in vivo spam  ltering as an accessible domain for investigating them.



Tom Fawcett är en gammal favorit. Se t.ex. Bibliography on Fraud Detection, What does music look like? samt publications.



S. Sarawagi, S. Srinivasan, V. G. Vinod Vydiswaran, K. Bhudhia:

Resolving citations in a paper repository

Abstract:

In this paper, we describe our process of creating a citation graph from a given repository of physics publications in LATEX format. The task involved a series of information extraction, data cleaning, matching and ranking steps. This paper describes the challenges we faced along the way and the issues involved in resolving them.



Shawndra Hill, Foster Provost:

The Myth of the Double-Blind Review?  Author Identification Using Only Citations

Abstract: 

Prior studies have questioned the degree of anonymity of the double-blind review process for scholarly research articles. For example, one study based on a survey of reviewers concluded that authors often could be identified by reviewers using combination of the author s reference list and the referee s personal background knowledge. For the KDD Cup 2003 competition s  Open Task,  we examined how well various automatic matching techniques could identify authors within the competition s very large archive of research papers. This paper describes the issues surrounding author identification, how these issues motivated our study, and the results we obtained. The best method, based on discriminative self-citations, identified authors correctly 40-45% of the time. One main motivation for doubleblind review is to eliminate bias in favor of well-known authors. However, identification accuracy for authors with substantial publication history is even better (60% accuracy for the top-10% most prolific authors, 85% for authors with 100 or more prior papers).






Posted by hakank at 11:57 FM
Posted to Machine learning/data mining







december 27, 2003


Bloggidentifiering (Blog Identification)

Inpirerad av idéerna i Automatisk identifikation av språk (språkidentifiering), Automatisk bloggning? (Blog Markov) samt Markov av svenska bloggar har jag nu skapat ett program för att automatiskt identifera bloggar: Blog Identification. 

Inparameter till programmet är en URL, t.ex. till en blogg. Sedan jämförs texten (se nedan) med olika bloggar, som jag synnerligen subjektivt valt ut bland några av mina dagligen besökta bloggar samt de flesta av bloggarna som finns med i Internetworld-artiklarna Världens bästa bloggar samt Bästa svenska bloggarna. (Tyvärr kommer min dator inte åt vissa bloggar, t.ex. Rymdimperiet, så jag har inte lyckats skapa en "profil" för dessa bloggar. Sorry.)

Programmet använder en n-gram metrik för att avgöra hur nära en text är de andra texterna, och använder metoden (nästan rakt av) som finns beskrivet i papret N-Gram Based Text Categorization skrivet av William B. Cavnar och John M. Trenkle. Metoden bygger på att man skapar en "profil" av de 300 mest frekventa n-grammen som sedan jämförs med en ny profil skapas från den webbsida som ska identifieras.

För att testa programmet körde jag alla bloggar som input till programmet för att se hur bra de kunde identifieras. Tanken är att en blogg ska vara sig själv närmast. Som man ser i sammanställningen lyckas det rätt bra. Idealet vore att avståndet för en sådan "självtest" är 0 (noll) men av olika skäl når man inte riktigt detta när det webbaserade programmet körs. Efterhand bloggarnas innehåll förändras kommer också resultatet att förändras, och jag vet inte riktigt hur ofta jag kommer att skapa nya profiler att jämföra med.

I slutet av sammanställningen finns en summering av placeringarna i testet. Den som fick lägst totalsumma (i körningen förmiddag 27 December 2003). Det är lite problematiskt att jämföra på detta sätt eftersom språk, ämne, HTML-layout etc påverkar resultatet. Jag vet inte riktigt vilka slutsatser man ska dra av att bajs.se har lägst totalpoäng och The church Of Me har högst.

Det finns några idéer till varianter och utvidgningar som jag nog kommer att testa inom den närmsta framtiden.

METOD

För intresserade beskrivs den metod som används, vilket i princip är en summering av ovan nämnda paper. 

Skapa profil



   läs in texten

  
 strippa bort allt som inte är relevant. (För närvarande tar jag först bort all HTML-kod samt allt som inte är vanliga bokstäver. Detta kan ändras i framtiden.)

  
 skapa profilen: 

    

     skapa en tom hashtabell

    
 för n=1..5:

       

        skapa n-grammen för n och lägg in dessa i hashtabellen 

       


    


  
 sortera hashtabellen i frekvensordning

  
 spara de F (=300) mest frekventa n-grammen i frekvensordning till en fil



Så här kan en profil se ut för hakank.blogg, fast här sparas frekvensen i stället för ranknumret (eftersom ranken helt enkelt är positionen i filen). Möjligen kommer frekvensen att användas i senare versioner av distansmetrik.

Blogg identifiering



 läs in texten som ska identifieras, och skapa en profil (målprofilen) 

  för denna text (se ovan, men spara inte i fil)

 läs in samtliga sparade profiler

 för samtliga sparade profiler:

   

      jämför profilen med målprofilen m.h.a. n-gram-distans/avstånd

  
 spara n-gram-avståndet

  
 vikta avståndet (Jag har delat avståndet med 300, dvs det värde som man använder i n-gram-distans/avstånd när n-grammet G saknas i den jämförda profilen P.)

   


 sortera de erhållna avstånden i stigande ordning, dvs lägst avstånd (=störst likhet) först

 presentera bloggnamn etc i avståndsordning





n-gram distans/likhet

Givet: målprofil (MP) och den profil (P) som ska jämföras



 För samtliga n-gram (G) i MP:

  

   slå upp ranknummer (R1) för G i MP.

  
 slå upp ranknumret (R2) för G i P.

    Om G saknas i P, tilldela R2 ett högt tal (här 300)

  
 räkna ut differensen mellan de två rankvärdena: abs(R1 - R2)

  


 summera samtliga differenser. Detta är n-gram-avståndet mellan MP och P..






Posted by hakank at 12:11 EM
Posted to Blogging
 | Machine learning/data mining
 | Program

| Comments (3)






december 18, 2003


Ny bok: Organizational Data Mining

Organizational Data Mining: Leveraging Enterprise Data Resources for Optimal Performance redigerad av Hamid Nemati och Christopher D. Barko. (Amazon)

Mer info: 

Table of Contents

Preface 

Excerpt (PDF) 



(via KDnuggets.)




Posted by hakank at 12:12 EM
Posted to Machine learning/data mining







december 16, 2003


Recension av Gordon Linoff & Michael Berry: 'Mining the Web'

Bokens fulla titel är Mining the Web: Transforming Customer Data, skriven av Gordon Linoff och Michael Berry.

(Varning för förväxling: Detta är inte samma bok som Soumen Chakrabarti's Mining the Web: Analysis of Hypertext and Semi Structured Data. Denna bok kommer jag förhoppningsvis att recensera inom en snar framtid.)

Linoff och Berrys bok kom ut i slutet av 2001 då en hel del av IT-hysterin hade lagt sig. Attacken i New York den 11 september 2001 nämns i förordet som något som precis hänt, och Enron-skandalen kommenteras i ett avsnitt ("när boken skulle tryckas ...") där Enron ges som ett exempel på en bra affärsidé. Så man kan anta att författarnas bild av e-commerce, den nya ekonomin, one-to-one-marketing etc, förändrades en hel del under skrivandet av boken. Några av de mer affärsinriktade böcker och artiklar som skrevs om den nya ekonomin kring år 2000 är nästan pinsamma att läsa nu när man vet hur det gick. Denna bok lider dock mycket lite av detta, utan ger som värst ett intryck att författarna beskriver ett ämne som de uppriktigt tror på och vill göra mer känt. Naturligtvis är det ett sätt för dem att även indirekt tjäna mer pengar eftersom de själv arbetar som data mining-analyser, med inriktning att att analysera och förbättra ett företags relationer till sina kunder.

Jag köpte denna bok strax efter den kom ut, men den har stått i stort sett oläst i bokhyllan sedan dess. Häromdagen bläddrade jag i den för att leta reda på en uppgift men hittade - i stället - kapitel 8 "Knowing when to Worry: Hazard Functions and Survival Analysis in Marketing". Survival analysis har jag tidigare kikat på i samband med statistisk analys, och blev nyfiken hur det används i samband med marketing. Det var ett intressant kapitel, så jag beslöt att läsa hela boken från pärm till pärm.

Eftersom jag urspungligen köpte boken för titelns "mining" blev jag lite besviken på att det var ganska lite direkt om data mining (se dock nedan), men blev å andra sidan mycket positivt överraskad av de intressanta diskussionerna om olika typer av affärsmodeller som finns eller kan komma att finnas på webben. Det görs även jämförelser mellan de olika modellerna och dess respektive styrkor och svagheter. Även icke-e-affärsmodeller förklaras, t.ex. traditionella snail-postorderföretag. Man går även igenom sådant som att sälja produkter som måste förpackas och sedan distribueras med bil (UPS nämns som exempel), annonsering på webben (t.ex. doubleclick.com) och hur modellerna för sådana verksamheter kan se ut. 

En bra sak är att man oftast lugnt och sansat går igenom de olika aktörerna och diskuterar dels deras roller och dels var de har att tjäna på att vara med i spelet. I avsnittet om marknadsplatser delas olika system in i olika segment som analyseras var för sig. Det finns ett ganska långt avsnitt om eBay och varför de lyckats och varför en icke namn-given konkurrent misslyckades. De företag/sajter som tas upp är för det mesta mycket kända, även om det i mer avgränsade domäner förekommer namn som var okända för mig. 

Det var skoj att läsa författarnas diskussion och kritik av Napster och liknande modeller, där de också skisserar en mer kommersiellt gångbar lösning. Hela detta kapitel, som ramades in av hur man ska sälja "produktlöst" på nätet (t.ex. musik eller virtuella tjänster), var enligt min mening ett av de mest intressanta.

De avslutande kapitlen är mer tekniska än de föregående, t.ex. det ovan nämnda kapitlet där man använder survival analysis för att lista ut hur trogna (eller otrogna) kunderna är. Andra kapitel diskuterar "cohort analysis" och kalkylering av kundvärde. Det finns t.o.m. lite SQL-kod i några av dessa avsnitt. I boken blandas alltså både översiktliga diskussionen och tekniska detaljer. I ett av de första kapitlen beskrivs hur cookies fungerar för att man ska använda dessa för avancerad annonsering eller up/down/cross-sell.

Författarna har gjort en hel del data mining-analyser och delar med sig av sin erfarenheter med en massa tips och varningar genom hela boken. Det sista kapitlet innehåller en fallstudie där man bland annat nämner en del fallgropar i sådana projekt. Det är alltså inte bara en dans på rosor, utan även törnen i form av t.ex. dålig data eller "politik" i organisationerna.

Beskrivningarna av själva data mining-teknikerna är lite lustigt insprängda i texten om affärsmodellerna, och det kan ge ett lite rörigt intryck. Trots detta tycker jag att boken lyckas göra kopplingarna mellan marknad och teknik på ett mestadels bra sätt. Det är en stor fördel att även läsa om en teknik sett i ett mer realistiskt sammanhang än bara algoritmerna rakt upp och ned (som i många av de mer tekniskt inklinerade böckerna om data mining). Några höjdpunkter här är deras genomgång av rekommendationssystem samt hur man skapar olika kundsegment med hjälp av klustringstekniker. I samband med detta kan nämnas att det är mycket få matematiska formler i boken, och det blir tyvärr lite konstigt när de förklarar statistiska begrepp som standardavvikelse med en "pratfversion".

För en bättre och mer systematisk genomgång av teknikerna, men fortfarande med ett marknadsperspektiv, skulle jag dock hellre vilja rekommendera författarnas tidigare bok Data Mining Techniques: For Marketing, Sales, and Customer Support  (från 1997 så den är lite gammal med definitivt läsbar). Där är förklaras mer i detalj hur man bör bedriva data mining-projekt. De har också skrivit Mastering Data Mining: The Art and Science of Customer Relationship Management. Även den beskriver tekniker och metoder, men dess främsta fördel är de många fallstudierna.

"Mining the Web" innehåller mycket intressant information men tyvärr ges alldeles för få referenser till andra böcker och artiklar, och det finns naturligtvis ingen litteraturlista. Jag hittade sammanlagt 4 böcker som refererades i boken, varav två var till författarnas egna böcker som nämndes ovan. De övriga två böckerna var Dorian Pyles utmärkta Data Preparation for Data Mining vilken rekommenderas, samt The Loyality Effect: The Hidden Force Behind Growth, Profits, and Lasting Value (som jag har, men inte läst). På författarnas sajt Data Miners finns det en sida med Suggested books. 



Slutord:

För mig var den stora behållningen av denna bok den utförliga genomgången av olika typer av affärsmodeller där man kan utnyttja webbens speciella förutsättningar. Både existerande system och funderingar kring framtida system diskuteras. Beskrivningarna av data mining-teknikerna gav mig inte så något nytt, mer än möjligen att se dem i konkreta affärssammanhang och med mer "kött på benen".  Det antyds att målgruppen för boken är blivande databrytare (data miners) men jag anser att det är alldeles för lite hands on-information för att denna bok ensam ska räcka till för detta.



Se även referenserna i slutet på Recension av Jiawei Han & Micheline Kamber: 'Data Mining - Concepts and Techniques'.




Posted by hakank at 01:56 FM
Posted to Machine learning/data mining







december 05, 2003


Recension av Jiawei Han & Micheline Kamber: 'Data Mining - Concepts and Techniques'

Denna bok läste jag för ett tag sedan, men kom på att det vore roligt att skriva en recension, speciellt eftersom jag tyckte om boken.

Boken Data Mining - Concepts and Techniques (Amazonlänk) av Jiawei Han och Micheline Kamber är, till skillnad från många andra introducerande böcker om Data Mining, skriven till stor del för en rätt speciell teknisk målgrupp: utvecklare och forskare i databasindustrin. Detta innebär inte att man måste vara databaskonstruktör för att förstå boken, däremot bör man inte banga för begrepp som "komplexitet", "curse of dimensionality", "OLAP" eller "full scan".  Det är få rena matematiska formler eller resonemang i boken, däremot används en hel del pseudokod för att beskriva algoritmerna.

Boken är skriven för att vara "self contained" genom att kapitlen ska gå att läsa oberoende av andra. En konsekvens av detta är att vissa begrepp förklaras flera gånger, vilket troligen ska ses som en fördel. Det blir trots detta en del korsreferenser för de viktiga begreppen (såsom "OLAP", "decision tree", "Apriori" etc), så min personliga rekommendation är att börja från början, och i alla fall skumma igenom det som inte känns så viktigt. Trots bokens cirka 500 sidor huvudtext (det finns några appendix samt en omfattande litteraturlista) går det rätt snabbt att läsa dem.

De första kapitlen (2 - 4) handlar om olika typer av förutsättningar för bra data mining: OLAP, data warehouse och förprocessering ("tvättning") av data. När jag först läste kapitlet om OLAP blev jag lite förvånad. Även om det är bra skrivet, så förstod jag inte riktigt poängen med det, men efter hand insåg jag att det beskriver en typ av beslutsstödssystem som är mer vanligt förekommande än data mining, och som i någon mån kan ses som en "base level" för den typ av kunskap man vill åstadkomma med data mining. Det är också en mjukstart som introducerar olika begrepp som sedan används. Kapitlen om data warehouse och datatvättning är viktiga, eftersom dessa två områden oftast är nödvändiga för lyckade projekt med data mining av mycket stora dataanhopningar.

Det är en herrans massa tekniker (algoritmer) som gås igenom i boken. De områden som behandlas är:

 - associationsregler, t.ex. Apriori och dess olika varianter.

 - klassifikation och prediktion, beslutsträd, neurala nätverk, Bayesiaska klassifikatörer etc

 - klusteranalys, många olika typer av klustertekniker presenteras

 - komplexa datatyper (t.ex. spatial data, tidsserier, text samt data på och via webben)

Varje område har ett eget kapitel och beskriver många algoritmer samt deras varianter och utvidgningar. Många tekniker kompletteras med små exempel på hur algoritmen fungerar. Man använder i stort sett samma data(bas) genomgående för detta, vilket är bra. Även om databasen förklaras i början av boken skulle det vara trevligt om den fanns online så att man själv kunde leka lite.

Jag ger extrapoäng för att man beskriver teknikernas fördelar och nackdelar, t.ex. om den är skalbar (dvs passar för data mining av mycket stora databaser) samt för vilka områden det behövs mer forskning.

Det är bra förklaringar av teknikerna. För vissa tekniker/algoritmer, t.ex. artificiella neurala nätverk, förklaras de kortfattat och hänvisas sedan till annan litteratur. Troligen är det ett klokt beslut för att boken inte ska svälla till en ohanterlig (och väldigt dyr) klump. Jag kunde dock inte hitta något ställe där författarna uttryckligen berättar om sina urvalskriterier om vilka eller hur mycket de beskriver om metoderna.

En intressant sak är att man diskuterar begreppshierarkier, dvs begrepp på olika nivåer, t.ex. begreppen gata, stad, landskap, land.  På många olika ställen förklaras hur en teknik ska användas (eller ändras) för att hantera denna typ av hierarki.

Bokens avslutas med diskussioner om trender, framtiden och - framförallt - möjliga sociala effekter av data mining. Man pratar även om hur man ska göra för att sälja in data mining till fler än de existerande användarna.

I den utvecklingsmodell med aktörerna:

 - innovators

 - early adopters

   CHASM ("avgrund")

 - early majority

 - late majority

 - laggards

befinner sig data mining enligt författarna i avgrunds-området, där uppfinnare, tekniker med flera försöker att sälja in en produkt/ett koncept till en grupp 'early majorities'. Denna grupp är troligen inte är så mottagliga för den typ av säljargument som hittills framförts, så något måste göras. Det är troligen bara tekniktöntar som jag själv som fascineras av (eller ens bryr sig om) algoritmerna bakom Amazon rekommenderarsystem eller googles sätt att ranka sajter. Däremot är det "allas angelägenhet" att (dvs inte hur) de fungerar på ett bra sätt. Även om det finns böcker som förklarar data mining utifrån sälj/marknadsperspektiv (t.ex. de skrivna av Michael Berry och Gordon Linoff) uppfattar jag att det fortfarande är teknikdominerat säljprat som dominerar.

Som en lösning föreslås "invisible data mining", som innebär att användarna inte ens ska märka eller veta om att det finns en avancerad teknik  (data mining) "under huven". Min tolkning av detta är att man helt enkelt försöker dölja begreppet "data mining", som numera samtidigt representerar en hype och har negativa konnotationer (samkörningar, intrång i den personliga integriteten). I stället för att sälja med hjälp av en teknik bör man alltså i stället presentera de resultat man kan få fram. Det låter som ett vettigt förslag.

(I boken The Tipping Point, av Malcolm Gladwell, beskrivs andra och generella sätt hur man ska komma förbi avgrunden. Se t.ex. Recension av Malcolm Gladwell "The Tipping Point".)

Varje kapitel avslutas med sammanfattning, övningar samt en genomgång av relevant litteratur; huvudtexten är nästan helt fri från referenser. (Det är när jag sitter och läser sådana referensidor som jag önskar att det fanns böcker som man kan surfa med för att läsa de många intressanta papers som diskuteras. Det räcker faktiskt inte med datorer som man kan använda för att läsa elektroniska dokument eller böcker.)

En liten stilistisk småsak som jag irriterade mig på i boken är att ett avsnitt börjar oftast med en fråga (i kursiv stil), varpå den genast besvaras kortfattat och svaret använder begrepp som först definieras i nästa stycke. Man kan se det som en form av introduktion av begreppet, men jag blev lite störd av det. Efter hand lärde jag mig dock att tycka om detta grepp eftersom det utgjorde ett litet avbräck (andningspaus) i de tekniska diskussionerna.

Slutomdöme

Jag tror inte jag skulle rekommendera "Data Mining - Concepts and Techniques" som första bok i data mining. Däremot som andra eller tredje bok och nog endast för de som vill antingen utveckla sådana system eller är välmotiverade att gå igenom ganska detaljerade algoritmer. Själv tyckte jag mycket om boken, om inte annat för att den gav en syn på data mining som är ganska ovanlig jämfört med övriga böcker jag läst. Boken är välskriven och trots tonvikten på tekniska förklaringar var den lättläst. Visserligen var det några småsaker (av ren stilitisk natur) som jag retade mig på/inte förstod poängen med, men de var snabbt förlåtna.



Vidare referenser

Bokens egen sajt innehåller errata, Powerpointfiler, bilder som finns i boken samt några referenser till kursupplägg. 

Jiawei Hans publikationer.

Här finns en kurs där man använder boken. Det finns också föreläsningar i PDF-format, samt några av de introducerande papers som refereras i boken.

Mer generellt om data mining:

KDnuggets är en av de bästa sajterna för att hitta resurser inom data mining.



Min egen Data Mining, Machine Learning etc innehåller bland annat några andra av mina recensioner av böcker inom data mining-området. Se även Data Mining - En liten presentation med vidhäftande referenser om några av de system och böcker som jag själv har använt/läst. 




Posted by hakank at 02:50 EM
Posted to Machine learning/data mining







november 27, 2003


Data mining-lista: Mi_Li_Wo

Mi_Li_Wo (Mining linking the World) är en lite layback modererad Yahoo-mailinglista om data mining. Efter dess skapande i augusti är det nu 33 medlemmar och det har blivit cirka 10 mail i månaden, så det är en lugn lista.

Från beskrivningen:

The term of Data Mining now shows in finance, marketing research, media, education, hospital, government, biology and so on. Different methodology solves different types of problems. Distinct mining ideas apply in distinct fields. This extensive domain, Data mining, is full of diversification and interest. As a result, this Mi_Li_Wo Discussion Group is formed for people all over the world who fall in love with data mining or already couldn't be energetic without it.


The Mi_Li_Wo Discussion Group would like to share any kind of interesting ideas with different people and exchange experiences with each other. Consequently, the emphasis is on the applications of modern modeling methodology and techniques from Statistics, Data Mining, and Machine Learning and on the valuable experience from data analysis. Participants could talk about any topic about data mining, such as "Data Quality, Data Pre-Processing, Database Marketing, Extensible Markup Language (XML), Business Intelligent, Web Knowledge Discovery" and new trends. 






Posted by hakank at 05:18 EM
Posted to Machine learning/data mining

| Comments (1)






november 25, 2003


Senaste KDnuggets

Den senaste KDnuggets innehåller några godbitar:

Poll Results: SVM, Web mining usage grows; Genetic algorithms, Associations decline, där man jämför vilka tekniker som nu används av kdnugget-besökarna med vilka som användes för ett år sedan. Titeln berättar de intressantaste förändringarna. Se även sammanställningen från årets undersökning.

XLMiner: Data Mining in Excel. Se XLMiners sida. 

(Möjligen intressant är att Resampling Stats Inc., som skapad XLMiner, även gjort det system, Resampling Stats, jag bland annat skriver om i Lite om resampling, simulering, sannolikhetsproblem etc..)

European Network of Excellence Text Mining Study. Rapporten som beskrivs är Network of Excellence in Text Mining and its Applications in Statistics (PDF).

InfoSpace uses Search Clustering from Vivisimo

Gartner sees IT rebound; data mining, real-time analytics among skills in demand




Posted by hakank at 12:30 EM
Posted to Machine learning/data mining







november 12, 2003


Weka version 3.4

Data mining/machine learning-systemet Weka har kommit med en ny stabil version, 3.4 (länk till sourceforge).

Några av de trevligaste nyheterna sedan förra versionen (3.3.6) är möjligheten att visualisera Bayesianska Nätverk (Bayes nets, kräver Java 1.4) samt att man kan se en scatterplot av datamängden.  Det finns även lite uppdateringar i KnowledgeFlow, men de får jag kolla in så småningon. 

För den som är intresserad finns en CHANGELOG med samtliga förändringar.

Se även min Weka-sida.




Posted by hakank at 09:37 FM
Posted to Machine learning/data mining







november 08, 2003


Machine learning och musikstilar

Ett intressant IEEE Computer Magazine-paper: Using Machine-Learning Methods for Musical Style Modeling av Shlomo Dubnov, Gerard Assayag, Olivier Lartillot, Gill Bejerano (PDF).



The ability to construct a musical theory from examples presents a great intellectual challenge that, if successfully met, could foster a range of new creative applications. Inspired by this challenge, we sought to apply machine-learning methods to the problem of musical style modeling. Our work so far has produced examples of musical generation and applications to a computer-aided composition system.


Machine learning consists of deriving a mathematical model, such as a set of stochastic rules, from a set of musical examples. The act of musical composition involves a highly structured mental process. Although it is complex and difficult to formalize, it is clearly far from being a random activity.

Our research seeks to capture some of the regularity apparent in the composition process by using statistical and information-theoretic tools to analyze musical pieces. The resulting models can be used for inference and prediction and, to a certain extent, to generate new works that imitate the style of the great master






Posted by hakank at 05:39 EM
Posted to Machine learning/data mining







oktober 07, 2003


Självorganisation och data mining/data analys, samt stigmergy

Här är två intressanta artiklar som kombinerar självorganisation och data mining. Jag har ännu bara bläddrat igenom dem. Sist finns lite länkar om stigmergi (stigmergy).



Båda artiklarna är skriva av  Vitorino Ramos och Ajith Abraham.



Web Usage Mining Using Artificial Ant Colony Clustering and Genetic Programming.

Paper.

Abstract

The rapid e-commerce growth has made both business community and customers face a new situation. Due to intense competition on one hand and the customer's option to choose from several alternatives business community has realized the necessity of intelligent marketing strategies and relationship management. Web usage mining attempts to discover useful knowledge from the secondary data obtained from the interactions of the users with the Web. Web usage mining has become very critical for effective Web site management, creating adaptive Web sites, business and support services, personalization, network traffic flow analysis and so on. The study of ant colonies behavior and their self-organizing capabilities is of interest to knowledge retrieval/management and decision support systems sciences, because it provides models of distributed adaptive organization, which are useful to solve difficult optimization, classification, and distributed control problems, among others. In this paper, we propose an ant clustering algorithm to discover Web usage patterns (data clusters) and a linear genetic programming approach to analyze the visitor trends. Empirical results clearly shows that ant colony clustering performs well when compared to a self-organizing map (for clustering Web usage patterns) even though the performance accuracy is not that efficient when comparared to evolutionary-fuzzy clustering (i-miner) approach.


KEYWORDS: Web Usage Mining, Ant Systems, Stigmergy, Data-Mining, Linear Genetic Programming.





Swarms on Continuous Data

Paper

Abstract

While being it extremely important, many Exploratory Data Analysis (EDA) systems have the inhability to perform classification and visualization in a continuous basis or to self-organize new data-items into the older ones (evenmore into new labels if necessary), which can be crucial in KDD - Knowledge Discovery, Retrieval and Data Mining Systems (interactive and online forms of Web Applications are just one example). This disadvantge is also present in more recent approaches using Self-Organizing Maps. On the present work, and exploiting past sucesses in recently proposed Stigmergic Ant Systems a robust online classifier is presented, which produces class decisions on a continuous stream data, allowing for continuous mappings. Results show that increasingly better results are achieved, as demonstraded by other authors in different areas.


KEYWORDS: Ant Systems, Stigmergy, Data-Mining, Exploratory Data Analysis, Image Retrieval, Continuous Classification.





En liten aside

Stigmergi är ett intressant begrepp.

På sidan 23 i Self-Organization in Biological Systems (Amazon-länk) står det:



In situations where many individuals contribute to a collective effort, such a colony of termites building a nest, stimuli provided by the emerging structure itself can be a rich source of information for the individual. 

... 

In other words, information from the local environment and work-in-progress can guide further activity. As a structure such a termite mound develops, the state of the building continually provide new information for the builders.


In the study of social insects, the term stigmergy (...) has been used

to describe such recursive building activity.



Begreppet stigmergy skapades av P-P Grassé. I boken är det dock endast franska artiklar som refereras.

Man kan läsa mer t.ex. på följande sidor:

Stigmergy and the World-Wide Web

www.stigmergicsystems.com

Stigmergy, Self-Organization, and Sorting in Collective Robotics (PDF)

Swarm Intelligence - varför myror är intressanta av Robert Johansson och Mia Living.

Se även Forskning och Framsteg: Temanummer om självorganisation och dess referenser.




Posted by hakank at 11:15 EM
Posted to Komplexitet/emergens
 | Machine learning/data mining







september 04, 2003


Senaste KDnuggets

Senaste nyhetsbrevet från KDnuggets har kommit. 

Ett axplock:



   KDD Cup 2003 Winners. Se även KDD Cup 2003.

   
 Bayesian filtering against spam? Se även Steven J. Vaughan-Nichols artikel Saving Private E-mail.






Posted by hakank at 08:13 EM
Posted to Machine learning/data mining







september 01, 2003


Tillägg till "Data mining, machine learning och emergens"

Äsch, jag glömde ju bort att nämna följande bok, trots att jag lagt fram den och allt:

Stuart J. Russell, Peter Norvig: Artificial Intelligence: A Modern Approach

Innehåller "allt" inom ämnet artificiell intelligens. Förutom (machine) learning och olika sök-/optimeringsalgoritmer (med ett kort avsnitt om genetiska algoritmer) går författarna igenom tekniker för representation och bearbetning av kunskap, planering, teoremlösning etc.Allt mycket fascinerande!  Det är en tjock bok som är en höjdare som översikt.

Se även bokens sajt.




Posted by hakank at 08:09 EM
Posted to Machine learning/data mining









Data mining, machine learning och emergens

Sedan ett antal (4-5) år har jag varit intresserad av data mining och machine learning, och läst en hel del böcker om den mer statistiska approachen, artificiella neurala nätverk, genetiska algoritmer etc, men inte förrän på sistone upptäckt kopplingen till emergensteorin.

"Data mining" och "machine learning" betecknar olika saker men används ofta för samma sak, nämligen att utifrån en datamängd (eller system som genererar data) lista ut något om den process (etc) som genererat datan. Machine learning betecknar också forskning kring hur man skapar system som lär sig själva via input, t.ex. en bil som styr givet input till ett neuralt nätverk, backgammon-spelande system (via neurala nätverk/genetiska algoritmer), vilket är något som är tätare kopplat till emergensteorin än ren dataanalys.



En av de orsaker till att jag är fascinerad av data mining/machine learning (och statistisk analys) är just att man med hjälp av data kan skapa en "bild" av ett "system" för att se vad som döljer sig bakom, t.ex. lära ett begrepp med hjälp av exempel, lista ut köpvanor hos de som köper saker, se vilka attribut (faktorer) som är viktigast bland en stor mängd olika attribut etc etc. 

Det verkar nästan magiskt att man kan göra sådant. Algoritmerna är relativt enkla så magin försvinner kanske lite grand när man läser mer i ämnet. Å andra sidan är jag fortfarande fascinerad när jag ser en duktig trollkonstnär även om jag vet hur denne gör sina tricks.



När jag nu har börjat läsa mer om komplexa adaptiva system utifrån emergensperspektivet har jag upptäckt viktiga länkar mellan neurala nätverk, genetiska algoritmer, och andra (själv)lärande system till emergensteorin.

Speciellt genetiska algoritmer skapades (i alla fall om man får tro Mitchell Waldrop i hans Complexity) för att undersöka teorin om hur sådana emergenta fenomen uppstår, liksom neurala nätverk skapades för att studera hur det mänskliga medvetandet fungerar. Andra tekniker, t.ex. Quinlans beslutsträd (se slutet på min anteckning JMLR Special Issue on Inductive Logic Programming) skapades bland annat för att förstå hur vi kan lära oss begrepp induktivt med hjälp av data, vilket kan ses som ett emergent fenomen eller åtminstone kopplat till detta.

Böckerna jag tidigare läst tar nämligen inte upp den emergenta sidan av forskningen utan behandlar i stort sett endast den tekniska delen, dvs teorin bakom (matematiken och/eller algoritmerna) eller hur man implementerar sådana system. Möjligen står det lite historiskt i inledningarna av böckerna, men alltså inget jag har "tänt till" på. Trist att jag inte upptäckt/insett detta tidigare!

Genetiska algoritmer har jag i princip sett endast som ett sätt att optimera lösningar, även om det har lockat lite med den biologiska kopplingen. Cellulära automater, som jag bland annat läste en del om när jag pluggade datalogi, sågs som teoretiska beräkningssystem, men inte som något emergent, även om jag tillbringade ett rätt stort antal timmar med Game of Life-simuleringar. Och Hofstadter skrev i sin Gödel Escher Bach-bok en hel del om emergenta fenomen.



Den första gången jag "nysåg" t.ex. genetiska algoritmer var i Duncan Watts bok Small Worlds, där han skrev om dem på ett sådant sätt att jag började bli intresserad igen, men eftersom jag inte ville avvika från min social network analysis/complex networks-väg så ignorerade jag denna "irrfärd".

Jag inser att jag - nu i min feberyra - möjligen överskattar kopplingarna. Men, hur som helst, data mining/machine learning är ett fascinerande område. (Man kanske inte ska blogga feberanfrätt i seriösare ämnen, liksom man inte bör blogga intoxikerad då...)



Böcker om data mining/machine learning

Här är några av de böcker jag läst om data mining/machine learning, beskrivet från den "tekniska sidan". Notera att dessa böcker alltså inte tar upp emergensfenomenet utan diskuterar en massa tekniker för att analysera datamängder eller lösa optimeringsproblem etc.



Tom Mitchell: Machine Learning

Är nog fortfarande den bästa introduktionsboken, även om den har några år 

på nacken. Har ett kapitel om genetiska algoritmer som optimeringsmetod, liksom ett kapitel om neurala nätverk.



David J. Hand, Heikki Mannila, Padhraic Smyth: Principles of Data Mining

En inträngande genomgång om en massa olika tekniker att analysera data.



Richard O. Duda, Peter E. Hart, David G. Stork: Pattern Classification

En annan klassiker. Teknisk.



Jiawei Han, Micheline Kamber: Data Mining: Concepts and Techniques. 

Behandlar ämnet utifrån ett databasperspektiv.



 Ian H. Witten, Eibe Frank: Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations.

Detta är en av mina biblar eftersom den beskriver mitt favorit-data mining-system (Weka). Den är inte lika teknisk som ovanstående böcker och behandlar inte allt som de gör. Däremot förklarar den de saker den förklarar på ett föredömligt sätt.



Michael J. A. Berry, Gordon Linoff:Data Mining Techniques For Marketing, Sales, and Customer Support

Lite gammal (1997) men behandlar data mining på ett konkret sätt, utifrån marknadsdata. Målgruppen är managementpersoner och kan läsas som en introduktion till data mining. Deras Mastering Data Mining: The Art and Science of Customer Relationship Management (från 2000) tyckte jag däremot inte alls lika bra om.



Se även mina bokrecensioner: Recension av Jesus Menas "Data Mining Your Website" och Recension av 'Building Data Mining Applications for CRM'.



Några lite mer lättsamma böcker:

Thomas A. Bass Predictors.

En underbar bok som berättar i en romanliknande form om några av hjältarna från både kaosforskningen och - visar det sig - emergensforskningen, nämligen Doyne Farmer och Norman Packard, som startar ett företag för att bli stenrika på börsen. De använder främst genetiska algoritmer och artificiella neurala nätverk för detta. Det står mycket lite om det tekniska men är en fascinerande resa.

Se även A few Prediction Company references.



David B. Fogel:

Blondie24

Självbiografi som berättar om hur författaren skapar ett Checkers-system med genetiska algoritmer och artificiella neurala nätverk. När jag nu tänker tillbaka på vad som står i boken är detta ett tydligt exempel på en "emergensapproach": författaren försöker att skapa en "riktigt" AI-system som utifrån nästan ingenting alls lär sig spelet och att spela riktigt bra. "Riktigt AI-system" i jämförelse med IBM:s schackmaskiner som "bara" är number crunching.



Själv har jag nu Prey av Michael Crichton som godnattlitteratur.

En vän till mig rekommenderade den och när han berättade att boken hade fyra sidors litteraturreferens om svärmintelligens, agent-baserad programmering/modellering samt Thomas Schellings 'Micromotives and Macrobehavior' var jag bara tvungen att köpa den. Speciellt långt har jag ännu inte kommit.




Posted by hakank at 07:26 EM
Posted to Agentbaserad modellering
 | Böcker
 | Dynamiska system
 | Komplexitet/emergens
 | Machine learning/data mining







augusti 19, 2003


KDnuggets

Senaste KDnuggets kommen. Se KDnuggets nyhetsamling om data mining/machine learning för lite mer info om KDnuggets.

Några av kortnyheterna:


   Yahoo Selects Island Data for real-time analysis of textual customer feedback

  
 6-degrees of separation in email? Innehåller en referens till New York Times-artikeln Degrees of Separation Are Likely More Than 6, Especially in E-Mail Age som innehåller lite kritiska röster om Six Degrees-projektet. Se även min anteckning för någon vecka sedan Six degrees-projektet avslutat.

 





Posted by hakank at 10:27 FM
Posted to Machine learning/data mining







augusti 18, 2003


JMLR Special Issue on Inductive Logic Programming

Den senaste Journal of Machine Learning Research (JMLR) innehåller papers om Inductive Logic Programming (ILP).  Dessa papers finns här.

I ILP utnyttjar man logikprogrammering (tänk Prolog e.dyl.) för att skapa maskininlärningssystem (machine learning). Som input till ett sådant system har man ett antal exempel, varpå systemet genererar kod för att "täcka" dessa exempel.

En av de främsta ILP-forskarna är Stephen Muggleton. Det rekommenderas att se hans publikationer och system (se nedan).  Dokumentet CProgol4.4: a tutorial introduction (.ps) är nog en bra introduktion. 

Böcker

Den enda bok jag har och läst om ILP är

Inductive Logic Programming: From Machine Learning to Software Engineering.

Det finns en onlinebok om ILP (från 1994): Inductive Logic Programming: Techniques and Applications av  N. Lavrac och S. Dzeroski som kan vara värd att kika på. 

System

När jag kollade in ILP för ett antal år sedan använde jag mest Progol (notera att det finns flera olika versioner, jag använde version 4.4 och 5.0), men även golem samt ffoil2 (obs! en sh-fil) av Ross Quinlan. Dessa system använder Prolog som resultat-språk, dvs genererar Prolog-kod.

En aside

Ross Quinlan är för övrigt en av pionjärerna inom fältet machine learning (som naturligtvis är relaterat till ILP). Källkod till hans C4.5-program finns här (tar.gz-fil). Numera använder jag dock systemet Weka (skrivet i Java) till allt sådant. C4.5-algoritmen finns implementerad i Weka under namn J48. Quinlans bok C4.5: Programs for Machine Learning är en klassiker inom machine learning.




Posted by hakank at 09:22 EM
Posted to Machine learning/data mining







augusti 15, 2003


Maskinell analys av argument

Natureartikeln Graphs test official reports berättar om en teknik att analysera resonemang i texter, t.ex. rapporter om olyckor.

A new analytical technique tests the conclusions and distils the arguments of complex documents. Designed to scour accident-inquiry reports, it could probe other long, controversial accounts, such as the UK government's Iraq dossier, or the US government's report on the terrorist attacks on 11 September 2001.


"This is a way to check that things aren't being oversimplified or hidden," says its developer, Chris Johnson, an accident analyst at the University of Glasgow, UK. The approach reveals whether or not a report's content support its conclusions.

Artikeln som refereras är Newspaper and online news reporting of major accidents: Concorde AFR 4590 in The Times, The Sun and BBC Online (PDF). Se även Chris Johnsons hemsida.

I artikeln nämns också  Peter Ladkin som forskat kring liknande problem. Se även projektet The Causal Systems Analysis and WB-Analysis (WB = Why-Because).

Detta verkar intressant.




Posted by hakank at 09:46 FM
Posted to Machine learning/data mining







augusti 07, 2003


KDnuggets nyhetsamling om data mining/machine learning

Senaste numret av KDnuggets nyhetssamling har kommit.

KDnuggets är en av mina favoritsajter vad gäller data mining och machine learning. Varannan vecka kommer nyhetbladet (det som nu är ute) som presenterar vad som hänt inom området, t.ex. nya böcker, system, konferenser, kurser samt övriga nyheter (små som stora).

System, såväl kommersiella som open source (etc), finns kategoriserade under Software, böcker under Publications, speciellt Books.  Det finns många andra länksamlingar, t.ex. Web sites relevant for Data Mining och Solutions using Data Mining for. Tyvärr är en flera av dessa sidor belamrade med reklam.

Bland denna varannan-veckas nyheter:


   Senate cuts off TIA funding; new proposal will effectively "ban" Federal data mining 

 
 NeuralWorks Predict again named a finalist in Scientific Computing Magazines Readers Choice Awards

  
 Amazon Sued for Patent Infringement over Personalization

  
 Relationship data mining or Six Degrees of Exploitation?

Detta är en kort resume om Wall Stree Journal-artikeln som jag nämnde häromdagen. Tyvärr sägs det inget nytt. Förhoppningsvis kommer det lite mer röster om dessa fascinerande system snart.

. 

Jag har skrivit lite mer om machine learning / data mining, t.ex. en kortfattad presentation skriven för ett föredrag jag höll för något år sedan. Presentationen är riktad främst till utvecklare och utgår från det alldeles underbara Java-systemet Weka . Några relevanta referenser finns på  Mer info. 

Andra áv mina data mining-saker/-experiment finns via Data Mining, Machine Learning etc.




Posted by hakank at 09:30 FM
Posted to Machine learning/data mining

| Comments (1)






juli 28, 2003


Information Immune System

Här finns en hel del intressanta papers om olika typer av datasäkerhet, t.ex. intrusion detection, email och spridning av virus, artificiella immunsystem. 

Kännetecknande är att de alla har någon koppling till immunsystemet eller levande organismer att göra. En kort presentation av projektet finns på Computer Immune Systems.

Några titlar i högen



 Immunology as information processing

 Email Networks and the Spread of Computer Viruses, skriven bl.a. av den allestädesnärvarande Mark Newman.

 A sense of self for Unix processes 



Det finns även lite program att ladda ner.




Posted by hakank at 11:47 EM
Posted to Machine learning/data mining







juli 22, 2003


JMLR - Journal of Machine Learning Research

 The Journal of Machine Learning Research  (JMLR) har nu ett specialnummer om The Fusion of Domain Knowledge with Data for Decision Support.  Gå till JMLR, klicka på Papers, rulla ner lite och välj under "Special Issues".  

Jag rekommenderar även specialnumren om Variable and Feature Selection och Machine Learning Methods for Text and Images





Posted by hakank at 07:39 FM
Posted to Machine learning/data mining







juli 18, 2003


Könsbestämning av text

I artikeln Computer that can tell the write sex just by reading berättas om ett program som automatiskt identifierar (med 80% säkerhet) om en text är skriven av en man eller kvinna.

A computer programme has been developed which can distinguish our sex simply by looking at the way we write.


But rather than looking at words for their macho posturing or feminine sense, the Israeli-developed programme has confirmed what many scholars already thought - women focus on people while men prefer to concentrate on things. 



Skaparen av programmet är Moshe Koppel. Paper som refereras: Automatically categorizing written texts by author gender (PDF) och  Gender, Genre, and Writing Style in Formal Written Texts (PDF).



Se även det urval av papers som Koppel gjort för sin seminarieserie om machine learning och textklassifikation Machine Learning Seminar  2002.  

Notera att åtminstone en länk strular. Ladda ner Naive (Bayes) at Forty: The Independence på Citeseer .  




Posted by hakank at 09:14 FM
Posted to Machine learning/data mining







juli 17, 2003


Bok: "Modeling the Internet and the Web" 

Boken Modeling the Internet and the Web Probabilistic Methods and Algorithms verkar vara intressant. Den borde man (också) läsa.

Pierre Baldi har även skrivit Bioinformatics: The Machine Learning Approach, Second Edition (Adaptive Computation and Machine Learning), om maskininlärning i bioinformatik. En trevlig sak.




Posted by hakank at 11:07 FM
Posted to Böcker
 | Machine learning/data mining









Data mining-forskare försvarar sitt fält

I ett öppet brev "Data Mining" Is NOT Against Civil Liberties (PDF-fil) förklarar data mining-forskare i en av de mest ansedda sammanslutningarna (ACM Special Interest Group on Knowledge, Discovery and Data Mining, SIGKDD) sin inställning till data mining och individens rättigheter, speciellt med anledning av diskussionerna kring det amerikanska TIA-projektet (numera uttytt "Terrorism Information Awareness" tidigare "Total Information Awareness").

The main goal of this letter is to help differentiate the data mining technology from data collection and specific applications in specific domains. We believe that the most signif icant sources of danger to civil liberties are the unnecessary and unauthorized collection of data, and misuse of collected data, including the use of wrong data, the use of data in unauthorized ways, the wrong and unauthorized dissemination of data, and reaching wrong conclusions from data.

We are concerned that recent newsmedia reports and a recent press release from the US ACM Public Policy Committee (see http://www.acm.org/usacm/Letters/tia_final.html) may have contributed to this misimpression. We are concerned that the proposed S. 188 Data Mining Moratorium Act of 2003 (see http://feingold.senate.gov/~feingold/releases/03/01/2003116745.html ) does not reflect a sound understanding of data mining science, technology or applications. Finally, we are concerned that the public debate has not distinguished between the research and development of data mining technology and the application and use of these technologies by specific agencies on specific data for specific purposes.

...Data mining is but one of many technologies that may be used in these projects. Other technologies include database management, online analytical processing, speech recognition, image (face, iris, fingerprint, etc.) recognition, natural language understanding and translation, data warehousing, data integration, information retrieval, etc. Does it make sense to attempt to outlaw any or all of these?

I notisen Can Total Information Awareness work or how can you separate bad coins from good ones? skrivs lite om de sannolikhetsteoretiska problemen som finns i TIA. Se även The Homeland Security Act and the proposed DARPA "Total Information Awareness" (TIA) program.




Posted by hakank at 10:47 FM
Posted to Machine learning/data mining







juli 10, 2003


Farliga rekommenderare

Jag är en sucker för "rekommenderare" (recommender systems), och använder ofta t.ex. Amazons bokrekommenderare, både den generella "Customers who bought this item (se t.ex. en av mina favoritböcker i ämnet data mining), och den imponerande personliga rekommenderaren (som dock kräver inloggning).  Även bokus har ett rekommenderarsystem, men det är inte riktigt lika imponerande som Amazons.



För ett tag sedan rapporterades om en undersökning, 

Recommenders can skew results ,  om tillförlitligheten i liknande system och hur de kan påverka användarna av dem. Några citat: 



Displaying a prediction introduces bias, said Joseph Konstan, an associate professor of computer science and engineering at the University of Minnesota. "Lying by [skewing rankings] higher or lower... biases the subsequent rating in that direction," he said. "Even the 'correct' rating led people to select that value more often." 

....

The distortion this chain of events induces may influence consumer buying in the short-term, but adversely affects long-term consumer trust in the system, said Konstan. "While a system can get away with a small degree of lying... in the long run dishonesty erodes trust and satisfaction," he said. 



Se även Good Ratings Gone Bad.

Ett annat exempel hur rekommenderare påverkar ens val, är Dived we Stand??? där det görs en liten undersökning om köptendensen av politiska böcker: It appears that echo chambers have emerged that repeat a consistent message within each cluster. Ron Burt, a leading network expert, explains that a tightly closed network "amplifies predispositions, creating a structural arthritis in which people cannot learn what they do not already know"[PDF...]. With no direct bridges between the clusters, these divisions are unlikely to change any time soon.

För mer om rekommenderare / collaborative filtering, se t.ex.:



 http://www.cis.upenn.edu/~ungar/CF/

 http://www.dcs.elf.stuba.sk/emg/collab.htm

 http://courses.washington.edu/~hs590a/weblinks/recommender.html






Posted by hakank at 09:43 FM
Posted to Machine learning/data mining
 | Rekommendationssystem







juli 04, 2003


Automatiserat detektivarbete

'Sherlock Holmes' thinks lateral for murder cops beskriver ett forskningsprojekt kring automatiska slutsatsdragningar vid brottsplatsundersökning.

Mer teknisk information om projektet, inklusive papers, finns på The Model Based Decision Support System for Crime Investigation. Det finns också en enkel Java-prototyp att ladda ner. Jag lekte med det en liten stund och blev inte  imponerad, men när systemet väl är utvecklat kan det kanske bli något.

Samma forskningscenter (The Joseph Bell Centre for Forensic Statistics and Legal Reasoning) har ett annat intressant projekt ff POIROT - Financial Fraud Prevention Oriented Information Resources using Ontology Technology : Positioned in the context of Semantic Web endeavour, the project seeks to build computable knowledge resources, ontology of financial forensics, from financial and legal expertise in detecting and preventing fraud in VAT processes, securities exchange, investment and banking and insurance services. Speciellt kopplingen till  Semantic Web är spännande.

För mer kvantitativa tekniker att avslöja bedrägerier, se t.ex. Artificial Intelligence and Fraud Detection / Fraud Management .




Posted by hakank at 09:59 FM
Posted to Machine learning/data mining







juni 24, 2003


En egen sökmotor - nästan

Hittade Open Source-projektet Carrot²  skrivet i Java. Tomcat rekommenderas som web server.

Carrot² är en "klustringsmotor" som samlar sökresultat från en sökmotor och grupperar  dem sedan i kluster, lite som t.ex. turbo10.com. En av finesserna är att det också finns filter, t.ex. stemmer för engelska, så att man kan manipulera med sökorden. I demon finns det en olika kombinationer av sökmotor+filter+klustringsalgoritmer att välja mellan. Det finns en demo  av systemet. Den är lite slö, men man ser i alla fall hur de har tänkt sig. 

Man kan ladda ner systemet här. Jag installerade systemet, vilket tog en liten stund i och med att man måste mixtra med lite XML-filer för Tomcat. Det är dock inga svårigheter om man följer installationsinstruktionerna .

Det enda jag ännu har fått att funka är dock förfabricerade demo-sökningar, så systemet är - ännu - inte användbart som en lokal sökmotor. Det ska bli intressant att följa utvecklingen.




Posted by hakank at 10:15 FM
Posted to Machine learning/data mining
 | Sökmotorer







juni 23, 2003


Bayesian Networks

I morse läste jag med spänning Thorvald Freiholtz översikt av system dynamics (Torsksystemdynamik) och de referenser han hänvisade till.

En sak jag kom att tänka på under läsningen var Bayesianska nätverk (BN). 

BN är en typ av "grafisk modellering" som bygger på sannolikhetsteoretiska relationer (Bayes regel) mellan olika typer av variabler (entiteter, fenomen) vilka är sammankopplade i en graf. 

Genom att laborera med olika förutsättningar i en sådan modell kan man få reda på hur detta  påverkar resten av systemet. T.ex. kan man modellera kopplingar mellan symptom och sjukdom (t.ex. som ett expertsystem), sannolikhetsteoretiska problem (t.ex. Monty Hall-problemet). En viktig del i modelleringen är att man kan gå från orsak till verkan, och även studera orsaken givet verkan,  t.ex. om en patient är sjuk (verkan), kan man se vilka möjliga orsaker det finns. Ytterligare en intressant sak med BN är att man utifrån existerande data kan automatiskt skapa en modell. 

Personligen har jag använt BN mest för att modellera mer eller mindre rena sannolikhetsteoretiska problem.

Några introduktioner till ämnet: 



 Charniaks Bayesian Networks without Tears (PDF)

 Kevin Murphy A Brief Introduction to Graphical Models and Bayesian Networks. Har många vidarelänkar.



En utmärkt introduktion i sannolikhetsteori, där bland annat Bayesiansk analys ingår, är  

Introduction to Probability av Grinstead och Snell.



Av en lite märklig slump kom senare under dagen ett mail från Hugin, en av de främsta produktutvecklarna av sådana system, om att det kommit en ny version av systemet. När jag kollade in Bayesianska nätverk använde jag bland annat deras demoversion som var alldeles utmärkt för enklare modellering. 

Hugin har bra introduktionsdokumentation hur man arbetar i systemet, t.ex. Getting Started, Tutorial  och kommer med en massa exempel varav några är väl dokumenterade, t.ex. modell av Monty Hallproblemet.

Det finns en begränsad demo av Hugin att ladda ner här. Finns för Windows, Linux samt  Solaris. Tyvärr är Hugins demo-version alldeles för begränsad för att man ska ha någon riktig nytta av dess möjligheter att automatiskt skapa en BN-modell.

Det finns naturligtvis även andra BN-produkter, se t.ex. googles Computers/Artificial_Intelligence/Belief_Networks/-katalog.




Posted by hakank at 08:55 EM
Posted to Machine learning/data mining
 | Statistik/data-analys







juni 22, 2003


Lying Words

Man kan med relativ hög sannolikhet (~67%) avgöra om en person ljuger eller talar sanning genom att analysera skriven text. Det hävdas i Lying Words - Predicting Deception from Linguistic Styles. Här undersöks olika typer av lingvistiska detektorer för vad som anses vara sanning respektive lögn.

Abstract:

Lying often involves telling a story that is either false or one that the individual doesn't believe. Most research has focused on identifying such lies through nonverbal cues or physiological activity. The current project investigates the linguistic styles that distinguish between true and false stories. In an analysis of five independent samples, a computer-based text 

analysis program correctly classified liars and truth-tellers at a rate of  67% when the topic was constant and a rate of 61% overall. Compared to truth-tellers, liars used fewer self-references, other-references, and exclusive words and more 'negative emotion' and 'motion' words. Results are discussed in terms of 1) context-independent and context-dependent markers of deception, and 2) implications for the detection of deception. 

Lite mer om detta projekt finns på http://www.simstat.com/LIWC.htm.




Posted by hakank at 12:50 EM
Posted to Machine learning/data mining







juni 19, 2003


Contextual Network Graphs

Contextual Network Graphs är en rätt ny variant av Latent Semantic Indexing (LSI, som förklaras på samma sajt). Dessa tekniker ger - anser man - mer intelligent sökresultat genom att ett dokument inte behöver innehålla det specifika sökordet/-en men anses vara likt ett relevant dokument.

(Jag förklarar LSI liten kort med R-kod i min data mining presentation, lite längre ner på sidan.)

Vad gäller Contextual Network Graphs är fördelen - enligt skaparna - att den är snabbare än LSI och - framförallt - att den inte är patenterad.

Det finns för en Perl-modul Search::ContextGraph (cpan.org) att leka med. Den är skapad av en av artikelförfattarna. Notera att det är version 0.01. Jag har lekt lite med modulen men tyvärr ännu inte fått de resultat jag förväntat mig. Det kan vara en bugg i programmet, eller i min förståelse av hur man använder modulen.




Posted by hakank at 10:22 EM
Posted to Machine learning/data mining






juni 18, 2003


Equation Discovery

Den senaste tiden har jag sysselsatt mig rätt mycket med dynamiska system, dvs differentialekvationer och sådant (läser bland annat om en massa kaosteoriböcker). Ett annat stort intresse är machine learning. "Varför inte koppla ihop dessa?", frågade jag mig i morse, varpå en sökning å webben gjordes.

Det finns en del forskning kring hur man, givet en datamängd, skapar differentitalekvationer (ett dynamiskt system), men här är det första stället jag stött på som har fungerande och intressanta system. Det är två system: LAGRANGE och LAGRAMGE där det förstnämnda är rätt mycket mer tillgängligt och lättanvänt än det sistnämnda. Jag leker som bäst med dessa system nu.






Posted by hakank at 01:40 FM
Posted to Machine learning/data mining

hakank.blogg

Anteckningar från en PopSci-junkie. Av Håkan Kjellerstrand (hakank@gmail.com).

februari 21, 2010

Ny engelskspråkig blogg: Arrays in Flux

januari 24, 2010

Eureqa: equation discovery med genetisk programmering

Installation

Mer om systemet

Modellering, några exempel

Datafiler

Mer om Eureqa

april 28, 2009

Karl Wettin intervjuas om Lucene and Mahout

augusti 19, 2007

Recension av Keith Devlin, Gary Lorden: The Numbers Behind Numb3rs: Solving Crime with Mathematics

mars 11, 2007

Några saker om Weka (databrytning, data mining och machine learning)

februari 16, 2007

Ansikten: länkar 20070216

februari 11, 2007

Några länkar om dataanalys, data mining etc 20070211

juni 21, 2006

Pascal Virtual Playground: machine learning videoföreläsningar

maj 11, 2006

Uppdatering på Weka-sidan

maj 08, 2005

Sällskapsspel, strategier och spelteori

april 14, 2005

Amazons "Statistically Improbable Phrases" (SIPs)

november 23, 2004

Wired: Software Detects the True Artist

november 02, 2004

InfoVis: Collaborative Filtering

augusti 24, 2004

Demokratiska akademiska tidskrifter

mars 22, 2004

Bibliomining - data mining for libraries

januari 23, 2004

Evolving a Stigmergic Self-Organized Data-Mining

januari 13, 2004

Senaste SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining) Explorations

december 27, 2003

Bloggidentifiering (Blog Identification)

december 18, 2003

Ny bok: Organizational Data Mining

december 16, 2003

Recension av Gordon Linoff & Michael Berry: 'Mining the Web'

december 05, 2003

Recension av Jiawei Han & Micheline Kamber: 'Data Mining - Concepts and Techniques'

november 27, 2003

Data mining-lista: Mi_Li_Wo

november 25, 2003

Senaste KDnuggets

november 12, 2003

Weka version 3.4

november 08, 2003

Machine learning och musikstilar

oktober 07, 2003

Självorganisation och data mining/data analys, samt stigmergy

september 04, 2003

Senaste KDnuggets

september 01, 2003

Tillägg till "Data mining, machine learning och emergens"

Data mining, machine learning och emergens

augusti 19, 2003

KDnuggets

augusti 18, 2003

JMLR Special Issue on Inductive Logic Programming

augusti 15, 2003

Maskinell analys av argument

augusti 07, 2003

KDnuggets nyhetsamling om data mining/machine learning

juli 28, 2003

Information Immune System

juli 22, 2003

JMLR - Journal of Machine Learning Research

juli 18, 2003

Könsbestämning av text

juli 17, 2003

Bok: "Modeling the Internet and the Web"