Klassificering är ett viktigt ämne inom datautvinningsforskning. Med tanke på en uppsättning dataposter, som var och en tillhör en av ett antal fördefinierade klasser, rör klassificeringsproblemet upptäckten av klassificeringsregler som kan göra det möjligt att korrekt klassificera register med okänt klassmedlemskap. Många algoritmer har utvecklats för att bryta stora datamängder för klassificeringsmodeller och de har visat sig vara mycket effektiva. Men när det gäller att avgöra sannolikheten för varje klassificering som görs, är många av dem inte utformade med ett sådant syfte i åtanke. För detta är de inte lätt att tillämpa på sådana problem som curn förutsägelse. För en sådan ansökan är målet inte bara att förutsäga om en abonnent skulle byta från ett lufttrafikföretag till ett annat, det är också viktigt att sannolikheten för att abonnenten gör det förutses. Anledningen till detta är att en operatör sedan kan välja att ge särskilda personliga erbjudanden och tjänster till de abonnenter som förutspås med större sannolikhet att curn. Med tanke på dess betydelse föreslår vi en ny databrytningsalgoritm, kallad DMEL, för att hantera klassificeringsproblem där noggrannheten hos varje förutsägelse måste uppskattas. Vid utförandet av sina uppgifter söker DMEL igenom det möjliga regelutrymmet med hjälp av en evolutionär metod som har följande egenskaper: (i) den evolutionära processen börjar med att en första uppsättning första ordningens regler (dvs. regler med en konjunkt/villkor) med hjälp av en probabilistisk induktionsteknik och baserad på dessa regler, regler av högre ordning (två eller fler konjunkter) erhålls iterativt; (ii) när identifiera intressanta regler, används en objektiv intressanthet åtgärd; (iii) lämpligheten hos en kromosom definieras i termer av sannolikheten att attributvärdena för en post kan bestämmas korrekt med hjälp av de regler den kodar; och (iv) sannolikheten för förutsägelser (eller klassificeringar) görs så att abonnenterna kan rankas enligt deras sannolikhet att churn. Experiment med olika datamängder visade att DMEL effektivt kan upptäcka intressanta klassificeringsregler. I synnerhet är det möjligt att förutsäga curn exakt under olika curn priser när det tillämpas på verkliga teleabonnenter data. Index Termer: data mining, prediktiv modellering, evolutionsberäkning, genetiska algoritmer, regel intressanthet åtgärder, churn förutsägelse, kundbevarande, kundrelationshantering. Klassificering är ett viktigt ämne inom datautvinningsforskning. Med tanke på en uppsättning dataposter, som var och en tillhör en av ett antal fördefinierade klasser, rör klassificeringsproblemet upptäckten av klassificeringsregler som kan göra det möjligt att korrekt klassificera register med okänt klassmedlemskap. Många algoritmer har utvecklats för att bryta stora datamängder för klassificeringsmodeller och de har visat sig vara mycket effektiva [3, 16-17, 30, 36-38]. Men när det gäller att avgöra sannolikheten för varje klassificering som görs, är många av dem inte utformade med ett sådant syfte i åtanke. Befintliga databrytningsalgoritmer såsom beslutsträdsbaserade algoritmer (t.ex. Möjligt att vissa blad i ett beslut träd har liknande klass sannolikheter. Till skillnad från beslutsträdsbaserade algoritmer kan andra klassificeringsmetoder såsom logit regression och neurala nätverk [3] med sannolikhet fastställa sannolikheten för en förutsägelse. Men att jämföra med beslut trädbaserade algoritmer, dessa algoritmer uttrycker inte uttryckligen de avtäckta mönster i en symbolisk, lättförståelig form (t.ex., om-då regler). På grund av begränsningarna i dessa befintliga tekniker föreslår vi en ny algoritm, kallad DMEL (Data Mining by Evolutionary Learning), för gruvklassificeringsregler i databaser. DMEL-algoritmen har följande egenskaper. Först, i stället för slumpmässig generation, den ursprungliga populationen, som består av en uppsättning första ordningen regler 1, genereras icke-slumpmässigt med hjälp av en probabilistisk induktionsteknik. Baserat på dessa regler, regler för högre order erhålls sedan iterativt med den ursprungliga befolkningen i början av 1 I detta dokument, ordningen av regeln är relaterad till antalet villkor i föregångaren till en regel. En enda regel är därför en regel i första ordningen. Om en regels föregångare innehåller två villkor, är det en andra ordningens regel. Om det finns tre villkor i förväg av en regel, det är en tredje-ordning regel, och så vidare. 3 varje iteration som erhållits baserat på de lägre ordningsregler som upptäckts i föregående iteration. För det andra använder DMEL, när man identifierar intressanta regler, en objektiv intressantitetsåtgärd som inte kräver subjektiv input från användarna. För det tredje, vid utvärdering av en kromosoms lämplighet, använder DMEL en funktion, som definieras i termer av sannolikheten för att attributvärdena för en tuple kan bestämmas korrekt med hjälp av de regler den kodar. För det fjärde uppskattas sannolikheten för förutsägelser (eller klassificeringar). För det femte kan DMEL hantera saknade värden på ett effektivt sätt. Med hjälp av de upptäckta reglerna kan DMEL användas för att klassificera poster med okänt klassmedlemskap. I synnerhet kan DMEL förutsäga churn, som handlar om förlusten av abonnenter som byter från ett lufttrafikföretag till ett annat. Eftersom konkurrensen inom telekommunikationsindustrin är mycket hård, anser många lufttrafikföretag att minska churn som ett viktigt affärsprojekt för att upprätthålla lönsamheten. Churn kostar transportföretagen en stor summa pengar varje år i Nordamerika och Europa [28]. En liten sänkning av den årliga churnräntan kan leda till en betydande ökning av värderingen och aktieägarvärdet för ett lufttrafikföretag [28]. Följaktligen är analys och kontroll churn avgörande för att lufttrafikföretagen ska kunna förbättra sina intäkter. En operatör ger oss en databas med 100 000 prenumeranter. Bland dessa abonnenter hade några av dem redan bytt till ett annat lufttrafikföretag. Uppgiften för oss är att minera databasen för att avslöja mönster som relaterar demografi och beteenden av prenumeranter med curning så att ytterligare förlust av prenumeranter kan förhindras så mycket som möjligt. Ansträngningar görs sedan för att behålla abonnenter som konstaterats ha stor sannolikhet att byta till andra lufttrafikföretag. Eftersom företagets kundtjänstcenter endast har ett fast antal anställda tillgängliga för att kontakta en liten del av alla abonnenter, är det viktigt för den att skilja abonnenter med hög sannolikhet för curning från dem med låg sannolikhet så att, med tanke på de begränsade resurserna, de höga sannolikheten curners kan kontaktas först. För en sådan ansökan är målet inte bara att förutsäga om en abonnent skulle byta från ett lufttrafikföretag till ett annat, det är också viktigt att sannolikheten för att abonnenten gör det förutses. Det kan vara svårt för transportören att dra nytta av upptäckten eftersom transportören inte har tillräckliga resurser för att kontakta alla eller en stor del av abonnenterna. Å andra sidan, logit regression och neurala nätverk, som kan bestämma en sannolikhet för en förutsägelse med sin sannolikhet, inte uttryckligen uttrycka de avtäckta mönster i en symbolisk, lätt förståelig form. Det är av denna anledning som transportören inte ansåg att dessa tillvägagångssätt var det bästa för deras uppgift, eftersom de inte kunde kontrollera och tolka de avtäckta kurvmönster. Till skillnad från befintliga tekniker, DMEL kan bryta regler som representerar curning mönster och att förutsäga om en abonnent sannolikt kommer att curn inom en nära framtid. Experimentella resultat visar att det är möjligt att upptäcka de regulariteter som döljs i databasen och att förutsäga sannolikheten för att en abonnent curns under olika churn priser. Dessutom, eftersom vissa attribut i abonnentdatabasen innehåller betydande mängd saknade värden, förmågan hos DMEL att hantera saknade värden effektivt är viktigt för framgång DMEL i churn förutsägelse. I följande avsnitt går vi igenom relaterat arbete inom datautvinning och evolutionär beräkningslitteratur för att bygga prediktiva modeller. I synnerhet förklarar vi hur de kan användas i churn förutsägelse. I Avsnitt 3 ger vi detaljer om DMEL och förklarar hur det kan användas för att upptäcka intressanta regler gömda i databaser. För att utvärdera DMEL:s prestanda tillämpade vi det på flera verkliga databaser. De experimentella resultaten ges i avsnitt 4. Närmare uppgifter om den abonnentdatabas som tillhandahålls av ett lufttrafikföretag i Malaysia och de experimentella resultat som använder denna databas för att testa om DMEL är effektivt för churn förutsägelse anges sedan i avsnitt 5. Slutligen ger vi i avsnitt 6 en sammanfattning av dokumentet. Bland de olika tillvägagångssätten för att bygga prediktiva modeller i datautvinning, beslut trädbaserade algoritmer är de mest populära (t.ex., [16-17, 30, 36-38] Antag att posterna i en databas kännetecknas av n attribut, A 1,..., A i,..., A n och att A i är attributet vars värden ska förutsägas. I träd-bygget fas, ett beslut träd konstrueras genom rekursivt partitionera utbildningen som enligt värdena för A j, j = 1,..., n, j  på i. Denna partitioneringsprocess fortsätter tills alla, eller majoriteten, av posterna i varje partition har samma attributvärden, Eftersom det resulterande beslutsträdet kan innehålla grenar som skapas på grund av ljud i data, kan vissa av grenarna behöva tas bort. Trädbeskärningsfasen består därför av att välja ut och ta bort de underträd som har den största uppskattade felfrekvensen. Beskärning av träd har visat sig öka exaktheten i ett beslutsträd å ena sidan och minska komplexiteten i trädet å den andra. Av de många beslut trädbaserade algoritmer som har använts i data mining, är C4.5 den överlägset mest populära [36]. Förutom användningen av beslut trädbaserade algoritmer, tekniker baserade på genetiska algoritmer (GAs) har också föreslagits för prediktiv modellering. Det finns för närvarande två olika GA-baserade metoder för att upptäcka regler: Michigan-metoden och Pittsburgh-metoden. Michigan tillvägagångssätt, exemplifierat av Hollands klassificeringssystem [21], representerar en regel som fastställts av hela befolkningen medan Pittsburgh tillvägagångssätt, exemplifierat av Smiths LS-1 system [39], representerar en regel som fastställs av en enskild kromosom. Även om Michigan-metoden kan hantera problem i flera klasser, är en av de största svårigheterna med att använda den problemet i kredittilldelning, vilket ger de aktiverade klassificeringarna en belöning om klassificeringen de producerade är korrekt och ger dem ett straff, annars. Det är särskilt svårt att komma fram till en bra kreditgivningsplan som fungerar. Algoritmerna baserade på Pittsburgh-metoden (t.ex. [10, 23, 39] ) representerar en hel regel inställd som en kromosom, upprätthålla en population av kandidatregeluppsättningar, och använda urval och genetiska operatörer för att producera ny generation av kromosomer och därmed nya regeluppsättningar. Varje kromosom konkurrerar med varandra när det gäller klassificeringsnoggrannhet på applikationsdomänen. Individer väljs för reproduktion med hjälp av roulette hjul val och en helt ny population genereras baserat på crossover och mutation. De utvalda kromosomerna producerar avkomma med hjälp av en utökad version av standard tvåpunkts crossover operatör så att crossover punkter kan uppstå antingen på regelgränser eller inom regler [10, 39]. Det vill säga, om en förälder skärs på en regelgräns, då den andra föräldern måste skäras på en regelgräns också; på liknande sätt, om en förälder skärs på en punkt, till exempel, 5 bitar till höger om en regelgräns, då den andra föräldern måste skäras på en liknande plats [10, 39]. Mutationsoperatorn är identisk med den klassiska, som utför bit-nivå-mutationer. Lämpligheten av varje enskild regel uppsättning beräknas genom att testa regeln som anges på den nuvarande uppsättningen av träningsexempel [10, 39]. Pittsburgh-metoden var ursprungligen utformad för en klass inlärningsproblem och därför var det bara föregångaren till en regel som kodades in i en allel av en kromosom [10, 23, 39]. En instans som matchar en eller flera regler klassificeras som ett positivt exempel på begreppet (klass) och en instans som inte matchar någon regel klassificeras som ett negativt exempel [10, 23, 39]. För att ta itu med problem i flera klasser skulle de kunna utvidgas genom att införa flera populationer så att en viss population är dedikerad till att lära sig varje koncept. Det är möjligt att en instans motsvaras av mer än en regel med olika begrepp å ena sidan och det är också möjligt att en instans motsvaras av ingen regel i något begrepp å den andra. Tyvärr har detta problem inte behandlats i många av de system som bygger på Pittsburgh-metoden (t.ex. [10, 23, 39] ). På senare tid har användningen av god jordbrukshävd och goda miljöförhållanden vid tillämpning av datautvinning undersökts i [9, 12, 15, 26]. Dessa algoritmer är baserade på Michigan metoden på ett sätt som varje regel kodas i en kromosom och regeln som representeras av hela befolkningen. Till skillnad från klassificeringssystem (t.ex. [19, 21, 29] Det är viktigt att notera att dessa algoritmer [9, 12, 15] utvecklades för att upptäcka regler för endast en klass. När de används för att hantera multi-klass problem, GAs körs en gång för varje klass. Specifikt, de skulle söka regler förutsäga den första klassen i den första körningen; de skulle söka regler förutsäga den andra klassen i den andra körningen och så vidare. Likt Pittsburgh tillvägagångssätt, är det möjligt att en instans matchas av mer än en regel förutsäga olika klasser å ena sidan och det är också möjligt att en instans matchas av ingen av någon regel förutsäga någon klass på den andra. Detta problem har inte tagits upp av dessa algoritmer. Även om metoder för upptäckt av god jordbrukshävd och goda miljöförhållanden kan ge exakta prediktiva modeller, kan de inte avgöra sannolikheten för deras förutsägelser. Detta hindrar dessa tekniker från att vara tillämpliga på uppgiften att förutsäga churn, vilket kräver rangordning av abonnenter beroende på deras sannolikhet att curn. Ett relaterat arbete om churn förutsägelse i en databas med 46.744 prenumeranter har presenterats i [32]. Resultaten av logit regression, C5.0 (en kommersiell programvaruprodukt baserad på C4.5) och icke-linjära neurala nätverk med ett enda dolt lager och viktfall [3] utvärderas empiriskt. De experimentella resultaten i [32] visade att neurala nätverk överträffade logit regression och C5.0 för churn förutsägelse. En empirisk jämförelse av DMEL med neurala nätverk och C4.5 på abonnentdatabasen som tillhandahålls av transportören i Malaysia kommer att ges i avsnitt 5. För att utföra sökning mer effektivt i en enorm regeluppsättning utrymme, föreslår vi att använda en evolutional algoritm som kallas DMEL. Med hjälp av en evolutionär inlärningsmetod, DMEL kan bryta regler i stora 7 databaser utan något behov av användardefinierade tröskelvärden eller kartläggning av kvantitativa till binära attribut. DMEL kräver dock att kvantitativa attribut omvandlas till kategoriska attribut genom användning av en discretizationalgoritm, vilket kommer att ses senare. I detta dokument är ordningen för regeln relaterad till antalet villkor i förväg av en regel. En engångsregel är därför en förstahandsregel. Om en regels föregångare innehåller två villkor, är det en andra ordningens regel. Om det finns tre villkor i förväg av en regel, det är en tredje-ordning regel, och så vidare. DMEL upptäcker regler genom en iterativ process. Det börjar med skapandet av en uppsättning första ordningen regler med hjälp av en probabilistisk induktionsteknik. På grundval av dessa regler upptäcker den sedan en uppsättning andra ordningens regler i nästa iteration och utifrån andra ordningens regler, upptäcker den tredje ordningens regler, etc. Med andra ord, om vi hänvisar till den första uppsättningen av första ordningen regler som R 1, De regler i R 1 används sedan för att generera en uppsättning andra ordningen regler, R 2. R 2 används sedan för att generera en uppsättning tredje ordningen regler, R 3, och så vidare för fjärde och högre ordningsregler. I allmänhet, vid (l - 1)-th iterationen, DMEL börjar en evolutionär inlärningsprocess genom att generera en initial population av individer (var och en representerar en uppsättning av l-th ordning regler) genom att slumpmässigt kombinera reglerna i R l -1 för att bilda en uppsättning regler av ordning l. När man väl börjat, den iterativa inlärningsprocessen fortsätter oavbruten tills inga mer intressanta regler i den nuvarande befolkningen kan identifieras. DMEL-algoritmen ges i bild. 1 nedan. Avkoda funktionen i bild. 1 är att extrahera alla intressanta regler kodade i en kromosom och lagra dem i R l. Om en allel i kromosomen hittas intressant baserat på den objektiva mått definieras i avsnitt 3.2, avkoda funktionen kommer att extrahera regeln den kodar. Regeln som returneras av decode-funktionen innehåller därför endast intressanta regler. När ingen av de regler som kodas i individen hittas intressant, decode funktionen kommer att returnera en null set och därmed R l kommer att bli en null set. För den evolutionära processen kodar DMEL en komplett uppsättning regler i en enda kromosom på ett sådant sätt att varje gen kodar en enda regel. Specifikt, med tanke på följande l-th order regel, till exempel: där  på grund av ekvation (14) senare, är en osäkerhetsåtgärd i samband med det, är denna regel kodad i DMEL av den allel som anges i Bild. 2 Det bör noteras att den därav följande och osäkerhetsåtgärden inte är kodad. Detta beror på att det som blir följden inte är, och i själva verket inte bör avgöras av slumpen. I DMEL bestäms både resultatet och osäkerhetsmåttet när en kromosoms lämplighet beräknas. Med tanke på detta representationsschema är antalet gener i kromosomen därför detsamma som antalet regler i regeluppsättningen. 9 DMEL börjar den evolutionära processen med att skapa en uppsättning första ordningens regler. Jämfört med slumpmässigt genererad initialpopulation har det visat sig att heuristiskt genererade initialpopulationer kan förbättra konvergenshastigheten och hitta bättre lösningar [20, 22, 24, 41]. Baserat på dessa resultat upptäcker DMEL först en uppsättning första ordningen regler och placerar den i den ursprungliga befolkningen. Dessutom skapas de ursprungliga reglerna för den första ordningen mycket snabbt. Den tid det tar att generera den ursprungliga befolkningen som innehåller de första ordningsreglerna är försumbar jämfört med den tid det tar för den bästa uppsättningen regler att utvecklas. Skapandet av första ordningen regler kan uppnås genom att använda den intressanthet åtgärd som anges av ekvation (5) och vikten av bevis åtgärd ges av (14) I stället för att använda chi-square test, föreslår vi att använda restanalys [6] [7] för att avgöra om en ip är beroende av en jq. Vi anser att sambandet mellan en ip och en jq är intressant om sannolikheten för att hitta en ip i en tuple med tanke på att en jq är i samma tuple skiljer sig avsevärt från sannolikheten att hitta en ip i tuple ensam. Med andra ord, det finns därför ett intressant samband mellan en ip och en jq om För att avgöra om skillnaden är betydande, den justerade rest [6] [7] Åtgärden definieras av (5), När en jq hittas, sannolikheten att en ip också finns i samma tuple förväntas vara betydligt lägre än när en jq inte hittas. I ett sådant fall säger vi att en jq är negativt associerad med Med tanke på att en ip och en jq är positivt eller negativt associerade, kan ett mått på styrkan i associationen definieras. I [6] [7] föreslås en sådan åtgärd och den kallas bevisåtgärdens vikt. Denna åtgärd definieras i termer av ett informationsteoretiskt begrepp som kallas ömsesidig information. Ömsesidig information mäter förändringen av osäkerhet om förekomsten av en ip i en tuple med tanke på att det har en jq. Det definieras enligt följande: Baserat på den ömsesidiga informationsmåttet, vikten av bevismått definieras som [6] [7] När antalet tuples som kännetecknas av både en jq och en ip är tillräckligt stor, kan vi helt enkelt använda provet bakre sannolikheten för en ip ges en jq, Pr(A i = a ip  och A j = en jq ), som populationen bakre sannolikhet. Emellertid, under skev klass fördelningar, antalet tuples som har en jq och en ip kan vara mycket liten och detta kan förbjuda användningen av provet bakre sannolikhet som populationen bakre sannolikhet. För att uppnå populationssannolikhet föreslår vi att man använder en empirisk Bayes-metod, som tar hänsyn till både provets bakre och provets tidigare sannolikheter [4]. Den empiriska Bayes uppskattning av den bakre sannolikheten för en ip givet en jq definieras som: där B är krympfaktorn, som väger vikten av den bakre och tidigare sannolikheter. Om sannolikhetsfördelningen för poster som har en jq och en ip och sannolikhetsfördelningen för den uppskattade bakre sannolikheten är både Gaussian, krympningsfaktorn definieras som: Vikten av bevis som definieras i Ekvation (9) kan sedan ändras som: Genom användning av den intressanthet åtgärd som ges av Ekvation (5) och vikten av bevismått ges av (14), kan en uppsättning intressanta första ordningen regler upptäckas. När dessa regler är upptäckta, DMEL kommer att börja en iterativ process av initialisering av befolkningen, utvärdering av lämplighet av individer, urval, reproduktion, och uppsägning, etc., för att upptäcka högre ordning regler. Eftersom en bra initial population kan förbättra hastigheten på den evolutionära processen och göra det lättare att hitta en optimal lösning, DMEL inte generera sina initiala populationer helt slumpmässigt. I stället använder man sig av en heuristisk där associationen mellan en jq och en ks och en ip är mer benägna att vara intressant om associationen mellan en jq och en ip och associationen mellan en ks och en ip är intressant. Initialisera funktionen tar som argument, R l -1. Den chrom i.allele j i bild. 3 betecknar j-th allelen av ith kromosomen. Den rand l (R) Funktionen returnerar en l-th order allele konstruerad genom att slumpmässigt kombinera l element i R. För våra experiment, popsize var inställd på 30 och antalet alleler i varje kromosom var inställd på nalles =  och R l -1. Vi sätter nalles = R l -1 Eftersom varje allel representerar föregångaren till en regel och kromosomen används för att koda R l -1. De genetiska operatörer som används av DMEL implementeras i den reproduktionsfunktion som visas i bild. 4 Crossover (krom 1, krom 2 ) funktion använder tvåpunkts crossover operatör eftersom det tillåter kombinationen av schemata, vilket inte är möjligt med den klassiska, en punkt crossover [31]. DMEL använder två olika strategier för att välja crossover punkter, nämligen crossover-1 och crossover-2. crossover-1-operatören tillåter crossover-punkter endast att uppstå mellan två regler medan crossover-2-operatören tillåter crossover-punkter att uppstå inom en enda regel. Ett exempel på crossover-1-operatören och crossover-2-operatören visas grafiskt i bild. 5 och bild 6, respektive. I DMEL, crossover sannolikhet för crossover-1 operatör och att för crossover-2 operatör betecknas som p 1 och p 2, Respektive. För våra experiment används fyra olika uppsättningar och de sammanfattas i tabell 1. De första tre uppsättningarna, DMEL-1, DMEL-2 och DMEL-3, använder konstanta värden för p 1 och p 2 medan den sista
I REF föreslog författarna en regelbaserad evolutional algoritm och tillämpade den för att förutsäga churns i en telekommunikationsdomän.
A Novel Evolutionary Data Mining Algorithm With Applications to Churn Prediction
{'venue': 'IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION', 'journal': None, 'mag_field_of_study': ['Computer Science']}