Jobs an Teilnehmer zuweisen - pandas dataframe

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Feynman
User
Beiträge: 3
Registriert: Montag 6. Januar 2020, 15:39

Hallo

Ich habe ein langes dataframe (ca. 400 Zeilen) mit folgenden Spalten:
  • ID
  • latitude
  • longitude
  • floor
Die erste Spalte ist die klassische ID, um jede Person eindeutig zuzuordnen. Latitude und Longitude sind die Koordinaten der Person (Wohnort) und floor ist das Stockwerk der Person. Ich möchte jeder Person einen von drei Jobs zuordnen: Vorspeise kochen, Hauptspeise kochen, Nachspeise zubereiten.

Bedingung 1:
Die Anzahl der Leute in der Liste ist immer ein Vielfaches von 9 (z.B. 27 oder 288). Das ursprüngliche dataframe (df) soll am Ende in kleinere Dataframes (clusters) zerteilt werden mit der Größe von 9 Teilnehmern pro Cluster.
Kurzes Beispiel:
Aus einem ursprünglichen df mit 27 Teilnehmern werden 3 dataframes (cluster) mit jeweils 9 Teilnehmer. In jedem dieser drei Cluster befinden sich dann jeweils 3 Leute für die Vorspeise, 3 Leute für das Hauptgericht und 3 Leute für die Nachspeise.
Bedingung 2:
Da die Personen zur Ausführung des Jobs eine Küche brauchen, dürfen Personen im selben Haushalt (identische Koordinaten: Latitude, Longitude und Floor) nicht den selben Job zugewiesen bekommen! Andernfalls würden sie sich in der Küche nur behindern. Macht ja auch Sinn, denn es können nicht 2 Personen gleichzeitig in der selben Küche ein Hauptgericht kochen. Jedoch sollten Personen in einem Cluster auch nicht zuweit von einander entfernt sein, weshalb ich in meinem Ansatz (siehe unten), die Personen erstmal nach den Koordinaten ordne.

Meine Frage:
Wie teile ich die Jobs automatisiert zu?

Mein Ansatz:

Code: Alles auswählen

import pandas as pd
from math import radians, sin, cos, atan2, sqrt

# function that calculates the shortes distance between two points given by the latitude and longitude
def distance(lat1, lon1, lat2, lon2):
    R = 6373.0 # approximate radius of earth in km
    lat1 = radians(lat1)
    lon1 = radians(lon1)
    lat2 = radians(lat2)
    lon2 = radians(lon2)

    dlon = lon2 - lon1
    dlat = lat2 - lat1

    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
    c = 2 * atan2(sqrt(a), sqrt(1 - a))

    distance = (R * c)
    return distance # in unit 'kilometers'

# dataframe of all people. Size is always multiple of 9.
d = {
        'latitude': [1.1,1.2,1.1, 1.3,1.3,1.4,1.4,1.4,1.4],
        'longitude': [1.1, 2, 1.1, 1.3, 1.3, 1.8, 1.8, 1.8, 1.8],
        'floor': [3,1,2,2,4,3,2,1,4],
        'id': [1,2,3,4,5,6,7,8,9]
    }

df = pd.DataFrame(data=d)
df.set_index('id', drop=False, inplace=True)



df['host'] = 'None'
df['group'] = 'None'

max_distance = 85

# Sort people for distance
emptyGroupList = df.loc[df['host'] == 'None'].sort_values(['latitude', 'longitude', 'floor'], ascending=True)

print(emptyGroupList)

group = []
groupNumber = 0

for index, person in df.iterrows():
  if len(group) == 3:
    for group_person in group:
      df.at[group_person['id'], 'group'] = groupNumber
    groupNumber += 1
    group = []

  if len(group) == 0:
    group.append(person)
  else: 
    for group_person in group:
      #print(group_person['floor'])
      dist = distance(person['latitude'], person['longitude'], group_person['latitude'], group_person['longitude']) 
      if 0 < dist <= max_distance:
        group.append(person)


print(df)
Leider funktioniert dieser Ansatz noch nicht richtig. Im Beispiel ist das df lediglich 9 Teilnehmer lang. Da alle an unterschiedlichen Orten wohnen (Latitude, Longitude, floor), sollte jeder einen Job zugewiesen bekommen. Was machen ich falsch?

Vielleicht habt ihr einige Ideen. Der Code kann direkt in Google Colab ausgeführt werden. Dort könnt ihr auch gerne Verbesserungen einführen: https://colab.research.google.com/drive ... RzXlpJkvOh
Nach oben
Benutzeravatar
__blackjack__
User
Beiträge: 14052
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:
Kontaktdaten von __blackjack__

@Feynman: Die Bedingung ist halt falsch, was man leicht sehen kann wenn man sich mal die Werte für Paare ausgeben lässt wenn jemand nicht der Gruppe hinzugefügt wird. Da sieht man dann Paare die hinzugefügt werden müssten.

Wenn Du jemanden `group` hinzugefügt hast, solltest Du die Schleife über `group` übrigens abbrechen, sonst kann eine Person mehrfach hinzugefügt werden wenn mehr als eine Person die schon in `group` steht die Bedingung(en) erfüllt.

Sonstige Anmerkungen: Eingerückt wird mit vier Leerzeichen pro Ebene.

Namen schreibt man in Python klein_mit_unterstrichen. Ausnahmen sind Konstanten (KOMPLETT_GROSS) und Klassen (MixedCase).

`distance` ist ein guter Name für einen Wert der einen Abstand darstellt, es ist kein guter Name für eine Funktion die einen Abstand ausrechnet. Funktionen werden üblicherweise nach der Tätigkeit benannt die sie ausführen, um sie von eher passiven Werte unterscheiden zu können. Nur weil die Funktion wie der Wert heisst, musste man sich hier ja für den Wert etwas anderes ausdenken was weniger verständlich ist.

Der Kommentar über der Funktion würde einen besseren Docstring abgeben.

Das die Länge vom Datenrahmen immer durch 9 teilbar ist würde ich nicht als Kommentar dran schreiben, sondern im Code tatsächlich überprüfen.

Eine Zeichenkette mit dem Wert "None" ist eigenartig. Da fragt man sich unweigerlich ob hier nicht der Wert `None` (Typ `NoneType`) gemeint war. Und bei Pandas/Numpy ist das dann auch vom Typ `object` was man eigentlich eher nicht in Datenrahmen/Arrays haben möchte, insbesondere wenn die Spalte/das Array eigentlich *Zahlen* enthalten soll. Andererseits sind 400 Zeilen keine wirklich grosse Datenmenge und ich sehe hier nicht warum man überhaupt einen Datenrahmen verwenden sollte, denn davon wird ja nicht wirklich etwas verwendet‽

Code: Alles auswählen

#!/usr/bin/env python3
from math import atan2, cos, radians, sin, sqrt

import pandas as pd


def calculate_distance(lat1, lon1, lat2, lon2):
    """
    Calculate the shortest distance between two points given by the latitude and
    longitude.
    """
    earth_radius = 6373  # Approximate / in km.
    lat1 = radians(lat1)
    lon1 = radians(lon1)
    lat2 = radians(lat2)
    lon2 = radians(lon2)

    dlon = lon2 - lon1
    dlat = lat2 - lat1

    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
    c = 2 * atan2(sqrt(a), sqrt(1 - a))
    return earth_radius * c  # in km.


def main():
    #
    # TODO Why a `DataFrame`?
    #
    all_persons = pd.DataFrame(
        {
            "latitude": [1.1, 1.2, 1.1, 1.3, 1.3, 1.4, 1.4, 1.4, 1.4],
            "longitude": [1.1, 2, 1.1, 1.3, 1.3, 1.8, 1.8, 1.8, 1.8],
            "floor": [3, 1, 2, 2, 4, 3, 2, 1, 4],
            "id": [1, 2, 3, 4, 5, 6, 7, 8, 9],
        }
    )
    assert len(all_persons) % 9 == 0
    all_persons.set_index("id", drop=False, inplace=True)
    
    all_persons["host"] = None
    all_persons["group"] = None

    max_distance = 85
    group_number = 0
    group = []
    for _, candidate in all_persons.iterrows():
        if len(group) == 3:
            for person in group:
                all_persons.at[person["id"], "group"] = group_number
            group_number += 1
            group = []

        if len(group) == 0:
            group.append(candidate)
        else:
            for person in group:
                distance = calculate_distance(
                    candidate["latitude"],
                    candidate["longitude"],
                    person["latitude"],
                    person["longitude"],
                )
                if 0 < distance <= max_distance:
                    group.append(candidate)
                    break

                print("\n>", candidate, person, "distance:", distance)

    print(all_persons)


if __name__ == "__main__":
    main()
“Vir, intelligence has nothing to do with politics!” — Londo Mollari
Nach oben
Feynman
User
Beiträge: 3
Registriert: Montag 6. Januar 2020, 15:39

Hi blackjack

Erstmal vielen Dank für deine Antwort und deine präzisen Erklärungen. Als Python-Anfänger konnte ich da einiges lernen. Echt super das du alles so genau erklärst.

Ich habe jedoch einige Fragen:

Wie wende ich deine Lösung konkret an? Kannst du vielleicht ein Beispiel geben? Du kannst gerne auch direkt in das Google Colab (siehe Link von post 1) schreiben.

Am besten wäre es doch, wenn ich eine Funktion (z.B. give_job_to_person) hätte, die als Argument die Input Daten einliest (in diesem Fall das besagte dataframe df) und als Output das Dataframe mit den entsprechenden Jobs ausgibt (z.B. df_jobs):

Code: Alles auswählen

give_job_to_person(df)
Momentan weiß ich nicht genau warum du das df in die main-Funktion gelegt hast und warum du diese main-Funktion auf diese Weise aufrufst.

Von der Logik der Funktion sieht das nun wirklich besser aus als zuvor und ich hab auch das Gefühlt das es so klappen könnte. Wie gesagt, ich versteh aber nicht genau wie ich deine Lösung konkret auf ein df anwende.

Ich habe ein dataframe welches sehr lang werden kann. Die Struktur und ein vereinfachtes Beispiel hatte ich ja bereits angegeben. In Realität ist es jedoch länger und die Koordinaten sind auch realistischer und nicht irgendwelche Zahlen.
Nach oben
Feynman
User
Beiträge: 3
Registriert: Montag 6. Januar 2020, 15:39

Hey, auch wenn es schon etwas her ist, beschäftigt mich das Thema noch sehr. Es gibt noch ein kleines Problem und ich hoffe du (oder jemand anderes) kann mir dabei helfen. Dafür habe ich extra ein Beispiel angefertigt, was sofort ausgeführt werden kann. Ich hoffe es schreckt nicht ab. Die Frage die ich habe, ist eigentlich ganz simpel und kann evtl. sehr leicht beantwortet werden.

Zuerst die Daten:

Code: Alles auswählen

array_data=([[ 50.56419  ,   8.67667  ,   2.       , 160.       ],
   [ 50.5643136,   8.6772816,   3.       ,  89.       ],
   [ 50.5646274,   8.6763909,   0.       , 259.       ],
   [ 50.5661047,   8.6765931,   1.       , 100.       ],
   [ 50.5663442,   8.6575205,   1.       , 117.       ],
   [ 50.56686  ,   8.67598  ,   1.       ,  95.       ],
   [ 50.56747  ,   8.67604  ,   2.       , 199.       ],
   [ 50.56762  ,   8.6702799,   0.       , 148.       ],
   [ 50.5693473,   8.6640855,  -1.       ,  50.       ],
   [ 50.5693473,   8.6640855,   0.       , 111.       ],
   [ 50.5705819,   8.6597279,   2.       , 183.       ],
   [ 50.57067  ,   8.65694  ,   2.       , 257.       ],
   [ 50.57075  ,   8.65748  ,   1.       , 211.       ],
   [ 50.57075  ,   8.65748  ,   1.       , 292.       ],
   [ 50.5722461,   8.6598248,   2.       , 142.       ],
   [ 50.57254  ,   8.65895  ,   1.       , 116.       ],
   [ 50.57259  ,   8.6592   ,   2.       , 228.       ],
   [ 50.5731636,   8.667609 ,   1.       , 181.       ],
   [ 50.5737814,   8.6720067,   0.       , 173.       ],
   [ 50.5740356,   8.6718179,   1.       ,   5.       ],
   [ 50.5746321,   8.6831284,   3.       , 202.       ],
   [ 50.5747453,   8.6765588,   4.       , 119.       ],
   [ 50.5748992,   8.6611471,   2.       , 260.       ],
   [ 50.5748992,   8.6611471,   3.       , 102.       ],
   [ 50.575    ,   8.65985  ,   2.       , 267.       ],
   [ 50.5751   ,   8.66027  ,   2.       ,   7.       ],
   [ 50.5751   ,   8.66027  ,   2.       ,  56.       ],
   [ 50.57536  ,   8.67741  ,   1.       , 194.       ],
   [ 50.57536  ,   8.67741  ,   1.       , 282.       ],
   [ 50.5755255,   8.6884584,   0.       , 276.       ],
   [ 50.5755273,   8.674282 ,   3.       , 167.       ],
   [ 50.57553  ,   8.6826   ,   2.       , 273.       ],
   [ 50.5755973,   8.6847492,   0.       , 168.       ],
   [ 50.5756757,   8.6846139,   4.       , 255.       ],
   [ 50.57572  ,   8.65965  ,   0.       ,  66.       ],
   [ 50.57591  ,   8.68175  ,   1.       , 187.       ]])
Daraus machen wir schnell ein Dataframe:

Code: Alles auswählen

df = pd.DataFrame(data=array_data) # convert back to dataframe

df.rename(columns={0: 'latitude', 1: 'longitude', 2:'floor', 3:'id'}, inplace=True) # rename columns
Nun haben wir die Daten wie sie mir im Jupyter Notebook vorliegen.

Zuerst definieren wir die Funktion zur Berechnung der Abstände:

Code: Alles auswählen


def calculate_distance(lat1, lon1, lat2, lon2):
    """
    Calculate the shortest distance between two points given by the latitude and
    longitude.
    """
    earth_radius = 6373  # Approximate / in km.
    lat1 = radians(lat1)
    lon1 = radians(lon1)
    lat2 = radians(lat2)
    lon2 = radians(lon2)

    dlon = lon2 - lon1
    dlat = lat2 - lat1

    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
    c = 2 * atan2(sqrt(a), sqrt(1 - a))
    return earth_radius * c  # in km.
Soweit so gut!
Als nächstes kommt die Funktion um die es hier eigentlich gehen soll. Ich möchte Leute die nicht am selben Ort leben (latitude, longitude, floor) in groups zuordnen. Das heißt, am Ende soll jeder in genau einer group sein. Die Größe einer group besteht immer aus 3 Personen. Diese haben, wie gesagt, unterschiedliche Ortkoordinaten.

Code: Alles auswählen

def main(all_persons, max_distance_parameter):

    assert len(all_persons) % 9 == 0
    all_persons.set_index("id", drop=False, inplace=True)
    
    all_persons["host"] = np.nan
    all_persons["group"] = np.nan

    Streufaktor = 0.0001 
    max_distance = max_distance_parameter
    group_number = 0
    group = []
    for _, candidate in all_persons.iterrows():
        if len(group) == 3:
            for person in group:
                all_persons.at[person["id"], "group"] = group_number
            group_number += 1
            group = []

        if len(group) == 0:
            group.append(candidate)
        else:
            for person in group:
                distance = calculate_distance(
                    candidate["latitude"],
                    candidate["longitude"],
                    person["latitude"],
                    person["longitude"],
                )
                distance = distance 

                if candidate['floor'] == -1:                 # consider the floor when calculating the distance 
                  distance = distance + Streufaktor + 0.001
                elif candidate['floor'] == 0:
                  distance = distance + Streufaktor + 0.002
                elif candidate['floor'] == 1:
                  distance = distance + Streufaktor + 0.003
                elif candidate['floor'] == 2:
                  distance = distance + Streufaktor + 0.004
                elif candidate['floor'] == 3:
                  distance = distance + Streufaktor + 0.005
                elif candidate['floor'] == 4:
                  distance = distance + Streufaktor + 0.006
                elif candidate['floor'] == 5:
                  distance = distance + Streufaktor + 0.007
                elif candidate['floor'] == 6:
                  distance = distance + Streufaktor + 0.008
                elif candidate['floor'] == 7:
                  distance = distance + Streufaktor + 0.009
                elif candidate['floor'] == 8:
                  distance = distance + Streufaktor + 0.010
                elif candidate['floor'] == 9:
                  distance = distance + Streufaktor + 0.011
                elif candidate['floor'] == 10:
                  distance = distance + Streufaktor + 0.012
                elif candidate['floor'] == 11:
                  distance = distance + Streufaktor + 0.013
                elif candidate['floor'] == 12:
                  distance = distance + Streufaktor + 0.014
                elif candidate['floor'] == 13:
                  distance = distance + Streufaktor + 0.015
                elif candidate['floor'] == 14:
                  distance = distance + Streufaktor + 0.016
                else:
                  distance = distance + Streufaktor + 0.017
                  
                if 0 < distance <= max_distance:
                    group.append(candidate)
                    break
Nun wende ich die Funktion an. Aus irgendwelchen Gründen, funktioniert die Funktion am besten wenn ich einen besonders hohen Wert für max_distance angebe:

Code: Alles auswählen

sort_people(df, 80000)
Da immer 3 Personen nicht einer group zugewiesen werden, mache ich das nun im letzten Schritt:

Code: Alles auswählen

all_persons = all_persons.reset_index(drop=True)

# get all rows where column "group" is NaN
nan_rows = all_persons[all_persons['group'].isnull()] 

nan_index = nan_rows.index # get index of all rows where column "group" is NaN

# replace all values where column "group" is NaN with value x 
for index in nan_index:
  all_persons.iloc[index, all_persons.columns.get_loc('group')] = (max_group_value[0] +1)
Eigentlich wäre ich nun fertig. Es gibt jedoch ein Problem:

Wenn ich das dataframe teste auf duplicate, stelle ich fest, dass es Leute gibt, die in der selben group sind und die selben Ortskoordinaten teilen. Aber das sollte ja eigentlich durch die Funktion sort_people() verhindert werden. Was läuft da schief?

Code: Alles auswählen

# check if function works!
duplication_parameters = ['latitude', 'longitude', 'floor', 'group']

duplicate_bool = all_persons.duplicated(subset = duplication_parameters, keep=False)
duplicate = all_persons.loc[duplicate_bool == True]
duplicate.sort_values(duplication_parameters, ascending=True, inplace=False )
Ich hoffe ihr könnt mir helfen!
Nach oben
Antworten

Zurück zu „Allgemeine Fragen“