K-means 알고리즘은 주어진 데이터를 k개의 클러스터로 묶는 클러스터링 알고리즘입니다.
기계 학습에서는 비지도 학습에 속하며, 클러스터링 알고리즘에서 중요한 역할을 차지합니다.
K-means 알고리즘은 다음과 같은 절차로 작동합니다:
1.
랜덤으로 선택된 k개의 데이터를 기준으로, 가장 가까운 데이터 포인트들을 동일한 클러스터로 할당합니다.
2.
각 클러스터의 중심점을 계산하고, 해당 중심점을 기준으로 다시 클러스터를 재조정합니다.
3.
클러스터 중심점이 더 이상 변경되지 않을 때까지 이 과정을 반복하여 최적의 클러스터를 찾습니다.
K-means 알고리즘은 단순하고 효율적이지만, 클러스터 수 k를 사전에 정해야 하는 특징이 있습니다.
Scikit-learn과 같은 머신러닝 라이브러리를 사용하면 K-means 알고리즘을 직접 구현할 필요 없이 쉽게 클러스터링을 적용할 수 있습니다.
예를 들어, 100명의 고객의 위도와 경도 데이터를 이용해 최적의 창고 위치 3개를 선정하는 문제에서 K-means 클러스터링 알고리즘을 사용할 수 있습니다. 고객의 위치 데이터를 3개의 클러스터로 묶고, 각 클러스터의 중심점을 창고 위치로 설정하는 방식입니다.
전체 소스
from sklearn.cluster import KMeans
import pandas as pd
import folium
def main():
#Warehouse 갯수
k = 3
restaurantDf = makeInput()
locList = [[0]*2 for i in range(len(restaurantDf))]
for idx, row in restaurantDf.iterrows():
locList[idx][0] = float(row['LAT'])
locList[idx][1] = float(row['LON'])
#Clustering
clusteringModel = KMeans(n_clusters=k, init='k-means++')
clusteringModel.fit(locList)
map = folium.Map(location=[37.1382167251, 127.3114503751])
for i in range(len(restaurantDf)):
color = ""
if clusteringModel.labels_[i] == 0:
color = "red"
if clusteringModel.labels_[i] == 1:
color = "blue"
if clusteringModel.labels_[i] == 2:
color = "orange"
folium.Marker([locList[i][0], locList[i][1]], icon = folium.Icon(color=color)).add_to(map)
#Warehouse Locations
for element in clusteringModel.cluster_centers_:
folium.Marker([element[0], element[1]], icon=folium.Icon(color='gray',icon='star')).add_to(map)
map.save('kmeansResult.html')
def makeInput():
restaurant = [
['LOC_0001', '고양시', '37.6699528060', '126.8554585712'],
['LOC_0002', '고양시', '37.6971520856', '126.8196849679'],
['LOC_0003', '고양시', '37.6737965993', '126.7754243376'],
['LOC_0004', '고양시', '37.6821145400', '126.7535463209'],
['LOC_0005', '과천시', '37.4277514160', '126.9920513446'],
['LOC_0006', '과천시', '37.4410791763', '127.0104554264'],
['LOC_0007', '광주시', '37.4992915278', '127.3027287142'],
['LOC_0008', '광주시', '37.3456586222', '127.1817497660'],
['LOC_0009', '광주시', '37.3398340658', '127.3356487393'],
['LOC_0010', '광주시', '37.4988495961', '127.3025714906'],
['LOC_0011', '광주시', '37.4771884535', '127.1821089446'],
['LOC_0012', '광주시', '37.3969132174', '127.2335940567'],
['LOC_0013', '광주시', '37.4778648562', '127.3511585039'],
['LOC_0014', '김포시', '37.6598939546', '126.6656656950'],
['LOC_0015', '김포시', '37.7312343266', '126.5260317627'],
['LOC_0016', '김포시', '37.6219227553', '126.7226238685'],
['LOC_0017', '남양주시', '37.7496438017', '127.2086783633'],
['LOC_0018', '남양주시', '37.6463075748', '127.3058545873'],
['LOC_0019', '남양주시', '37.7450001929', '127.2079587740'],
['LOC_0020', '남양주시', '37.6580785222', '127.2948606613'],
['LOC_0021', '남양주시', '37.7493163194', '127.2074650581'],
['LOC_0022', '동두천시', '37.9052438433', '127.0526923103'],
['LOC_0023', '동두천시', '37.9035354078', '127.0513831636'],
['LOC_0024', '동두천시', '37.9064954987', '127.0644013502'],
['LOC_0025', '동두천시', '37.8908018400', '127.0566123836'],
['LOC_0026', '동두천시', '37.9029587869', '127.0538094986'],
['LOC_0027', '부천시', '37.5035236772', '126.7620258315'],
['LOC_0028', '부천시', '37.5063329471', '126.7515325472'],
['LOC_0029', '부천시', '37.5147426141', '126.8138873897'],
['LOC_0030', '부천시', '37.5269360205', '126.8058649020'],
['LOC_0031', '부천시', '37.5030341284', '126.7805625009'],
['LOC_0032', '부천시', '37.5198204179', '126.7900314838'],
['LOC_0033', '부천시', '37.5238039668', '126.8097303400'],
['LOC_0034', '성남시', '37.3589256866', '127.1230193698'],
['LOC_0035', '성남시', '37.4212308831', '127.1016185455'],
['LOC_0036', '성남시', '37.4630729599', '127.1689498109'],
['LOC_0037', '성남시', '37.4615481492', '127.1558057480'],
['LOC_0038', '성남시', '37.4169832834', '127.1344363205'],
['LOC_0039', '수원시', '37.3062283022', '127.0006673650'],
['LOC_0040', '수원시', '37.2780234393', '127.0406385621'],
['LOC_0041', '수원시', '37.2876000885', '127.0167086820'],
['LOC_0042', '수원시', '37.2468926793', '127.0557111821'],
['LOC_0043', '수원시', '37.3069449243', '127.0147568265'],
['LOC_0044', '수원시', '37.2915640479', '127.0504732206'],
['LOC_0045', '수원시', '37.2730696429', '126.9723723275'],
['LOC_0046', '수원시', '37.2737747878', '127.0492142019'],
['LOC_0047', '수원시', '37.2817865208', '126.9724694093'],
['LOC_0048', '수원시', '37.2742267822', '127.0287166267'],
['LOC_0049', '수원시', '37.2581805115', '127.0328989333'],
['LOC_0050', '수원시', '37.2808998463', '126.9737502924'],
['LOC_0051', '수원시', '37.2587743497', '127.0303466174'],
['LOC_0052', '수원시', '37.2759603301', '127.0294390047'],
['LOC_0053', '수원시', '37.2665453057', '127.0062077815'],
['LOC_0054', '수원시', '37.2855805568', '126.9583188924'],
['LOC_0055', '수원시', '37.3149390687', '127.0014674565'],
['LOC_0056', '시흥시', '37.3859529890', '126.8401627128'],
['LOC_0057', '시흥시', '37.3473228929', '126.7329946337'],
['LOC_0058', '시흥시', '37.3513047782', '126.7229955822'],
['LOC_0059', '안산시', '37.3584852392', '126.8220989209'],
['LOC_0060', '안산시', '37.3360457748', '126.8502513353'],
['LOC_0061', '안산시', '37.2916416855', '126.8304611688'],
['LOC_0062', '안산시', '37.2825222625', '126.8470568385'],
['LOC_0063', '안산시', '37.3136027749', '126.8326702103'],
['LOC_0064', '안산시', '37.2937728261', '126.8722884714'],
['LOC_0065', '안산시', '37.3016898071', '126.8510886317'],
['LOC_0066', '안산시', '37.3189003905', '126.8274543496'],
['LOC_0067', '안성시', '37.0149959069', '127.2034579297'],
['LOC_0068', '안성시', '37.0367419397', '127.3714092154'],
['LOC_0069', '안양시', '37.4118002524', '126.9111036546'],
['LOC_0070', '안양시', '37.4179241084', '126.9191133005'],
['LOC_0071', '안양시', '37.4023181615', '126.9504858297'],
['LOC_0072', '안양시', '37.3940395160', '126.9613578915'],
['LOC_0073', '양주시', '37.7811156739', '127.0295140877'],
['LOC_0074', '양주시', '37.9076372438', '127.0065728358'],
['LOC_0075', '양주시', '37.7934964587', '127.0888606835'],
['LOC_0076', '양주시', '37.7849242640', '126.9937618394'],
['LOC_0077', '양주시', '37.7758002468', '126.9356283570'],
['LOC_0078', '양평군', '37.5352268162', '127.4671754909'],
['LOC_0079', '양평군', '37.4936033784', '127.4734269154'],
['LOC_0080', '여주시', '37.2145722794', '127.5802137871'],
['LOC_0081', '여주시', '37.2568394331', '127.6531870348'],
['LOC_0082', '여주시', '37.3185910690', '127.6485946251'],
['LOC_0083', '여주시', '37.4031973764', '127.5489582384'],
['LOC_0084', '연천군', '37.9897043024', '126.9206352812'],
['LOC_0085', '오산시', '37.1785982389', '127.0244560122'],
['LOC_0086', '오산시', '37.1774158872', '127.0240804100'],
['LOC_0087', '오산시', '37.1819471000', '127.0370076234'],
['LOC_0088', '오산시', '37.1868046144', '127.0120339544'],
['LOC_0089', '용인시', '37.3274739465', '127.1737784768'],
['LOC_0090', '용인시', '37.3231024501', '127.0454433819'],
['LOC_0091', '용인시', '37.3280639271', '127.0962075693'],
['LOC_0092', '용인시', '37.1382167251', '127.3114503751'],
['LOC_0093', '용인시', '37.2608624281', '127.2799286839'],
['LOC_0094', '용인시', '37.2224807513', '127.1033876860'],
['LOC_0095', '용인시', '37.2364221748', '127.2039907925'],
['LOC_0096', '용인시', '37.3303506971', '127.1283772195'],
['LOC_0097', '의왕시', '37.3497876203', '126.9626000497'],
['LOC_0098', '의왕시', '37.3519805191', '126.9711656591'],
['LOC_0099', '의정부시', '37.7497577536', '127.0717920267'],
['LOC_0100', '의정부시', '37.7455788063', '127.0904425858']]
restaurantDf = pd.DataFrame(restaurant, columns = ['ID', 'CITY', 'LAT', 'LON'])
return restaurantDf
if __name__ == '__main__':
main()
Python
복사
결과는 아래와 같습니다.
빨간색, 파란색, 오랜지색의 3개의 색상으로 구분된 클러스터를 확인 할 수 있습니다.
창고의 위치는 각 클러스터의 중심점으로 생각 할 수 있습니다.
Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Google OR Tools
Reference
