flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-2030) Implement an online histogram with Merging and equalization features
Date Thu, 20 Aug 2015 14:47:46 GMT

    [ https://issues.apache.org/jira/browse/FLINK-2030?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14705037#comment-14705037
] 

ASF GitHub Bot commented on FLINK-2030:
---------------------------------------

Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/861#discussion_r37537538
  
    --- Diff: flink-staging/flink-ml/src/main/scala/org/apache/flink/ml/statistics/DiscreteHistogram.scala
---
    @@ -0,0 +1,126 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.ml.statistics
    +
    +import scala.collection.mutable
    +
    +/** Implementation of a discrete valued online histogram
    +  *
    +  * =Parameters=
    +  * -[[numCategories]]:
    +  * Number of categories in the histogram
    +  */
    +class DiscreteHistogram(numCategories: Int) extends OnlineHistogram {
    +
    +  require(numCategories > 0, "Capacity must be greater than zero")
    +  val data = new mutable.HashMap[Double, Int]()
    +
    +  /** Number of categories in the histogram
    +    *
    +    * @return number of categories
    +    */
    +  override def bins: Int = {
    +    numCategories
    +  }
    +
    +  /** Increment count of category c
    +    *
    +    * @param c category whose count needs to be incremented
    +    */
    +  override def add(c: Double): Unit = {
    +    data.get(c) match {
    +      case None =>
    +        require(data.size < numCategories, "Insufficient capacity. Failed to add.")
    +        data.put(c, 1)
    +      case Some(value) =>
    +        data.update(c, value + 1)
    +    }
    +  }
    +
    +  /** Merges the histogram with h and returns a new histogram
    +    *
    +    * @param h histogram to be merged
    +    * @param B number of categories in the resultant histogram.
    +    *          (Default: ```0```, number of categories will be the size of union of categories
in
    +    *          both histograms)
    +    * @return Merged histogram with capacity B
    +    */
    +  override def merge(h: OnlineHistogram, B: Int = 0): DiscreteHistogram = {
    +    h match {
    +      case h1: DiscreteHistogram => {
    +        val finalMap = new mutable.HashMap[Double, Int]()
    +        data.iterator.foreach(x => finalMap.put(x._1, x._2))
    +        h1.data.iterator.foreach(x => {
    +          finalMap.get(x._1) match {
    +            case None => finalMap.put(x._1, x._2)
    +            case Some(value) => finalMap.update(x._1, x._2 + value)
    +          }
    +        })
    +        require(B == 0 || finalMap.size <= B, "Insufficient capacity. Failed to merge")
    +        val finalSize = if (B > 0) B else finalMap.size
    +        val ret = new DiscreteHistogram(finalSize)
    +        ret.loadData(finalMap.toArray)
    +        ret
    +      }
    +      case default =>
    +        throw new RuntimeException("Only a discrete histogram is allowed to be merged
with a " +
    +          "discrete histogram")
    +    }
    +  }
    +
    +  /** Number of elements in category c
    +    *
    +    * @return Number of points in category c
    +    */
    +  def count(c: Double): Int = {
    +    data.get(c) match {
    +      case None => 0
    +      case Some(value) => value
    +    }
    +  }
    +
    +  /** Returns the total number of elements in the histogram
    +    *
    +    * @return total number of elements added so far
    +    */
    +  override def total: Int = data.values.sum
    +
    +  /** Returns the string representation of the histogram.
    +    *
    +    */
    +  override def toString: String = {
    +    s"Size:" + bins + " " + data.toString
    +  }
    +
    +  /** Loads values and counters into the histogram.
    +    * This action can only be performed when there the histogram is empty
    --- End diff --
    
    remove there


> Implement an online histogram with Merging and equalization features
> --------------------------------------------------------------------
>
>                 Key: FLINK-2030
>                 URL: https://issues.apache.org/jira/browse/FLINK-2030
>             Project: Flink
>          Issue Type: Sub-task
>          Components: Machine Learning Library
>            Reporter: Sachin Goel
>            Assignee: Sachin Goel
>            Priority: Minor
>              Labels: ML
>
> For the implementation of the decision tree in https://issues.apache.org/jira/browse/FLINK-1727,
we need to implement an histogram with online updates, merging and equalization features.
A reference implementation is provided in [1]
> [1].http://www.jmlr.org/papers/volume11/ben-haim10a/ben-haim10a.pdf



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message