If I were to do this, instead of using a hash and naming the clasess, I would use an array of classes where each array is a class. Then to add works you look at each class and and the word to the first class where the average distance from the new word to each word in the collection is below a certain threshold. That is what I've done below. To make it even better you could scan every class and add it to the class that has the lowest average distance. I also only added the word once, and if its already added skipped it.

#!/usr/bin/perl 
use strict;
use warnings;
use Text::Levenshtein qw/fastdistance/;
use Data::Dumper;

my $classes = [];
my $index   = {};
my $limit   = 0.5;

sub avg_distance {
    my ($new_word, $class) = @_;
    my $distance = 0;
    for my $word (@$class) {
        $distance += fastdistance($new_word, $word);
    }
    return $distance / @$class;
}

sub put_or_create {
    my ($w) = @_;
    $w =~ s/[^a-z]//g;
    my $found=0;
    return if exists $index->{$w};
    foreach my $class ( @$classes ) {
        if((avg_distance($w,$class)/length($w)) < $limit) {
            push @$class, $w;
            $index->{$w} = $class;
            $found = 1;
            last;
        };
    };
    if(! $found) {
        my $class = [$w];
        push @$classes, $class;
        $index->{$w} = $class;
    };
};



#watch for an error opening the file
open( my $file,"<", "possible_locations.txt") or die "Failed to open f
+ile: $!";
my @locations = <$file>;
#remove the line endings
chomp(@locations);

my $count = 0;
for (@locations) {
    #last if ++$count/@locations > 0.2;#not all
    put_or_create($_)
}

for (@$classes) {
    print join(",", sort @$_), "\n";
}
[download]

This approaches might need some improvement. The first that comes to mind is add the word to the class/set that is closest, then divide that set up when the average distance becomes too great. I might even give that a shot as it sounds fun!