Hallgatói preferencia rangsorok készítése a jelentkezések alapján

Hallgatói preferencia rangsorok készítése a jelentkezések alapján Telcs András, Kosztyán Zsolt Tibor, Török Ádám Pannon Egyetem, Kvantitatív Módszerek Tanszék, MTA Kutatócsoport

Tartalom Bevezetés Forrásadatok bemutatása Adatok szűrése Mi legyen egy objektum? Gráf reprezentációk, műveletek Rangsorok kialakítására alkalmazott függvények Eredmények További tervek 2013.11.19.

Hiányos rangsorok kezelése

2

A kezdetek

2013.11.19.

3

A bőség zavara

2013.11.19.

4

Bevezetés Cél: Objektív egydimenziós rangsor kialakítása.

2013.11.19.


5

Preferenciák 1. diák (a,c,b) 2. diák (b,a,c,d,e) 3. diák (a) 4. diák (b,a) . n. diák (a,b) Egyesített rangsor(a,b,c,d,e) 2013.11.19.

6

Preferenciák (a,c,b) (b,a,c,d,e) (a) (b,a) (a,b) (a,b,c,d,e)

2013.11.19.

7

Hiányok kezelése (a,c,b,(b,e)) (b,a,c,d,e) (a,(b,c,d,e)) (b,a,(c,d,e)) (a,b,(c,d,e)) (a,b,c,d,e)

2013.11.19.

8

Forrásadatok bemutatása Hallgatói felvételi jelentkezések 20012011-ig. A fejléc tartalma: Év Eljárás (normál, keresztfélév) Egyedi azonosító Jelentkezési hely Intézmény Kar Szak Képzés formája (alap, mester, osztatlan) Képzés módja (nappali, levelező) Képzés finanszírozása (állami, költség tér.) 2013.11.19.


9

Rangsor Országos intézmények szerint Tudomány terület szerint Karok szerint Szakok szerint

2013.11.19.


10

Mi legyen egy objektum? Mik között állítsunk fel rangsort?

2013.11.19.

Objektum

Előnyök

Hátrányok

Kihívások

Intézmény

Viszonylag kevés objektum

Információvesztés, inhomogenitási problémák

Inhomogenitás feloldása szűrésekkel

Kar

Kezelhető számú objektum

Információvesztés

Információvesztés minimalizálása

Szak

Nincs információvesztés

Rengeteg objektum, „Optimális” megoldás megtalálása reménytelen

Gyors heurisztikus módszer keresése


11

Gráfreprezentáció Objektumok (intézmények, karok, szakok): 1,2,…,m. A hallgatói jelentkezési sorrendek: A:={a1,…,an}, ai:=[ai1,…,aimi]T Legyen pl. 4 lehetséges szak. A hallgató jelentkezési sorrendje: a1:={1,2,3,4}.

1

2

3

4

ID

1

2

3

4

1

--

1

1

1

--

1

1

--

1

2 3 4  2013.11.19.


-0

1

2

3 12

Gráfreprezentáció Legyen pl. 4 lehetséges szak. A hallgató jelentkezési sorrendje: a2:={1,2}.

1

ID

1

22

33

44

3

1

--

11

1

1

---

1 ---

1

4

2 3 3

2

M

4 4 

2013.11.19.


0

11

.5 ----

.5 2.5 0 2.5 0

13

Csúcsok összevonása Pl. SzakokKarokIntézmények 3 1

4 II

I

2013.11.19.

1

2

3

4

1

--

1

1

1

--

1

1

2

2

ID

I

II

I

--

4

II

ID

3 4

---

--


14

Összesítés jósága (a,c,b) (b,a,d,c,e) (a) (b,a) (a,b) (a,b,c,d,e)

2013.11.19.

1 2 1

15

Arrow’s impossibility theorem “Clear order of preferences cannot be determined while adhering to mandatory principles of fair voting procedures.”

Investopedia http://www.investopedia.com/terms/a/arrows-impossibility-theorem.asp

2013.11.19.

16

Alkalmazott módszerek Egyszerű heurisztikus módszerek Páros összehasonlításon alapuló módszerek Genetikus algoritmusok Naiv algoritmusok

2013.11.19.


17

Hibafüggvény ,

M

ID

1

2

3

4

ID

1

3

4

2

1

--

5

5

3

1

--

5

3

5

2

3

--

1

5

3

2

--

2

3

3

2

3

--

2

4

1

3

--

5

4

1

5

3

--

2

3

1

5

--



6

13

9

10



6

9

10

13

=17

h(M,[1,2,3,4]T) b

2013.11.19.



1

3

Mb

h(M,b) 4


=15

2

18

Oszlopösszegek – Eredmények Helyezés 1 2 3 4 5 6 7 8 9 10 2013.11.19.

OBJID 1 3 9 2 4 8 10 5 7 6

Intézmény IW BCE 2741 BME 6770 XXX* 7779 * -al jelöltek BGF szégyenlőssek 7920 DE 8157 SZE 8206 SZTE 8235 ME 8240 PTE 8252 8294 XXX* ,

453

19

Apriori feltevés Gottfried Wilhelm von Leibniz (July 1, 1646 – November 14, 1716) John Maynard Keynes (5 June 1883 – 21 April 1946) Edwin Thompson Jaynes (July 5, 1922 – April 30, 1998) • principle of insufficient reason • principle of indifference • n-objektum 1/n egyenletes valószínűséggel • Non-informative prior vagy a maximális entrópia elve Equivalent states of knowledge should be assigned equivalent epistemic probabilities. 2013.11.19.

20

Rangösszeg módszer – Példa Legyen: a1:=[1,2]T; m:=4; s1:=[1,2,3.5,3.5]T s*1:=[0,1,2.5,2.5]T= s1-1 3 1

ID

1

2

3

4

1

--

1

x

x

--

x

x

2

2 4

3

--

4

-0

1

s*1

0

1

2x

2x

2.5

2.5

=

 x=1.25 2013.11.19.


21

Rangösszeg módszer Legyen: a1:=[2,6]T; a2:=[1]T; m:=10;

Ekkor a rangokat tartalmazó vektor a következőképpen számítható:

esetén 2013.11.19.


≔ ≔

22

Rangösszeg módszer Eredmények Helyezés OBJID Intézmény Átlagos rangérték 1 1 BCE 2,83 2 3 BME 5,03 3 9 XXX 5,67 4 2 BGF 5,73 5 4 DE 5,91 6 10 SZTE 5,96 7 8 SZE 5,97 8 7 PTE 5,99 9 5 ME 6,01 10 6 XXX 6,02 , 2013.11.19.


451 23

Páros összehasonlításon alapuló módszerek Eredetileg csak teljes összehasonlítások esetén lehetett alkalmazni! Létezik olyan változata is, amely nem teljes összehasonlítások esetén is alkalmazható.

2013.11.19.


24

Páros összehasonlításon alapuló módszerek Páronkénti összehasonlítások Arány skála! => Skála-transzformáció Sorrendi skála

2013.11.19.


25

Páros összehasonlításon alapuló módszerek – Lépései (vázlatosan) Sorrend (kialakítása) Ellenőrzés 2013.11.19.

Gyakorisági táblázat M Relatív gyakorisági táblázat (P) Inverz normál transzformáció (Z) Arányskála az oszlopösszegek alapján Relatív gyakoriságok rekonstruálása ( ) Illeszkedésvizsgálat (2-próba) Hiányos rangsorok kezelése

26

Páros összehasonlítás – eredmények Helyezés 1 2 3 4 5 6 7 8 9 10 2013.11.19.

OBJID 1 3 7 2 4 6 10 5 8 9


Intézmény BCE BME PTE BGF DE XXX2 SZTE ME SZE XXX1

Z 0,85 0,44 0,05 0,03 -0,09 -0,14 -0,16 -0,22 -0,38 -0,39 ,

418

27

Genetikus algoritmusok Fogalmazzuk át a problémát! Keresünk egy olyan sorrendjét az 1,2,…,m számoknak, amelyre a hiba függvény értéke minimális. Nagyon sok lehetőség van! Több mint Sessa kérése 2013.11.19.


28

Genetikus algoritmus Populáció: Véletlen sorrendjei az 1,2,…,m-nek. Jósági függvény=hibafüggvény Szelekció: Kisebb hibafüggvényérték => nagyobb életképesség “fitness”

2013.11.19.


29

Genetikus algoritmus Mutáció: véletlen pozíciócsere Pl. [1 2 3 4 10 5 6 7 8 9]T => [1 2 3 10 4 5 6 7 8 9]T Rekombináció: szekvencia részletek „öröklődése” Pl. [1 2 3 4 6 10 5 7 8 9] + [3 2 1 6 4 10 9 8 7 5] => [1 2 3 6 4 10 9 8 7 5] 2013.11.19.


30

Genetikus algoritmus – eredmény Bementi mátrix

Helyezés 1 2 3 4 5 6 7 8 9 10 2013.11.19.


M

M’

Intézmény BCE BME XXX1 BGF DE SZE ME SZTE PTE XXX2

,

454

33

Intézmémyi preferenciák alakulása

További tervek, ötletek, kutatási irányok Preferenciák vizsgálata A végeredményül kapott rangsor hogyan korrelál más módon meghatározott rangsorokkal? Mi az eltérés, egyezés oka? Az időbeli fejlődések elemzése

2013.11.19.


35

Köszönjük a figyelmet!

Bemutatott módszerek értékelése I Módszer

h(M’,b)

h(M,b)

Optimális Miért? megoldás?

Oszlopösszeg

10 105

453

Nem

Rangösszeg

10 175

451

Nem

Páros összehasonlítás (M’)

10 100

454

Nem

Páros összehasonlítás (M)

13 580

418

Genetikus (M’)

10 100

454

Genetikus (M)

12 994

411

Naiv (M’)

10 100

454

2013.11.19. Naiv (M)

12Hiányos 994 rangsorok 411 kezelése

Nem teljes rangsor. Nem teljes rangsor.

Sok hiányzó páros összehasonlítás miatt a relatív gyakoriságok jelentősen eltérnek a gyakorisági tábláktól. Talán

Az optimális megoldás megtalálása nem garantálható!

Igen

Az összes megoldást megvizsgáljuk 37

Bemutatott módszerek értékelése II Módszer

O(f(n))

Előnyök

Hátrányok

Oszlopösszeg

n+m+m2

Nagyon gyors módszer

Nem vesszük figyelembe, hogy a hallgató egy intézménybe többször is jelentkezhet.

Rangösszeg

n+m+m2

Nagyon gyors módszer

Nem vesszük figyelembe, hogy a hallgató egy intézménybe többször is jelentkezhet. Nem kapunk rangsort!

n hallgatók száma m intézmények száma Páros összehasonlítás

n+m+m2

Figyelembe vesszük, hogy a hallgató egy intézménybe többször is jelentkezhet.

Nem teljes rangsor => Nem optimális.

Genetikus

?

Optimális megoldás megtalálásának lehetősége nagy m esetén

Az optimum megtalálása nincs garantálva.

Naív

m2m!

Optimális

Nagy m-ek esetén esélytelen

2013.11.19.

38

Hibafüggvény M, M’ a preferencia mátrix. b=[b1,b2,…,bm]T egy tetszőleges sorrend Legyen Mb, illetve Mb’ az M, illetve M’ mátrix átrendezettjei.

2013.11.19.


39

Hibafüggvény ,

M

ID

1

2

3

4

ID

1

3

4

2

1

--

5

5

3

1

--

5

3

5

2

3

--

1

5

3

2

--

2

3

3

2

3

--

2

4

1

3

--

5

4

1

5

3

--

2

3

1

5

--



6

13

9

10



6

9

10

13

=17

h(M,[1,2,3,4]T) b

2013.11.19.



1

3

Mb

h(M,b) 4


=15

2

40

Arrow’s impossibility In social choice theory, Arrow’s impossibility theorem, the General Possibility Theorem, or Arrow’s paradox, states that, when voters have three or more distinct alternatives (options), no rank order voting system can convert the ranked preferences of individuals into a community-wide (complete and transitive) ranking while also meeting a specific set of criteria. These criteria are called unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives.

2013.11.19.

41

Hallgatói preferencia rangsorok készítése a jelentkezések alapján

Recommend Documents