Unsupervised learning looks for structure in unlabeled data: there is no supplied correct output for each input. Clustering groups objects by similarity; dimensionality reduction is another approach. For example, a self-driving vehicle could group similar intersections or roundabouts without being given labels for those categories. section 11.2
Methods include k-means, DBSCAN, principal component analysis, autoencoders, and self-organizing maps (SOMs). A SOM uses competitive learning rather than the error-correction learning used by other neural networks. It can also serve as a practical heuristic for the traveling-salesperson problem (TSP): arrange a network around city coordinates, then extract and measure a route. section 11.2 section 11.10 section 11.8
A SOM-based TSP experiment follows a short loop:
- Read a TSP instance, normalize city coordinates to [0, 1], and initialize a network of neurons. section 11.8
- Sample a city, find its closest network neuron, and move neurons toward the city according to a neighborhood weight and learning rate. Repeat for the chosen number of iterations. section 11.8
- Extract the route and track its length. Experiment with neuron count, neighborhood width, learning rate, and iterations rather than assuming one setting is best. section 11.8
route_lengths = [] #1
paths_x = [] #2
paths_y = [] #2
for i in tqdm(range(iterations)): #3
if not i % 100:
print('\t> Iteration {}/{}'.format(i, iterations), end="\r") #4
city = cities.sample(1)[['x', 'y']].values #5
winner_idx = select_closest(network, city) #6
gaussian = get_neighborhood(winner_idx, number_of_neurons // 10,
network.shape[0]) #7
network += gaussian[:, np.newaxis] * learning_rate * (city - network) #8
paths_x.append(network[:, 0].copy()) #9
paths_y.append(network[:, 1].copy()) #9
learning_rate = learning_rate * 0.99997 #10
number_of_neurons = number_of_neurons * 0.9997 #10
if not i % 1000: #11
plot_network(cities, network, name='diagrams/{:05d}.png'.format(i))
if number_of_neurons < 1: #12
print('Radius has completely decayed, finishing execution',
'at {} iterations'.format(i))
break
if learning_rate < 0.001:
print('Learning rate has completely decayed, finishing execution',
'at {} iterations'.format(i))
break
route = get_route(cities, network) #13
problem = problem.reindex(route) #13
distance = route_distance(problem) #13
route_lengths.append(distance) #13
else:
print('Completed {} iterations.'.format(iterations)) #14
#1 Store the lengths of the TSP routes during the SOM training iterations.
#2 Store the x and y coordinates of the neurons in the network during the training iterations.
#3 Training loop
#4 Print only if the current iteration index is a multiple of 100.
#5 Choose a random city.
#6 Find the index of the neuron (winner) in the SOM network that is closest to the randomly chosen city.
#7 Generate a filter that applies changes to the winner’s gaussian.
#8 Update the network’s weights.
#9 Append the current coordinates to the paths.
#10 Decay the learning rate and the neighborhood radius n at each iteration to gradually reduce the influence of the Gaussian filter over time.
#11 Check for the plotting interval.
#12 Check if any parameter has completely decayed.
#13 Calculate distance, and store it in the route_lengths list.
#14 Indicate that the specified number of training iterations has been completed.
The training-loop listing shows city sampling, winner selection, neighborhood weighting, and the network update in Python. section 11.8
Qatar TSP: useful route, not guaranteed optimum
On qa194.tsp, one SOM run ends with a route length of 9,816; the stated optimum is 9,352. A MiniSom-based implementation produces 11,844.47 on the same instance. Compare measured routes and tune parameters: an unlabeled learning approach can produce a candidate solution without ensuring an optimal one. section 11.8
