[Python] use a priority queue to do hierarchical clustering without import heapq

I am using priority queue to do the hierarchical clustering(can not import heapq), and want to use the complete-link method, but I don't know what is the problem of my code, the reason is far from what I expected...by the way the data I use to cluster is 1095 documents which are stored in a data folder.

from nltk.stem.porter import PorterStemmer
import os
import numpy as np

porter_stemmer = PorterStemmer()


script_dir = os.path.dirname(__file__)
txt_folder_path = os.path.join(script_dir, 'data')
output_folder = os.path.join(script_dir, 'output')
sw_path = os.path.join(script_dir, 'stopwords.txt')
docfreq = {}


with open(sw_path, 'r') as sw:
stopwords = set(sw.read().splitlines())


txt_files = [f for f in os.listdir(txt_folder_path) if f.endswith('.txt')]
N = len(txt_files)

for filename in txt_files:
file_path = os.path.join(txt_folder_path, filename)


with open(file_path, 'r') as f:
data = f.read().lower()

adjusted = [word for word in data.split() if word.isalpha() and not any(char.isdigit() for char in word)]
text = " ".join(adjusted).split()
filtered_sentence = [w for w in text if w not in stopwords]
stemming = [porter_stemmer.stem(w) for w in filtered_sentence]
termfreq = {}
totalword = len(stemming)
unique_words_in_doc = set(stemming)


for word in unique_words_in_doc:
docfreq[word] = docfreq.get(word, 0) + 1

for word in stemming:
termfreq[word] = termfreq.get(word, 0) + 1
for word in termfreq:
termfreq[word] /= totalword


termfreq_file_path = os.path.join(output_folder, filename)
with open(termfreq_file_path, 'w', encoding='utf-8') as termfreq_file:
termfreq_file.write(f"{'term':<20}{'termfreq':<20}\n")
for term, freq in sorted(termfreq.items()):
termfreq_file.write(f"{term:<20}{freq:<20}\n")

sorted_terms = sorted(docfreq.items(), key=lambda x: x[0].lower())
result = [[i, doc, freq] for i, (doc, freq) in enumerate(sorted_terms, 1)]


def log(x, base):
return np.log(x) / np.log(base)

index_mapping = {term: i for i, (term, _) in enumerate(sorted_terms, 1)}

for filename in txt_files:
file_path = os.path.join(output_folder, filename)
termfreq = {}
with open(file_path, 'r', encoding='utf-8') as f:
next(f)
for line in f:
parts = line.split()
if len(parts) == 2:
word = parts[0]
try:
tf = float(parts[1])
termfreq[word] = tf
except ValueError:
continue

tf_idf = {}
for word in sorted(termfreq.keys()):
df = docfreq.get(word, 0)
if df > 0:
tf = termfreq[word]
idf = log(N / df, 10)
tf_idf[word] = tf * idf

tf_idf_file_path = os.path.join(output_folder, filename)
with open(tf_idf_file_path, 'w', encoding='utf-8') as tf_idf_file:
tf_idf_file.write(f"{'t_index':<8}{'tf-idf':<20}\n")
for term, value in sorted(tf_idf.items()):
index = index_mapping.get(term, 0)
tf_idf_file.write(f"{index:<8}{value:<20}\n")


def load_tfidf_vector(doc_filename):
tfidf_vector = {}
file_path = os.path.join(output_folder, doc_filename)

with open(file_path, 'r', encoding='utf-8') as file:
next(file)
for line in file:
parts = line.split()
if len(parts) == 2:
term_index = int(parts[0])
tfidf_value = float(parts[1])
tfidf_vector[term_index] = tfidf_value

return tfidf_vector

def cosine(Docx, Docy):
vec_x = load_tfidf_vector(Docx)
vec_y = load_tfidf_vector(Docy)

all_indices = set(vec_x.keys()).union(set(vec_y.keys()))

x_vector = np.array([vec_x.get(i, 0.0) for i in all_indices])
y_vector = np.array([vec_y.get(i, 0.0) for i in all_indices])

dot_product = np.dot(x_vector, y_vector)
norm_x = np.linalg.norm(x_vector)
norm_y = np.linalg.norm(y_vector)

if norm_x == 0 or norm_y == 0:
return 0.0

return dot_product / (norm_x * norm_y)

def hierarchical_clustering(documents, num_clusters):
N = len(documents)
C = np.zeros((N, N)) # Similarity matrix
I = [1] * N # Indicator: 1 = active, 0 = merged
clusters = {i: for i in range(N)} # Initialize each document as its own cluster

# Compute initial pairwise similarities
for n in range(N):
for i in range(n + 1, N): # Only compute for i > n
similarity = cosine(documents[n], documents)
C[n] = similarity
C[n] = similarity # Symmetric

# Perform hierarchical clustering
for _ in range(N - 1): # Perform N-1 merges
# Find the most similar clusters to merge
max_sim = -float('inf')
i, m = -1, -1

for x in range(N):
for y in range(x + 1, N):
if I[x] == 1 and I[y] == 1 and C[x][y] > max_sim:
max_sim = C[x][y]
i, m = x, y

# Merge clusters
clusters.extend(clusters[m])
clusters[m] = [] # Clear the merged cluster
I[m] = 0 # Mark cluster m as merged

# Update similarities for the merged cluster
for j in range(N):
if I[j] == 1 and j != i: # Update only active clusters
new_sim = min(C[j], C[m][j])
C[j] = C[j] = new_sim # Update similarity matrix

# Stop if the desired number of clusters is reached
if sum(I) == num_clusters:
break

# Extract the final clusters
final_clusters = [sorted(clusters[key]) for key in sorted(clusters.keys()) if len(clusters[key]) > 0]
return final_clusters

def save_clusters_to_file(clusters, k, cluster_folder):
file_name = f"{k}.txt"
file_path = os.path.join(cluster_folder, file_name)

with open(file_path, 'w', encoding='utf-8') as f:
for cluster in clusters:
cluster = sorted(cluster) # Sort doc IDs in ascending order
f.write("\n".join(map(str, cluster))) # Write cluster separated by empty line

print(f"Clustering results saved to {file_path}")

# Create cluster folder if it doesn't exist
cluster_folder = os.path.join(script_dir, 'cluster')
os.makedirs(cluster_folder, exist_ok=True)

# Perform clustering and save results for k=8, k=13, k=20
for k in [8, 13, 20]:
clusters = hierarchical_clustering(txt_files, k)
save_clusters_to_file(clusters, k, cluster_folder)


I want it to correctly clustering for 8,13,20 clusters.and the result will be saved in a txt. like the image I attached.

Continue reading...