Clustering algorithms are essential in data mining and pattern recognition for grouping unlabeled data into meaningful clusters based on similarities. Among them, K-Means is widely used due to its simplicity and efficiency but suffers from sensitivity to initial centroid selection and inability to capture feature dependencies. This study proposes an Enhanced Mutual Information-based K-Means (MIK-Means) algorithm combined with Triangle Inequality and Lower Bound (TILB) seeding to improve clustering accuracy and computational efficiency, particularly in the context of network traffic classification for cybersecurity applications. The TILB method accelerates the initialization phase by reducing redundant distance calculations using mathematical pruning techniques, thereby selecting well-distributed initial centroids efficiently. Meanwhile, MIK-Means incorporates mutual information as a similarity measure during clustering assignment, enabling the algorithm to capture complex statistical dependencies among features, which traditional Euclidean distance metrics fail to address. The combination of these two approaches results in a robust clustering framework capable of handling large-scale, high-dimensional, and noisy datasets commonly found in network intrusion detection. The proposed method was evaluated on several benchmark datasets including Darpa 1998-99, KDD Cup99, NSL-KDD, UNSW-NB15, and CAIDA. Comparative experiments with state-of-the-art algorithms such as K-Means++, K-NNDP, and DI-K-Means showed that the proposed approach consistently outperformed or matched competitors in terms of Silhouette Coefficient, Calinski-Harabasz index, and Davies-Bouldin index, indicating better cluster cohesion, separation, and compactness. Additionally, the computational efficiency gained from TILB seeding facilitates faster convergence without compromising clustering quality. Furthermore, a threshold-based cluster labeling mechanism was applied to translate clustering results into practical classifications for detecting attacks versus normal traffic, enhancing the usability of the method in real-world cybersecurity systems. Overall, this research demonstrates that the integration of TILB seeding and mutual information-based clustering provides an effective and efficient solution for network traffic classification challenges.