K-means segmentation algorithm can be applied to customer segmentation in banks. If loan over-due amount of bank customers are normally distributed, then k-means can be used. In cases of significant outliers, k-means segmentation algorithm cannot be applied. In the authors’ proposed solution, bank loan customers are segmented based on security value and loan overdue amount. Proposed solution addresses segmentation issues on outliers and provides security value based heuristic approach as a replacement to k-means segmentation.