k-means初探

type (
    Point struct {
        X float64 `json:"x"`
        Y float64 `json:"y"`
    }

    Res struct {
        Center Point   `json:"center"`
        Group  []Point `json:"group"`
    }
)

func (p Point) Fmt() string {
    return fmt.Sprintf("x:%.1f,y:%.1f", p.X, p.Y)
}

func NewPoint(x, y float64) Point {
    return Point{
        X: x,
        Y: y,
    }
}

func newGroup(k int) [][]Point {
    groups := make([][]Point, k)
    for i := 0; i < k; i++ {
        groups[i] = make([]Point, 0)
    }
    return groups
}

func getDistances(center, data []Point) [][]float64 {
    distances := make([][]float64, len(center))
    for i := 0; i < len(center); i++ {
        currCenter := center[i]
        distances[i] = make([]float64, len(data))
        for j, c := range data {
            distances[i][j] = Calc(c, currCenter)
        }
    }
    return distances
}

func splitGroup(groups [][]Point, data []Point, distances [][]float64) {
    for i, v := range data {
        minIndex := 0
        minValue := math.MaxFloat64
        for j := 0; j < len(groups); j++ {
            curr := distances[j][i]
            if curr < minValue {
                minValue = curr
                minIndex = j
            }
        }
        groups[minIndex] = append(groups[minIndex], v)
    }
}

func Calc(p1, p2 Point) float64 {
    if p1.X == p2.X && p1.Y == p2.Y {
        return 0
    }
    p3 := []float64{p1.X - p2.X, p1.Y - p2.Y}
    return math.Sqrt(sum(power(p3, 2)))
}

func sum(i []float64) float64 {
    s := float64(0)
    for _, v := range i {
        s += v
    }
    return s
}

func power(i []float64, f float64) []float64 {
    r := make([]float64, len(i))
    for i, v := range i {
        r[i] = math.Pow(v, f)
    }
    return r
}

func getCenter(g [][]Point) []Point {
    newCenter := make([]Point, len(g))
    for i, v := range g {
        sumX, sumY := float64(0), float64(0)
        for j := range v {
            sumX += v[j].X
            sumY += v[j].Y
        }
        l := float64(len(v))
        newCenter[i] = Point{
            X: sumX / l,
            Y: sumY / l,
        }
    }
    return newCenter
}

func max(a ...float64) float64 {
    f := float64(0)
    for _, v := range a {
        if v > f {
            f = v
        }
    }
    return f
}

func KMeans(loopLimit, maxDistance, k int, center, data []Point) []Res {
    var (
        res    = make([]Res, k) //创建最终返回结果
        groups [][]Point        //用于记录最后的分簇结果
    )
    for loop := 0; loop < loopLimit; loop++ {
        //初始化簇
        groups = newGroup(k)
        //查找与质心的距离
        distances := getDistances(center, data)
        //根据距离划分簇
        splitGroup(groups, data, distances)
        //重新计算质心
        newCenter := getCenter(groups)
        //计算质心偏离距离
        centerDistance := make([]float64, k)
        for i, v := range newCenter {
            centerDistance[i] = Calc(v, center[i])
        }
        //质心偏移条件
        x := max(centerDistance...)
        if x < float64(maxDistance) {
            break
        }
        center = newCenter //重复使用变量
    }
    for i, v := range center {
        res[i] = Res{
            Center: v,
            Group:  groups[i],
        }
    }
    return res
}

func main() {
    samples := defaultData()
    centers := defaultCenters()
    loopLimit := 100
    maxDistance := 1
    k := 2
    res := km.KMeans(loopLimit, maxDistance, k, centers, samples)
    for i, v := range res {
        fmt.Println("|簇编号|", i+1, "|")
        fmt.Println("|质心坐标|", v.Center.Fmt(), "|")
        fmt.Println("|分组样本|", v.Group, "|")
    }
}

//初始化样本数据
func defaultData() []km.Point {
    return []km.Point{km.NewPoint(1, 1), km.NewPoint(2, 1), km.NewPoint(1, 2), km.NewPoint(2, 2),
        km.NewPoint(4, 3), km.NewPoint(5, 3), km.NewPoint(4, 4), km.NewPoint(5, 4)}
}
//初始化质心数据
func defaultCenters() []km.Point {
    return []km.Point{km.NewPoint(1, 1), km.NewPoint(1, 2)}
}