The　k-means　problem　is　a　classic　NP-hard　problem　in　machine　learning　and　computational　geometry.　And　its　goal　is　to　separate　the　given　set　into　k　clusters　according　to　the　minimal　squared　distance.　The　k-means　problem　with　penalties,　as　one　generalization　of　k-means　problem,　allows　that　some　point　need　not　be　clustered　instead　of　being　paid　some　penalty.　In　this　paper,　we　study　the　k-means　problem　with　penalties　by　using　the　seeding　algorithm.　We　propose　that　the　accuracy　only　involves　the　ratio　of　the　maximal　penalty　value　to　the　minimal　one.　When　the　penalty　is　uniform,　the　approximation　factor　reduces　to　the　same　one　for　the　k-means　problem.　Moreover,　our　result　generalizes　the　k-means++　for　k-means　problem　to　the　penalty　version.　Numerical　experiments　show　that　our　seeding　algorithm　is　more　effective　than　the　one　without　using　seeding.